Search for content and authors
 

Fast rumour source detection in large social networks

Robert M. Paluch 1Janusz A. Hołyst 1Krzysztof Suchecki 1Bolesław K. Szymanski 2Xiaoyan Lu 2

1. Warsaw University of Technology, Faculty of Physics and Cent.of Exc.for Complex Systems Research, Koszykowa 75, Warszawa 00-662, Poland
2. Rensselaer Polytechnic Institute, Social and Cognitive Networks Academic Research Cencer (RPI), 110 8th Street, Troy, NY 12180, United States

Abstract

The localization of a source of a malicious rumour became an urgent issue in last years. Most of the known methods works under very restricted conditions and their computational complexity is rather high. We examined carefully the method invented by Pinto et al. and we proposed improved version. The improvements include filtering the low quality information and smart selection of nodes suspected of being the source. As a results of improvements, our Gradient Pinto Algorithm (GPA) has the time complexity O(N2log(N)), while the complexity of Basic Pinto Algorithm (BPA) is O(N a ), where a \in (3,4) depending on the number of the observers in the network. The numerical tests performed using three different measures confirmed that GPA outperforms BPA also in terms of efficiency.

 

Legal notice
  • Legal notice:
 

Related papers

Presentation: Poster at Econophysics Colloquium 2017, Symposium C, by Robert M. Paluch
See On-line Journal of Econophysics Colloquium 2017

Submitted: 2017-03-14 18:21
Revised:   2017-03-16 16:30