2013-10-22 | 编辑：文\信息技术部 

 

社会网络中信息、影响力和疾病是如何传播与扩散的，是一项与人们的生活密切相关的重要研究课题，它对于有效地控制信息传播或防止疾病扩散有实际意义。目前，这类问题的相关理论研究主要集中在两个方面。其一，为了有效地追踪发生在网络上信息、病毒、疾病、污染物等的传播过程并对之进行预测，如何进行有效的识别或确认它们正在通过网络的那些边进行传播或者扩散。其二，如何找到一种有效的方法来追踪传播或者扩散过程。这些问题都具有很大的挑战性。例如，在一个大型的网络上怎样自动地识别出信息传播或者疾病扩散的不同阶段，就不是一件简单的工作；另外，如何还原信息传播或者疾病扩散的路径，并找出它们的源头，也是一件非常困难的工作。

尽管信息传播与疾病扩散都可看作是发生在网络上，然而它们有时是不易被察觉或观察到的；有时人们只能观察到网络中的一部分节点被“感知”或“感染”，但是不知道是谁“告知”或“传染”给它们的。例如，在社交网络的信息传播中，有些用户得到了新消息后，他们会马上以某种方式告知他们的朋友，但常常不确切的标明是从哪里得到的信息。类似地，在病毒的扩散过程中，患者往往能意识到自己生病了，至于是受谁的传染却不得而知。因此，人们往往只能观察到被“感知”或“感染”的时间节点，但不能确切的知道谁是上一级的信息传播者或者病毒扩散者。事实上，怎样利用这些有限的信息来确定信息传播或者疾病扩散的源头是一件非常有意义、但也非常具有挑战性的课题。特别是，与已经有的研究信息传播和疾病扩散过程的大量工作相比，确定信息传播或疾病扩散的源头的文献非常少。

最近，陈旭瑾和胡晓东的研究小组采用组合优化的方法对上述社会网络中的溯源问题开展了理论研究。他们建立了一个离散的优化模型。假设在某一时刻，当网络中某一节点被“感知”或“感染”后，在下一个时刻，它的所有邻居节点也都会被感染，这样信息或疾病就在网络中被传播或者扩散出去，网络中越来越多的节点会被“感知”或“感染”。为了及时地确定信息或者疾病的初始源头，可以在网络的节点集合中选取一些节点作为观察点。通过这些观察节点，可以知道该节点在每一个时刻是否被“感知”或者“感染”，但无法确定是被哪个邻居节点“告知”或“传染”的。当然，对网络中所有节点都可以进行监控，但这往往不容易实现，而且选取不同的节点作观察点所需要的费用可能也不相同。该优化问题的目标是，找一个能唯一地确定信息传播或疾病扩散源头的观察点集合且其费用最小。

他们经过研究发现，这个最小观察集问题等价于在图中寻找一个权重最小的双分辨集（doubly resolving set）问题。而这个问题已被证明是NP-难的，亦即不太可能存在求解该问题最优解的多项式时间算法。因此，他们研究的重点是：能不能找到求解该问题一个好的近似解的多项式时间算法。最终，他们证明了，对于任意小的ε>0，不存在近似比为 log(n)-ε的多项式时间算法。同时，给出了一个近似比为 (1+o(1)) log(n) 的多项式时间算法。