Research On Identifying Information Sources In Networks

In the modern world, the ubiquity of networks has made us vulnerable to various network risks. For instance, rumor posted by a malicious individual in an online so-cial network, such as Facebook and Weibo, can easily propagate to a large number of people in a relatively short time. A contagious disease like Severe Acute Respiratory Syndrome (SARS) can spread quickly through a population and lead to an epidemic. Computer viruses propagate throughout the Internet and infect millions of computers. Isolated failures could lead to rolling blackouts in smart grids. Every year, tremendous damages caused by those risks have incurred massive losses to society in finance and labor. Identification of these malicious information sources in the network allows time-ly quarantine of the epidemic-like spreading to limit the damage caused. For the issue of information source estimation, our main contributions are as follows:We study the problem of a single rumor source estimation with multiple obser-vations, from a statistical point of view of a spreading over a network, based on the susceptible-infected (SI) model. We propose a unified inference framework based on the union rumor centrality, and provide explicit detection performance for degree-regular tree networks. Surprisingly, even with merely two observations, the detection probabil-ity at least doubles that of a single observation, and further approaches one, i.e., reliable detection, with increasing degree. We also showed that for degrees greater than two, the detection probability increases with the number of observations and decreases with the number of infected nodes. This indicates that both diversity and connectivity enhance detectability. For general graphs, a detection algorithm using a breadth-first search s-trategy is also proposed and evaluated. Besides rumor source detection, our results can be used in network forensics to combat recurring epidemic-like information spreading such as online anomaly and fraudulent email spams.We focus on the problem of estimating the rumor source under the susceptible-infected (SI) spreading model is addressed, when partial infection order information among part of infected nodes, called "anchors", is available. The maximum likelihood estimator is established and is shown to be the node that possesses the largest rumor centrality under the restriction imposed by the partial infection order information, which is named the restricted rumor center as a variant of the rumor center originally proposed in [1]. Besides, a simple heuristic estimator is also proposed, by directly adopting the rumor center after expurgating some impossible source candidates. The probability of correct estimation is analytically studied for regular tree networks. When the anchors are randomly scattered and only the first infected node among the anchors is known, it is shown that the impact of partial infection order information is significant when the ratio between the number of the anchors and the total infected population size is relatively small. When the anchors are connected, it is shown that the probability of correct estimation is substantially improved, even for line networks. The insights in the analytical results are corroborated by experimental evaluations with several synthetic and real-world networks.We consider the problem of estimating the rumor source under three meaningful scenes. First, we study the problem of a single rumor source estimation based on the susceptible-infected-susceptible (SIS) spreading model. Based on the rumor centrality proposed in the susceptible-infected (SI) model by Shah and Zaman, we propose a ru-mor centrality based algorithm, that leverages multiple observations to first construct a diffusion tree graph, and then use the union rumor centrality to find the rumor source. Our simulation results on different network structures shows that our proposed algo-rithm performs well. For tree networks, increasing the observations can dramatically improve the exact detection probability. This clearly indicates that a richer diversity enhances detect-ability. Second, we study the problem of multiple connected sources estimation under the susceptible-infected (SI) model We characterize and evaluate the exact and asymptotic detection probability for general trees. Third, we study the prob-lem of a single rumor source estimation with multiple sequential observations based on the susceptible-infected (SI) model. For tree networks, multiple sequential observation-s for one single instance of rumor spreading cannot improve over the initial snapshot observation. The impossibility of performance improvement demonstrates the need for early detection.