Fast and Accurate Detection of Spread Source in Large Complex Networks
Journal Article - Open Access
Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University Warsaw Russia
Pagination or Media Count:
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 ON, 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.
- Information Science