Source-linked AI summary
Identifying the starting point of a spreading process in complex networks
Cesar Henrique Comin, Luciano da Fontoura Costa
TL;DR
The paper addresses how to locate the origin of spreading processes in networks, a question with applications including epidemics and computer viruses. It evaluates centrality-based source identification across three spreading schemes and network models. The source often has the highest centrality values, although performance depends on network topology and sampling.
Problem
The paper investigates how to identify the node where a spreading process began in a complex network.
Method
The method computes degree, betweenness, closeness, and eigenvector centrality on sampled networks generated by snowball, diffusion, and contact-process spreading.
Results
The source node tends to have the highest centrality values, with finding rates reaching 0.97 for some Barabási-Albert network parameters.
Takeaways & Limitations
Centrality-based source identification can work across theoretical network models and a real email network, but topology and extraction size affect its success.
Abstract
from arXiv · showhide
When dealing with the dissemination of epidemics, one important question that can be asked is the location where the contamination began. In this paper, we analyze three spreading schemes and propose and validate an effective methodology for the identification of the source nodes. The method is based on the calculation of the centrality of the nodes on the sampled network, expressed here by degree, betweenness, closeness and eigenvector centrality. We show that the source node tends to have the highest measurement values. The potential of the methodology is illustrated with respect to three theoretical complex network models as well as a real-world network, the email network of the University Rovira i Virgili.
I. INTRODUCTION
The paper asks where a spreading process began, a question relevant to epidemics, computer viruses, fads, and other network dynamics. It studies source identification across three propagation schemes using centrality measurements on the sampled network.
- The paper analyzes snowball, diffusion, and contact-process propagation schemes.Snowball is described as breadth-first graph search, while diffusion is tied to random walks.
- Source identification asks where a spreading process originated in a network, but little prior work addressed this question.
- The method applies degree, betweenness, closeness, and eigenvector centrality to the network generated by the spread.It also proposes a modified betweenness measure for sources with low centrality in the original network.
- The evaluation covers ER and scale-free theoretical networks, three spreading schemes, and a real University Rovira i Virgili email network.
II. MATERIALS AND METHODS
The study uses Erdős-Rényi and scale-free networks to examine how network topology affects source-identification methods. Scale-free networks are generated with Barabási-Albert and configuration-model procedures.
- The experiments use Erdős-Rényi graphs with Poisson degree distributions and scale-free networks with power-law degree distributions.ER graphs have fixed node counts and mean degree; scale-free networks are heterogeneous.
- Scale-free network construction: The Barabási-Albert procedure adds nodes that connect preferentially to older high-degree nodes.Starting from m0 nodes, each new node makes m connections with probability proportional to existing degree.
- Scale-free network construction: The configuration model samples node degrees from a power-law distribution and randomly connects the resulting stubs.
A. Measuring centrality
The paper defines four standard centrality measures and introduces an adjusted betweenness measure to reduce bias from the original network topology. These measures are intended to identify sources because the source region should be central in the sampled network.
- The study uses degree, closeness, betweenness, and eigenvector centrality.
- Closeness: Closeness centrality is defined from the inverse of a node's mean geodesic distance to other vertices.The mean uses shortest-path lengths and the network's number of vertices.
- Betweenness: Betweenness centrality measures the share of geodesic paths between node pairs that pass through a given node.The measure is conventionally normalized by (N −1)(N −2).
- Eigenvector centrality: Eigenvector centrality assigns greater importance to nodes connected to other high-scoring nodes.The scores are defined through the adjacency matrix and the eigenvector associated with its maximal eigenvalue.
- Adjusted betweenness: The proposed adjusted betweenness divides betweenness by node degree to reduce bias from the original topology.The authors state that degree is more likely than other usual centralities to remain constant after sampling because it is local.
B. Spreading on complex networks
The paper examines three single-node spreading schemes—snowball, random walk, and contact process—and evaluates centrality-based identification of their source nodes.
- Spreading schemes: The three spreading schemes are snowball, random walk, and contact process, each beginning from a single node.Figure 1 distinguishes their propagation mechanisms after two iterations.
- Snowball spreading: Snowball spreading forms a subgraph from the first n breadth-first searched nodes around the seed.If the final hierarchical level is incomplete, nodes are randomly selected to reach the target size.
- Random-walk spreading: Random sampling starts R agents at one node, performs simultaneous random walks, and retains the first n visited nodes.With sufficiently many agents, this process approaches snowball spreading.
- Contact process: The contact process follows the susceptible-infected model, infecting susceptible neighbors with fixed probability p.When p = 1, transmission becomes breadth-first and exactly matches snowball spreading.
- Source identification: The source-identification method samples n-node subnetworks and applies centrality measurements to locate each spreading seed.The analysis considers degree, betweenness, closeness, and eigenvector centrality, with seed nodes expected to score highly.
A. Source identification of a spreading process on artificial networks
The study evaluates centrality-based source identification across artificial networks and spreading schemes, showing that performance depends on network topology, sampling size, and spreading parameters. An unbiased betweenness measure substantially improves seed-finding in several settings.
- ER networks: In ER networks, degree, betweenness, closeness, and eigenvector centrality were applied to sampled subgraphs to identify the spreading seed.For 400 sampled subgraphs of size 100, seed and non-seed centrality distributions were compared.
- ER networks: Closeness and betweenness gave good seed-identification results in ER networks even for samples of 1000 nodes.The authors attribute this to the homogeneity of the ER network, although sampling changes the degree distribution.
- Scale-free networks: In scale-free samples, standard centralities performed fairly for small extractions but completely failed for larger ones because low-degree seeds were often near hubs.The sampling-induced topological bias is especially strong when randomly chosen seeds have very low degree.
- Bias correction: Dividing betweenness by node degree was introduced to reduce the sampling bias caused by the original topology.The adjustment addresses cases in which low-degree seeds are mixed with high-degree ordinary nodes.
- Bias correction: For BA networks, the unbiased-betweenness method achieved a finding rate as high as 0.97 for some parameter settings.The preferred r value was near the constant estimated from the betweenness–degree regression.
- Scale-free networks: Larger power-law exponents improved results, whereas highly heterogeneous networks with small γ produced excessive high-centrality nodes and strong fluctuations.The comparison used configuration-model networks with γ = 2 and γ = 4.
- Other spreading schemes: The unbiased-betweenness method gave fair results for random-walker samples with few agents and good results for contact processes across varying contagion rates.Few agents produced samples containing many chains of degree-two nodes.
B. Source identification in a real network
The method was tested on the University Rovira i Virgili email network using unbiased betweenness and snowball samples from randomly selected seeds.
- The email network’s giant component contains 1133 nodes and 10902 edges.
- Snowball spreads extracted between 100 and 1000 nodes from randomly selected seeds.
- The analysis used unbiased betweenness with r = 0.85 to identify the spreading source.
IV. CONCLUSION
The conclusion emphasizes that identifying the seed node is important for characterizing a network.
- Identifying the seed node is important for characterizing a network.