Source-linked AI summary
Searching for superspreaders of information in real-world social media
Sen Pei, Lev Muchnik, Jose S. Andrade, Zhiming Zheng, Hernan A. Makse
TL;DR
The paper examines how network sampling affects the ranking of spreaders and compares network measures requiring different structural information. It defines PageRank and k-shell decomposition, evaluates sampled networks, and uses bootstrap confidence intervals; sampled rankings are reported as not destroyed.
Problem
Network sampling can affect spreader measures and may change relative rankings in the original network.
Method
The paper defines PageRank and k-shell decomposition, tests snowball and activity sampling effects, and estimates confidence intervals with bootstrap resampling.
Results
The relative rankings of kS, kin, and PageRank are reported as not destroyed under the tested activity-sampling conditions.
Takeaways & Limitations
PageRank requires the complete network structure, while sampling experiments assess whether relative rankings remain usable under partial network observations.
Takeaways & Limitations
Bootstrap analysis does not provide very good approximations for extremely small sample sizes.
Abstract
from arXiv · showhide
A number of predictors have been suggested to detect the most influential spreaders of information in online social media across various domains such as Twitter or Facebook. In particular, degree, PageRank, k-core and other centralities have been adopted to rank the spreading capability of users in information dissemination media. So far, validation of the proposed predictors has been done by simulating the spreading dynamics rather than following real information flow in social networks. Consequently, only model-dependent contradictory results have been achieved so far for the best predictor. Here, we address this issue directly. We search for influential spreaders by following the real spreading dynamics in a wide range of networks. We find that the widely-used degree and PageRank fail in ranking users' influence. We find that the best spreaders are consistently located in the k-core across dissimilar social platforms such as Twitter, Facebook, Livejournal and scientific publishing in the American Physical Society. Furthermore, when the complete global network structure is unavailable, we find that the sum of the nearest neighbors' degree is a reliable local proxy for user's influence. Our analysis provides practical instructions for optimal design of strategies for "viral" information dissemination in relevant applications.
Methods Calculation of studied measures
The paper calculates global and local network measures, tests their robustness to sampling, and compares their ability to identify influential spreaders using bootstrap confidence intervals. It finds that local ksum performs comparably to kS despite using partial network information.
- Network measures: PageRank and k-shell are global measures requiring complete network structure, whereas degree is a local measure.PageRank uses the full network; k-shell decomposition iteratively removes low-degree nodes to assign each node a kS index.
- Sampling robustness: Snowball sampling leaves the relative ranking of k-core, in-degree, and PageRank almost unchanged.The sampling experiment uses 1% and 5% samples from the complete LiveJournal network.
- Sampling robustness: Activity sampling does not significantly destroy the relative ranking of kS, in-degree, and PageRank.The experiment samples 0.5% and 1% of LiveJournal posts and retains links between their authors.
- Bootstrap analysis: Bootstrap confidence intervals are estimated by repeatedly resampling observations with replacement and recomputing the target quantity.The reported intervals use a=0.05 and m=10^5 bootstrap samples.
- Influence prediction: ksum outperforms in-degree and PageRank for predicting average influence across LiveJournal, APS, Facebook, and Twitter.Figure 5 reports this comparison across the four datasets.
- Influential spreader identification: ksum performs comparably to kS for identifying influential spreaders, while k2sum improves performance slightly with more local information.The comparison covers LiveJournal, APS, Facebook, and Twitter; error bars represent 95% confidence intervals.