Fast rumor source identification via random walks

Show simple item record Garg, Dinesh Jain, Alankar Borkar, Vivek 2016-08-29T11:32:39Z 2016-08-29T11:32:39Z 2016-12
dc.identifier.citation Jain, Alankar; Borkar, Vivek and Garg, Dinesh, “Fast rumor source identification via random walks”, Social Network Analysis and Mining, DOI: 10.1007/s13278-016-0373-6, vol. 6, no. 1, Dec. 2016. en_US
dc.identifier.issn 1869-5450
dc.identifier.issn 1869-5469
dc.description.abstract We consider the problem of inferring the source of a rumor in a given large network. We assume that the rumor propagates in the network through a discrete time susceptible-infected model. Input to our problem includes information regarding the entire network, an infected subgraph of the network observed at some known time instant, and the probability of one-hop rumor propagation. We propose a heuristic based on the hitting time statistics of a surrogate random walk process that can be used to approximate the maximum likelihood estimator of the rumor source. We test the performance of our heuristic on some standard synthetic and real-world network datasets and show that it outperforms many centrality-based heuristics that have traditionally been used in rumor source inference literature. Through time complexity analysis and extensive experimental evaluation, we demonstrate that our heuristic is computationally efficient for large, undirected and dense non-tree networks. en_US
dc.description.statementofresponsibility by Alankar Jain, Vivek Borkar and Dinesh Garg
dc.format.extent vol. 6, no. 1
dc.language.iso en_US en_US
dc.publisher Springer Vienna en_US
dc.subject Rumor source identification en_US
dc.subject Random walk en_US
dc.subject Hitting time en_US
dc.subject Centrality measures en_US
dc.subject Maximum likelihood estimate en_US
dc.title Fast rumor source identification via random walks en_US
dc.type Article en_US
dc.relation.journal Social Network Analysis and Mining

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account