Source-linked AI summary
Identify influential spreaders in complex networks, the role of neighborhood
Ying Liu, Ming Tang, Tao Zhou, Younghae Do
TL;DR
Identifying influential spreaders matters for controlling spreading in complex networks, but node influence may depend on neighborhoods as well as direct connections. The paper proposes neighborhood centrality and evaluates it with SIR simulations on six real-world networks. It reports that this measure outperforms degree and coreness, with two-step neighborhoods often balancing performance and cost.
Problem
Ranking influential spreaders matters for controlling spreading, while node influence may depend on neighbors beyond direct connections and large-neighborhood analysis can be difficult in changing, information-poor networks.
Source: §1 · pp. 2–3Method
The authors define neighborhood centrality by combining a node’s centrality with contributions from neighbors across multiple steps, then evaluate spreading with SIR simulations on six real-world networks.
Source: §1 · p. 3, §4 · p. 14Results
Neighborhood centrality outperforms degree and coreness in identifying influential spreaders, while two-step neighborhoods often perform well and further steps may add little or reduce accuracy.
Source: §1 · p. 3, §4 · p. 14Takeaways & Limitations
Considering two-step neighborhoods is reported to balance cost and performance; the average distance to potential infection range among top spreaders is 2–4 steps.
Source: §1 · p. 3, §4 · p. 14
Abstract
from arXiv · showhide
Identifying the most influential spreaders is an important issue in controlling the spreading processes in complex networks. Centrality measures are used to rank node influence in a spreading dynamics. Here we propose a node influence measure based on the centrality of a node and its neighbors' centrality, which we call the neighborhood centrality. By simulating the spreading processes in six real-world networks, we find that the neighborhood centrality greatly outperforms the basic centrality of a node such as the degree and coreness in ranking node influence and identifying the most influential spreaders. Interestingly, we discover a saturation effect in considering the neighborhood of a node, which is not the case of the larger the better. Specifically speaking, considering the 2-step neighborhood of nodes is a good choice that balances the cost and performance. If further step of neighborhood is taken into consideration, there is no obvious improvement and even decrease in the ranking performance. The saturation effect may be informative for studies that make use of the local structure of a node to determine its importance in the network.
1 Introduction
The paper proposes neighborhood centrality to rank influential spreaders, motivated by evidence that a node’s influence depends on its neighbors as well as its direct connections. Across six real-world networks, it reports that considering two-step neighborhoods often balances ranking performance and computational cost.
1 Introduction
- Centrality measures use network position to rank spreading influence; degree is simple and widely used, while coreness has been reported as more accurate and computationally efficient.The introduction also notes that k-shell rankings can remain robust when up to 50% of edges are missing.Source: §1 · p. 2
- Prior work reports that node influence depends on neighbors’ connections and that neighborhood-based measures can improve ranking over basic centralities.Examples include four-step neighbor counts, summed neighbor coreness, resource allocation, and counts of possible infection paths.Source: §1 · p. 2
- Social-network studies report behavioral associations extending from direct neighbors to three steps away, a pattern termed the three degree of separation.The paper uses this as motivation for considering a node’s potential influence range.Source: §1 · p. 2
- Complete network information can be difficult to collect in large, changing networks such as Twitter and Facebook, making large-neighborhood analysis seem unfeasible.Source: §1 · p. 3
- Neighborhood centrality generally outperforms degree and coreness, with two-step neighborhoods often balancing ranking accuracy and cost; larger neighborhoods may add little or reduce accuracy.The study evaluates neighborhoods from one to four steps.Source: §1 · p. 3
2 Methods
The methods define degree and coreness benchmarks, extend them with neighborhood centrality, and evaluate node spreading using SIR simulations on six real-world networks.
2 Methods
- The study benchmarks degree and coreness, proposes neighborhood centrality, simulates SIR spreading, and evaluates six real-world datasets.Source: §2 · p. 3
2.1 Degree centrality
- Degree centrality counts a node’s direct links, so a larger degree indicates more one-step neighbors it can influence directly.Source: §2.1 · p. 3
2.2 Coreness centrality
- K-shell decomposition assigns nodes coreness values by successively removing low-degree nodes; higher coreness indicates a more central core position.Source: §2.2 · p. 4
2.3 Neighborhood centrality
- Neighborhood centrality combines a node’s benchmark centrality with contributions from neighbors across multiple steps, with farther neighbors assigned less influence.The study uses degree and coreness as benchmarks and considers up to four steps; the parameter a ranges from 0 to 1.Source: §2.3 · p. 4
2.4 The SIR model
- In the SIR simulations, a single seed spreads infection with probability λ, infected nodes recover with probability µ=1, and the recovered fraction measures spreading efficiency.The authors average each node’s spreading efficiency over 100 runs and choose λ above the estimated epidemic threshold.Source: §2.4 · p. 5
2.5 Data sets
- The six networks are Email, CA-Hep, Hamster, PGP, Astro physics, and Router; Table 1 reports network topology and SIR-related parameters.Source: §2.5 · pp. 5–6, Table 1 · p. 6
3 Results
Across six real-world networks, neighborhood centrality generally improves on degree and coreness, with the strongest results usually at one or two neighborhood steps. Larger neighborhoods bring no consistent benefit and can reduce ranking performance.
3 Results
- Across six networks, neighborhood centrality outperforms degree and coreness in identifying influential spreaders, with best imprecision generally at 1–2 steps and possible declines at 3–4 steps.Source: §3 · pp. 7, 11, Figure 1 · p. 7, Figure 2 · p. 8
- For top-ranked nodes, 1–2-step neighborhoods usually maximize improved Kendall correlation, although the best step varies by network and 3-step coreness gains can turn negative.Source: §3 · pp. 9–10, Figure 3 · p. 9, Figure 4 · p. 10
- Across tested parameter values and infection probabilities, two-step neighborhood measures generally retain positive ranking gains, with a few network- and condition-specific exceptions.Source: §3 · pp. 11–12, Figure 5 · p. 11, Figure 6 · p. 12
4 Conclusion and Discussion
Neighborhood centrality outperforms degree and coreness in identifying influential spreaders, with performance generally saturating around a 2-step neighborhood. The authors suggest this may reflect the distance to a node’s potential infection range and note possible relevance to other neighborhood-based network studies.
4 Conclusion and Discussion
- Across six real-world networks, neighborhood centrality outperforms degree and coreness; 2-step neighborhoods usually perform well, while larger ones add little or can reduce performance.The authors report that this pattern is robust across tested parameter values and infection rates.Source: §4 · p. 14
- The authors suggest saturation may reflect an action scope: average shortest distances from reached nodes to influential spreading origins fall between 2 and 4.They propose that considering neighbors within this scope is useful, while considering those beyond it is less meaningful.Source: §4 · p. 14
- The authors expect suitable neighborhood ranges to inform work on core-periphery structure, missing-link prediction, and immunization strategies.Source: §4 · p. 14