Fast rumor source identification via random walks

Show simple item record

dc.contributor.author Garg, Dinesh
dc.contributor.author Jain, Alankar
dc.contributor.author Borkar, Vivek
dc.date.accessioned 2016-08-29T11:32:39Z
dc.date.available 2016-08-29T11:32:39Z
dc.date.issued 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.identifier.uri https://repository.iitgn.ac.in/handle/123456789/2444
dc.identifier.uri http://dx.doi.org/10.1007/s13278-016-0373-6
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


Browse

My Account