  A premise at a heart of network analysis is that entities in a network derive
utilities from their connections. The {\em influence} of a seed set $S$ of
nodes is defined as the sum over nodes $u$ of the {\em utility} of $S$ to $u$.
{\em Distance-based} utility, which is a decreasing function of the distance
from $S$ to $u$, was explored in several successful research threads from
social network analysis and economics: Network formation games [Bloch
andJackson 2007], Reachability-based influence [Richardson and Domingos 2002,
Kempe et al. 2003], "threshold" influence [Gomez-Rodriguez et al. 2011], and
{\em closeness centrality} [Bavelas 1948].
  We formulate a model that unifies and extends this previous work and address
the two fundamental computational problems in this domain: {\em Influence
oracles} and {\em influence maximization} (IM). An oracle performs some
preprocessing, after which influence queries for arbitrary seed sets can be
efficiently computed. With IM, we seek a set of nodes of a given size with
maximum influence. Since the IM problem is computationally hard, we instead
seek a {\em greedy sequence} of nodes, with each prefix having influence that
is at least $1-1/e$ of that of the optimal seed set of the same size. We
present the first highly scalable algorithms for both problems, providing
statistical guarantees on approximation quality and near-linear worst-case
bounds on the computation. We perform an experimental evaluation which
demonstrates the effectiveness of our designs on networks with hundreds of
millions of edges.
