英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
使用k-shell迭代因子在复杂网络中快速排列有影响力的节点
Zhixiao Wang , Ya Zhaoa , Jingke Xi a, Changjiang Dua
摘要：识别复杂网络的有影响力的节点对于优化网络结构或通过网络有效传播信息很重要。 k-shell方法是广泛使用的节点排序方法，其性能和效率具有固有的优势。 然而，在k-shell分解中产生的迭代信息在节点排名中被忽略。 本文提出了一种使用k-shell迭代因子评估节点影响能力的快速排名方法。 关于单调性，正确性和效率的实验结果表明，所提出的方法可以在人造和现实世界网络上产生优异的性能。 它更精确地区分节点的影响能力，并提供比以前的方法更合理的排名列表。
关键词：复杂网络，影响节点排名，k-shell分解，k-shell迭代因子
1绪论
许多网络机制，如级联，扩展和同步，会受到一些节点的高度影响。 节点影响力的识别是一个根本问题，其在复杂网络的许多领域都有实际应用。 例如，可以通过利用交通网络的重点来优化网络结构和流量。 另外，社会网络中有影响力的人们也可以加快信息传播，同时识别疾病网络中的关键节点可以帮助控制疫情传播。
最近提出了各种措施来对复杂网络中的有影响力的节点进行排名，有三种着名的指标：本地度量标准，全局指标和随机游标式指标。度中心性是典型的本地度量，而参考文献中也引入了其他类似的局部度量。本地度量标准简单但不太有效，因为它们忽视了全球网络结构。这种缺陷在大型网络中变得更加显着。典型的全球指标包括亲密中心性，中间性中心性和Katz中心性。全局度量在识别有影响的节点方面表现良好，但计算复杂度高。因此，现在的大型网络通常被认为是不可行的。基于随机漫游的度量，以特征向量中心性为例，PageRank，LeaderRank和HITS，通过多次迭代操作来评估节点的重要性。因此，与本地度量相比，它们的复杂性也相对较高。基于随机漫游的指标在有向网络和无向网络中表现出良好的性能。然而，Sen Pei等 通过跟踪广泛网络中的真实传播动态，搜索有影响力的吊具，发现了广泛使用的度中心性和PageRank在用户排名上是失败的。当前网络的规模不断增加。 例如，2013年6月，每月活跃的Facebook用户总数为11亿。大多数传统的措施是对有影响力的节点排名而言是耗时且不可行的。因此，需要在大规模网络中为这项具有挑战性任务的快速算法。
Kitsak等人为大规模网络提出了一种称为k-shell分解的快速节点排序方法。k-shell方法的计算复杂度为O（n），其中n表示网络的节点数。他们认为节点的影响应该由网络中节点的位置决定。 影响节点是位于网络核心的节点。通过使用k-shell分解方法分解网络，最有影响力的节点可以通过最大的k-shell值来识别。 Sen Pei和Hernan A. Makse通过大规模在线社区“LiveJournal”评估了几个广泛使用的中心，并声称k-shell测度在查找具有较大影响力的节点方面更有效。参考文献中也有类似的结论。然而，传统的k-shell方法分配了太多具有相同k-shell值的节点。 后来，研究人员提出了改进的方法来克服这个缺点。曾学者开发了一种称为MDD的基于K-shell的方法，以进一步区分具有相同k-shell值的节点的影响能力。与原始k-shell方法不同，MDD考虑了剩余度和疲劳度。然而，这种改进的方法需要通过考虑给定网络的统计特性来手动设置最优参数。Liu 等人。提出了另一种改进的方法，考虑到目标节点与k-shell值最高的节点之间的最短距离。 该方法计算网络节点之间的最短距离，导致O（n2）的计算复杂度考虑到目标节点的k-shell信息，Ren 等人。开发了一种新方法来确定具有最小k-shell值的节点的扩展能力。该方法仅对最小k-shell节点有效。侯等人 同时考虑三个指标（度，密度中心和k-shell）来评估节点影响能力; 然而，由于其计算复杂度，即O（n 3），该方法不能应用于大规模网络。Joonhyun等人 [22]提出了一种核心中心度量，以使用其邻居的k-shell值来估计网络中节点的扩散影响。所有现有的基于k-shell的方法都不会利用k-shell分解中产生的迭代信息。事实上，迭代信息对于节点影响能力评估是非常重要和有意义的。
最近，Flaviano Morone和Hernan A. Makse提出了另一个新颖的度量标准CI（集体影响）来识别有影响力的节点。他们认为有影响力的节点是保证全球网络连接的节点。Flaviano Morone和Hernan A. Makse使用了一种有效的方式来找到能够以非常快速的方式破坏网络的最佳结构影响因素。他们发现，最优的影响者要小得多。与CI不同，本文着重于所有网络节点的影响能力排名，而不是定位最小的结构影响因素集。
本文提出了一种新颖的节点排序测度，即k-shell迭代因子，以量化节点的影响能力。新方法利用k-shell分解的迭代信息来区分具有相同k-shell值的节点的影响能力。而且已经进行了详尽的实验来评估该方法的性能。首先将该方法与其他用于区分节点影响能力的知名措施进行比较。其次，通过比较排名结果与从可疑感染恢复（SIR）模拟获得的扩散影响，研究不同措施的正确性。第三，在计算复杂度和执行时间方面评估节点排序方法的效率。实验结果表明，该方法可以在影响节点排名方面取得优异的性能。它可以克服传统k-shell方法的缺点，并提供更准确的排名列表。
本文的其余部分组织如下：第2节描述了我们的动机和所提出的方法; 第3节报告了详尽的实验和结果; 第4节介绍了本文的结论。
2 算法
Kitsak等人 声称节点影响能力可以由其在网络中的位置来确定。 最有影响力的节点是位于网络核心的节点，可以通过k-shell分解方法来识别。
图1是参考文献中提出的示意性网络，我们的论文使用这个网络来说明k-shell分解过程。首先，将节点度参数设置为1，进行第一次迭代。 在该迭代中，所有1度节点被删除，即节点1,2,3,5,9,14和17。接下来，扫描网络，完成第二次迭代，以删除先前节点删除后生成的新的1度节点。对于这个例子，这些新的1度节点是节点4和节点16。在上述两次迭代之后，网络中没有等于1的节点，并且1度迭代的过程被终止。ks = 1被分配给这些被删除的节点。其次，将节点度参数相加到2，进行2度迭代。在第一次迭代中，所有2度节点都被删除，即节点6。在第二次迭代中，新生成的2度节点，即节点7,8和15也被删除。在这两次迭代之后，不再有等于2的任何节点，并且2度迭代完成。然后将ks = 2分配给这些已删除的节点。第三，节点度数增加到3，执行3度迭代。在第一次迭代中，删除所有3度节点，即节点10,11,12和13。在这个迭代之后，没有节点，ks = 3被分配给这四个被删除的节点。此时，整个k-shell分解处理完成。
图1 K-shell算法示意
表1显示了每个节点的迭代过程和分配的ks值。显然，k-shell方法倾向于分配具有相同ks值的许多节点，尽管相同值的扩展影响可能不同。例如，节点3和节点4的ks值为1，这意味着它们具有相同的影响能力。然而，Kitsak声称节点影响能力由其在网络中的位置决定。 节点3在1度过程的第一次迭代中被删除，而节点4在第二次迭代中被去除。因此，可以得出结论，节点4比节点3更靠近网络的核心节点，因此两个节点的影响能力应该不同。如果迭代信息用于识别网络中节点的位置差异，则可以进一步区分具有相同k-shell值的节点的影响能力。本研究中提出的方法是由这一想法激发的。
表1 ks值示意
基于k-shell值和分解过程中的迭代信息，将新的度量定义为k-shell迭代因子，以区分具有相同ks值的节点。
定义1.给定一个复杂的网络G，通过k-shell分解为每个节点分配一个ks值。假设节点niisin;G，ni的ks值为k。对于k度迭代的过程，总迭代次数为m，并且在k度过程的第n次迭代中除去ni，1le;nle;m。 delta;ni表示节点ni的k-shell迭代因子，其定义如下：
（1）
因此可以用公式获得每个节点的k-shell迭代因子。对于图3中的节点3 1，ks = 1，n = 1，m = 2（见表1）; 因此，delta;n3= 1·（1 1/2）= 1.5。 对于节点4，ks = 1，n = 2，m = 2，因此delta;n4= 1·（1 2/2）= 2。虽然节点3和节点4具有相同的ks值，即1，但是它们具有不同的k-shell迭代因子。该结果表明，k-shell迭代因子可以进一步区分具有相同ks值的节点的影响能力，克服传统k-shell方法的缺点。
参考文献的研究结果。已经表明，与位于网络核心的邻居连接更多的节点更有影响力。更多的连接意味着更大的程度; 因此，k-shell迭代因子随着节点的程度而扩展，并且开发了一种新的方法，同时考虑了程度和k-shell迭代因子来量化节点的影响能力。
定义2.给定一个复杂的网络G，节点niisin;G，假设ni的k-shell迭代因子是delta;ni。 ni的程度和邻居分别是dni，Ni。 ni的最终影响力定义如下：
（2）
其中，ICni表示ni的影响能力，nj表示ni的邻居，njisin;Ni; delta;nj和dnj分别表示k-shell迭代因子和nj的程度。
令人惊奇的是，度数是局部度量，而k-shell迭代因子是全局度量。新方法同时考虑了本地和全球的影响能力来更精确地区分节点。可以用线性时间复杂度O（n）有效地获得k-shell迭代因子; 度的复杂度为O（n）。因此，相信所提出的方法比其他耗时的节点排序方法更有效。
3 实验和结果
在本节中，提出的方法的有效性和效率通过一系列实验进行经验评估3.1 k-shell算法的不足。将方法（称为KS-IF）与其他六种众所周知的措施进行比较，从单调性，正确性和效率。这些措施包括k（度中心性），KS（参考文献[15]中的传统k-壳分解），MDD（参考文献[17]中的混合度分解），min-KS（参考文献[ 19]），KS-k（参考文献[18]中与最高ks值节点的最短距离），Cnc （参考文献[22]中的扩展邻域核心中心度量））。实验中有两种类型的复杂网络：人造网络和现实世界网络。人造网络由LFR基准生成器创建。LFR是一个网络生成器，可以用植入社区生成所需的网络。
3.1 单调性
理想情况下，每个节点在影响能力评估中应分配不同的值，因此，所有节点可以容易地彼此区分。换句话说，具有相同价值的节点越少，评估措施就越好。在本节中，参考文献[22]中描述的度量M。被用于评估不同排名措施的单调性。
（3）
在公式（3）中，R表示网络节点的排列向量，n表示向量R的秩数，nr表示具有相同秩r的节点数。如果所有节点处于同一等级，则向量R为无效等级，对应的M为0; 如果每个等级只有一个节点，则矢量R是一个完美的排名，而相应的M是1。
3.1.1在示意图网络上进行测试
首先，将上述七个等级度量应用于图1中的示意性网络。表2显示了由d，KS，MDD，min-KS，KS-k，Cnc 和KS-IF识别的节点等级。 在表2中，每列显示了与不同措施相对应的示意图网络的节点顺序。具有相同值的节点具有相同的等级，而“其他”的节点表示剩余的节点。 KS-IF方法将原理图网络节点的影响能力划分为14个等级，大多数队列只有一个节点。该结果表明，KS-IF方法在区分节点的影响能力方面非常有效。另一种竞争方法是Cnc ，它比所提出的方法效果较差。 以节点7和节点15为例。这些节点在拓扑结构和亲密度中心上彼此不同; 因此，他们应该有不同的影响力。 KS-IF方法可以正确地识别这种区别，而Cnc 方法不能。
表2 示意图网络的节点顺序由不同的措施
3.1.2对现实世界网络的测试
其次，在更广泛的十个现实世界网络中，包括空手道俱乐部网络（空手道）[28]，海豚社交网络（Dolphin）[29]，爵士音乐家网络[30]等，对不同措施的单调性能进行了检验。 ，科学家联合作家网络（NetScience）[31]，URV的电子邮件网络[32]，博客通信网络[33]，Pretty-Good-Privacy算法（PGP）[34]，Enron电子邮件网络（Enron）[35]，Facebook网络（Facebook）[13]和Twitter（Twitter）的社交网络。
表3 单调性能应用于十个现实世界网络
表3显示了不同排名方法的单调性能M，适用于上述十个现实世界网络。“网络”列表示实际网络的名称
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[25436]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
