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

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.