How can we localize the source of diffusion in a complex network? Due to the tremendous size of many real networks-such as the Internet or the human social graph-it is usually infeasible to observe the state of all nodes in a network. We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely-placed observers. We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization. We describe efficient implementations with complexity O(N α ), where α = 1 for arbitrary trees, and α = 3 for arbitrary graphs. In the context of several case studies, we determine how localization accuracy is affected by various system parameters, including the structure of the network, the density of observers, and the number of observed cascades. Localizing the source of a contaminant or a virus is an extremely desirable but challenging task. In nature, many animals are intrinsically capable of performing source localization. Through chemotaxis, for example, certain bacteria can analyze concentration gradients around them in order to quickly move towards the source of a nutrient, or quickly avoid the source of a poison [1, 2] . Animals such as the Pacific salmon and the green sea turtles are capable of using olfaction to navigate in odor plumes, for foraging or reproductive activities [3, 4] . In certain systems, however, the task of localizing the source has to be performed in a network, rather than in the continuous space. This is the case, for example, when an infectious disease spreads through human populations across a large region, as observed with the worldwide H1N1 virus pandemic in 2009. Here the system is more conveniently modelled as a network of interconnected people, and source localization reduces to identifying which person in the network was first infected. In recent years, there has been significant effort in studying the dynamics of epidemic outbreaks on networks [5] [6] [7] [8] [9] [10] [11] . In particular, the focus has been on the forward problem of epidemics: understanding the diffusion process and its dependence on the rates of infection and cure, as well as on the structure of the network. In this letter, we focus on the inverse problem of inferring the original source of diffusion, given the infection data gathered at some of the nodes in the network. The ability to estimate the source is invaluable in helping authorities contain the epidemic or contamination. In this context, the inference of the underlying propagation network was studied in [12] , while the inference of the unknown source was analyzed in [13] , in both cases assuming that we know the state of all nodes in the network. More recently, the controllability of complex networks was considered in [14], using appropriately selected driver nodes. Here, our goal is to locate the source of diffusion under the practical constraint that only a small fraction of nodes can be observed. This is the case, for example, when locating a spammer who is sending undesired emails over the Internet, where it is clearly impossible to monitor all the nodes. Thus, the main difficulty is to develop tractable estimators that can be efficiently implemented (i.e., with sub-exponential complexity), and that Source estimation on an arbitrary graph G. At the unknown time t = t * , the information source s * initiates the diffusion. The blue edges denote those over which information has already propagated. In this example, there are three observers, which measure from which neighbours and at what time they received the information. The goal is to estimate, from these observations, which node in G is the information source. perform well on multiple topologies. We first introduce our network model. The underlying network on which diffusion takes place is modeled by a finite, undirected graph G = {V, E}, where the vertex set V has N nodes, and the edge set E has L edges (Fig. 1) . The graph G is assumed to be known, at least approximately, as is often verified in practice-e.g., rumors spreading in a social network, or electrical perturbations propagating on the electrical grid. The information source, s * ∈ G, is the vertex that originates the information and initiates the diffusion. We model s * as a random variable (RV) whose prior distribution is uniform over the set V , i.e., any node in the network is equally likely to be the source a priori. The diffusion process is modeled as follows. At time t, each vertex u ∈ G has one of two possible states: i) informed, if it has already received the information from any neighbour; or ii) ignorant, if it has not been informed so far. Let V(u) denote the set of vertices directly connected to u, i.e., the neighbourhood or vicinity of u. Suppose u is in the ignorant state and, at time t u , receives the information for the first time from one neighbour-say, s-thus becoming informed. Then,
The reference REF considers the source estimation problem when only a fraction of infected nodes can be observed.
Locating the Source of Diffusion in Large-Scale Networks
Physical review letters
Physical review letters
Physics Medicine Computer Science