英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
识别复杂网络中的重要节点
识别出在复杂网络中传播速度更快、传播范围更广的有影响的节点具有重要的理论和现实意义。度中心性算法非常简单，但相关性不大。而全局度量方法，如中间中心性和接近中心性，可以更好地识别有影响的节点，但由于计算的复杂性，无法应用于大规模网络中。为了设计一种有效的排序方法，我们提出了一种半局部中心性方法，作为低关联的度中心性性度量与其他耗时度量之间的权衡。我们用采用SIR模型，利用传播速率和受感染节点数来评价系统的性能。在四个实际网络上的仿真结果表明，该方法能够很好地识别有影响的节点。
1. 介绍
对网络结构、功能及其相互关系的理解近年来引起了人们的广泛关注[1-5]。众所周知，很少一部分的重要节点对许多机制如级联、扩散和同步等产生了巨大的影响。如何发现这些有影响的节点具有重要的理论意义。此外，识别有影响的节点也具有显著的实用 性：这有助于控制谣言和疾病传播以及创造新的营销模式。
度中心性是一种简单而有效的度量，但是由于一个具有几个高影响力邻居的节点的节点可能比一个具有较多的没有影响力的节点具有更高的影响力。虽然一些著名的全局度量指标，如中间中心度和接近中心度，由于计算复杂度很高，可以提供更好的结果。但是他们不是很容易应对非常大规模的在线社交网络。最近，Luuml;et al.[12]提出了一种基于随机游走的算法LeaderRank来识别社交网络中的领导者，这个算法比著名的的PageRank[13]算法在进行舆论传播和防止垃圾邮件发送者的攻击时确定最有影响力的节点方面要做得好。LeaderRank[12]和PageRank[13]在有向网络中都有良好的的性能，但在无向网络中效果不佳(它将不如无向网络的度中心性)。总之，设计一种有效的排序方法来识别有影响力的节点仍然是一个悬而未决的问题。
lowast;作者
邮箱地址: linyuan.lue@unifr.ch (L. Luuml;).
12
11
13
3
4
14
2
5
10
23
15
22
1
9
6
21
20
18
16
8
7
19
17
图1 一个由23个节点和40个边组成的示例网络。虽然节点23的度低于节点1，但其影响可能更大
本文提出了一种半局部中心度测度，作为低关联度中心度与其他耗时测度的折衷。为了评估算法性能，我们使用敏感-感染-恢复(SIR)模型[14]，用不同的中心排序算法来评估节点的传播影响。在四个实际网络上的仿真结果表明，我们的方法可以识别出网络中的重要节点。与度中心法、近中心度法和中间度法相比，我们的方法几乎与接近中心度法一样有效，而计算复杂度较低，比度和中间中心性方法要好得多。此外，我们还基于排名靠前的节点的影响考察了这些中心测度之间的关系。
以下部分组织如下：我们介绍了我们的新中心度度量，并简要在第二节中总结了其他中心度量的定义作为比较.在第三节中，我们使用SIR模型来评估一个例子网络的性能。数据描述见4.1节，中心性度量的有效性及其相关关系分别在第4.2节和第4.3节中讨论。结论见第5节。
2.节点影响的中心性措施
人们提出了许多中心性措施来对网络中的节点进行排序。一个简单的例子是度中心性，即一个度较大的节点可能比度小的节点具有更大的影响(例如，作为一个初始感染节点，其传播速度和广度会更快）。然而，在某些情况下，这种方法不能识别出有影响的节点，因为它只考虑了很有限的信息。例如，如图1所示，虽然节点1在所有23个节点中的度最大，但如果传染病起源于节点1，则可能不会是传播地速度最快或范围最广的，引文节点1的所有邻居都有很低的度。相反，尽管节点23与节点1相比具有较低度，但它可能具有更高的影响力。
另一组考虑全局信息的排序方法给出了更好的排序结果，例如两种显著的基于路径的排序算法，介数中心性和接近中心。介数是网络中节点的中心性度量，通常定义为穿过感兴趣节点的节点对之间的最短路径数目的比例。在某种意义上，在某种意义上，介数一种衡量节点对通过网络传播的信息或传送网络中节点的预期负载的影响的度量[15，16]。网络G=(V，E)具有n=V个节点和m=E条边，节点v之间的中心度以CB(V)表示为[17，18]：
(1)
其中sigma;st是节点s和t之间的最短路径数，sigma;st(V)表示节点之间最短路径的数目。
节点v的接近性定义为与V[19]节点距离所有其他节点的距离之和的倒数：
(2)
其中dG（V，T）是V和T之间的路径距离，可以被看作是它将从给定节点向其他可达节点传播信息的时间的度量。Dangalchev[20]将这一定义修改为一种一般形式，称为残余密切度，这比众所周知的脆弱性衡量标准[21]更为敏感，因为它能够反映删除节点的影响，即使此删除不会导致部分连接的断开。残余接近度是[20]：
(3)
与度中心性比较，介数与接近中心性测度可以更好地量化节点的影响，但它们具有较高的计算复杂度（基于PageRank或者LeaderRank的中心性更相关但更耗时[12，13，22，23]）。用Floyd算法[24]计算网络中所有节点对间最短路径的复杂度为O(N3)。对于稀疏图，使用约翰逊算法[25]将更有效，它的复杂度为O(n2 log n nm)。对于未加权网络，用Brandes算法[26]计算中间中心性时，复杂度是O(nm) = O(n2(k)) ，其中(K)是网络的平均度。由于在线社交网络通常包含数以百万计的节点或更多的节点，因此在进行度和接近中心性的计算时非常耗时甚至是不可行的。
表1
在图1所示的示例网络上对有效性的模拟。最初，只选择一个节点被感染。K(V)是每个初始节点的节点v的度，F(TC)是由100多个部分平均得出的。
|
v |
K(v) |
Nv |
Qv |
CL(v) |
CC (v) |
CB(v) |
F(tc ) |
|
1 |
8 |
9 |
67 |
145 |
0.1368 |
242.00 |
7.34 |
|
2 |
2 |
8 |
17 |
92 |
0.0749 |
0.00 |
8.45 |
|
3 |
3 |
8 |
25 |
101 |
0.0772 |
1.00 |
7.93 |
|
4 |
2 |
8 |
17 |
92 |
0.0749 |
0.00 |
7.74 |
|
5 |
1 |
8 |
9 |
67 |
0.0727 |
0.00 |
8.24 |
|
6 |
2 |
11 |
18 |
104 |
0.1690 |
224.00 |
12.62 |
|
7 |
2 |
8 |
17 |
92 |
0.0749 |
0.00 |
8.65 |
|
8 |
3 |
8 |
25 |
101 |
0.0772 |
1.00 |
8.73 |
|
9 |
2 |
8 |
17 |
92 |
0.0749 |
0.00 |
7.95 |
|
10 |
3 |
9 |
37 |
111 |
0.1964 |
234.00 |
12.48 |
|
11 |
4 |
12 |
41 |
166 |
0.1795 |
89.73 |
12.71 |
|
12 |
4 |
9 |
38 |
157 |
0.1288 |
26.00 |
11.45 |
|
13 |
4 |
8 |
39 |
157 |
0.0953 |
5.67 |
12.01 |
|
14 |
4 |
9 |
40 |
166 |
0.1288 |
23.33 |
12.05 |
|
15 |
4 |
9 |
37 |
156 |
0.0982<!-- 全文共17722字，剩余内容已隐藏，支付完成后下载完整资料 资料编号：[12138]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
