Finding Rumor Sources on Random Graphs
We consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor centrality as an estimator for detecting the s...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/76261 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811090337948499968 |
|---|---|
| author | Shah, Devavrat Zaman, Tauhid |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Zaman, Tauhid |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | We consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor centrality as an estimator for detecting the source. They establish it to be the maximum likelihood estimator with respect to the popular Susceptible Infected (SI) model with exponential spreading time for regular trees. They showed that as the size of infected graph increases, for a line (2-regular tree) graph, the probability of source detection goes to 0 while for d-regular trees with d ≥ 3 the probability of detection, say α[subscript d], remains bounded away from 0 and is less than 1/2. Their results, however stop short of providing insights for the heterogeneous setting such as irregular trees or the SI model with non-exponential spreading times.
This paper overcomes this limitation and establishes the effectiveness of rumor centrality for source detection for generic random trees and the SI model with a generic spreading time distribution. The key result is an interesting connection between a multi-type continuous time branching process (an equivalent representation of a generalized Polya's urn, cf. [1]) and the effectiveness of rumor centrality. Through this, it is possible to quantify the detection probability precisely. As a consequence, we recover all the results of [10] as a special case and more importantly, we obtain a variety of results establishing the universality of rumor centrality in the context of tree-like graphs and the SI model with a generic spreading time distribution. |
| first_indexed | 2024-09-23T14:43:13Z |
| format | Article |
| id | mit-1721.1/76261 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:43:13Z |
| publishDate | 2013 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/762612022-10-01T22:08:23Z Finding Rumor Sources on Random Graphs Rumor centrality: A universal source detector Shah, Devavrat Zaman, Tauhid Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat We consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor centrality as an estimator for detecting the source. They establish it to be the maximum likelihood estimator with respect to the popular Susceptible Infected (SI) model with exponential spreading time for regular trees. They showed that as the size of infected graph increases, for a line (2-regular tree) graph, the probability of source detection goes to 0 while for d-regular trees with d ≥ 3 the probability of detection, say α[subscript d], remains bounded away from 0 and is less than 1/2. Their results, however stop short of providing insights for the heterogeneous setting such as irregular trees or the SI model with non-exponential spreading times. This paper overcomes this limitation and establishes the effectiveness of rumor centrality for source detection for generic random trees and the SI model with a generic spreading time distribution. The key result is an interesting connection between a multi-type continuous time branching process (an equivalent representation of a generalized Polya's urn, cf. [1]) and the effectiveness of rumor centrality. Through this, it is possible to quantify the detection probability precisely. As a consequence, we recover all the results of [10] as a special case and more importantly, we obtain a variety of results establishing the universality of rumor centrality in the context of tree-like graphs and the SI model with a generic spreading time distribution. 2013-01-15T21:22:26Z 2013-01-15T21:22:26Z 2012-06 Article http://purl.org/eprint/type/JournalArticle 978-1-4503-1097-0 http://hdl.handle.net/1721.1/76261 Shah, Devavrat, and Tauhid Zaman. “Rumor Centrality.” Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems (SIGMETRICS '12) (2012): 199. https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1145/2254756.2254782 Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems (SIGMETRICS '12) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Shah, Devavrat Zaman, Tauhid Finding Rumor Sources on Random Graphs |
| title | Finding Rumor Sources on Random Graphs |
| title_full | Finding Rumor Sources on Random Graphs |
| title_fullStr | Finding Rumor Sources on Random Graphs |
| title_full_unstemmed | Finding Rumor Sources on Random Graphs |
| title_short | Finding Rumor Sources on Random Graphs |
| title_sort | finding rumor sources on random graphs |
| url | http://hdl.handle.net/1721.1/76261 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT shahdevavrat findingrumorsourcesonrandomgraphs AT zamantauhid findingrumorsourcesonrandomgraphs AT shahdevavrat rumorcentralityauniversalsourcedetector AT zamantauhid rumorcentralityauniversalsourcedetector |