PaperlayerView exact revision on arXiv

Source-linked AI summary

Identifying Infection Sources and Regions in Large Networks

Wuqiong Luo, Wee Peng Tay, Mei Leng

arXiv:1204.0354v2cs.DMcs.SIphysics.soc-ph

TL;DR

The paper addresses estimation of multiple infection sources and their infection regions from infected-node connectivity, even when the number of sources is unknown. It derives infection-sequence-count-based estimators and evaluates them theoretically, through simulations, and on two real data sets. For at most two sources in geometric trees, source identification is asymptotically correct, while broader experiments report strong source and region-estimation performance.

  • Problem

    The paper asks how to estimate infection sources and the nodes infected by each source when only infected-node connectivity is known and the source count is unknown.

  • Method

    The paper derives estimators from approximations of infection-sequence counts, including a quadratic-complexity procedure for general graphs with a known maximum source count.

  • Results

    For at most two sources in a geometric tree, the estimator identifies the source count and source nodes with probability going to one as infected nodes increase; reported source accuracy exceeds 65% overall and 90% for geometric trees.

  • Takeaways & Limitations

    The estimators jointly support inference of infection sources and their regions across tree, small-world, and power-grid networks, with validation on SARS and power-outage data.

Abstract

from arXiv · show

Identifying the infection sources in a network, including the index cases that introduce a contagious disease into a population network, the servers that inject a computer virus into a computer network, or the individuals who started a rumor in a social network, plays a critical role in limiting the damage caused by the infection through timely quarantine of the sources. We consider the problem of estimating the infection sources and the infection regions (subsets of nodes infected by each source) in a network, based only on knowledge of which nodes are infected and their connections, and when the number of sources is unknown a priori. We derive estimators for the infection sources and their infection regions based on approximations of the infection sequences count. We prove that if there are at most two infection sources in a geometric tree, our estimator identifies the true source or sources with probability going to one as the number of infected nodes increases. When there are more than two infection sources, and when the maximum possible number of infection sources is known, we propose an algorithm with quadratic complexity to estimate the actual number and identities of the infection sources. Simulations on various kinds of networks, including tree networks, small-world networks and real world power grid networks, and tests on two real data sets are provided to verify the performance of our estimators.

I. INTRODUCTION

The paper studies how to estimate infection sources and the nodes infected by each source using only infected-node connectivity, including cases where the number of sources is unknown. This problem matters across disease, computer-virus, and rumor spreading, where prompt source identification supports containment and investigation.

  • Why the problem matters: Identifying sources and their infection regions supports disease investigation, containment policies, computer-network protection, and rumor investigation.The paper connects source identification with studying causes, focusing scarce testing resources, protecting vulnerable servers, and identifying rumor perpetrators.
  • Problem setting: Infection-source estimation applies to contagious diseases, computer viruses, and rumors spreading through population, computer, and social networks.These settings can be modeled as infection spreading over network nodes.
  • Problem setting: The available observations are the infected nodes and their connections, because complete infection-detection times are typically unavailable.The paper therefore formulates estimation from structural infection information rather than a full spreading history.
  • Paper objective: A first-detected-node rule can be incorrect because node-specific random dormant periods may make symptoms appear out of infection order.This motivates source estimation that does not equate detection order with infection order.
  • Paper objective: The paper estimates both infection sources and the subset of nodes likely infected by each source when source number and locations are unknown a priori.This extends the single-source setting considered in earlier work.

B. Our Contributions

The paper develops estimators for multiple infection sources and their regions under a homogeneous SI spreading model, including unknown source counts. It provides asymptotic guarantees for geometric trees, algorithms for general graphs, and empirical validation on simulations and real data.

  • Motivation and model: The paper adopts a homogeneous SI diffusion model in which spreading is approximately homogeneous and infections happen independently.The authors explicitly describe this model as highly simplistic and not representative of many practical spreading processes.
  • Motivation and model: The multiple-source problem is more complex than single-source estimation and cannot be solved exactly even for regular trees.The paper addresses this complexity by deriving approximations and estimation procedures rather than exact general solutions.
  • Tree-network estimators: For tree networks with two known sources, the paper derives an infection-sequence-count estimator computable in O(n^2) time.Here n is the number of infected nodes.
  • Tree-network estimators: For geometric trees with at most two sources at least two hops apart, the estimator identifies the source count and source nodes with probability going to one as infections increase.The same analysis estimates the corresponding infection regions.
  • General graphs and validation: For general graphs with at most kmax sources, the procedure estimates sources and regions; simulations place source estimates within a few hops on average.The authors also report real-data tests on SARS contact tracing and Arizona–Southern California power outages.

