Identifying Infection Sources and Regions in Large Networks

Abstract

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.

References in corpus (1)

• Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity

Cited by in corpus (37)

• CSI: A Hybrid Deep Model for Fake News Detection
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Bayesian inference of epidemics on networks via Belief Propagation
• Rooting out the Rumor Culprit from Suspects
• How to Identify an Infection Source with Limited Observations
• Identifying spatial invasion of pandemics on metapopulation networks via anatomizing arrival history
• A Hilbert Space Theory of Generalized Graph Signal Processing
• Infection Spreading and Source Identification: A Hide and Seek Game
• Whose Opinion to follow in Multihypothesis Social Learning? A Large Deviations Perspective
• Epidemic Source Detection in Contact Tracing Networks: Epidemic Centrality in Graphs and Message-Passing Algorithms
• The zero-patient problem with noisy observations
• Choosing among alternative histories of a tree
• On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• Classical and quantum random-walk centrality measures in multilayer networks
• Schemes of Propagation Models and Source Estimators for Rumor Source Detection in Online Social Networks: A Short Survey of a Decade of Research
• Finding an infection source under the SIS model
• Information Source Detection in the SIR Model: A Sample Path Based Approach
• Source Localization in Networks: Trees and Beyond
• Locating Contagion Sources in Networks with Partial Timestamps
• Multiple Infection Sources Identification with Provable Guarantees
• Estimating Infection Sources in Networks Using Partial Timestamps
• Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process
• A Robust Information Source Estimator with Sparse Observations
• Network infection source identification under the SIRI model
• Combinatorial approach to spreading processes on networks
• Folded Graph Signals: Sensing with Unlimited Dynamic Range
• GFCN: A New Graph Convolutional Network Based on Parallel Flows
• Network Topology Inference Using Information Cascades with Limited Statistical Knowledge
• Graph Signal Processing over a Probability Space of Shift Operators
• On Privacy of Socially Contagious Attributes
• Identifying Rumor Sources Using Dominant Eigenvalue of Nonbacktracking Matrix
• Social Bubbles and Superspreaders: Source Identification for Contagion Processes on Hypertrees
• Inference in Spreading Processes with Neural-Network Priors
• Contamination source inference in water distribution networks
• Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations
• Subgraph Signal Processing