TY - GEN
T1 - Network observability and localization of the source of diffusion based on a subset of nodes
AU - Zejnilovic, Sabina
AU - Gomes, Joao
AU - Sinopoli, Bruno
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84897713446
U2 - 10.1109/Allerton.2013.6736613
DO - 10.1109/Allerton.2013.6736613
M3 - Conference contribution
AN - SCOPUS:84897713446
SN - 9781479934096
T3 - 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
SP - 847
EP - 852
BT - 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
PB - IEEE Computer Society
T2 - 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Y2 - 2 October 2013 through 4 October 2013
ER -