Source-linked AI summary
The role of centrality for the identification of influential spreaders in complex networks
Guilherme Ferraz de Arruda, André Luiz Barbieri, Pablo Martín Rodriguez, Yamir Moreno, Luciano da Fontoura Costa, Francisco Aparecido Rodrigues
TL;DR
Identifying influential spreaders is complicated by dynamics-dependent rankings and the lack of a universal centrality measure, especially when spatial networks are considered. The paper compares nine centrality measures across epidemic and rumor spreading in spatial and non-spatial networks, introducing generalized accessibility. It finds that the best centrality measure depends on network type and spreading process, with accessibility strongest across spatial networks.
Problem
Influential-spreader identification lacks a universal centrality measure and may depend on whether epidemic or rumor dynamics are studied.
Method
The paper compares nine centrality measures with epidemic and rumor spreading across spatial and non-spatial networks, introducing generalized random-walk accessibility.
Results
In non-spatial networks, degree and coreness correlate most with epidemic spreading, while neighborhood degree, closeness, and accessibility correlate more with rumor dynamics; accessibility performs best in spatial networks.
Takeaways & Limitations
Centrality rankings from synthetic non-spatial networks cannot be generalized to spatial networks, where generalized accessibility is most consistently related to spreading capacity.
Abstract
from arXiv · showhide
The identification of the most influential spreaders in networks is important to control and understand the spreading capabilities of the system as well as to ensure an efficient information diffusion such as in rumor-like dynamics. Recent works have suggested that the identification of influential spreaders is not independent of the dynamics being studied. For instance, the key disease spreaders might not necessarily be so when it comes to analyze social contagion or rumor propagation. Additionally, it has been shown that different metrics (degree, coreness, etc) might identify different influential nodes even for the same dynamical processes with diverse degree of accuracy. In this paper, we investigate how nine centrality measures correlate with the disease and rumor spreading capabilities of the nodes that made up different synthetic and real-world (both spatial and non-spatial) networks. We also propose a generalization of the random walk accessibility as a new centrality measure and derive analytical expressions for the latter measure for simple network configurations. Our results show that for non-spatial networks, the $k$-core and degree centralities are most correlated to epidemic spreading, whereas the average neighborhood degree, the closeness centrality and accessibility are most related to rumor dynamics. On the contrary, for spatial networks, the accessibility measure outperforms the rest of centrality metrics in almost all cases regardless of the kind of dynamics considered. Therefore, an important consequence of our analysis is that previous studies performed in synthetic random networks cannot be generalized to the case of spatial networks.
I. INTRODUCTION
The paper examines how network structure and centrality relate to spreading dynamics, addressing disagreement over which centrality measures identify influential nodes and extending analysis to spatial networks.
- I. INTRODUCTION: Network organization fundamentally affects spreading processes, including epidemic thresholds and disease diffusion.For scale-free networks with degree exponent γ < 3, the epidemic threshold approaches zero as N →∞.
- I. INTRODUCTION: Centrality is studied because central nodes are expected to diffuse influence through networks faster than other nodes.Prior work linked epidemic influence to k-shell position, including nodes that are not necessarily the most connected.
- I. INTRODUCTION: No universal centrality definition exists: shortest-path metrics ignore alternative paths, while k-core decomposition can exclude peripheral vertices connected through low-degree nodes.These limitations motivate evaluating additional centrality measures.
- I. INTRODUCTION: The paper addresses a gap by investigating spatial networks, whose topological constraints can alter centrality metrics and spreading dynamics.Previous studies had largely focused on non-spatial networks.
- I. INTRODUCTION: The analysis considers multiple centrality measures, including degree, neighborhood degree, eigenvector, closeness, betweenness, clustering, coreness, and PageRank.The paper introduces these measures as alternative ways to quantify node centrality.
III. GENERALIZED RANDOM WALK ACCESSIBILITY
The paper generalizes random-walk accessibility using a matrix exponential, weighting walks of all lengths while penalizing longer ones to measure access diversity.
- III. GENERALIZED RANDOM WALK ACCESSIBILITY: The accessibility measure quantifies the diversity of nodes reached from a starting node through random walks.For a fixed distance h, it is defined using the exponential of Shannon entropy over transition probabilities.
- III. GENERALIZED RANDOM WALK ACCESSIBILITY: Generalized accessibility uses the matrix exponential of the transition matrix to account for walks of all lengths between vertices.The matrix exponential provides transition information across multiple walk lengths.
- III. GENERALIZED RANDOM WALK ACCESSIBILITY: The accessibility random walk retains trajectories whose independently sampled fitness values increase along the walk.The resulting transition probability for a length-n walk includes the factor 1/n!, linking the process to W.
- III. GENERALIZED RANDOM WALK ACCESSIBILITY: The weighting matrix assigns walks an inverse-factorial weight, giving shorter walks more influence than longer walks.This weighting is represented through the matrix W.
- III. GENERALIZED RANDOM WALK ACCESSIBILITY: Accessibility differs from communicability because it measures diversity through a transition matrix, whereas communicability concerns vertex-to-vertex communication through an adjacency matrix.The paper notes that the two measures have no trivial relation in irregular graphs.
- III. GENERALIZED RANDOM WALK ACCESSIBILITY: The paper derives exact expressions for the generalized accessibility on simple graph configurations to clarify the metric’s behavior.The star graph is included because it captures an extreme heterogeneous structure relevant to network dynamics.
A. Accessibility in star graphs
For star graphs, the paper derives transition probabilities and accessibility expressions for hubs and leaves, then compares the star approximation with network models.
- A. Accessibility in star graphs: The accessibility of star-graph hubs and leaves is obtained from the derived transition probabilities and exponential-matrix expressions.The paper provides separate formulas for the hub and any connected leaf.
- A. Accessibility in star graphs: The star-graph analysis derives the exponential transition matrix by distinguishing the hub, leaves, and leaf-to-leaf transitions.The hub is indexed as node one, with k = N −1 leaves.
- A. Accessibility in star graphs: The analytical hub expression is a good predictor of accessibility for hubs in scale-free networks.The comparison is based on the results shown in Figure 2.
- A. Accessibility in star graphs: The star-graph approximation is not accurate for Erdös-Rényi networks because the star does not capture homogeneous-network topology.The paper explicitly contrasts the approximation’s performance across network classes.
1. Eigendecomposition analysis
The eigendecomposition analysis recovers the star-graph accessibility formulas, while Figure 2 compares analytical results with regular structures and complex-network models.
- 1. Eigendecomposition analysis: The exponential matrix is constructed from eigenvectors of the transition matrix and exponentials of its eigenvalues.The matrices V and D provide the eigenvector and diagonal-exponential components.
- 1. Eigendecomposition analysis: For the star graph, the transition matrix has eigenvalues λ1 = −1, λ2 = 1, and λi = 0 for the remaining modes.The zero eigenvalue has multiplicity N−2.
- 1. Eigendecomposition analysis: Figure 2 compares accessibility in star, complete, ring, and line graphs with maximum values from ER, BA, and SSF networks.Complex-network points average 50 networks with ⟨k⟩≈4.
- 1. Eigendecomposition analysis: The eigendecomposition calculation recovers the previously derived accessibility expressions for star-graph hubs and leaves.The paper states that substituting the eigendecomposition into the accessibility expression yields the earlier formulas.
B. Accessibility in ring graphs
The generalized random walk accessibility is derived analytically for ring graphs, a K-regular case with K = 2. The resulting closed-form solution is compared with network-model calculations.
- Ring graphs are treated as a special case of K-regular graphs with K = 2.
- The transition matrix for the ring is analyzed using its known spectrum and eigenvectors.The decomposition diagonalizes P and supports a closed expression for the matrix.
- The resulting expression provides a closed form for evaluating P in ring graphs.
- Figure 2 compares network-model results with analytical solutions for regular structures.
- For line graphs, accessibility does not depend on network size; endpoints have the lowest values and central nodes the highest.
C. Accessibility in complete graphs
The generalized random walk accessibility is derived for complete graphs, where every pair of distinct nodes is connected. All nodes have equal accessibility, reaching the network’s maximum possible value.
- In a complete graph, every pair of distinct nodes is connected, so each transition probability is P(i, j) = 1/(N−1).
- The exponential matrix is constructed by separating diagonal entries, which represent paths that start and end at the same node.
- All nodes in a complete graph have the same accessibility.
- Because one step reaches any other node, this common accessibility equals the upper bound for a network with N nodes.
- Figure 2 shows how accessibility in complete graphs varies with network size.
1. Eigendecomposition analysis
The eigendecomposition analysis uses the spectrum and eigenvectors of the transition matrix to obtain a closed expression. Although complex numbers are used computationally, the resulting solution is real.
- For complete graphs, the eigenvalues of P are the adjacency-matrix spectrum scaled by 1/(N−1): λ1 = 1 and λ2 = … = λN = 1/(N−1).
- The eigenvector associated with λ1 has equal components, while the remaining eigenvectors satisfy a zero-sum condition.
- The eigenvectors are assembled into V and V−1 to substitute into Eq. 20 and obtain the matrix expression.
- The matrix exponential should be computed with Padé approximation for greater precision and lower computational cost than truncated Taylor series.
IV. EPIDEMIC AND RUMOR SPREADING
The paper models epidemic and rumor spreading as distinct contagion processes initiated from a single seed. It quantifies node spreading capacity using the eventual outcome of each process.
- In SIR dynamics, nodes are susceptible, infected, or recovered, with transmission probability β and spontaneous recovery probability µ.
- The epidemic ends when no infected node remains and the disease cannot propagate further.
- Rumor dynamics classify nodes as spreaders, ignorants, or stiflers, with spreaders contacting ignorants at rate λ.
- In the Maki–Thompson model, a spreader contacting another spreader or stifler becomes a stifler at rate δ; the Daley–Kendall model uses rate λ for two spreaders.
- The processes begin with one seed node, and SIR spreading capacity is measured by the final fraction of recovered vertices.
V. DATABASE
The study uses numerical simulations of epidemic and rumor spreading on both real-world and artificial networks.
- Numerical simulations evaluate epidemic and rumor spreading processes on real-world and artificial networks.
A. Network models
The database combines synthetic network models with extracted road networks and several real-world social networks. The models include preferential-attachment, spatial, and spatial scale-free constructions.
- Network models: The Barabási–Albert model generates networks through growth and preferential attachment, producing a power-law degree distribution.
- Network models: The Waxman model places nodes uniformly in a unit square and connects pairs according to their Euclidean distance, generating an exponential degree distribution.
- Network models: The Barthélemy model produces scale-free networks embedded in space using a regular lattice, random activation, degree, and distance-dependent attachment.
- Network models: Road networks were extracted from United Nations map PDFs through preprocessing, skeletonization, hit-or-miss filtering, and label propagation.
- Network models: The social-network dataset comprises email, political-blog, Advogato, and Google+ networks, analyzed as unweighted undirected giant components.
VI. SPATIAL NETWORKS
The study compares centrality measures with epidemic and rumor spreading outcomes in spatial road networks. Generalized accessibility shows the strongest relationship with both dynamics, while its distributions and real-network patterns reveal spatial structure in influential spreaders.
- Method: Nine unweighted, undirected centrality measures are compared with final recovered or stifler densities in spreading simulations.The measures include degree, clustering coefficient, betweenness, average neighborhood degree, PageRank, eigenvector centrality, k-core, closeness, and accessibility.
- Method: Spearman rank correlations assess monotonic relationships between centrality values and final epidemic or rumor outcomes.The coefficient is used because correlations may be monotonic without being linear.
- Spatial-network results: Accessibility has the highest correlations with both spreading processes in the analyzed spatial networks, often exceeding 0.7.The relationship between generalized accessibility and spreading potential is described as almost linear and positive across the road networks.
- Spatial-network results: In real road networks, accessibility identifies influential cities including Nagoya, Osaka, Hiroshima, London, Liverpool, Manchester, New York, Houston, Dallas, Chicago, Berlin, München, and Düsseldorf.Tokyo is highly connected but is described as a peripheral hub with lower spreading capability than several Japanese cities.
- Spatial-network results: Border nodes have the smallest accessibility values, so accessibility can identify network boundaries.This extends the measure’s use beyond ranking influential spreaders in spatial networks.
- Spatial-network results: Accessibility distributions are asymmetric with long high-value tails; variation is smallest in Germany and England and highest in Japan.The paper relates Japan’s greater variation to its terrain, which directly influences highway distribution.
VIII. CONCLUSIONS
The study compares centrality measures across spatial and non-spatial networks and finds that the best predictor depends on both network type and spreading process. Generalized accessibility is strongest for spatial networks, while degree, coreness, neighborhood degree, closeness, or accessibility lead in different non-spatial dynamics.
- The study evaluates eight centrality metrics across spatial and non-spatial networks using epidemic and rumor-spreading simulations.The networks include Barabási–Albert, Waxman, and scale-free spatial models.
- Generalized accessibility is the best predictor of spreading capacity in spatial networks.It has the highest correlation in most spatial-network cases.
- Degree and k-core centralities are most suited to epidemic spreading in non-spatial networks.This finding confirms earlier results for epidemic spreading.
- Average neighborhood degree, closeness centrality, and accessibility yield higher correlations for rumor dynamics in non-spatial networks.The strongest measure varies between the contact and truncated rumor cases.
- Accessibility correlates more strongly with spreading in spatial than non-spatial networks because higher spatial distances prevent saturation of the measure.In non-spatial networks, recovered or stifler fractions can plateau beyond a threshold, reducing Spearman correlation.
- Accessibility is defined through random walks and reflects how many nodes a spreading process can reach with similar probability.Its construction weights walks of all lengths by the inverse factorial of their lengths.