II. PROBLEM FORMULATION

The paper formulates inference of infection sources and source-specific regions from an observed connected infection graph, including cases where the number of sources is unknown. It models spreading with independent exponential transmission times and approximates sequence-count-based posterior estimation because exact computation is hard.

  • Spreading model: Transmission times are independent exponential random variables with rate 1, and a susceptible node exposed to multiple infected neighbors selects its transmitting neighbor uniformly.Once infected, a node does not lose its infection.
  • Observed infection and targets: At time 0, k source nodes infect the remaining nodes, and an observation of n infected nodes produces the infection graph Gn.Typically, n is much larger than k.
  • Observed infection and targets: The infection partition divides Gn into disjoint connected regions whose nodes can be traced back to individual sources.The objective is to estimate both the source set and these regions.
  • Observed infection and targets: When k is unknown, the task also includes estimating the number of infection sources, subject to a known upper bound kmax.The infection graph is assumed connected, and closely spaced sources may be treated as one source.
  • Sequence-count formulation: Exact posterior maximization is computationally hard because it involves combinatorial infection-sequence counts related to #P-complete linear-extension counting.The paper therefore develops approximations and computationally efficient algorithms rather than exact MAP estimators.
  • Sequence-count formulation: An infection sequence orders non-source infected nodes by infection time, with each node adjacent to a source or an earlier infected node.The sequence count C(S | Gn) is the number of valid infection sequences for source set S.

III. IDENTIFYING INFECTION SOURCES AND REGIONS FOR TREES

For tree networks, the paper estimates infection regions and sources using Voronoi and infection-sequence-count approximations. It develops specialized procedures for one or two sources and a heuristic for an unknown number of sources bounded by kmax.

  • Tree-based estimation: The tree-network analysis first estimates infection partitions for a given source set, then derives source estimators from infection-sequence counts.The treatment includes two-source approximations and unknown-source estimation.
  • Infection regions: Under a path-separation condition in Hn, the optimal infection-partition estimator is exactly the Voronoi partition centered at the infection sources.The condition requires paths between source pairs not to intersect except possibly at source nodes.
  • Infection regions: For general infection graphs, a Voronoi partition need not be optimal, but the paper adopts it as an intuitively appealing low-complexity approximation.This approximation supports the design of a low-complexity source-estimation algorithm.
  • Source estimation: For one source on a regular tree, maximizing C(v | Gn) yields the MAP estimator, and the same sequence-count estimator performs well on other tree classes.On geometric trees, correct single-source identification probability goes to one as observation time grows.
  • Source estimation: For multiple sources, the paper extends sequence-count-based estimation from one source to two sources and then to unknown source counts bounded by kmax.The general-tree procedure is heuristic, while the two-source development motivates the multiple-source algorithm.

C. Two Infection Sources

For two sources in a tree, the paper characterizes the infection-sequence count using rooted subtree sizes and a recursion over reverse infection sequences. The resulting TSE algorithm computes pairwise source scores in O(n^2d*^2) time.

  • Two-source sequence counts: For candidate sources s1 and s2, the path between them is separated into rooted subtrees, whose sizes contribute to the two-source sequence-count characterization.The characterization adds a path-dependent q(u1, um; s1, s2) term to the single-source form.
  • Two-source sequence counts: The recursion q(ui, uj; s1, s2) combines the two possibilities of removing either endpoint of the intervening path, weighted by the inverse remaining subtree size.This recursion applies for i < j.
  • Two-source sequence counts: Reverse infection sequences enumerate valid orderings of the path nodes, while Ii counts nodes that can be infected after the later reverse-sequence nodes have been infected.This gives the path contribution used in the pairwise count.
  • Computation: The tree-size and product quantities needed for all nodes are computed by message passing with an upward sweep followed by a reverse sweep.Algorithm 1 stores the values associated with neighboring rooted subtrees.
  • Computation: O(n^2d*^2) is the overall complexity for computing the two-source sequence-count quantities under the bounded-degree assumption.The recurrence is evaluated across node pairs, with d* denoting maximum degree.
  • Computation: The Two Source Estimation algorithm maximizes the pairwise sequence-count score and provides the basis for the later multiple-source estimator.The algorithm is named TSE in the paper.

D. Geometric Trees with Two Sources

