网络传播中最有影响力的节点

最近我们仔细阅读了2010年11月发表在《NATURE PHYSICS》第6卷上的文章《Identifying  influential  spreaders in complex networks》，作者是美国Boston  University的 Maksim Kitsak 等7位学者。文章很有趣，结论颇具颠覆性。

我们知道，现实世界的大量复杂系统都可以通过网络来描述，在社会网络中到底哪些节点最有影响力，在疾病传播网络中哪些节点最具有感染力？目前一般的研究结果都认为网络中的Hubs节点或者高介数的节点是传播中最有影响力的节点，这是因为Hubs节点拥有更多的人际关系，而高介数的节点有更多的最短路径通过，于是疾病控制和免疫首先要确定这样的节点。但是，这篇文章的作者调查（1）340万市民的LiveJournal.com友谊网络，（2）伦敦大学计算机科学系的学院电子邮件联系网络，（3）在瑞典收集的医院住院病人的接触网络（CNI） ，以及（4）由imdb.com标记为在同一电影中有合作的演员网络，并且通过SIR模型和SIS模型的建模分析指出，对于单个传播源情形，Hubs节点或者高介数的节点不一定是最有影响力的节点，而通过K-shell分解分析确定的网络核心节点（即K-shell值大的节点）才是最有影响力的节点。K-shell是图论里的一个经典的概念，网络的外壳和边缘的K-shell为1，然后往内像剥洋葱一样进入网络的核心（K-shell值大的区域）。之所以产生Hubs节点或者高介数的节点不一定最具有影响力的原因在于，它们如果在整个网络的边缘，那么它在传播中的作用就很微弱了。而某些度数虽然比较小却位于网络核心的节点将对传播过程产生重大的影响。以CNI的网络为例说明，一个传播过程中感染的规模并不一定与传播起源节点的度k有关，即使从度数相近的不同Hub节点开始，感染结果也可能会非常不同。相反，从相同的kS层节点开始，即使有不同的度K，传播规模却很相近，说明初始传播节点的kS值可以准确地预测感染的规模。同时kS值对于不同的传播率显得相当健壮。这也说明节点所处网络的位置比一个节点的局部属性度K更能决定它的影响力。同样地，高介数的节点和Hub节点一样，也远不如kS值更能准确地预测感染的规模。

当然文章也指出，当初始存在多个传播源的时候，传播的规模很大程度依赖于初始传播源之间的距离。尽管高kS点是最好的单一传播者，但是在多个传播源情况，度大的Hub节点往往比kS大的节点具有更高传播效率。这是因为传播存在交叉感染现象（感染者传染给感染者），kS大的节点往往在网络的核心，它们聚集在一起，而度大的Hub节点可以分散在网络的不同区域。因此，如果考虑多个传播源有更大的传播规模的话，应该选择处于不同shell（层）、不直接相连的较大的 k的节点作为初始传播源。这篇文章对于我们认识传播网络中到底哪些节点最有影响力，评价网络中节点的重要性，以及从事网络控制、信息传播、疫苗具有重要意义。但是仍然存在很多问题有待研究。譬如怎么更好地定义节点的影响力，怎么反映传播速度和传播范围，随机、小世界和无标度网络上节点影响力的评价有何差异，都值得进一步考虑。