Network science started with trying to understand the structure of large-scale complex networks, from social connections to the makeup of protein interactions. It then proceeded to explore the behavior of processes that occur on top of networks. And one of the most important ones is diffusion: how something, such as information or disease, propagates over a network.
But what about the reverse problem? Given that something has diffused across a network, can we infer the source of this epidemic's spread?
In a new paper in Physics Review Letters (general summary here), a team of scientists led by Pedro Pinto attempted to do this. And unlike other methods, they explore how observing only a small fraction of the nodes of a network can be used to identify the source of the diffusion process.
It all comes down to a process of maximum likelihood estimation, where the most likely values of the parameters of a statistical model can be calculated. In this case, the parameters are related to the source of the diffusion given the possible paths that the disease or bit of information could have taken across the network.
It seems to work. They compare their method to an actual cholera outbreak in South Africa in 2000 and found good results, which could be determined using only 20 percent of the nodes in the network, where the nodes represent different communities in the region. In their supplemental case studies, they explore how the leader of a terrorist organization can be identified, and even show how this methodology could be used in finding contamination sources in a subway system. They found that they could determine the source of a contamination to within a single subway stop by monitoring the behavior fewer than 20 percent of the stations:
Of course, it's not always easy to implement this kind of detection. There are certain assumptions about how the epidemic diffuses and how the detection works, as well as the assumption that there is even only source, which don't necessarily hold in every diffusion situation. Nonetheless, exploring the source of diffusion is an exciting problem and one that demands further attention for everything from gossip to disease.
Top image:Enzo Figueres/Flickr/CC
