Source-linked AI summary
Identification of influential spreaders in complex networks
Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Eugene Stanley, Hernan A. Makse
TL;DR
The paper examines spreading efficiency across k-shell layers. It finds that nodes in higher k-shells reach a larger fraction of the network and are infected more often and earlier than low-kS nodes.
Problem
The paper investigates which network nodes are most effective spreaders.
Method
The analysis evaluates spreading outcomes as a function of nodes' k-shell values, including infection probability and timing.
Results
Nodes in higher k-shells consistently reach a larger fraction of the network and are more likely to be infected earlier than nodes with low kS.
Takeaways & Limitations
Nodes in higher k-shells are consistently the most efficient independently of the β value.
Abstract
from arXiv · showhide
Networks portray a multitude of interactions through which people meet, ideas are spread, and infectious diseases propagate within a society. Identifying the most efficient "spreaders" in a network is an important step to optimize the use of available resources and ensure the more efficient spread of information. Here we show that, in contrast to common belief, the most influential spreaders in a social network do not correspond to the best connected people or to the most central people (high betweenness centrality). Instead, we find: (i) The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis. (ii) When multiple spreaders are considered simultaneously, the distance between them becomes the crucial parameter that determines the extend of the spreading. Furthermore, we find that-- in the case of infections that do not confer immunity on recovered individuals-- the infection persists in the high k-shell layers of the network under conditions where hubs may not be able to preserve the infection. Our analysis provides a plausible route for an optimal design of efficient dissemination strategies.
A. The k-shell decomposition
The k-shell decomposition assigns each node a unique shell index through successive pruning, representing the network as a union of progressively higher shells.
- A. The k-shell decomposition: Nodes are assigned to k-shells according to their remaining degree after successive pruning.Nodes with degree below the current layer value are removed iteratively.
- A. The k-shell decomposition: The first removed layer forms kS = 1, followed by successive higher-index shells until all nodes are removed.Each pruning stage removes nodes whose current degree is below the layer threshold.
- A. The k-shell decomposition: Every node receives a unique kS index, and the network is represented as the union of all k-shells.The resulting classification can differ from classification based only on degree.
B. The spreading models
The paper studies spreading with SIR and SIS models, which differ primarily in whether recovered individuals become permanently immune or can be reinfected.
- B. The spreading models: The spreading process is studied using Susceptible-Infectious-Recovered and Susceptible-Infectious-Susceptible models.Both models begin with susceptible nodes except for one infectious origin.
- B. The spreading models: In SIR, infectious nodes infect susceptible neighbors with probability β, then recover and become immune.Recovered nodes cannot be infected again.
- B. The spreading models: In SIS, infected individuals return to susceptibility with probability λ or remain infectious with probability 1 −λ.The model uses λ = 0.8, allowing subsequent reinfection.
C. The imprecision function
The imprecision function compares spreading from nodes selected by k-shell index, degree, or betweenness centrality with spreading from the most efficient nodes.
- C. The imprecision function: Betweenness centrality CB(i) is based on the fraction of shortest paths between node pairs that pass through node i.The calculation sums over all node pairs s and t.
- C. The imprecision function: The imprecision function ε(p) measures the difference between average spreading by selected nodes and by the pN most efficient spreaders.It tests the merit of k-shell, degree, and betweenness-based identification strategies.
- C. The imprecision function: For a fraction p of the network, the method identifies the most efficient spreaders and the nodes with highest k-shell index.Analogous groups are selected using degree and betweenness centrality.
- C. The imprecision function: For k-shell selection, ǫkS(p) ≡1 −MkS/Meff compares average infected percentages for k-shell-selected and efficient-spreader groups.The degree- and betweenness-based imprecision measures are defined similarly.
Additional information
Across network examples and spreading analyses, higher k-shell position generally identifies more efficient spreaders, while multiple-spreader performance depends on their separation and SIS persistence is concentrated in inner shells.
- Additional information: Degree-preserving rewiring places hubs in the inner core and recovers a standard pattern in which hubs contribute equally to spreading.The original network contains hubs in peripheral low-kS layers.
- Additional information: Spreading is larger for nodes with higher kS, while equal degree or betweenness values can produce different outcomes depending on kS.This pattern appears across the compared network examples.
- Additional information: For 2% < p < 10%, the k-shell strategy has ǫkS approximately twice lower than ǫk, while ǫCB exceeds 40%.The k-shell and degree strategies are comparable at p = 2%.
- Additional information: With multiple origins, selecting highest-degree nodes can outperform highest-kS nodes when the latter are connected to one another.Restricting both sets to non-directly linked nodes significantly enhances spreading and makes their results similar.
- Additional information: In SIS spreading, infection persistence is concentrated in nodes with large kS and is consistently higher in inner k-shells.Higher-kS nodes remain the most efficient independently of β.
I. DATASETS
The study analyzes real-world networks spanning hospital contacts, actor collaborations, email, social, scientific, Internet, and product relationships. These datasets provide varied interaction structures for evaluating spreading behavior.
- Network types: The datasets include hospital inpatients, actors in adult films, email accounts, reciprocal LiveJournal friendships, scientific collaborations, Internet routers and autonomous systems, and product proximities.The networks represent contacts, collaborations, communication, friendships, infrastructure, and economic relationships.
- Network construction: Hospital links connect inpatients sharing quarters, while email links require at least two messages exchanged in both directions.These construction rules define edges from observed interactions during restricted recording periods.
- Network scale: The largest studied components range from 8,622 hospital inpatients and 12,701 email accounts to 3,453,394 LiveJournal members.The listed network sizes illustrate the broad scale of the empirical collection.
- Network construction: The Internet datasets connect routers or autonomous systems through physical connections and contain 493,312 routers and 20,556 autonomous systems in their largest components.The corresponding average degrees are 3.3 and 6.1, respectively.
- Robustness: Product-space results were recovered using a proximity threshold of 0.3 and remained similar for different thresholds.The paper summarizes the basic properties of the studied networks in Table I.
II. THE k-SHELL DECOMPOSITION METHOD
The k-shell decomposition recursively prunes low-degree nodes to assign each node a shell index that captures its position from network periphery to core. The index remains useful under substantial link removal.
- Shell extraction: The k-shell algorithm repeatedly removes nodes of degree k to form successive shells, beginning with kS = 1 and continuing to higher k values.The resulting network is represented as adjacent k-shells.
- Shell index: Each node receives a unique kS index identifying its shell, which provides structural information distinct from degree k.A shell with index kS can contain nodes whose degree satisfies k ≥ kS.
- Shell index: In real networks, hubs can occupy either peripheral or core shells because degree and shell index need not correspond.This differs from random networks, where the two quantities are strongly correlated.
- Robustness: 10% and 50% link removals leave the relative node ranking invariant across the Email, Hospital, Adult IMDB, and LiveJournal networks.This tests whether k-shell-based ordering survives incomplete network information.
- Robustness: Random link removal produces a practically linear dependence between original and incomplete-network kS values, preserving spreading-efficiency predictions.The authors report that the kS assignment is robust under missing information.
III. PROBABILITY AND TIME OF INFECTION
The paper characterizes nodes by spreading size, infection probability, and infection time. Across the studied networks, high-kS nodes spread epidemics more widely and are infected more often and earlier.
- Core findings: The kS index identifies node locations that consistently predict spreading behavior.Nodes with larger kS values infect larger network regions, are infected more frequently, and are infected earlier.
- Core findings: High-kS nodes are more likely to be infected and are infected earlier when spreading begins at a random node.This connects core location with both epidemic reach and exposure during network-wide outbreaks.
- Node measures: Mi measures the infected population size when an epidemic originates at node i, while Ei and Ti measure infection probability and average infection time from random origins.These quantities characterize a node’s role in an epidemic process.
- Correlations: Mi, Ei, and Ti are strongly correlated: nodes infected by an origin can themselves reach similarly sized clusters, and their reachability probability is proportional to Mi.The average time Ti is inversely proportional to spreading efficiency Mi.
IV. THE IMPRECISION FUNCTIONS
The imprecision analysis compares k-shell selection with degree and betweenness-based selection for identifying efficient spreaders. Across the tested networks and spreader fractions, k-shell selection stays closest to the optimum.
- Method: The analysis ranks nodes by spreading efficiency and compares the optimal set with the highest-kS set for each considered spreader fraction p.The corresponding average infected sizes define the basis for k-shell imprecision.
- Visualization: The cross-plots relate Mi to Ti and Ei across email, hospital, actor, and Internet networks, with colors denoting low, intermediate, and high kS regimes.The plots examine how spreading efficiency, infection time, and infection probability vary with shell position.
- Results: The k-shell method identifies efficient spreaders in the CNI, actor, collaboration, and email contact networks with consistently lower imprecision than degree and betweenness centrality.This establishes the comparison across four empirical networks.
- Method: An imprecision value near 0 indicates that the selected nodes are practically those contributing most to epidemics.The metric compares the average infected size of the optimal and k-shell-selected sets.
- Results: Across the studied cases, k-shell selection produces spreading closer to the optimum than either degree or betweenness centrality.The behavior is independent of the fraction p of spreaders considered.
V. SIR SPREADING EFFICIENCY
SIR spreading efficiency depends more on k-shell position than on degree alone: core nodes generally spread farther, while reaching the core can enable larger outbreaks.
- Nodes in higher k-shells consistently reach a larger fraction of the network.
- At intermediate infection probability, outbreaks form peaks near M = 0 and a finite infected fraction, with peak intensities depending strongly on the origin’s k-shell.The zero peak represents infections dying within the first few steps, whereas the finite peak occurs at a similar M across origins.
- For the inpatient contact network at β = 4%, higher k-shell origins produce more large-infection realizations, while low-k-shell origins more often produce zero spreading.The distributions show peaks around M = 0 and M ≃33%.
- A high-degree node in a low k-shell can spread less effectively than a lower-degree node in a high k-shell.High-k-shell neighborhoods better sustain infection early, helping it reach the critical mass needed for substantial network coverage.
- Core spreaders with high kS can outperform hubs with high k and low kS, although degree and k-shell selection become equivalent in near-random networks.
- Rewiring while preserving degree places hubs in the innermost k-shell and makes degree and k-shell rankings nearly equivalent.Original networks can scatter high-degree nodes across peripheral and central shells, whereas rewired networks show a monotonic k versus kS relation.
VII. VIRUS PERSISTENCE IN SIS
SIS persistence is concentrated in the network’s inner k-shells, including conditions where low-shell nodes lose the virus. Dense inner cores can sustain infection locally.
- For SIS spreading, node persistence ρi(t) is defined as the probability that node i is infected at time t.
- In the supercritical regime, persistence increases with both degree k and k-shell index kS, reaching maximum values for hubs in innermost layers.
- In the subcritical regime, viruses persist only in the highest kS layers, while infection is unlikely in low-kS layers.
- Virus persistence is consistently higher in inner k-shells across infection probabilities, with epidemic thresholds substantially below random-network values except for the Email Contact network.The reported comparison is βc < βrand.
- The innermost k-shell forms a dense sub-network that helps the virus survive locally.These inner layers can be viewed as a small subgraph consisting exclusively of hubs.