Search for content and authors |
Fast rumour source detection in large social networks |
Robert M. Paluch 1, Janusz A. Hołyst 1, Krzysztof Suchecki 1, Bolesław K. Szymanski 2, Xiaoyan Lu 2 |
1. Warsaw University of Technology, Faculty of Physics and Cent.of Exc.for Complex Systems Research, Koszykowa 75, Warszawa 00-662, Poland |
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 |
|
Related papers |
Presentation: Poster at Econophysics Colloquium 2017, Symposium C, by Robert M. PaluchSee On-line Journal of Econophysics Colloquium 2017 Submitted: 2017-03-14 18:21 Revised: 2017-03-16 16:30 |