Source-linked AI summary
Understanding the spreading power of all nodes in a network: a continuous-time perspective
Glenn Lawyer
TL;DR
The paper addresses the limited accuracy of conventional centrality measures for quantifying the spreading power of most network nodes. It defines Expected Force from the local distribution of force of infection generated by transmission clusters and finds that it strongly predicts epidemic outcomes across network structures and spreading processes. Spreading power reflects both neighbor degree and the seed’s own degree, with the balance depending on node power and network density.
Problem
Conventional centrality measures identify highly influential nodes but are rarely accurate for quantifying the spreading power of the majority of nodes.
Method
Expected Force summarizes the force-of-infection distribution over local transmission clusters after a small number of transmissions, using only local network topology.
Results
Expected Force strongly predicts epidemic outcomes, generally outperforming existing spreading-power and centrality metrics across simulated and empirical networks.
Takeaways & Limitations
For most nodes, neighbor degree is the main determinant of spreading power; as node power increases, the node’s own degree becomes more important, especially in denser networks.
Takeaways & Limitations
The approach relies on local topology, which supports incomplete or dynamic networks but constrains the information used about the broader network.
Abstract
from arXiv · showhide
Centrality measures such as the degree, k-shell, or eigenvalue centrality can identify a network's most influential nodes, but are rarely usefully accurate in quantifying the spreading power of the vast majority of nodes which are not highly influential. The spreading power of all network nodes is better explained by considering, from a continuous-time epidemiological perspective, the distribution of the force of infection each node generates. The resulting metric, the \textit{expected force}, accurately quantifies node spreading power under all primary epidemiological models across a wide range of archetypical human contact networks. When node power is low, influence is a function of neighbor degree. As power increases, a node's own degree becomes more important. The strength of this relationship is modulated by network structure, being more pronounced in narrow, dense networks typical of social networking and weakening in broader, looser association networks such as the Internet. The expected force can be computed independently for individual nodes, making it applicable for networks whose adjacency matrix is dynamic, not well specified, or overwhelmingly large.
Definition and validation
The Expected Force (ExF) summarizes the distribution of force of infection generated by a seed after two transmissions, using local cluster topology. Across simulated and empirical networks, it strongly predicts epidemic outcomes and generally outperforms established node metrics.
- Definition and validation: ExF is computed from all possible two-transmission clusters around a seed, whose cluster degree counts edges from infected cluster nodes to susceptible nodes.The enumeration includes transmission orderings, and x = 2 is generally sufficient.
- Definition and validation: The expected force of infection is approximated by the entropy of normalized cluster degrees, accommodating highly variable distributions across seed nodes.This makes the metric a local network property independent of the rest of the network and any specific spreading process.
- Definition and validation: ExF is highly predictive across simulated and empirical networks, with mean correlations of 83% and 74% for SI outcomes and 91% and 82% for processes with recovery.Standard deviations on simulated networks were typically 0.02–0.03, and ExF generally outperformed accessibility, eigenvalue centrality, and k-shell.
- Definition and validation: ExF’s predictive power remains robust across network structures, while accessibility performs substantially worse on dense networks.For continuous-time SIS, ExF correlations changed little between loose and dense network families; accessibility’s mean correlation fell to 0.28/0.20 on dense Astrophysics/Facebook networks.
- Weighted graphs: The weighted-graph extension preserves high predictive ability, with weighted and unweighted ExF showing no meaningful difference across tested edge-weight distributions.The extension uses edge weights as transmission likelihoods and weighted outgoing cluster degree.
Discussion
The ExF predicts epidemic outcomes across network structures and spreading processes while showing that spreading power balances neighbor connectivity with the node’s own degree. This balance becomes more pronounced in denser networks, although ExF’s local topology leaves it insensitive to larger community structure.
- Predictive performance: The ExF predicts epidemic outcomes with high accuracy across diverse network structures and spreading processes.It is strongly correlated with epidemic outcomes and outperforms existing spreading-power and centrality metrics.
- Mechanism: Transmission-cluster combinatorics explain this shift: second-geodisc paths dominate initially, until the quadratic growth of first-geodisc neighbor combinations overtakes them.Triangles and squares further increase ExF through motif-sensitive cluster enumeration and entropy.
- Network structure: The neighbor-degree and own-degree relationships are stronger in dense collaboration networks than in more diffuse networks.Dense-network motifs such as triangles and squares reduce disparity among cluster-degree distributions, increasing ExF.
- Relation to centrality: Unlike walk-counting centralities, ExF is based on local topology and does not assume that one walk type, scale, or length ranks all nodes equally well.It nevertheless has high rank correlation with eigenvalue centrality and k-shell across reported networks.
- Scope and limitation: Locality enables accurate whole-network epidemic prediction from partial network knowledge and supports dynamic networks, but misses bridge effects between large disparate communities.A bridge may spread farther than a locally stronger node even when ExF assigns it less local spreading power.
- Determinants of spreading power: For most nodes, spreading power is driven primarily by the sum of neighbors’ degrees, whereas a node’s own degree becomes more important as its power increases.The figure compares ExF with node degree, neighbor degree, and second-neighbor degree.
Methods
The study evaluates ExF across simulated and empirical contact networks using SI, SIS, and SIR epidemic simulations, with outcomes defined from coverage time or epidemic probability. It also tests network structure, weighting, parameter robustness, and comparisons with existing spreading-power and centrality measures.
- Epidemic simulations and outcomes: SI outcomes use time to half coverage, estimated from 100 continuous-time spreading simulations per seed node.Transmission events are drawn from an exponential distribution whose rate equals the current number of infected-susceptible edges.
- Epidemic simulations and outcomes: SIS/SIR outcomes use epidemic potential, the probability that a seed node produces an outbreak infecting at least half the network.The simulations count successful outbreaks among 100 runs per seed node.
- Parameter calibration: The transmission-to-recovery parameter is calibrated separately for each network as a fixed multiple of 1/λ, placing at least 96% of continuous-time nodes in the critical range.Here λ is the largest adjacency-matrix eigenvalue; discrete-time simulations reach at least 76% of nodes in that range.
- Network evaluation: The study evaluates five simulated network families derived from theoretical, co-purchase, hyperlink, collaboration, and Facebook networks, plus 23 empirical networks.Empirical networks contain between 1,133 and 855,800 nodes; simulated families use 1,000-node networks.
- Metric comparison: ExF is compared with accessibility, dynamic spreading measures, eigenvalue centrality, and k-shell using epidemic-outcome correlations across network structures and spreading processes.The comparison represents both spreading-power metrics and conventional centrality measures based on different walk structures.
Results tables on following pages
The tables report correlations between node spreading-power metrics and epidemic outcomes across simulated and real-world networks, with some metric-specific exclusions noted.
- Table S6 summarizes mean correlations and standard errors across one hundred simulated networks from each network family.
- ExFM is omitted from SI analyses, while accessibility is omitted for real-world networks exceeding 25,000 nodes.
- Table S7 reports correlations between spreading-power metrics and time to half coverage in real-world networks, with 95% confidence bounds.
- Tables S8 and S9 report correlations with epidemic potential for discrete-time SIS and SIR processes, respectively, including 95% confidence bounds.