Accurate ranking of influential spreaders in networks based on dynamically asymmetric link weights

We propose an efficient and accurate measure for ranking spreaders and identifying the influential ones in spreading processes in networks. While the edges determine the connections among the nodes, their specific role in spreading should be considered explicitly. An edge connecting nodes $i$ and $j$ may differ in its importance for spreading from $i$ to $j$ and from $j$ to $i$. The key issue is whether node $j$, after infected by $i$ through the edge, would reach out to other nodes that $i$ itself could not reach directly. It becomes necessary to invoke two unequal weights $w_{ij}$ and $w_{ji}$ characterizing the importance of an edge according to the neighborhoods of nodes $i$ and $j$. The total asymmetric directional weights originating from a node leads to a novel measure $s_i$, which quantifies the impact of the node in spreading processes. An $s$-shell decomposition scheme further assigns an $s$-shell index or weighted coreness to the nodes. The effectiveness and accuracy of rankings based on $s_i$ and the weighted coreness are demonstrated by applying them to nine real-world networks. Results show that they generally outperform rankings based on the nodes' degree and $k$-shell index while maintaining a low computational complexity. Our work represents a crucial step towards understanding and controlling the spread of diseases, rumors, information, trends, and innovations in networks.

Figure 1

Local structure of a network emphasizing the role of the link $e_{ij}$ in spreading a disease from node $i$ to node $j$ and then to reach out to nodes that node $i$ itself cannot reach. The same link $e_{ji}$, however, plays a different role as it does not help spread the disease to nodes beyond the reach of node $j$ after it infects node $i$. The asymmetry requires the assignment of directional weights with $w_{ij}\ne w_{ji}$.

Figure 2

Mean spreading efficiency $M$ of nodes as classified by their degree $k$ (black squares) or their node strength s (red circles) in nine real-world networks. As the node strengths are real numbers instead of integers, data are grouped in intervals of size unity. The corresponding average spreading efficiency and node strength in each interval are displayed, starting from the minimal strength. The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.

Figure 3

Kendall's $\tau$ correlation coefficients evaluated between the actual spreading efficiency of the nodes and the ranking based on node strength (black square) and based on the $s$-shell index (red circle) for different values of the parameter $a$ in Eq. (3). The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.

Figure 4

Imprecision of rankings based on the degree ($k$, black squares), $k$-shell index ($k_S$, red circles), and node strength ($s$, blue triangles) evaluated at the optimal value of $a$ as a function of $p$ for nine real-world networks. The node strength provides a better measure for identifying influential spreaders. The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.

Figure 5

Imprecision of rankings based on the node strength ($s$, black dash) and weighted coreness ($s_s$, red solid) obtained by $s$-shell decomposition as a function of $p$. The weighted coreness $s_s$ provides a further improvement over $s$ in identifying influential spreaders. The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.

Figure 6

Imprecision of rankings based on the degree ($k$, black squares), $k$-shell index ($k_S$, red circles), and node strength ($s$, blue triangles) evaluated by $a=0.5$ for nine real-world networks as a function of $p$. The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.

Figure 7

Imprecision of rankings based on the node strength ($s$, black dashed line) and weighted coreness ($s_s$, red solid line) obtained by $s$-shell decomposition for $a=1/2$ as a function of $p$. The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.

Figure 8

Kendall's $\tau$ correlation coefficients evaluated between the actual spreading efficiency of the nodes and the rankings based on weighted coreness $s_s$ (red circles) as obtained by assigning asymmetric weighting $w_{ij}$ of Eq. (3) to the links and based on weighted coreness $s_s^{\prime }$ (black square) by assigning symmetric weighting $w_{ij}^{\prime }$ of Eq. (5) to the links. The necessity of invoking asymmetric weights is demonstrated by the higher accuracy in the ranking based on $s_s$ rather than on $s_s^{\prime }$. The real-world networks are (a) CA-Hep, (b) Astro, (c) Emailcontact, (d) PGP, (e) Blog, (f) AS, (g) Router, (h) Hamster, and (i) Netsci.