Local structure can identify and quantify influential global spreaders in large scale social networks

0 · Context

A global process, and the question of whether local information is enough

Online social networks are now where information and opinions spread. They are also gigantic: in mid-2016 Facebook had about 1.5 billion monthly active users. Viral marketing, the adoption of new products and the control of false information all ask the same question: which users, if they start spreading something, will reach the most people?

Because a viral spread reaches a finite fraction of the whole network, the influence of a node is usually measured with global information: k-shell decomposition, degree discount, betweenness, closeness, the Katz index and others. On networks of a billion users these become impractical, because the full structure is not available or the computation does not scale. On the other side, Christakis and Fowler’s “three degrees of influence” suggests from social experiments that influence fades beyond friends of friends of friends, an unexplained local effect, and a local approximation was recently found to work for a global measure of collective influence. This apparent paradox raises a basic question:

Can local network structure accurately determine the size of global spreading?

1 · Two phases

A spread either dies out nearby or takes over a fixed share of the network, with nothing in between

We model spreading with the susceptible–infected–recovered (SIR) family, which describes information spreading in social media well. An active node activates each neighbour with probability $\beta$. The spreading influence of node $i$ is the expected number of nodes it eventually activates,

where $g(i,s)$ is the probability that $s$ nodes in total end up activated, in a network of $N$ nodes. Above the epidemic threshold $\beta_c$, we find that $g(i,s)$ has two well-separated peaks. A local peak sits at small $s$. A viral peak, sharp as a delta function, sits at a large size $s^\infty$ that does not depend on the seed node or on the realization. Between them is a wide gap.

Percolation theory explains both features. An SIR process maps onto bond percolation: remove every link with probability $1-\beta$, and the nodes a seed activates are exactly the cluster it belongs to, so $g(i,s)$ equals the cluster-size distribution $p(i,s)$. Above the percolation threshold a giant component of size $s^\infty\propto N$ appears, and $p(i,s)$ splits into a finite part $p_f(i,s)$ and the giant part $p(i,s^\infty)$. Since the finite clusters contribute little,

a node’s spreading power is the size of the giant component times the probability that the node is in it. For random networks with a given degree distribution this has a closed form; for real networks it does not, but the two-phase behaviour is the same.

2 · The size s*

A characteristic size, independent of the seed and of the network size, marks the point of no return

Percolation theory says that the finite clusters have an exponentially decaying size distribution. Averaged over all nodes, the finite part of the cluster-size distribution behaves as

$$p_f(s)\sim s^{-\tau}e^{-s/s^*} ,$$

(5)

and $s^*$ is the characteristic size of finite clusters. In an Erdős–Rényi random network with mean degree $\langle k\rangle$, $s^*_{ER}=1/(\beta\langle k\rangle-1-\ln\beta-\ln\langle k\rangle)$, which near the threshold scales as $s^*\sim|\beta-\beta_c|^{-1/\sigma}$ with the mean-field exponent $\sigma=0.5$. In real networks we obtain $s^*$ by fitting Eq. 5 to simulations; on the Facebook network it also follows a power law near $\beta_c$, with a non-mean-field $\sigma=1.05$ (Fig. 1D).

So a spread that has activated more than about $s^*$ nodes is almost certainly in the giant component. This gives the truncated spreading power: run the SIR process from node $i$ and stop it once $m$ nodes are active,

where $\tilde p$ is the probability of reaching at least $m$ nodes and $\tilde s^\infty=\sum_i\tilde p(i,\tilde s^\infty)$. For $m\ge s^*$ the error is small: the relative error $E_r(i,m)=[\tilde S(i)-S(i)]/S(i)$ falls quickly with $m$ and is below 1 % for $m>s^*$ (Fig. 2B). Because $s^*$, like the giant component, is a property of the network and not of the seed, it can be determined once and used as the threshold for every node.

Exact influence costs time proportional to $N$; the truncated estimate costs a constant $O(m)$.

3 · Influence radius

Whether a spread goes global is decided within three to four steps of the seed

To see what $s^*$ means on the network, we define an influence radius $\ell^*$: run the SIR process until $s^*$ nodes are active and record the largest number of hops (shortest-path distance) between the seed and an active node, averaged over realizations and seeds. With $\beta$ chosen so that the giant component holds 30 % of the nodes in every network, $\ell^*\approx3$–4 in all nine online social networks, much smaller than the average distance to the farthest nodes and the diameter (Fig. 2C).

So a local spread vanishes within three to four steps; otherwise it reaches about 30 % of the network. $\ell^*$ grows as $\beta$ approaches $\beta_c$ (Fig. 2D), as in a continuous phase transition: at the critical point the correlation length diverges, but away from it a characteristic scale appears. This resolves the paradox: spreading is global in the supercritical phase, yet whether a node starts a global spread depends only on its local environment.

4 · Picking seeds

A greedy search on the truncated estimate finds near-optimal seed sets in constant time

The practical problem is to choose $M$ seeds $V=\{v_1,\dots,v_M\}$ from a set of $L$ candidates to maximize their collective spreading power $S(V)$. Targeting many ordinary users is often more cost-effective than targeting a few hubs, and the full network is rarely available, so we take candidates of about average degree. The collective version of the estimator, $\tilde S(V)\equiv\tilde s^\infty\,\tilde p(V,\tilde s^\infty)$, uses the probability that the $M$ seeds activate at least one cluster of at least $m$ nodes, and is again independent of $N$.

Combining it with the natural greedy algorithm gives the percolation-based greedy algorithm (PBGA): pick the candidate with the largest $\tilde S$; then, with it fixed, add the candidate that most increases $\tilde S(V)$; repeat until $M$ seeds are chosen. With the real spreading power instead of $\tilde S$, this would be the natural greedy algorithm (NGA).

The cost of PBGA does not grow with the network (Fig. 3), which matters for networks with billions of nodes. Maximum degree, degree discount and maximal collective influence (MCI) also have size-independent theoretical cost, but the first two perform much worse, and MCI is much slower, because it needs all nodes up to a distance $\ell$ from the seeds, and in small-world networks even a small $\ell$ means thousands of nodes. PBGA depends only on $s^*$, which the small-world effect does not inflate.

For all numbers of seeds studied, PBGA, NGA and the genetic algorithm perform best, and for small $M$ their solutions are indistinguishable from the brute-force optimum (Fig. 4A, B insets). PBGA clearly beats MCI when $M$ is small (Fig. 5), probably because collective influence was designed to find the nodes whose removal breaks the network, which are not necessarily the best spreaders. As $M$ grows the differences between methods shrink.

Since the true optimum is usually unknown, we also derived two lower bounds on the performance ratio $S(\tilde V)/S(V^*)$: a combined bound that is rigorous for any network and an approximate bound that becomes rigorous for random networks. The approximate bound is close to 1 for every $M$ considered (Fig. 4C), so we argue that PBGA gives a nearly optimal solution for any number of seeds.

The spreading rate $\beta$ is usually unknown in practice. Seeds chosen at a rate $\beta_0$ perform almost optimally at any higher rate, as long as both are above $\beta_c$ (Fig. 4D), so one can choose seeds at a rate slightly above the threshold.

5 · Summary

Global influence, measured locally

Our framework is shown for the basic SIR model, but it carries over to other spreading models with two properties: (i) the final state of a set of seeds is either a small local outbreak or a global one proportional to the network size, and (ii) the size of a global outbreak does not depend on the initial spreaders. The SI Appendix discusses a wider SIR family, models with stiflers, and the susceptible–infected–susceptible model. Applications range from viral marketing to surveillance of false information, epidemic control and network protection.