Principal Investigator Devavrat Shah
Project Website http://lids.mit.edu/research/research-highlights/finding-culprit
In many scenarios such as the spread of viruses in computer networks, the spread of (mis)information in social networks and even the spread of Alzheimer’s disease in the brain, one wishes to find out the source or the culprit by observing who is infected. At first glance, this seems like finding a needle in a haystack and impossible to solve.
Our main observation is the following: the spread of viruses/information/disease obeys causality with respect to the underlying network structure. Therefore, if the network structure is rich enough it may be possible to obtain information about the source. Indeed, we establish a threshold phenomenon: the culprit can be found if and only if the network structure is expanding enough, irrespective of the size of the spread (the time after which the spread is observed). Figure 1 shows a simulation of the effectiveness of our estimator which we call rumor centrality.