网络传播过程中的节点重要性度量.docx
- 文档编号:6932819
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:10
- 大小:74.96KB
网络传播过程中的节点重要性度量.docx
《网络传播过程中的节点重要性度量.docx》由会员分享,可在线阅读,更多相关《网络传播过程中的节点重要性度量.docx(10页珍藏版)》请在冰点文库上搜索。
网络传播过程中的节点重要性度量
网络传播过程中的节点重要性度]
在复杂网络的传播过程中,找到最有影响力的传播者对于控制系统的传播力和确保信息的有效扩散等方面有着十分重要的意义。
而即使对于同一动力学过程,不同的度量方法(如度、聚类系数等)在判断重要节点时往往有着不同的结果。
这篇文章介绍了八种不同的节点重要性度量方法,并在四种不同的实际网络中进行了流行病传播的模拟,通过计算这八种指标与节点传播能力的相关性来判断哪种方法更适合。
结果表明,特征向量中心性是与流行病传播相关性最强的度量方法,其次,度、接近中心性与k核也能很好地衡量流行病传播过程中的节点重要性。
关键词:
复杂网络,节点重要性,流行病传播
第一章引言
在复杂网络的传播过程中,一般地,人们认为中心性较强的节点相比其他节点可以更快并且更大范圉地将他们的影响扩散到整个网络中去,我们可以以此为依据判断网络中重要的节点。
H前,已经有许多用来度量网络传播过程中的节点重要性的方法被提出和被验证,但它们的结论并不一致,事实上,根本没有一个统一的方法来定义节点的“重要性”,每一个度量方法都是考虑了网络中一个特定的性质提岀的,它们有着各自的优势和缺陷。
比如,介数和接近中心性是基于节点对之间的最短距离提出的,它们充分考虑了路径长度对于网络传播的影响,却在一定程度上忽略了其他可能的通路。
K核分解能找到网络中的hub集团,但也可能会忽略一些连接数较少却相对重要的节点。
为了验证在实际网络的传播过程中,哪些节点中心性度量方法在判断网络中最重要的传播者时更可幕,做了本次模拟和计算。
在这篇文章中,首先介绍了复杂网络研究背景,回顾了网络理论发展的历程,接着指出了度量网络传播过程中的节点重要性的现实意义,介绍了八种常见的中心性度量方法,它们分别是度中心性、平均邻居度、接近中心性、介数中心性、特征向量中心性、聚类系数、K核、网页排序。
为了说明在实际网络的传播过程中,这八种中心性量度在衡量节点的重要性问题上的可靠程度,接着在四个不同的实际网络中分别计算了它们与节点传播能力的相关性,其中节点的传播能力通过各节点流行病SIR传播后网络中康复者个数所占的比例来表示。
通过计算结果可以看出,特征向量中心性、度、接近中心性和k核在寻找重要的传播者时具有一定的优势。
其中特征向量中心性虽然算法较复杂,但曲于它是在考虑整体的网络结构的基础上给每个节点一个中心性指标,在寻找核心节点上具有明显的优势。
度和k核体现了网络传播过程中hub节点的重要性,接近中心性则说明了路径长度对于网络中传播范围的影响。
对于特定的网络和传播方式,我们要根据实际需要采取不同侧重点的量度来寻找影响力最大的节点。
第二章复杂网络概述
复杂系统在我们的生活中是无处不在的。
山数十亿手机组成的通信网络方便了人与人之间的联络,大脑中数十亿神经元的活动成就了我们理解这个世界的能力,细胞中成千上万的基因完美的结合保证了我们每个人都是特别的存在,棋至我们身在其中的由儿十亿的人口联合运作起来的社会也是一个复杂系统。
正是由于它在我们的生活中处于如此息息相关的重要地位,对复朵系统的研究成为了21世纪最重要的课题之一。
事实上,每个复杂系统都可以转化成一个错综复杂的网络,这些复朵网络既有特殊性也有普遍性。
它的特殊性在于每个网络的规模,作用,演化时间以及节点和边代表的意义等方面的不同,例如新陈代谢网中的节点代表分子,边代表分子间的化学反应;万维网中的节点代表网页,边代表网页间的链接地址;社会网中的节点代表个人,边代表人与人之间的关系一一朋友、家人、同事等等。
而这些在不同领域的看似拥有巨大差异的网络事实上也有很多共同点,一方面这些网络都可以看作是山一些节点按照一定的方式连接起来的图,另一方面,研究发现它们具有许多相似的性质。
在复杂网络的研究中,人们不仅仅是要发现不同网络的特殊性质,更重要的是要去发掘其中普适的演化规律和处理方法。
在历史进程中,网络科学在两个不同的领域有它的研究基础:
社会科学和图论ll|o其中社会科学中的研究更倾向于关注网络连接背后的涵义而非网络结构本身,网络分析被当作一个解释工具来描述社会中一种现象的演化和传播。
然而,它也为我们提供了很多关于网络连接的定量和定性的信息,而且,在社会科学中,也会进行对个体重要性的度量,因为一个人的社会重要性将会对网络中信息传播和关系建立产生一定的影响。
相比之下,图论中的研究为我们提供了大量的定量工具和描述网络的机制,它是网络科学最重要的数学基础。
在图论的基本表示中,节点代表系统中的事物,用两点之间的连线代表相应的两个事物之间的联系。
图论的起源要追溯到1736年瑞典数学家欧拉对著名的哥尼斯堡七桥问题的研究,他是第一个用图来解决数学问题的人。
通过把一个实际的问题转换成图的形式,人们认识到网络结构中往往蕴含了一些网络性质,可以限制或促进某些行为的发生。
要充分理解网络是如何影响系统的某些性质,图论是不可或缺的基础。
在图论创立后的很长一段时间里并没有得到较大的发展。
20世纪60年代,两位匈牙利数学家Erdos和Renyi对随机网络的研究奠定了复朵网络理论研究的基石。
在1959到1968年间,他们共发表了八篇一系列的文章SI,将概率论与组合学的内容融合到了图论的理论当中,建立了一个数学中新的分支一一随机图理论(randomgraphtheory)。
在随机图模型中,任意两个节点之间有边相连的概率都相同。
在随机图理论创立后的三四十年里,复杂网络研究一直都把随机网络做为基础,但在绝大多数的现实网络中,连接并不是完全随机的。
20世纪末期,互联网的发展极大地促进了复杂网络的研究,人们对复杂网络的探索发生了极大的转变。
1998年,Watts和Strogatz提出了小世界网络模型1,01(如图2」),通过对规则网络进行一定的随机重连,使得到的网络同时具有规则网络的聚集度高和随机网络的路径长度小的特征,这确实反映了现实网络中的一些特点,比如在朋友关系网中,一方面人们的大部分朋友都与他们离得比较近,这是聚集度高的体现,另一方面也会有一些住得较远的甚至是在异国他乡的朋友,这则是网络中一些少量的远程连接的情形。
在小世界网络中,度分布可以近似为泊松分布,与随机网络相似(如图2.2),它的特点是在平均度附近有一个峰值,随后呈指数衰减,这意:
味着度值远大于平均值的节点是儿乎不存在的。
而在人们对复杂网络的研究中发现,许多现实网络,比如万维网,蛋口质相互作用网,科研人员合作网等都存在度值很大的节点,并且度分布呈幕率分布(如图2.3)。
规则网络小世界网络随机网络
图2.1随机程度介于规则网络和随机网络之间的小世界网络
1999年,Barabasi和Albert提出了一个无标度网络模型,也可以称为BA模型1小,解释了幕率分布的产生机理。
他们认为增长和优先连接是现实网络中出现幕率分布的两个主要原因。
增长的意思是节点总数的增加,它意味着网络是开放的,新的个体不断加入。
例如每个人在生活中都会不断结交到新的朋友,学术刊物上会不断有新的文章发表。
优先连接是指新加入的节点总是倾向于与度值较大的节点连接,在现实网络中确实如此,最受欢迎的人总是会认识更多的人,富
有的人总是比穷人容易赚更多的钱,一些经典的参考文献总是会得到更多的引用量。
这两个模型的提出让人们对现实网络得到了新的认识,也使人们意识到使用网络来研究现实中复杂系统的重要性,也让复杂网络研究进入到一个新的热潮。
2000n
1500-
1000-
500-
图2・2随机网络的度分布,近似于泊松分布
图2・3无标度网络的幕律分布,近似于幕律分布
第三章节点重要性研究概述
3.1网络传播过程中节点重要性的研究意义
传播现象在现实生活中是广泛存在的。
人与人之间的谣言传播,流行病在人或动物间的传播,木马病毒在全世界范围内的计算机中的传播。
科学技术的发展,现代通讯方式的普及以及交通的发达不仅会给我们的生活带来极大的便利,也使不良信息,病毒等的传播变得极为迅速。
在这样的悄形下,有效评佔网络中节点的重要性是十分重要的。
比如对于一个在社会中影响较大的谣言,通过对一些有较高影响力的谣言传播者的处理,可以有效控制网络中谣言的传播;在严重的流行病肆虑的时期,有针对性地隔离治疗关键病人可以有效控制疾病在人群中的进一步传播;对于计算机集群中相对重要的服务器节点进行重点防护,以及做好对重要数据的备份工作,可以有效提高计算机网络的鲁棒性。
3.2节点重要性度量方法
评估网络中重要的节点的方法多种多样,每一种度量方法都是基于网络中某一特性来评价节点的重要程度,一般来说,对于某种特定的问题,人们只考虑其中一种或儿种方法即可大致判断不同节点的重要程度。
下面详细介绍其中常用的儿种度量方法。
1.度(Degree)
中心性最基础的一个定义方法就是度中心性,用《表示,它考虑了节点具有的连接边的数U。
在这种情况下,具有最大边数的节点就被认为是最重要的节点。
节点i的度定义为
ki=Xav
(1)
其中G代表整个网络中的节点,知为邻接矩阵的(心)元,即当节点i和j之间有连接边时,呦为1,否则为零。
2.平均邻居度(Averageneighborhooddegree)
平均邻居度定义为节点邻居的度的平均值,这种中心性方法考虑了节点的笫二层邻居,主要原因是考虑到虽然有些节点本身的边数较少,但如果它的邻居中有度值较大的节点,那么它很有可能也会是一个比较重要的节点。
节点i的平均
邻居度定义为
其中l,(j)是节点i的邻居点集。
无论是对于流行病传播还是谣言传播,度中心性都是衡量节点重要性的有效方法,因为在一个网络中,度值高的节点或者集团在传播过程中通常起着十分重要的作用。
文献[12]中的数据表明,在一些非空间的社会网络中的谣言传播过程中,平均邻居度的指标更适合衡量节点重要性。
3.接近中心性(Closenesscentrality)
用节点间的最短距离来定义中心性,认为一个节点越接近中心,它到所有其他节点的总距离就越小。
节点i的接近中心性定义为
其中给是节点i和j之间的最短距离,N是网络中的节点总数。
注意这个指标只适合于连通图,如果一个网络中有不连通的部分,那么对任何一个节点都会存在血=8的情况,则对应的C,=0o
4.介数中心性(Betweennesscentrality)
节点的有效负载也可以作为中心性度量方法。
介数中心性就考虑了节点作为其他两个节点的最短路径中的桥梁的次数,因此,对节点h介数中心性定义为
Mb(“)
其中b©汕)是节点对(⑦巧间的最短路径通过节点i的次数,巩么巧则是节点对(ab)间的最短路径数。
对网络中所有的节点对⑺”)求和。
5.特征向量中心性(Eigenvectorcentrality)
特征向量中心性是将其他节点中心性的线性组合作为一个节点的中心性,它的U的是在网络结构的整体意义上找到最核心的节点。
它定义为网络邻接矩阵最大特征值对应的特征向量,公式表达为
对应的矩阵形式为:
AX=xX,其中X是特征向量,2是最大特征值。
6.聚类系数(Clustering)
聚类系数山网络中出现的三角形的个数决定。
它定义为
(6)
以)
其中仗(,)是包括i点的三角形的数三角形意味着三个点两两之间都有连边,川3(。
是与i点相连的三元组的数II。
聚类系数可以理解为如果两个节点只有通过节点i才相连,那么i节点可以控制这两个节点间的信息流,那么节点i就是重要的。
要注意的是与其他中心性度量方法相反,聚类系数越小节点越重
要。
7.核数(Coreness)
k核分解通过依次将网络中度为k的节点删去并标记每个节点得到的中心性值。
节点根据它们的剩余度值的大小被分配到相应的k层。
一开始,我们首先删去网络中所有度为1的节点,当删去这些节点之后,一些节点可能只剩下一条连边,所以我们继续删去剩余度为1的节点,反复删除一直到整个网络中不再有度为1的节点。
所有被删去的节点,包括它们的连边,就被标记为k核等于1的一层。
接着,用同样的方式,我们再反复删去剩余度为2的节点,它们的k核标记为2。
删去并标记度更高的节点,直到所有的节点都被删去。
最终,每一个节点都会有一个相应的k核,网络可以被看作是所有k层的一个集合体。
用这样的方法,处于网络边缘的节点的核数就小,然而,核数大的节点必定是位于网络最深层的节点。
即使度很大的节点,也有可能拥有很小的核数。
核数越大的节点,删除后对网络的破坏程度越大。
8.网页排名(PageRank)
在随机行走的过程中被访问次数越多的节点重要性越强,类似的,随意点开网贝中的链接,被点到次数越多的网页就越重要。
谷歌网页排名就是用这样的思想来评估网页的相关性和重要性的。
网页排名的算法是山谷歌的创始人SergeyBrin和LawrencePage最早提出的2】,最早的算法描述如下:
假设页面Tl,T2,...,Tn指向页面A,常数d是0到1之间的阻尼系数,常设为0.85,它的意义就是用户到达某页面并继续向后浏览的
概率,则1-d为用户停止点击,随机跳转到其他页面的概率,C(A)为页面A中链接的数目,则页面A的网页排名为
第四章节点重要性度量方法的模拟和评估
4.1研究目的与方法
为了研究不同的节点重要性度量方法在衡量节点的传播能力上的差异。
在实际网络中,首先,用第三章介绍的八种量度分别计算了每个节点的值,它们分别是:
度、平均邻居度、聚类系数、接近中心性、介数、k核、网页排名和特征向量中心性。
然后从网络中的一个源节点出发进行流行病传播过程的演化,把最终康复者占总人数的比例看做该节点的传播能力。
最后用斯皮尔曼等级相关系数(Spearmanrankcorrelationcoefficient)来计算节点传播能力与各量度的相关性,相关性越强则说明该度量方法越可靠。
4.2流行病传播过程
本次研究用到的流行病传播模型为SIR模型,网络中的节点有三种可能的状态:
易感(susceptible)、感染(infectious)、康复(recovered)。
其中易感者是健康并且可能被感染的个体,感染者是已经感染并且可以向自己的易感者邻居传播疾病的个体,而康复者就意味着个体已经康复并对疾病产生了永久免疫,在传播过程中没有作用。
在每个时间步长中,感染节点向它的易感者邻居传播疾病,传播率为0,同时感染节点以一定概率康复,康复率为“,这是一个同步过程。
整个过程是自发的,不需要接触。
当网络中没有感染节点,疾病不可能再继续传播时,这个流行病传播过程终止。
4.3实际网络基本信息
研究中使用了四种不同的真实复杂网络,包括社交网络和空间网络。
它们分别是
(1)海豚社会网(Dolphinsocialnetwork)
62只生活在新西兰神奇湾的频繁接触的海豚之间的无向的社会网络,山62个节点,159条边组成【叫
(2)空手道俱乐部(Zachary'skarateclub)
20世纪70年代美国某大学空手道俱乐部34位成员的朋友关系网络。
山34
个节点,78条边组成I,5,o
(3)科学家合著网(Coauthershipsinnetworkscience)
网络科学方向的科学家的合著者关系网络,是Newman在2006年5月编译的。
由1589个节点,2742条边组成【⑹。
(4)电力网(powergrid)
一个无向无权的网络,代表了美国西部电力网的拓扑结构。
由4941个节点,6594条边组成I,0|o
这些网络的基本信息及各量度的平均值见表4.1o
表4.1各网络的基本信息
网络
N
㈣
0
&〉
㈣
9〉
Dolphins
62
5.081
6.862
0.259
0.310
71.468
3.129
1.60x102
0.349
Karate
34
4.088
9.498
0.567
0.423
1&513
2.794
2.65xlO*2
0.364
coauthership
1589
3.450
4.462
0.637
6.78xlO4
231xl02
2.930
6.29x10,
0.022
Power
4941
2.669
3.966
0.080
0.054
4.44xlO4
1.687
2.02x1O'4
0.030
4.4计算结果与讨论
在四个实际网络中,分别计算了当传播率0=0.3,康复率A=1.0以及0=0.8,“=1.0时的SIR传播中最终康复者个体占全部个体数LI的比例与各中心性度量方法的相关性,结果见表4.2。
从表4.2可以看出,特征向量中心性与网络中最终康复节点比例的相关程度最好,其次是度、接近中心性和k核,其中在合著者网络中,平均邻居度的相关性比度要高。
特征向量中心性将一个节点相关的其他节点的中心性也考虑进来,进而得到该节点的中心性值,这种度量方法是在网络整体结构上给出节点的重要程度,算法比较复杂。
度与k核所用的方法不同,但目的都是寻找网络中的hub节点(即拥有邻居较多的中心节点),总的来说,hub节点在传播过程中起着十分重要的作用。
而接近中心性则体现了路径长度对传播过程的影响,在有些网络中,特别是在低传播率的情况下,路径长度儿乎起着决定性的作用。
另外,聚类系数、介数和网页级别与节点传播能力的相关性并不显著。
10
表2各度量方法和网络中SIR演化最终康复个体的比例的相关性表。
这些中心性测度
分别是度(k)、平均邻居度(r)、聚类系数(cc)、接近中心性(C)、介数中心性(B)、k核咨)、
网页排名(PR).特征向量中心性(E)。
其中加粗的为相关系数较大的值
SIR参数
网络
K
r
cc
C
B
k.
PR
E
dolphins
0.49
0.10
0」4
0.56
0.41
0.46
0.43
0.63
0=0.3
〃=1・0
karate
0.20
0」6
-0.01
0.21
0.07
0.23
0.08
0.48
coauthership
0.73
0.83
0.46
0.79
0.28
0.74
0」3
0.85
power
038
0.34
036
0.25
0.26
0.39
0.24
0.54
dolphins
0.48
-0.08
0」9
0.44
0.48
0.44
0.46
0.48
/?
=0.8
〃=1・0
karate
0.22
0.12
-0.16
0.33
0.23
0.30
0.13
0.38
coauthership
0.64
0.83
0.43
0.86
0.28
0.65
0.03
0.80
Power
0.20
0.37
0.28
0.35
0.11
0.24
0.06
0.45
11
第五章结论
本次研究在四个实际网络中模拟了流行病SIR传播过程,并计算了从各节点出发进行SIR演化的最终康复者(R)的比例,作为该节点的传播能力,分别计算了度、平均邻居度、聚类系数、接近中心性、介数中心性、k核、网页排名和特征向量中心性这八项可以衡量网络中节点重要性的指标。
通过计算节点的传播能力与各指标的斯皮尔曼等级相关系数,得到该指标在度量网络传播过程中的重要节点时的可靠程度。
对比发现,普遍惜况下,特征向量中心性与节点传播能力都呈高度相关,这与特征向量中心性的计算方法是密不可分的。
其次,度、接近中心性和k核这三种方法也能得到较好的结果,这分别体现了hub节点和节点间的路径长度在传播过程中所起的重要作用。
另外,聚类系数、介数和网页级别与节点传播能力的相关性不太显著。
在此之前,也有度量节点重要性的相关工作被发表,由于节点中心性方法的选择与网络结构和传播过程有着一定的关系,通过了解前人的工作,可以对各量度产生更加全面的认识。
例如,文献[17]主要论证了针对网络中的流行病传播过程,k核在节点重要性排序上起着很好的效果。
文献[18]乂用同样的方法进行了谣言传播的模拟,发现节点的传播能力并不依赖于它们的k核,而这篇文献中的结论也证实了,hub节点在信息传播过程中起着十分重要的作用。
文献[12]告诉我们,在非空间的网络中,度和k核在分析流行病传播时是更加适合的方法。
然而,对于谣言传播的情况,平均邻居度和接近中心性反而是更好的量度。
由于传播过程和网络结构的差异,在实际网络中衡量节点重要性时,还可以根据具体传播过程和研究内容,在这些基本的度量方法之上增加细节改进算法,从而获得更加可靠的结果。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 传播 过程 中的 节点 重要性 度量