Source-linked AI summary
Identifying influential spreaders in complex networks based on gravity formula
Ling-Ling Ma, Chuang Ma, Hai-Feng Zhang, Bing-Hong Wang
TL;DR
Identifying influential spreaders matters for information diffusion, product promotion, and epidemic control, but existing centralities provide competing approaches. The paper proposes a gravity centrality based on k-shell mass and shortest-path distance, evaluates it with SIR dynamics, and reports better influence ranking across real and synthetic networks. Its scope is limited by testing typical networks and using classical SIR dynamics despite broader network structures and spreading processes.
Problem
Identifying influential spreaders is important for accelerating information diffusion, promoting products, and controlling epidemic spreading.
Method
The method treats k-shell values as node masses and shortest-path distances as distances in a gravity-inspired centrality index, evaluated with SIR dynamics.
Results
The gravity method better distinguishes and evaluates node influence than other indices in the reported real and synthetic network experiments.
Takeaways & Limitations
Gravity centrality provides an effective way to identify influential spreaders in social networks within the evaluated settings.
Takeaways & Limitations
The study examines typical networks and uses the classical SIR model, while real network structures and spreading dynamics are more diverse.
Abstract
from arXiv · showhide
How to identify the influential spreaders in social networks is crucial for accelerating/hindering information diffusion, increasing product exposure, controlling diseases and rumors, and so on. In this paper, by viewing the k-shell value of each node as its mass and the shortest path distance between two nodes as their distance, then inspired by the idea of the gravity formula, we propose a gravity centrality index to identify the influential spreaders in complex networks. The comparison between the gravity centrality index and some well-known centralities, such as degree centrality, betweenness centrality, closeness centrality, and k-shell centrality, and so forth, indicates that our method can effectively identify the influential spreaders in real networks as well as synthetic networks. We also use the classical Susceptible-Infected-Recovered (SIR) epidemic model to verify the good performance of our method.
1 Introduction
The paper addresses the practical importance of identifying influential spreaders and proposes gravity centrality as an alternative to established centrality measures. Its effectiveness is evaluated using SIR spreading dynamics.
- Identifying influential spreaders supports strategies for controlling epidemics, accelerating information diffusion, and promoting new products.
- Existing approaches include degree, betweenness, neighborhood, closeness, and k-shell centrality.
- The proposed gravity centrality treats each node’s k-shell value as mass and shortest-path distance as distance.
- SIR spreading dynamics are used to evaluate whether the proposed index identifies influential nodes effectively.
- The paper compares gravity centrality with established centrality indices in evaluating influential spreaders.
2 Method
The method combines k-shell-based node importance with distance-dependent interactions in a gravity-inspired centrality index. It compares this approach with several centrality measures and limits computation to nodes within distance three.
- Network representation: An undirected network is represented by nodes, edges, and an adjacency matrix indicating whether node pairs are connected.
- Comparison indices: Degree, betweenness, closeness, and k-shell centralities provide comparison baselines for ranking node influence.
- Comparison indices: Mixed degree decomposition combines residual and exhausted degree, with remaining mixed degrees updated during node removal.
- Comparison indices: Neighborhood coreness combines node degree and coreness, with an extended version also considered.
- Gravity centrality: Gravity centrality models k-shell value as mass and shortest-path distance as distance, incorporating influence from non-nearest neighbors.
- Gravity centrality: The gravity index sums k-shell products divided by squared shortest-path distances over a specified neighborhood.
- Gravity centrality: Setting r = 3 includes nearest, next-nearest, and next-next-nearest neighbors to reduce algorithmic complexity.
3 Experimental results
The experiments compare gravity-based and established centrality indices using SIR spreading influence, ranking agreement, monotonicity, and tests on real and synthetic networks. G and G+ generally distinguish influential nodes effectively, especially above the epidemic threshold, while performance varies across network types and methods.
- Experimental setup: The study compares G and G+ with multiple centrality indices across real and synthetic networks, using SIR to evaluate spreading influence.The SIR setup infects one seed node and measures its spreading capability under infection and recovery probabilities.
- Real-network evaluation: In a 20-node example, G and G+ rankings agree well with the SIR ranking, whereas k-shell centrality poorly distinguishes nodes within the same shell.Table 1 reports rankings for DC, MDD, G, G+, Cnc+, ks, BC, CC, SL, and SIR influence R at β = 0.25.
- Resolution: The gravity indices provide higher monotonicity than competing measures, with M(G) and M(G+) near 1 in some networks.The monotonicity index measures how well a ranking assigns distinct values to nodes; M = 1 denotes perfect monotonicity.
- Real-network evaluation: G and G+ generally outperform other indices when β > βth across the evaluated real networks.Figure 2 plots Kendall’s τ between SIR rankings and topology-based rankings for Facebook, Netsci, Email, TAP, Y2H, Blogs, Router, and HEP.
- Parameter sensitivity: The results are stable when the neighborhood parameter r increases beyond its typical optimum of about 3–5.The authors report that τ becomes stable as r is further increased, making very large r unnecessary.
- Synthetic-network evaluation: On BA networks, G, G+, and Cnc+ perform similarly and outperform CC, DC, BC, and MDD; on WS networks, G and G+ remain better than the alternatives above βth.The results suggest that the gravity method identifies influential nodes in both real and synthetic networks.
4 Conclusions and discussions
The paper proposes a gravity method for identifying influential spreaders by combining nodes’ k-shell values with shortest-path distances. Evaluations on real and synthetic networks report stronger influence discrimination and ranking performance than comparison indices, while the method’s scope remains limited by network and spreading-dynamics assumptions.
- Conclusions and discussions: The gravity method treats each node’s k-shell value as mass and shortest-path distance as distance to model influence.The model reflects proportional dependence on k-shell values and decreasing neighbor influence with distance.
- Conclusions and discussions: Across real and synthetic networks, the method better distinguishes differences in node influence than other indices.This conclusion is based on monotonicity index M comparisons.
- Conclusions and discussions: The method can be generalized to weighted networks once an appropriate weighted k-shell value is assigned.The paper suggests extensions using weighted degree and weighted-network k-shell decomposition.
- Conclusions and discussions: The evaluation covers some typical networks and uses the classical SIR model, whereas real networks and spreading dynamics can be more diverse.Interconnected networks and rumor, opinion, and scientific-idea diffusion may challenge the effectiveness of the proposed indices.