Source-linked AI summary
Spreading dynamics in complex networks
Sen Pei, Hernan A. Makse
TL;DR
Identifying influential spreaders matters across epidemic and information diffusion, but choosing several originators differs from ranking individuals because their infected populations can overlap. The paper reviews spreading models and approaches to identifying single and multiple spreaders, then examines LiveJournal diffusion data, where k-shell better identifies users with large influence than indegree or PageRank.
Problem
Finding multiple influential spreaders is not equivalent to selecting the top individual spreaders, because their infected populations may overlap and the k-set optimization problem is NP-hard.
Source: §1 · pp. 2–3Method
The paper reviews spreading models and methods for finding individual and multiple influential spreaders, and evaluates centralities using LiveJournal diffusion data.
Source: §1 · p. 3Results
In LiveJournal, indegree better locates users participating in diffusion, while k-shell identifies users with larger influence than indegree and PageRank.
Source: §6 · p. 17, §5 · p. 17Takeaways & Limitations
For identifying individual spreaders with large influence in the studied setting, k-shell is more reliable than indegree and PageRank.
Source: §5 · p. 17Betweenness and closeness require the complete network structure and shortest-path calculations, making them time-consuming to compute.
Source: §3.2 · p. 9
Abstract
from arXiv · showhide
Searching for influential spreaders in complex networks is an issue of great significance for applications across various domains, ranging from the epidemic control, innovation diffusion, viral marketing, social movement to idea propagation. In this paper, we first display some of the most important theoretical models that describe spreading processes, and then discuss the problem of locating both the individual and multiple influential spreaders respectively. Recent approaches in these two topics are presented. For the identification of privileged single spreaders, we summarize several widely used centralities, such as degree, betweenness centrality, PageRank, k-shell, etc. We investigate the empirical diffusion data in a large scale online social community -- LiveJournal. With this extensive dataset, we find that various measures can convey very distinct information of nodes. Of all the users in LiveJournal social network, only a small fraction of them involve in spreading. For the spreading processes in LiveJournal, while degree can locate nodes participating in information diffusion with higher probability, k-shell is more effective in finding nodes with large influence. Our results should provide useful information for designing efficient spreading strategies in reality.
1. Introduction
Spreading ability varies across complex social networks, making influential-node identification important for applications such as epidemic control and product promotion. The paper reviews models and methods for identifying individual and multiple spreaders, then reports empirical diffusion results.
1. Introduction
- Real-world networks have varied, non-random structures, so people in them can differ substantially in spreading ability.Examples of these structures include heavy-tailed degree distributions, small-world effects, clustering, and community structure.Source: §1 · p. 2
- A few influential spreaders can start large-scale diffusion, making their identification important for epidemic-control strategies and commercial campaigns.The paper distinguishes individual originators from sets of nodes selected to maximize influence.Source: §1 · p. 2
- Single-spreader searches rank nodes by topological or dynamical measures, whereas multiple-spreader searches seek a set that maximizes final influence.The paper associates single origins with epidemic or rumor diffusion and multiple origins with viral marketing.Source: §1 · p. 2
- For multiple spreaders, selecting individually influential nodes can fail because their infected populations overlap, and finding the best k-set is NP-hard.The paper notes that solutions mainly rely on heuristic algorithms based on network diffusion models.Source: §1 · p. 3
- The paper introduces spreading models, reviews measures and heuristics for locating individual and multiple spreaders, and presents empirical results from online communities.Its review compares single-spreader measures by features, calculation complexity, and performance.Source: §1 · p. 3
2. Theoretical models for spreading
Spreading models specify both the interaction network and the rule governing diffusion. The section contrasts independent-contact models with threshold models and outlines how network structure shapes spreading outcomes.
2. Theoretical models for spreading
- Models describe diffusion using an underlying interaction network and a spreading rule; the paper groups rules into independent-interaction and threshold models.The network is represented as G(N, E), with nodes and edges encoding individuals and their possible contacts.Source: §2 · p. 3
2.1. Independent interaction models
- Independent-interaction models assign each contact an independent contagion probability, with SIR, SIS, and the Bass model as examples.The probability for a susceptible person depends on contact with an infected person, not on other contacts.Source: §2.1 · pp. 3–4
- SIR represents susceptible, infected, and immune recovered states, while SIS allows reinfection and can sustain an endemic infected fraction.SIR results are measured by the fraction ever infected; SIS results by the fraction remaining infected at endemic state.Source: §2.1 · p. 4
- Under homogeneous mixing, SIR has threshold λc = 1/⟨k⟩; on uncorrelated graphs it is λc = ⟨k⟩/(⟨k²⟩−⟨k⟩), vanishing when ⟨k²⟩ diverges.The section also surveys effects of clustering, small-world structure, and degree correlations.Source: §2.1 · p. 5
2.2. Threshold models
- Threshold models make adoption depend on accumulated exposures: in the Linear Threshold Model, active neighbors’ weights must exceed a node’s threshold.The General Threshold Model replaces the weighted-sum rule with a threshold function; exposure-history models can produce global cascades from few originators.Source: §2.2 · pp. 5–6
- Other models covered include rumor, voter, and strategic-game models, which describe spreading across social and biological phenomena.Source: §2.2 · p. 6
3. Searching for individual influential spreaders
The section surveys node-ranking measures for identifying individual influential spreaders, comparing what network information they capture, their predictive performance, and computational demands. It also reviews path-counting approaches that estimate spreading influence from walks or infected clusters.
3. Searching for individual influential spreaders
- Individual-spreader predictors rank nodes using topological features and assumed spreading mechanisms, with some measures requiring the complete network structure.The section introduces predictors used to quantify spreading ability and notes the challenge of computing global measures on large social networks.Source: §3 · p. 6
3.1. Degree
- Degree is computationally feasible on sparse networks, but peripheral hubs can have limited spreading ability because degree captures only immediate neighbors.The review gives O(V^2) complexity for dense networks and O(E) for sparse networks.Source: §3.1 · p. 7
3.2. Betweenness and closeness centralities
- Betweenness and closeness capture global network structure through shortest paths, but their computation can be infeasible for very large online networks.Both require the complete network structure; the cited algorithms have substantial time costs, including O(VE) for Brandes on unweighted sparse networks.Source: §3.2 · pp. 7–9
3.3. Eigenvector and PageRank centralities
- Eigenvector centrality incorporates neighbors’ importance, while PageRank adds random jumps and both can be computed efficiently by power iteration.PageRank’s conventional jumping probability is 0.85, and changing it can affect rankings.Source: §3.3 · pp. 9–10
3.4. k-shell index
- In SIR and SIS models on real networks, high k-shell nodes produce larger average infected populations than high-degree or high-betweenness nodes.The review attributes this to core nodes’ well-connected neighbors and their access to many pathways; k-shell decomposition runs in O(E), but may have low resolution in tree-like or growth-model networks.Source: §3.4 · p. 11
3.5. Path counting
- Path-counting approaches estimate influence from walks or infected-cluster properties, but their computational expense can be a concern.Dynamical influence predicts SIR spreading efficiency well at the critical regime, outperforming degree, k-shell, and betweenness; estimated infection impact can use a maximum walk length L = 4, with its definition dependent on the assumed spreading model. Expected reach uses the expected degree of the infected cluster, and X = 3 is reported as sufficient to determine the outcome.Source: §3.5 · pp. 12–13
4. Finding the most influential sets of nodes
Finding a small set of nodes that maximizes spread is distinct from identifying influential individuals because originators can overlap in whom they reach. The section reviews greedy and message-passing approaches to this hard optimization problem.
4. Finding the most influential sets of nodes
- Viral marketing illustrates the practical objective: selecting a small set of nodes to reach the largest number of people under a limited advertising budget.Source: §4 · p. 13
- For a set S of k originators, the goal is to maximize the expected number of infected nodes, but finding the optimal set is NP-hard for a generic class of threshold models.Single-node rankings may select originators with overlapping infected populations, so distance between originators must be considered.Source: §4 · p. 13
- For submodular spreading models, greedy search adds the node with the largest marginal spread gain and has a proven solution within 63% of optimal.Spread estimation by Monte Carlo simulation makes this algorithm time-consuming.Source: §4 · p. 14
- CELF, NewGreedy, and CELF++ improve greedy algorithms’ computational efficiency by reducing calls to spread-estimation procedures.CELF uses the fact that a node’s marginal gain cannot exceed its gain in a previous iteration.Source: §4 · p. 14
- A message-passing approach maps spread optimization to a high-dimensional static constraint-satisfaction model and accounts for cooperation among originators.The approach is reported to solve the problem efficiently on large networks across a wide range of irreversible dynamics, even without submodularity.Source: §4 · p. 14
5. Empirical research on influential spreaders
Using LiveJournal’s social network and diffusion records, the study compares indegree, PageRank, and k-shell as predictors of spreading. Indegree better identifies users likely to participate in diffusion, while k-shell better identifies users with larger influence.
5. Empirical research on influential spreaders
- The study tests centrality measures against complete LiveJournal network structure and diffusion records because information diffusion in reality is not fully described by existing theoretical models.The analysis considers indegree, PageRank, and k-shell; betweenness is infeasible at this network scale because of its computational complexity.Source: §5 · p. 15
- The measures convey distinct information: many users have large indegree but small k-shell, and not all users with large k-shell have large indegree.The reported correlations between k-shell and indegree or PageRank are weak.Source: §5 · pp. 15–16, Figure 1 · p. 16
- Only 246,423 LiveJournal users participate in diffusion; influence is measured as the number of nodes reachable from a user in the diffusion graph.The social network contains 9,636,481 nodes and 197,368,009 links; the diffusion graph is inferred from posts linking to other posts.Source: §5 · pp. 15–16
- In the top region, users with large indegree have a higher fraction participating in diffusion than users ranked by k-shell or PageRank.The authors attribute this to the small number of hubs with extremely large indegree, which raises the participation fraction despite relatively few spreading users.Source: §5 · p. 17
- Users ranked by k-shell generally have larger average influence than those ranked by indegree or PageRank, while indegree better identifies users likely to participate in diffusion.The authors conclude that k-shell is more reliable for identifying influential individual spreaders in this setting.Source: §5 · p. 17
6. Conclusion and discussion
The paper reviews models and methods for finding individual and multiple influential spreaders, then uses LiveJournal diffusion data to compare centrality measures. Its empirical results distinguish predictors of participation from predictors of influence, while the authors note limits in the data scope and network availability.
6. Conclusion and discussion
- In LiveJournal, indegree better identifies users participating in diffusion, whereas k-shell is preferred for identifying users with large influence.Only a small fraction of users participate in spreading, and different measures convey distinct information about nodes.Source: §6 · p. 17
- The empirical k-shell findings have been tested only on LiveJournal, so their applicability to other systems remains to be examined.Source: §6 · p. 17
- Many current single- and multiple-spreader algorithms require the underlying network topology, which can be difficult to reconstruct in practice.The authors identify local algorithms as desirable future work.Source: §6 · p. 17