Leveraging percolation theory to single out influential spreaders in networks

Filippo Radicchi and Claudio Castellano

Phys. Rev. E 93, 062314 – Published 22 June 2016

Abstract

Among the consequences of the disordered interaction topology underlying many social, technological, and biological systems, a particularly important one is that some nodes, just because of their position in the network, may have a disproportionate effect on dynamical processes mediated by the complex interaction pattern. For example, the early adoption of a commercial product by an opinion leader in a social network may change its fate or just a few superspreaders may determine the virality of a meme in social media. Despite many recent efforts, the formulation of an accurate method to optimally identify influential nodes in complex network topologies remains an unsolved challenge. Here, we present the exact solution of the problem for the specific, but highly relevant, case of the susceptible-infected-removed (SIR) model for epidemic spreading at criticality. By exploiting the mapping between bond percolation and the static properties of the SIR model, we prove that the recently introduced nonbacktracking centrality is the optimal criterion for the identification of influential spreaders in locally tree-like networks at criticality. By means of simulations on synthetic networks and on a very extensive set of real-world networks, we show that the nonbacktracking centrality is a highly reliable metric to identify top influential spreaders also in generic graphs not embedded in space and for noncritical spreading.

Received 15 March 2016

DOI:https://doi.org/10.1103/PhysRevE.93.062314

Physics Subject Headings (PhySH)

Network flow Spreading

Networks

Authors & Affiliations

Filippo Radicchi^*

Center for Complex Networks and Systems Research, School of Informatics and Computing, Indiana University, Bloomington, Indiana 47408, USA

Claudio Castellano

Istituto dei Sistemi Complessi (ISC-CNR), Via dei Taurini 19, 00185 Roma and Dipartimento di Fisica, Sapienza Università di Roma, 00185 Roma, Italy

^*filiradi@indiana.edu

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 93, Iss. 6 — June 2016

Reuse & Permissions

Access Options

Article Available via CHORUS

Download Accepted Manuscript

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Impact of individual nodes at criticality. The scatterplot shows the relation between the predicted impact $x_{i}$ and the actual impact in simulations $〈 Q_{i} 〉$ . Both measures are divided by their maximal values to obtain numbers in the interval $[0, 1]$ . Predicted impact is determined on the basis of the centrality score associated with every node. (a) Erdős-Rényi graph of average degree $〈 k 〉 = 4$ and varying size $N$ . Only NB centrality is considered. (b) Scale-free graph with $N = 10^{4}$ nodes constructed according to the uncorrelated configuration model [33]. The degree sequence is composed of integer numbers selected randomly from a probability distribution $P (k) \sim k^{- γ}$ defined over the interval $[3, \sqrt{N}]$ . We consider here $γ = 2.5$ .
Reuse & Permissions
Figure 2
Identification of influential spreaders in scale-free (SF) graphs at criticality. (a, c) The imprecision function $ε$ and (b, d) the Jaccard distance $d_{J}$ are plotted against the fraction of top nodes $ρ$ . The relative performance of the various centrality measures as a function of $ρ$ can be deduced from direct comparison among the curves: the lower is the value of the dissimilarity metrics, the better the centrality measure predicts the true top spreaders. Results are obtained on the largest connected component of SF graphs, constructed according to the uncorrelated configuration model [33]. The preimposed degree sequence is composed of random integer numbers selected randomly from a probability distribution $P (k) \sim k^{- γ}$ defined over the interval $[3, \sqrt{N}]$ . We consider the case $γ = 3.5$ and two distinct network sizes: $N = 10^{4}$ (a, b) and $N = 10^{5}$ (c, d). Numerical simulations of the SIR model are performed at the critical values of $λ$ [ $λ_{c} = 0.216$ in (a) and (b) and $λ_{c} = 0.212$ in (c) and (d).
Reuse & Permissions
Figure 3
Identification of influential spreaders in real-world graphs at criticality. The description of the various panels is similar to that in Fig. 2. (a, b) Results for the e-mail contact network [12]. (c, d) Results for the peer-to-peer network of Gnutella as of August 31, 2002 [38]. The clustering coefficients of the networks are 0.1088 and 0.0055, respectively. SIR simulations are performed at criticality, with $λ = λ_{c}$ . The epidemic thresholds of the two networks are $λ_{c} = 0.031$ and $λ_{c} = 0.099$ , respectively.
Reuse & Permissions
Figure 4
Comparison of the predictive power of the different centralities in nonspatially embedded real-world graphs at criticality. Bars indicate the fraction of real networks where each centrality provides the best prediction for the top $ρ N$ influential spreaders. For every network in our sample, we determine the best centrality measure as the metric generating the minimal value of the imprecision function (dark-shaded bars) or the Jaccard distance (light-shaded bars) at predetermined values of $ρ$ . We consider (a) $ρ = 0.05$ , (b) $ρ = 0.10$ , (c) $ρ = 0.15$ , and (d) $ρ = 0.20$ . In the case of ties, the score is equally split among the top metrics.
Reuse & Permissions
Figure 5
Influential spreaders in the U.S. air transportation network at criticality. We consider the unweighted and undirected version of the air transportation network within the United States, reconstructed by aggregating the information on all flights by major carriers (American Airlines, Delta, and United) in January 2014 [39, 40]. (a) A visualization of the impact of individual airports in the spreading process. The impact of airport $i$ is measured as $〈 Q_{i} 〉 / {〈 Q 〉}_{\max}$ , with ${〈 Q 〉}_{\max}$ the maximal value of the spreading power over all airports. In the representation, the size of the circles is proportional to the impact of the corresponding airport. Colors of the circles are also proportional to the spreading power of the airport, with a continuous scale ranging from red (maximal impact) to blue (minimal impact). (b, c) The same representation as in (a), but replacing the spreading power with the value of their centrality. (d) Scatterplot of the centrality metrics vs the value of the spreading power for individual airports. The gray line is the benchmark for perfect performance. Whereas NB centrality and the generalized RWA provide a distinction for airports, $k$ -core centrality generates identical scores for many airports.
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics