Estimating Infection Sources in Networks Using Partial Timestamps

We study the problem of identifying infection sources in a network based on the network topology, and a subset of infection timestamps. In the case of a single infection source in a tree network, we derive the maximum likelihood estimator of the source and the unknown diffusion parameters. We then i...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information forensics and security 2018-12, Vol.13 (12), p.3035-3049
Main Authors: Tang, Wenchang, Ji, Feng, Tay, Wee Peng
Format: Article
Language:English
Subjects:
Algorithms
Clustering algorithms
Clusters
Computer simulation
diffusion process
Estimation
Gaussian distribution
Graphs
Gromov product
Heuristic algorithms
Infection source
infection timestamps
Infections
Maximum likelihood estimators
multiple sources estimation
Network topology
Parameters
Propagation delay
rumor source
Silicon
single source estimation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of identifying infection sources in a network based on the network topology, and a subset of infection timestamps. In the case of a single infection source in a tree network, we derive the maximum likelihood estimator of the source and the unknown diffusion parameters. We then introduce a new heuristic involving an optimization over a parametrized family of Gromov matrices to develop a single source estimation algorithm for general graphs. Compared with the breadth-first search tree heuristic commonly adopted in the literature, simulations demonstrate that our approach achieves better estimation accuracy than several other benchmark algorithms, even though these require more information like the diffusion parameters. We next develop a multiple sources estimation algorithm for general graphs, which first partitions the graph into source candidate clusters, and then applies our single source estimation algorithm to each cluster. We show that if the graph is a tree, then each source candidate cluster contains at least one source. Simulations using synthetic and real networks, and experiments using real-world data suggest that our proposed algorithms are able to estimate the true infection source(s) to within a small number of hops with a small portion of the infection timestamps being observed.
ISSN:1556-6013
1556-6021
DOI:10.1109/TIFS.2018.2837655