For geometric trees with two sources, the paper replaces an analytically intractable sequence count with a lower-bound proxy and a geometric-tree TSE estimator. Under the stated regularity and separation conditions, the estimator identifies the true sources with probability tending to one as the infection grows.

  • Geometric-tree assumptions: A geometric tree requires source-relative trees to grow polynomially at comparable rates, a regularity condition used in the asymptotic analysis.The condition is parameterized by fixed positive constants α, b, and c.
  • Asymptotic result: As the infection graph becomes large, the geometric-tree estimator identifies the actual two infection sources with probability going to one under the theorem's conditions.The result is asymptotic and applies to two sources in the specified geometric-tree class.
  • Scope and evaluation: The geometric-tree regularity assumption may be overly strong for some applications, so numerical studies examine performance across different tree-network classes.The analysis lets observation time, rather than directly n, become large.
  • Geometric-tree assumptions: With high probability at large observation time, infection reaches nearly distance t from each source without extending beyond the corresponding outer boundary.Event Et captures the inner and outer distance conditions.
  • Approximate estimator: The method adds virtual nodes x1 and x2 to the candidate sources and uses their sequence count on the augmented graph to obtain a lower bound for the original two-source count.The virtual nodes are attached to s1 and s2.
  • Approximate estimator: The proposed proxy orders path nodes by descending rooted-subtree size and uses the resulting lower bound to define the geometric-tree TSE score.A fixed δ is selected using prior knowledge about the graph's regularity.

E. Unknown Number of Infection Sources

The paper addresses the practical case where the number of infection sources is unknown, first analyzing one or two sources in geometric trees and then proposing an iterative estimator for larger unknown source sets.

  • Geometric trees: When there is one source, the geometric tree TSE algorithm finds two neighboring nodes, one of which is the true source, with probability approaching one.This follows from Theorem 3 under the stated geometric-tree and degree assumptions.
  • Geometric trees: With two sources, the geometric tree TSE algorithm identifies both source nodes with high probability when they are at least two hops apart.The estimated pair can therefore support source-count estimation through their mutual distance.
  • Unknown source counts: The Infection Partition algorithm initializes up to kmax source candidates, forms a Voronoi partition, and repeatedly applies SSE within regions until estimates stabilize or iterations end.The procedure assumes that a maximum possible source count kmax can be guessed or specified.
  • Unknown source counts: The MSEP algorithm combines neighboring regions, applies TSE to their union, decrements the source count when estimates are closer than τ, and repeats until no regions can be merged.Its worst-case complexity is quadratic in the infection-graph size, with dependence on the maximum source count.

IV. IDENTIFYING INFECTION SOURCES AND REGIONS FOR GENERAL GRAPHS

For general graphs, the paper adapts the multiple-source estimator using breadth-first-search trees, replacing exact tree procedures with BFS-based heuristics while retaining the partition-and-merge structure.

  • General-graph adaptation: The paper generalizes MSEP to identify multiple infection sources in general graphs.The general-graph version uses the same BFS heuristic throughout the adaptation.
  • SSE-BFS: SSE-BFS roots a spanning tree at each candidate node, applies SSE, and weights infection-sequence counts by the likelihood of the BFS tree.Repeating this over all roots yields a source estimator with O(n^2) complexity.
  • MSEP-BFS: MSEP-BFS replaces SSE in the infection-partition procedure with SSE-BFS and applies TSE to unions of neighboring BFS-tree regions.The two BFS trees are connected by randomly selecting an edge between the regions.
  • Complexity and evaluation: The MSEP-BFS algorithm has complexity O(kmax^3 n^2), matching the stated complexity of MSEP.The paper evaluates it on synthetic and real-world networks.

V. SIMULATION RESULTS AND TESTS

The paper evaluates its estimators through simulations on several network classes and tests them on contact-tracing and cascading-power-outage data.

  • Evaluation design: The evaluation covers geometric trees, regular trees, small-world networks, and real-world power-grid networks.These experiments are intended to verify the proposed algorithms across multiple network settings.
  • Real-world tests: The real-data tests use SARS outbreak contact-tracing data from Singapore in 2003 and Arizona–Southern California cascading power-outage data from 2011.The two datasets provide disease-spread and infrastructure-failure applications.
  • Reported outputs: Figure 5 reports estimation of the number of infection source nodes, while Table II presents performance comparisons.The supplied captions identify the plotted and tabulated evaluation targets.

A. Synthetic Networks

