Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
13th International Engine Congress 2026 | 24 + 25 February 2026

Meeting Place for the Powertrain and Sustainable Fuels Community

Take part as a speaker in the 13th International Engine Congress 2026, the Meeting Place for the Powertrain, and Sustainable Fuels Community for the exchange of experience. Submit a subject proposal online about our main subject areas: Passenger car engine technology, Commercial vehicle engine technology and Sustainable Fuels & Energy!
EXTENDED SEARCH
Log in
Top
Social Network Analysis and Mining
Published in:

01-12-2016 | Original Article

Fast rumor source identification via random walks

Authors: Alankar Jain, Vivek Borkar, Dinesh Garg

Published in: Social Network Analysis and Mining | Issue 1/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Unveiling mobility complexity through complex network analysis
next article Users key locations in online social networks: identification and applications

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
Dong W, Zhang W, Tan CW (2013) Rooting out the rumor culprit from suspects. In: IEEE International Symposium on Information Theory Proceedings (ISIT), pp 2671–2675
Donovan P (2007) How idle is idle talk? One hundred years of rumor research. Diogenes 54(1):59–82CrossRef
Karamchandani N, Franceschetti M (2013) Rumor source detection under probabilistic sampling. In: IEEE international symposium on information theory, pp 2184–2188
Kempe D, Kleinberg JM, Tardos E (2003) Maximizing the spread of influence through a social network. In: ACM SIGKDD international conference on knowledge discovery and data mining, pp 137–146
Lappas T, Terzi E, Gunopulos D, Mannila H (2010) Finding effectors in social networks. In: ACM SIGKDD international conference on knowledge discovery and data mining, pp 1059–1068
Luo W, Tay W (2012) Identifying infection sources in large tree networks. In: IEEE communications society conference on sensor, mesh and ad hoc communications and networks (SECON), pp 281–289
McAuley J, Leskovec J (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems (NIPS), pp 548–556
Prakash B, Vrekeen J, Faloutsos C (2012) Spotting culprits in epidemics: how many and which ones? In: IEEE international conference on data mining (ICDM), pp 11–20
Qazvinian V, Rosengren E, Radev DR, Mei Q (2011) Rumor has it: identifying misinformation in microblogs. In: Conference on empirical methods in natural language processing (EMNLP), pp 1589–1599
Shah D, Zaman T (2012) Finding rumor sources on random graphs. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on measurement and modeling of computer systems (SIGMETRICS ’12). arXiv:​1110.​6230
Tripathy RM, Bagchi A, Mehta S (2010) A study of rumor control strategies on social networks. In: ACM international conference on information and knowledge management (CIKM), pp 1817–1820
Wang Z, Dong W, Zhang W, Tan C (2014) Rumor source detection with multiple observations: fundamental limits and algorithms. In: ACM international conference on measurement and modeling of computer systems (SIGMETRICS), pp 1–13
Watts DJ, Strogatz S (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442CrossRef
Zhu K, Ying L (2013) Information source detection in the SIR model: a sample path based approach. In: Information theory and applications workshop (ITA). IEEE, pp 1–9
Metadata
Title
Fast rumor source identification via random walks
Authors
Alankar Jain
Vivek Borkar
Dinesh Garg
Publication date
01-12-2016
Publisher
Springer Vienna
Published in
Social Network Analysis and Mining / Issue 1/2016
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-016-0373-6

Other articles of this Issue 1/2016

Mining half a billion topical experts across multiple social networks

  • Original Article

Understanding massive artistic cooperation: the case of Nico Nico Douga

  • Original Article

Close communities in social networks: boroughs and 2-clubs

  • Open Access
  • Original Article

A penalty box approach for approximation betweenness and closeness centrality algorithms

  • Original Article

Applying the Clique Percolation Method to analyzing cross-market branch banking network structure: the case of Illinois

  • Original Article

A hybrid epidemic model for deindividuation and antinormative behavior in online social networks

  • Original Article

Premium Partner

    Image Credits