Distance-Based Influence in Networks: Computation and Maximization
  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. 
Edith Cohen and Daniel Delling and Thomas Pajor and Renato F. Werneck
cs.SI