Fast and Accurate Detection of Spread Source in Large Complex Networks
Abstract
Spread over complex networks is a ubiquitous process with increasingly wide applications. Locating spread sources is often important, e.g. finding the patient one in epidemics, or source of rumor spreading in social network. Pinto, Thiran and Vetterli introduced an algorithm (PTVA) to solve the important case of this problem in which a limited set of nodes act as observers and report times at which the spread reached them. PTVA uses all observers to find a solution. Here we propose a new approach in which observers with low quality information (i.e. with large spread encounter times) are ignored and potential sources are selected based on the likelihood gradient from high quality observers. The original complexity of PTVA is O(N), where (3,4) depends on the network topology and number of observers (N denotes the number of nodes in the network). Our Gradient Maximum Likelihood Algorithm (GMLA) reduces this complexity to O (N2log (N)). Extensive numerical tests performed on synthetic networks and real Gnutella network with limitation that ids of spreaders are unknown to observers demonstrate that for scale-free networks with such limitation GMLA yields higher quality localization results than PTVA does.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 06, 2018
- Accession Number
- AD1053548
Entities
People
- Boleslaw Szymanski
- Janusz A. Hołyst
- Krzysztof Suchecki
- Robert Paluch
- Xiaoyan Lu
Organizations
- Cancer Genomics Centre