Project Highlight: Finding the 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.
More details can be found here.
Figure 1. Rumor spreading simulation in a Facebook network. The red nodes have the rumor and the blue node is the true source. The sizes of the nodes are proportional to their likelihood of being the rumor center. The green node, which is a neighbor of the blue node, is estimated as the rumor center by our algorithm.