Estimating rumor source in social networks using incomplete observer information

Utilization of observers in social networks for rumor source estimation is quite common. However, existing observer-based techniques have several drawbacks. Mostly existing approaches use the information available (such as timestamps) with many observers to locate the source node, which degrades their performance. Estimation of exact timestamps of non-observer nodes also poses an added challenge. To overcome these issues, we introduced a Radial Observer Source Estimator (ROSE) algorithm to estimate the source node in the network. The ROSE algorithm utilizes shares of a particular message instead of timestamps, and it considers the information available with only those observers that have minimum shares. The overall complexity of the algorithm is O(log(N) * N2), where N is the number of nodes in a network. We evaluate our algorithm on small-scale, large-scale, and artificial networks. Empirical results show that the proposed algorithm is highly efficient in terms of execution time compared to four other state-of-the-art rumor source identification algorithms. Also, it mostly performs well in accurately discovering a rumor source node, with a higher success rate and fewer distance errors.