# Rumors in a Network: Who's the culprit? - 2011

###### tags: `Tag(HashCloak - Validator Privacy)`

Paper: https://devavrat.mit.edu/wp-content/uploads/2017/10/Rumors-in-a-network-whos-the-culprit.pdf

Definitions: A lot of unknown terms/concepts.

### Table of Contents
[toc]

:::info
>Abstract: We provide a systematic study of the problem of
finding the source of a rumor in a network.
:::

### Introduction
IN the modern world the ubiquity of networks has made us vulnerable to new types of network risks. These network risks arise in many different contexts, but share a common structure: an isolated risk is amplified because it is spread by the network. For example, as we have witnessed in the recent financial crisis, the strong dependencies or ’network’ between institutions have led to the situation where the failure of one (or few) institution(s) have led to global instabilities.

### MAIN RESULTS: THEORY
> We establish that the asymptotic detection probability has a phase-transition effect: for linear graphs it is 0, while for trees which grow faster than a line it is strictly greater than 0. We will use different proof techniques to establish these results for trees with different rates of expansion. Throughout this section, we will be interested in the rumor source detection probability.

1. Linear Graphs: No Detection
Suppose the rumor starts spreading on a linear graph at time 0 as per the SI model.

2. Regular Expander Trees: Nontrivial Detection
Suppose the rumor starts spreading on a regular
expander tree with degree d > 2 at time 0 as per the SI model

3. Degree 3 Regular Expander Trees: Exact Detection Probability
Suppose the rumor starts spreading on a regular
expander tree with degree d = 3 at time 0 as per the SI model.

4. Geometric Trees: Correct Detection
> We note that unlike in regular trees, in a geometric tree the rumor centrality is not necessarily the ML estimator due to the heterogeneity. Nevertheless, we can use it as an estimator. Indeed, as stated below we find that the rumor centrality based estimator has an asymptotic detection probability of 1. That is, it is as good as the best possible estimator.

### SIMULATION RESULTS
> The BFS heuristic improves the correct detection probability for the AS network. This is due to the fact that the AS network has many high degree hubs, similar to scale-free networks. However, in the powergrid network, the BFS heuristic spreads out the histogram to higher errors. Again, this may be due to the fact that the powergrid network does not have as much degree heterogeneity as the AS network, and the BFS heuristic is amplifying weak heterogeneities, similar to small-world networks.

### CONCLUSION AND FUTURE WORK

* This paper has provided, to the best of the authors’ knowledge, the first systematic study of the problem of finding rumor sources in networks.
* Using the well known SI model, we constructed an estimator for the rumor source in regular trees, general trees, and general graphs. We defined the ML estimator for a regular tree to be a new notion of network centrality which we called rumor centrality and used this as the basis for estimators for general trees and general graphs
* We analyzed the asymptotic behavior of the rumor source estimator for regular trees and geometric trees. For linear graphs, it was shown that the detection probability goes to 0 as the network grows in size. However, for trees which grew faster than lines, it was shown that there was always nontrivial detection probability.
* On trees, we showed that the rumor center is equivalent to the distance center. However, these were not equivalent in a general network. Also, it was seen that in networks which are not treelike, rumor centrality is a better rumor source estimator than distance centrality.
* The next step of this work would be to better understand the effect of the BFS heuristic on the estimation error and under what precise conditions it improves or degrades performance.
* Another future direction would be to generalize the estimator to networks with a heterogeneous rumor spreading rate.