谁是谣言的制造者？哪台电脑最先被病毒攻击？哪个人或哪个地区是某种新型疾病的发源地？

这些问题都与我们的生活息息相关。而这些问题从网络科学的角度出发就归纳为一个问题——如果探测传播源，这方面最近有很多工作，比较有影响力的文章是PRL上面的一篇文章：

Locating the Source of Diffusion in Large-Scale Networks，Pedro C. Pinto, Patrick Thiran, and Martin Vetterli,Phys. Rev. Lett. 109, 068702 (2012).关于这篇这个文章我不做过多解释，这里我给大家提供一个关于这篇文章的科学报道：Focus: Tracking Down an Epidemic’s Sourcehttp://physics.aps.org/articles/v5/89。

我今天介绍一篇计算机方面的文献，我感觉这是非常棒的一篇文章：Information Source Detection in the SIR Model:A Sample Path Based Approach，Kai Zhu and Lei Ying，Information Theory and Applications Workshop (ITA), 2013 ，http://arxiv.org/pdf/1206.5421.pdf。

文章的出发点是这样的，在知道部分传播者的前提下如何找到传播源。作者考虑了SIR传播模型，考虑这个模型是因为有的谣言（病毒）传播者可能在传播过某个谣言以后变成恢复者（R），而这些恢复者有可能是传播源。因此现在的问题就是如何从有限的情报中（知道哪些人是感染者）从整个网络找出传播源。

 思路是这样的：在图论中有节点离心率eccentricity的定义——节点到其他节点的最大路径称为这个节点的离心率，而”Jordan center"就是具有最小离心率的那个节点,类似于closenesss（注：这部分我没有认真考证！）。这篇文章基于这个思想定义了“infection eccentricity"和Jordan infection centers——就是到所有感染节点离心率最小的点。求Jordan infection centers是一个优化问题，真正求出来可能需要很大的计算量和很多的网络结构信息。为了克服这个问题，作者设计了一个方法。算法的核心思想是：让每个感染者广播一条带“标签”的消息（记节点v的标签卫"v"），然后向所有邻居传播这个标签（类似随机游走！），如果邻居的存储库中没有这个消息，那么这个邻居就记录下这个消息(v)，并记录下收到这个消息的时间（t_v），然后再向他的邻居传播。如果找到一个节点收到了所有的标签，那么就终止程序，并认为此节点很大可能是信息源。如果同一个时刻存在多个这样的点，就选择时间和（sum(t_v)）最小的点。

通过在实际数据上验证发现，该算法预测出节点虽然不一定是实际感染源，但他离感染源非常靠近，往往不超过两步。这个算法的好处就是不需要很多信息，也不需要大的计算量。