Thursday, July 5, 2012

Uncovering the Source of Epidemics, Influence, and Ideas

LN12765 - How can we localize the source of a virus, a contamination, or even an idea  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. In this paper, we demonstrate why and how  it is fundamentally possible to infer the location of the source   by observing  the information flow at only  a few nodes in the network. We find that  the proposed  technique can perform source localization in a remarkable variety of real networks,  such as the Thukela river basin in South Africa, which was affected by a large cholera outbreak in 2000.