Source-linked AI summary
Identifying Influential Spreaders by Weighted LeaderRank
Qian Li, Tao Zhou, Linyuan Lv, Duanbing Chen
TL;DR
Identifying influential spreaders matters for understanding and controlling spreading processes, yet effective and efficient identification remains challenging. The paper weights LeaderRank’s ground-node links according to users’ in-degree and evaluates the resulting biased random walk. Simulations report better performance than LeaderRank in finding influential spreaders, tolerating noisy data, and resisting intentional attacks.
Problem
Identifying influential spreaders is important for controlling epidemic and information spreading, but doing so effectively and efficiently remains challenging.
Method
The method assigns in-degree-dependent weights to links from the ground node and applies a biased random walk within LeaderRank.
Results
The weighted LeaderRank performs better than LeaderRank in identifying influential spreaders, tolerating noisy data, and resisting intentional attacks.
Takeaways & Limitations
Weighting ground-node links by users’ numbers of fans provides the paper’s supported improvement to LeaderRank’s spreading-influence ranking.
Abstract
from arXiv · showhide
Identifying influential spreaders is crucial for understanding and controlling spreading processes on social networks. Via assigning degree-dependent weights onto links associated with the ground node, we proposed a variant to a recent ranking algorithm named LeaderRank [L. Lv et al., PLoS ONE 6 (2011) e21202]. According to the simulations on the standard SIR model, the weighted LeaderRank performs better than LeaderRank in three aspects: (i) the ability to find out more influential spreaders, (ii) the higher tolerance to noisy data, and (iii) the higher robustness to intentional attacks.
1 Introduction
Identifying influential spreaders is important for understanding and controlling epidemic and information spreading, but doing so effectively and efficiently remains challenging. The paper improves LeaderRank by weighting ground-node links according to users’ numbers of fans.
- Influential spreaders play a major role in quick and wide epidemic and information spreading.
- Identifying influential spreaders effectively and efficiently remains a major challenge.
- Degree centrality is efficient but can overlook nodes with fewer, highly influential neighbors.
- Closeness, betweenness, and eigenvector centrality are often too time-consuming for large-scale networks.
- LeaderRank adds a bidirectionally connected ground node to the network and applies a standard random walk to identify influential spreaders.
- Weighted LeaderRank replaces the standard random walk with a biased one, giving users with more fans more scores from the ground node.
2 Algorithm
The weighted LeaderRank algorithm adds degree-dependent weights to ground-node links and uses a biased random walk to compute node influence. Final steady-state scores determine the ranking.
- The algorithm adds a ground node to create a strongly connected network with N + 1 nodes and M + 2N directed links.
- Standard LeaderRank initializes every node score to 1 and iterates until reaching a unique steady state.
- Nodes are ranked by their final steady-state scores, with larger scores indicating greater spreading influence.
- Weighted LeaderRank assigns the ground-to-node weight w_gi = (k_in_i)^α while setting the reverse ground-link weight and other weights to 1.
- The resulting dynamics is a biased random walk in which score transferred from node j to node i is proportional to w_ji.
- As in LeaderRank, the weighted method uses final steady-state scores to quantify node influence.
3 Results
The weighted LeaderRank is evaluated on three real social networks using SIR spreading simulations and comparisons with degree centralities and original LeaderRank. Across the tested settings, it identifies more influential spreaders, improves spreadability, tolerates noisy links better, and is more robust to sybil attacks.
- Experimental setup: The evaluation uses Delicious, Epinions, and Slashdot, with the standard SIR model estimating the spreading influence of top-ranked users.Each SIR process begins with one infected node; infected nodes transmit with probability β and are then removed with γ = 1.
- Comparison with Degree Centralities: Across all 27 tested cases, weighted LeaderRank with α = 1 outperforms in-degree, out-degree, and total-degree centralities.The comparisons use top-ranked lists of lengths L = 20, 50, and 100 and measure the number of infected and removed nodes over time.
- Difference between LeaderRank and Weighted LeaderRank: The top-L lists become more different from original LeaderRank as the absolute value of α increases.Original LeaderRank is recovered at α = 0; the list difference is defined as n/L, where n is the number of differing nodes.
- Spreadability: Weighted LeaderRank considerably improves the relative spreadability of top-ranked nodes, with optimal performance around α = 1 in all three networks.Spreadability is the average number of removed nodes at steady state when a node is initially infected, averaged over 100 independent runs.
- Robustness to Noisy Data: With α = 1, weighted LeaderRank is more tolerant of randomly added or removed links than original LeaderRank, showing a smaller score change Is.The score change Is increases as more links are randomly added or removed.
4 Conclusion and Discussion
Weighted LeaderRank improves LeaderRank by directing more score from the ground node to users with more fans. Simulations indicate better influential-spreader identification, noise tolerance, and attack robustness, with comparable convergence speed.
- Weighted LeaderRank performs better than LeaderRank in finding influential spreaders, tolerating noisy data, and resisting intentional attacks.The paper reports almost the same converging speed as LeaderRank while improving these three aspects.
- Weighted LeaderRank assigns more score from the ground node to nodes with more fans, using in-degree as the influence-related weighting basis.The paper contrasts this design with weighting by out-degree, which it considers less explainable and less robust.
- The alternative weighting schemes tested performed worse than the proposed scheme, while using two or more parameters produced only slightly better but less interpretable performance.The authors describe the more complicated formulation as difficult to understand.