Synthetic-network experiments compare MSEP or MSEP-BFS with nSSE for source-count, source-location, and infection-region estimation, while also evaluating a power-grid network.

  • Synthetic-network setup: The experiments simulate geometric trees, regular trees, and small-world networks with 1, 2, or 3 sources and kmax = 3.Each scenario uses 1000 runs with 500 infected nodes.
  • Source-count estimation: MSEP correctly estimates the number of sources more than 93% of the time on geometric trees and more than 71% on regular trees.Accuracy is about 69.2% on small-world networks, where BFS heuristics introduce additional errors.
  • Source-location estimation: MSEP/MSEP-BFS outperforms nSSE in average error distance, even when nSSE knows the true number of sources.nSSE performance deteriorates as the known source count increases.
  • Region estimation: The average minimum infection-region covering percentage exceeds 59% for all evaluated networks.Coverage is computed after matching estimated and actual sources and assigning empty regions to unmatched sources.
  • Power-grid evaluation: On the 4941-node western states power-grid network, MSEP-BFS outperforms nSSE in every scenario.The experiments use 1, 2, or 3 randomly selected sources, 500 infected nodes, and 1000 runs per source count.

C. Tests on Real Data

Tests on the SARS infection network and a cascading power-outage network show that MSEP-BFS can estimate source counts and identify sources accurately in these real data sets. Across broader simulations and experiments, the proposed estimators perform well, while their analytical guarantees rely on a simple homogeneous SI model.

  • SARS infection network: The SARS network contains a 193-patient cluster reconstructed from contact-tracing data, and MSEP-BFS assumes at most kmax = 3 sources.Edges represent interactions or relationships such as family ties, classmates, colleagues, or shared public transport.
  • SARS infection network: MSEP-BFS correctly estimates one infection source and correctly identifies the real source in the SARS network.
  • Cascading power outages: MSEP-BFS correctly estimates two infection sources in the power network, identifies one source correctly, and places the other estimate 1 hop from the real source.
  • Overall performance: Simulations and real-data experiments report average error distance below 4, but the homogeneous SI model does not adequately capture many real-world network dynamics.The paper identifies richer diffusion models incorporating drifts and other dynamics as future research.
  • Overall performance: Across the considered networks, source-node accuracy exceeds 65%, geometric-tree accuracy exceeds 90%, and minimum infection-region coverage exceeds 59%.The reported estimation procedure uses only infected-node identities and underlying network connections.

APPENDIX A

The appendix counts infection sequences under multiple sources and uses these counts to show that the optimal infection partition is a Voronoi partition. It also establishes asymptotic source-estimation results through path-based probability bounds.

  • Infection sequence counting: Infection sequences are analyzed through susceptible-edge dynamics, with the next spreading edge chosen uniformly under exponential infection times.The susceptible-edge set decreases by two when the last node on a source-connecting path is infected.
  • Infection partition estimation: The infection partition estimator is a Voronoi partition of the infection graph when the source set is given.The proof compares colorings and infection-sequence probabilities to establish the estimator's Voronoi structure.
  • Infection sequence counting: For two sources, sequence counts along the connecting path are computed recursively using the quantity R(ui, uj).The recursion gives R(ui, uj) = |Tρ(ui,uj)|! · q(ui, uj; s1, s2) · J(ui, uj).
  • Infection sequence counting: The path-counting proof uses induction and establishes the stated sequence-count identities from the recursive decomposition.The final identities follow from the inductive hypothesis, Lemma 1, and equations (8) and (9).
  • Source recovery: For sufficiently large observation times, probability bounds show that the estimated source set equals the true source set with probability approaching one.The argument conditions on event Et, proves exact recovery on that event, and then applies the lower bound in (26).
  • Source recovery: The two cases u0 ≠ v0 and u0 = v0 are handled separately to compare candidate source pairs with the true pair.The proof derives strict inequalities for candidate pairs outside the source set using subtree-size bounds.

APPENDIX E

The appendix proves that Algorithm TSE asymptotically estimates the infection source and one of its neighbors. It does so by showing the corresponding score exceeds scores for node pairs farther from the source.

  • Proof objective: Algorithm TSE estimates the source s and one of its neighbors with probability converging to 1 as t →∞.The probability is conditioned on s being the infection source.
  • Score comparison: For sufficiently large t, the score of (s, r) exceeds that of every pair containing nodes farther than one hop from s.Here, r is a neighbor of s selected according to the network geometry.
  • Choice of neighbor: When both branches toward u_m and v_l are nontrivial, r is the neighbor of s on the path to u_m.This is the node denoted w_1 in Figure 11.
  • Boundary cases: If k = 0, r is chosen as either u_1 or v_1; if m = 0, r = w_1, with analogous treatment when l = 0.The construction assumes m + l > 0.
  • Proof conclusion: The proof concludes after establishing the preceding inequality using equation (25) and Lemma 3.This completes the theorem's proof.
Loading 1204.0354v2…