Source-linked AI summary
Ranking the spreading influence in complex networks
Jian-Guo Liu, Zhuo-Ming Ren, Qiang Guo
TL;DR
The paper asks how to identify influential spreaders when k-shell values do not distinguish nodes with different spreading outcomes. It proposes a parameterless method combining k-core values with shortest distance to the network core, and compares rankings with SIR simulations. Across four real networks and a Barabási–Albert network, the method is reported to identify spreading influence more accurately than degree, closeness centrality, k-shell, and mixed degree decomposition methods, while systematic comparison of distance-based measures remains future work.
Problem
Nodes with identical k-shell values can have different spreading influence, motivating improved ranking of influential spreaders.
Method
The method ranks nodes using their k-core values and shortest distance to the node set with the highest k-core value.
Results
The parameterless method is reported to identify node spreading influence more accurately than degree, closeness centrality, k-shell, and mixed degree decomposition methods on four real networks and a Barabási–Albert network.
Takeaways & Limitations
Nodes closer to the network core play a more significant role in the spreading process, within the evaluated networks and SIR comparisons.
Takeaways & Limitations
Systematic comparison and understanding of distance-based measures remains future work.
Abstract
from arXiv · showhide
Identifying the node spreading influence in networks is an important task to optimally use the network structure and ensure the more efficient spreading in information. In this paper, by taking into account the shortest distance between a target node and the node set with the highest $k$-core value, we present an improved method to generate the ranking list to evaluate the node spreading influence. Comparing with the epidemic process results for four real networks and the Barabási-Albert network, the parameterless method could identify the node spreading influence more accurately than the ones generated by the degree $k$, closeness centrality, $k$-shell and mixed degree decomposition methods. This work would be helpful for deeply understanding the node importance of a network.
1 Introduction
The paper frames identifying influential spreaders as important for controlling disease or accelerating information dissemination. It highlights that k-shell values can tie many nodes despite different spreading influence.
- Spreading pathways matter for either hindering disease transmission or accelerating information dissemination.
- The k-shell method identifies the network core through the largest k-core values.
- Many nodes can share the same k-core value even though their spreading performances differ.This limitation is visible in the Email, P2P, PGP, and AS networks.
2 Method
The method represents networks through adjacency and node-degree structure, then decomposes them into shells using iterative pruning. It motivates refining k-shell rankings because equal-shell nodes can have different spreading influence.
- A network G = (N, E) is represented by an adjacency matrix A, where aij indicates whether nodes i and j are connected.
- Node degree ki counts a node’s neighbors, while closeness centrality is the reciprocal of its total shortest distance to other nodes.
- K-shell decomposition repeatedly prunes low-degree nodes to assign nodes to sets with different k-core values.Nodes removed first form the k-core-one set, and the process repeats on the remaining network.
- Nodes with the same ks value can produce different numbers of infected nodes in SIR simulations, limiting k-shell ranking of global spreading influence.
- The improved method uses shortest distances from target nodes to the network-core set alongside their k-core values.The network core is the node set with the highest k-core value.
3 How to evaluate the performance
The paper evaluates topology-based rankings against SIR spreading results using network datasets and Kendall’s tau. Higher tau indicates closer agreement with the epidemic-process ranking.
- Four real networks—Email, P2P, PGP, and AS—are used to evaluate the improved method.The AS network consists of router subgraphs called Autonomous Systems, and network statistics are reported in Table I.
- The network datasets’ node counts, link counts, average degrees, second-order average degrees, and spreading thresholds are reported in Table I.
- Kendall’s tau measures the correlation between topology-based rankings and rankings generated by the SIR model.A higher tau indicates greater ranking accuracy, with τ = 1 representing the ideal case.
- In the SIR model, one initially infected node spreads to susceptible neighbors at rate β, while infected nodes recover after two time steps.
- The spreading influence sβ_i is the number of infections generated by initially infected node i.
4 Numerical results
Across real and Barabási–Albert networks, the improved method generally aligns more closely with SIR-based influence rankings above the epidemic threshold and better distinguishes nodes sharing k-core values. Its advantage can diminish at very high spreading rates, while degree and MDD rankings coincide in BA networks.
- Real networks: Above the epidemic threshold, the improved method θ achieves higher Kendall’s tau than the other indices in the real-network comparisons.Kendall’s tau compares structure-based rankings with SIR rankings; higher values indicate greater accuracy.
- Real networks: Below the threshold, degree-based rankings can perform strongly because high-degree nodes infect more nodes during the first few infection steps.The SIR process may stop quickly at low spreading rates, favoring nodes with large degree.
- Real networks: The improved method identifies nodes closer to the network core as having larger spreading influences, consistent with its design.This comparison is reported for the real-network experiments.
- Barabási–Albert networks: In BA networks, MDD degenerates to degree k, while θ ranks spreading influence more accurately above the spreading threshold.The degree and MDD Kendall’s tau values are equal across the tested BA networks.
- Barabási–Albert networks: At very large spreading rates, Kendall’s tau for θ and degree-based methods exhibits a crossover as infections rapidly reach the network core and then the whole network.The reported explanation is that high-degree nodes easily infect the core at very large β.
- Distinctness analysis: The distinctness metric D evaluates how well methods differentiate nodes sharing the same k-core value, and the improved method performs better than degree k and MDD.D uses the number of distinct elements within node sets sharing a k-core value; D = 1 is the stated maximum.
5 Conclusions an discussions
The paper proposes a parameterless ranking method that combines k-shell values with shortest distance to the network core. Across four real networks and a BA network, it more accurately identifies spreading influence than several established measures, while broader systematic comparisons remain future work.
- Method: The method ranks nodes using both k-shell values and shortest distance to the highest-k-shell network core.It is parameterless and depends only on the target node’s k-shell value and distance to the core.
- Interpretation: Nodes close to the network core play a more significant role in the spreading process, even when nodes share the same k-shell value.The method addresses differences in spreading influence that k-shell values alone do not distinguish.
- Results: The simulations on four real networks and the BA network show more accurate influence identification than degree, closeness centrality, k-shell, and MDD methods.The comparison uses results from the SIR spreading process.
- Limitations and future work: Systematic comparison of distance-based methods and their performance remains future work.The paper also calls for empirical analysis using additional indices and dynamic models.