• 网站导航
学院动态
通知公告
学术活动
观点导读
最新资讯
统计数据
统计机构
统计资源
您现在的位置: 首页 > 观点导读 > 正文
网络中影响力节点识别的k-shell方法
[发布时间]:2012-10-24 [浏览次数]:

Identification of influential spreaders in complex networks. Nature Physics, 2010,  6(November), 6–11. doi: 10.1038/NPHYS1746

Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A. (2010).

Abstract: Networks portray a multitude of interactions through which people meet, ideas are spread and infectious diseases propagate within a society1–5. Identifying the most efficient ‘spreaders’ in a network is an important step towards optimizing the use of available resources and ensuring the more efficient spread of information. Here we show that, in contrast to common belief, there are plausible circumstances where the best spreaders do not correspond to the most highly connected or the most central people. Instead, we find that the most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis and that when multiple spreaders are considered simultaneously the distance between them becomes the crucial parameter that determines the extent of the spreading. Furthermore, we show that infections persist in the high-k shells of the network in the case where recovered individuals do not develop immunity. Our analysis should provide a route for an optimal design of efficient dissemination strategies.

在对复杂网络的各种基础性研究中,寻找网络中最具影响力的节点一直是一个重要问题, 这个问题对于评估网络中节点的重要性,发掘网络中的重要节点,具有重要的实用价值。尤其是对各种各样具体的网络,更可以有针对性地分析其性质,制定正确的策略和措施。如在罪犯关系网络中,可以迅速定位犯罪团伙的头目;在电力网络中,对重要的断路器、发电单元等进行保护;在搜索引擎的应用方面,可以把搜索到的正确结果根据其匹配和重要程度排序后返回给用户;在传染病、病毒网络中,可以有针对性地先治疗、隔离病源,有效防止病毒的传播和扩散等等。什么是节点影响力呢?针对影响力的说法和研究一直就有,如全球最有影响力人物、高校影响力排名、影响力最大的网站杂志等。对于影响力的定义,没有统一的说法,而在网络中,可以这样刻画节点的影响力:以这个节点为感染源,利用SIS或者SIR模型(描述疾病传播以及信息和谣言传播的模型), 计算同一时段内的传染规模或者其所能感染的最大规模。那么,传播规模最大或者全部被感染所需时间最短的那个节点称为最有影响力的节点。传播模型SIRSIS最初是用来刻画疾病传播的过程而提出的,分别针对患者被治愈后产生免疫和不产生免疫两种情形,现在它们已经成为网络传播动力学中最常用的两个模型,被广泛应用在描述疾病、谣言以及信息等的传播过程中。

两个模型的具体介绍如下:

1SIR模型

网络中的节点被分成三种状态:易感染Ssusceptible)、被感染Iinfectious)和被治愈Rrecovered)。初始时除了一个或者多个点处于I状态外,其他所有点都处于S状态;在每一个时间步骤里,被感染者I都以一定的概率 感染它的处于S状态的邻居,同时以一定的概率被治愈或者死亡从而转到R状态。在这个模型中,感染者被治愈后会产生免疫或者死亡从而以后不会再被感染,因此也被叫做移除者。为了识别节点的影响力,一般使用较小的感染概率,从而使最终的受感染人群保持在一定的范围之内,因为若该概率太大,被感染的人群可以很快蔓延整个网络,节点的作用就不再重要了。

2 SIS模型

不同于SIR模型,SIS模型被用来描述被治愈者不会产生免疫的传播过程。这个模型中,只有两类人群:易感染者Ssusceptible)、被感染者Iinfectious)。初始时假定有一定比例的人被感染,其他所有点都处于S状态;在每一个时间步骤里,被感染者I以一定的概率 感染他的处于S状态的邻居,同时以一定的概率被治愈。与SIR不同的是,这里被治愈的人不会产生免疫而被移除,而是重新回到易感染状态S而会在接下来的时间里重新被感染。

目前来说,针对节点影响力识别的方法有很多,包括点度(degree)、接近度(closeness)、介数(betweeness)、信息(information)、特征向量(eigenvector)等。但最常用的方法主要是点度(degree)和点介数(betweeness)等指标。其优劣将另外介绍。

我们将介绍的这篇201011月发表在 Nature Physics (Nature 子刊) 6卷上的文章采用了k-shell分解方法来确定网络中的节点影响力。k-shell是复杂网络里的一个方法,基本想法是迭代地给网络中的顶点分层,层数越高,说明该点越重要,影响力越大。 方法的具体步骤为:首先删除度为1的节点,在此基础上重新扫描网络,再次去掉度为1的节点,直到没有度为1的节点为止,将去掉的节点赋层为1,就得到ks=1的节点;同样的,按照前面的方法,再删除度为2的节点,依次进行,得到ks=2的节点;…。如此重复迭代直到网络中所有的点都被分配了一个ks值。

论文的实验研究表明,对于单个传播源低感染率的情形,Hubs节点或者高介数的节点不一定是最有影响力的节点,而通过K-shell分解分析确定的网络核心节点(即K-shell值大的节点)才是最有影响力的节点;对于多传播起源情况下,由于存在交叉感染,传播的规模很大程度依赖于初始传播源之间的距离。研究表明,k-shell分解方法是一种比较好的影响力节点识别方法,可以更好地预测疾病等的传播。当传染病在网络的核心(高Ks)爆发,病毒总是可以在网络核心通过许多种路径开始感染其它部分,无论该节点的度是多少这个结论都是有效的。这些通路的存在反过来也意味着,如果以一个随机节点为源爆发疫情,有高 Ks值的节点更有可能早于其他节点被感染(疾病预测)。

编者按: 本文由教师张忠元和研究生孙凯迪联合撰写。欢迎那些对本文感兴趣的研究生和教师给编者写信, 提出您的宝贵意见或者评论。我将及时地将您的建议反映在述评当中,或者将您的评论放在本文后面。

邮箱是: zhyuanzh@gmail.com.