  Finding an envy-free allocation of indivisible resources to agents is a
central task in many multiagent systems. Often, non-trivial envy-free
allocations do not exist, and, when they do, finding them can be
computationally hard. Classical envy-freeness requires that every agent likes
the resources allocated to it at least as much as the resources allocated to
any other agent. In many situations this assumption can be relaxed since agents
often do not even know each other. We enrich the envy-freeness concept by
taking into account (directed) social networks of the agents. Thus, we require
that every agent likes its own allocation at least as much as those of all its
(out)neighbors. This leads to a "more local" concept of envy-freeness. We also
consider a "strong" variant where every agent must like its own allocation more
than those of all its (out)neighbors.
  We analyze the classical and the parameterized complexity of finding
allocations that are complete and, at the same time, envy-free with respect to
one of the variants of our new concept. To this end, we study different
restrictions of the agents' preferences and of the social network structure. We
identify cases that become easier (from $\Sigma^\textrm{p}_2$-hard or NP-hard
to polynomial-time solvability) and cases that become harder (from
polynomial-time solvability to NP-hard) when comparing classical envy-freeness
with our graph envy-freeness. Furthermore, we spot cases where graph
envy-freeness is easier to decide than strong graph envy-freeness, and vice
versa. On the route to one of our fixed-parameter tractability results, we also
establish a connection to a directed and colored variant of the classical
SUBGRAPH ISOMORPHISM problem, thereby extending a known fixed-parameter
tractability result for the latter.
