We provide a systematic study of the problem of finding the source of a rumor in a network. We model rumor spreading in a network with a variant of the popular SIR model and then construct an estimator for the rumor source. This estimator is based upon a novel topological quantity which we term . We establish that this is an ML estimator for a class of graphs. We find the following surprising threshold phenomenon: on trees which grow faster than a line, the estimator always has non-trivial detection probability, whereas on trees that grow like a line, the detection probability will go to 0 as the network grows. Simulations performed on synthetic networks such as the popular small-world and scale-free networks, and on real networks such as an internet AS network and the U.S. electric power grid network, show that the estimator either finds the source exactly or within a few hops of the true source across different network topologies. We compare rumor centrality to another common network centrality notion known as distance centrality. We prove that on trees, the rumor center and distance center are equivalent, but on general networks, they may differ. Indeed, simulations show that rumor centrality outperforms distance centrality in finding rumor sources in networks which are not tree-like.
Prior work on rumor spreading has primarily focused on viral epidemics in populations. The natural (and somewhat standard) model for viral epidemics is known as the or SIR model @cite_13 . In this model, there are three types of nodes: (i) susceptible nodes, capable of being infected; (ii) infected nodes that can spread the virus further; and (iii) recovered nodes that are cured and can no longer become infected. Research in the SIR model has focused on understanding how the structure of the network and rates of infection cure lead to large epidemics @cite_0 , @cite_25 , @cite_26 , @cite_19 . This motivated various researchers to propose network inference techniques for learning the relevant network parameters @cite_16 , @cite_10 , @cite_4 , @cite_22 , @cite_5 . However, there has been little (or no) work done on inferring the source of an epidemic.
@cite_26 @cite_4 @cite_22 @cite_10 @cite_0 @cite_19 @cite_5 @cite_16 @cite_13 @cite_25
2030539428 2913597007 1674853078 2962705874
The study of social networks, and in particular the spread of disease on networks, has attracted considerable recent attention in the physics community. In this paper, we show that a large class of standard epidemiological models, the so-called susceptible infective removed (SIR) models can be solved exactly on a wide variety of networks. In addition to the standard but unrealistic case of fixed infectiveness time and fixed and uncorrelated probability of transmission between all pairs of individuals, we solve cases in which times and probabilities are nonuniform and correlated. We also consider one simple case of an epidemic in a structured population, that of a sexually transmitted disease in a population divided into men and women. We confirm the correctness of our exact solutions with numerical simulations of SIR epidemics on networks. Abstract A two-layer susceptible-infected-recovered unaware-aware (SIR-UA) epidemic model is presented to analyze the effect of different heterogeneous networks in a population. Random, scale-free, and small-world network topologies are tested to investigate the impact of awareness on the spread of epidemics in a two-layer network with diverse combinations of degree and structure. Susceptible and infected (both unaware and aware) individuals are associated with their neighboring nodes in a social network structure with various degree distributions. In the two-layer SIR-UA epidemic model, a virtual network represents the connections that spread information, while a physical network represents the physical social interactions that spread diseases. We test various combinations of network structures in virtual or physical networks, to understand the impact of information diffusion on the spread of epidemics in a heterogeneous network structure. Then, the effects of awareness on the spread of a disease are discussed. Finally, phase diagrams are illustrated to reveal the final regions covered by an epidemic with various network parameters. We find that a disease spreads less if the virtual social network is more connected than the network of physical connections. The last decade has seen the rise of immense online social networks (OSNs) such as MySpace and Facebook. In this paper we use epidemiological models to explain user adoption and abandonment of OSNs, where adoption is analogous to infection and abandonment is analogous to recovery. We modify the traditional SIR model of disease spread by incorporating infectious recovery dynamics such that contact between a recovered and infected member of the population is required for recovery. The proposed infectious recovery SIR model (irSIR model) is validated using publicly available Google search query data for "MySpace" as a case study of an OSN that has exhibited both adoption and abandonment phases. The irSIR model is then applied to search query data for "Facebook," which is just beginning to show the onset of an abandonment phase. Extrapolating the best fit model into the future predicts a rapid decline in Facebook activity in the next few years. We investigate the effects of modular and temporal connectivity patterns on epidemic spreading. To this end, we introduce and analytically characterise a model of time-varying networks with tunable modularity. Within this framework, we study the epidemic size of Susceptible-Infected-Recovered, SIR, models and the epidemic threshold of Susceptible-Infected-Susceptible, SIS, models. Interestingly, we find that while the presence of tightly connected clusters inhibits SIR processes, it speeds up SIS phenomena. In this case, we observe that modular structures induce a reduction of the threshold with respect to time-varying networks without communities. We confirm the theoretical results by means of extensive numerical simulations both on synthetic graphs as well as on a real modular and temporal network.