Network observability and localization of the source of diffusion based on a subset of nodes

Abstract

Identifying the patient-zero of an epidemic outbreak, locating the person who started a rumor in a social network, finding the computer that initiated the spreading of a computer virus in a network- these are all applications of localizing the source of diffusion in a network. Since most of the networks of interest are very large, we are usually able to observe only a part of the network. In this paper, we first present a model for the dynamics of network diffusion similar to state update of a linear time-varying system. Based on this model, we provide a sufficient condition for observability of the network, i.e., we establish when is the partial information available to us sufficient to uniquely localize the source. Also, we connect the problem of finding the smallest subset of observed nodes to the problem of metric basis of the graph. We then present different methods to perform source localization depending on network observability.