【《基于影响力分配的重要边排序算法概述》7100字】

基于影响力分配的重要边排序算法概述目录TOC\o"1-2"\h\u30303基于影响力分配的重要边排序算法概述 1267421.1引言 183971.2算法设计与示例分析 2160331.3实验结果与分析 61.1引言在生产生活中，我们通常将复杂系统抽象地表示成网络，通过网络来模拟探索复杂系统中的信息。大多数复杂网络方向的研究都集中在对网络当中节点或者社团的研究，而对边的研究相对比较少。但随着技术的发展，尤其是计算机运算能力的提升，对边性质的探索逐渐成为了研究的热点。实际上，在某些情况下，边的研究更加本质的还原了复杂系统本身的运行情况。例如在研究鲁棒性问题上，使用网络模拟真实的交通网络时，很难移除某个节点，因为这意味着实际中移除了某个站点。但是事实上的交通堵塞造成了某条道路停止运行，在网络中应该被表现为这条道路所对应的边被移除了。因此对于重要边排序的研究逐渐兴起。而在复杂网络中，一些经典的重要边排序算法仅仅将网络中节点的度等价于节点的影响力，然后将网络中边两端节点的影响力简单结合，作为边的影响力。传统的算法中，认为与网络中影响力较大的节点相连的边同样有较大的影响力。但是，实际上由于现实中许多重要的节点本身存在很多条连边，对于这些连接着同样一个影响力很大的节点的连边来说，区分它们之间的重要程度成为了研究的难点。如图1.1所示，两个节点影响力最大的节点之间的连边对连通性的影响不一定大于其他连边。图1.1示例网络Fig.1.1Examplenetwork在图1.1中，网络中节点影响力最大的是节点4和节点5，其接近中心性值分别为0.667和0.56，但是移除4与5节点之间的连边对网络整体的连通性的影响却不如移除节点4和节点13之间的连边大，其中节点13的接近中心性值为0.5。一个节点的影响力不能等同于与这个节点相连的边的影响力，当一个节点的连边很多时，影响力相应的就会被稀释。解决上述问题的途径之一是考虑将节点的影响力尽可能的按照实际规律分配给关键的边。目前，大部分针对网络连通性问题的重要边排序算法都仅仅考虑了网络的局部信息。大部分算法，如度中心性算法，将边两端节点的影响力作为边的影响力，然后将边两端节点的影响力简单的加和或者作乘积，由此得到边的中心性值。这种算法的优点是简单，时间复杂度较低，但同时效果不尽人意。在局部信息的基础上有人提出了半局部的算法，该算法考虑了边两端节点的二阶邻居，性能得到了大大的提升。而在节点中的介数中心性算法基础上发展来的边介数中心性算法，虽然性能相对优秀，但是由于时间复杂度过高，不适用于大规模的网络。本章提出了一种较为简单却又非常有效的影响力分配算法，影响力是指网络中节点本身的影响力，通过将节点本身的影响力加权分配给与节点相连的不同的边，尽可能还原网络中节点影响力的真实分配情况。通过将影响力有区别地被分配给它的连边，构建高效的重要边排序算法。在9个真实网络，12个BA网络和12个ER网络中观察并对比其他不同的算法的实验效果。1.2算法设计与示例分析网络中节点的影响力实际上是通过边来传递到整个网络中的。通常我们认为，越重要的节点所连接的边相对应的影响力也就越大，如DP算法就是将边两端节点的度作乘积。但是，如果一个节点所连接的边的数量特别多，那么并非所有的边的影响力都和节点相匹配，有可能每条边的影响力反而特别小，节点的影响力相对应的会被这些边所分散，分配到每条边上的影响力反而下降。而且同样连接两个影响力相当的边，它们之间的重要性如何区别，如何去衡量节点影响力的分配成为了研究的重点。为了量化网络中节点的影响力，本章选用了节点重要性排序算法中的接近中心性算法来评价网络中节点的影响力。接近中心性算法是通过判断一个节点到网络中其他节点的距离的平均值来衡量该节点在网络连通性问题中的重要程度，通过计算节点到其他节点的平均距离，得到的平均距离的倒数作为该节点的中心性值。接近中心性算法考虑了网络的全局信息，可以更好的接近一个节点真实的重要性。对于网络来说，接近中心性最大的节点，对于网络中的信息流动性有最大的控制力。接近中心性的定义如式(1.1)所示。CC(1.1)其中N代表网络中节点的个数，dij代表从节点i到节点j的距离，根据公式可以看出，当节点i到网络中其他节点的平均距离越小，节点i的影响力也被认为越大，i的重要性也就越高。基于上述的背景，可以将节点的中心性值作为节点的影响力的评价标准，通过加权分配的方式，将节点的影响力分配给与节点相连的边，如式(1.2)所示。ID(1.2)其中，CC(i)代表了通过节点中心性算法中的接近中心性算法得到的节点i的中心性值。N(i)代表节点i的邻居集合。公式实际上是将网络中边两端的节点分配给该边的影响力相乘，而节点分配给边的影响力的比例是节点通过该边相连的另一端的节点的影响力在该的邻居影响力和中的比例。根据上述公式可知，节点的影响力越大，与节点相连的边的影响力也就越大。除此之外，节点相连的边的另一端节点的影响力越大，则该节点分配给这条边影响力的比重也就越大，一条边两端的节点分配给该边的影响力的乘积就是该边的中心性值。同时，如果一条边所连接的节点有很多邻居，则这个节点分配给该边的影响力就相应的被这些邻居所稀释，从而达到了一个节点影响力在与它相连的边中的有效分配。算法伪代码如下所示。算法1.1重要边排序ID算法输入网络G(n,m)输出ID(m)1开始2根据输入网络信息构建网络/*初始化*/3Fori=1tondo4计算每个节点i的CC(i)值，并统计5EndFor6Forj=1tomdo7counti1=0,counti2=0,a、b分别为边j两端的节点/*初始化*/8Foraiinneighbor(a)do/*计算a的每个邻居的CC(i)值*/9counti1=counti1+CC(ai)10EndFor11Forbiinneighbor(b)do12counti2=counti2+CC(bi)13EndFor14ID(j)=CC(a)*CC(a)*CC(b)*CC(b)/(counti1*counti2)15EndFor16统计每条边的中心性值17结束下面通过设计一个包含11个节点和13条边的网络，用来演示影响力分配算法的具体计算过程。演示网络如图1.2所示。图1.2ID算法示例图Fig.1.2ExamplediagramofIDalgorithm首先，先通过计算演示网络中各个节点的接近中心性值，计算结果如表1.1所示。表1.1示例网络中各节点的接近中心性值Table1.1Closenesscentralityvaluesofeachnodeinthesamplenetwork节点编号接近中心性值A0.4347826B0.4347826C0.7142857D0.4545455E0.6666667F0.4166667G0.4166667H0.5263158表1.1（续表）示例网络中各节点的接近中心性值ContinuedTable1.1Closenesscentralityvaluesofeachnodeinthesamplenetwork节点编号接近中心性值I0.625J0.4K0.4以边2为例，边2得到了来自节点A和节点C分配的影响力，其中节点A只有节点C一个邻居，只与边2相连，因此节点A的全部影响力都分配给了边2，而节点C虽然是影响力最大的节点，但是与此同时与C相连的边也多，导致C的影响力被分配给了不同的边。边2所接收到的影响力被稀释，其中与C相连的边1，2，3，4，5，6中，边另一端节点的影响力分别为节点B，A，D，I，H，E的接近中心性值。因此节点C分配到边2上的影响力计算如下：influenceC→2边2的ID值为边两端节点分配给边的影响力值的乘积，由此可得边2的ID值ID(AC)=0.042973154954531474。相对应的我们可以得到其他边的ID值，计算结果如表1.2所示。表1.2示例网络中各边的ID值Table1.2TheIDvalueofeachedgeinthesamplenetwork边编号ID值BC10.021487AC20.042973CD30.022034CI40.018359CH50.013182CE60.01917EF70.025525DH80.009113EI90.017555EH100.019929EG110.034389IK120.035639IJ130.022926将表1.2中ID值从大到小进行排序，则演示网络中各边的重要性序列为：2，12，11，7，13，3，1，10，6，4，9，5，8。影响力分配的算法可以快速识别一些边缘模块和连通子图之间的连边，通过将这些连边优先去除达到尽快破坏网络整体连通结构的效果，相对于传统的算法，影响力分配的算法在考虑了边本身的信息以及路径的信息，可以更加全面的反应边的重要性。1.3实验结果与分析本节实验环境如下：CPU：Intel(R)Core(TM)i7-8700CPU@1.20GHz，1.19GHz。内存：8GBDDR4。操作系统：64位Windows10。1.1.1真实网络实验首先，本节通过9个真实网络来评估影响力分配算法的性能，真实网络信息如表1.3所示。表1.3真实网络拓扑信息Table1.3Realnetworktopologicalinformation网络名网络节点数网络边数Dolphin62159Jazz1982742Email11335451as-733647412572polblogs122216714PG629920776Sex1581038540CA-Condmat2313393439Facebook26954497878表1.3中数据为实验采用的真实网络的网络信息，包括网络节点数和网络边数，本文认为，在考虑网络连通性问题时，网络中的孤立节点对研究并没有影响，因此本文使用的网络数据已经过滤了网络中的孤立节点，网络为无向无权网络，网络情况如下所示：(1)社交网络。本文选用了四个真实的社交网络，包括Dolphin[39]，polblogs[40]，Sex[41]和Facebook[42]网络。其中Dolphin网络是一个62只海豚之间的社交网络；Polblogs是政治博客圈的社交网络；Sex有两种节点构成，分别是女性节点和男性节点，当两种节点在实际中接触时，节点之间相互连接；Facebook也是一种经典的社交网络。(2)通信网络。本文选用了三个真实的通信网络，包括Email[43]，As-733[44]和PG[45]网络。其中Email网络是RoviraIvirgili大学成员之间电子邮件交流的通信网络；As-733是因特网中路由器之间交换流量的通信网络；PG是Gnutella文件共享的通信网络。(3)合作网络。本文选用了两个真实的合作网络，包括Jazz[46]和CA-Condmat[45]网络。其中Jazz是一个由198个Jazz音乐家组成的合作网络，CA-Condmat是一个由提交凝聚物质方向的作者的合作网络，当论文之间存在合作，作者之间就建立了连边。为了验证ID算法的有效性，本节在上述9个真实网络中对比了ID算法和4个传统的重要边排序算法的性能，包括DP，DI，TO和EB。其中EB算法考虑了网络的全局信息，而DP，DI和TO算法考虑了网络局部和半局部的信息。ID算法在节点重要性排序阶段考虑了全局的信息，同时在影响力分配时也考虑了边的局部信息，因此效率更高。在实验过程中，首先通过边重要性排序算法分别计算得到每条边的边中心性值，通过将中心性值从大到小排序，得到了每种算法对应的边的中心性序列，然后按照中心性序列依次移除网络中的边，每次移除边后都计算网络当前最大连通子图的规模，得到了关于网络的鲁棒性指标的R值，其结果如表1.4所示。表1.4ID算法与经典算法在真实网络中的对比实验Table1.4ComparativeexperimentofIDalgorithmandclassicalalgorithmsinrealnetworks网络EBDPDITOIDDolphin0.5110.67450.61650.47090.4502Jazz0.6660.91360.80510.63980.6182Email0.62530.8090.76220.55330.4734as-7330.52620.5640.56750.44920.4993polblogs0.59560.93620.85370.48090.4575PG0.57640.73480.73770.60020.4432Sex0.52080.64160.63950.59250.3885CA-Condmat0.43950.62780.53130.41250.4546Facebook0.69790.92840.88240.7280.5259通过表1.4中的数据可以看出，在参与实验的五种算法中，ID算法的表现最为优秀，在实验采用的9个真实网络中，ID算法在Dolphin，Jazz，Email，polblogs，PG，Sex，Facebook这七个真实网络中的表现性能最好。在as-733网络中ID算法的性能仅次于TO算法，在CA-Condmat网络中，ID算法逊色于TO算法和EB算法。TO算法的表现总体上仅次于ID算法，在4个真实网络中表现第二，两个真实网络as-733和CA-Condmat中TO算法表现最优。EB算法的性能相对也比较优秀，在四个网络中表现第二。总体来说，在上述实验的9个网络中，DP算法的表现则是最差的，仅仅在as-733网络和PG网络中略微优秀于DI算法。由此可见，针对不同的网络，可以通过选择不同的算法达到最优的效果。总体上，ID和TO算法的性能都比较优秀，EB算法由于考虑了网络的全局信息，性能比仅考虑了网络局部信息的DI和DP算法更优秀。相对于考虑了半局部信息的TO算法，ID算法综合考虑了网络的全局信息和局部信息，通过结合节点和边的关系，更能反映出网络边的重要性程度，在真实网络中性能相对更优秀。R值作为网络鲁棒性计算的常用指标，通过上述实验得到的数据，可以反映出ID算法对于真实网络连通性的破坏的高效。同时，通过观察网络最大连通子图相对原始网络最大连通子图比例的动态变化，可以更好的展示算法对上述实验网络的破坏过程，其结果如图1.3所示。图1.3真实网络中ID算法与经典算法在移除边时对网络连通性的破坏变化Fig.1.3ThedamageofIDalgorithmandclassicalalgorithmstonetworkconnectivitywhenremovingedgesinrealnetworks由图1.3中实验数据可以看出，ID算法在寻找网络中的关键边方面性能较为优秀。在选用的9个真实网络中，ID算法都在实验的前期，优先删除网络中较为重要的边时，使得网络的连通性受到了最大的破坏。即使在ID算法表现不是最优的as-733网络和CA-Condmat网络中，ID算法在删除前20%和前50%的边时，对网络造成的破坏都强于其他四种算法。同时，在Facebook网络中，ID算法全程最优，更加真实地还原了网络真实的边中心性序列。剩余网络中，在删除了一半以上的边后，ID算法对网络的破坏性依旧优于其他算法，这说明相较于其他四种算法，ID算法可以优先识别网络中的重要的连边。动态网络实验证明了ID算法的有效性。上述实验验证了ID算法在真实网络中的有效性，相较于实验中的其他四种算法，考虑了网络中更多信息的ID算法可以以更高的效率破坏真实网络的连通性。1.1.2生成网络实验为了进一步验证ID算法的有效性，本节在上述实验的基础上，拓展了生成网络实验，通过与之前实验中的四种重要边排序算法作对比，验证了ID算法在生成网络中的有效性。本节选取了不同规模的BA网络和ER网络作为实验网络，通过设计不同的网络参数，生成了不同梯度的网络，包括不同节点规模的网络和不同平均度的网络。所选用的网络节点数量分为500，5000，50000三种网络规模层次，对于每个规模的网络，分别生成平均度为3，6，9，12四种平均度的网络。生成的BA网络的信息如表1.5所示。表1.5BA网络拓扑信息Table1.5BAnetworktopologicalinformation网络名网络节点数网络边数BA_500_35001491BA_500_65002964BA_500_95004419BA_500_125005856BA_5000_3500014991BA_5000_6500029964BA_5000_9500044919BA_5000_12500059856BA_50000_350000149991BA_50000_650000299964BA_50000_950000449919BA_50000_1250000599856为了验证ID算法的有效性，本节在以上12个不同规模和平均度的BA网络上进行实验，通过选用四种不同经典重要边排序算法和ID算法进行对比。计算网络的边中心性序列，然后将序列依照从大到小的顺序，将不同算法得到的边中心性序列对应的边从网络中移除，并计算网络中最大连通子图的规模，得到关于网络鲁棒性的指标R值。实验结果如表1.6所示。表1.6ID算法与经典算法在BA网络中的对比实验Table1.6ComparativeexperimentofIDalgorithmandclassicalalgorithmsinBAnetworks网络EBDPDITOIDBA_500_30.73250.72510.72620.71030.6426BA_500_60.86510.8440.83060.77710.6907BA_500_90.8860.86610.85510.81610.7288BA_500_120.90660.87280.86340.83840.7648BA_5000_30.73460.72570.72270.73520.6494BA_5000_60.86360.84450.83410.79820.7284BA_5000_90.89620.87020.85750.82980.7614BA_5000_120.90690.87880.86530.86930.779BA_50000_30.73580.7230.72220.73790.6543BA_50000_60.85780.84450.83330.82140.7283BA_50000_90.89580.87150.85760.84840.7763BA_50000_120.91540.88040.86550.8660.8139根据表1.6中的实验数据，可以看出，在BA网络中，ID算法的性能还是最优秀的。在参与实验的12个不同节点规模和不同平均度的BA网络中，ID算法的结果都优于其他四种重要边排序算法。同时也可以看出，TO算法仅次于ID算法，在12个网络的8个网络中，TO算法比EB，DP和DI算法性能更好，出乎意料的是，考虑了网络局部信息的DI算法在BA网络中的性能优于考虑了全局信息的EB算法，在4个网络中，DI算法的性能都仅次于ID算法。对于BA网络来说，网络存在度分布极端不均匀的特点，绝大多数节点的度非常小，并和少数度非常大的节点紧密相连，实际上，在基于移除节点的鲁棒性研究上，Barabasi[47]发现，无标度网络对随机移除节点的攻击拥有极强的鲁棒性，但对于蓄意攻击度高的节点时，无标度网络会在极短的时间内崩溃。因此综合利用节点本身度的信息和节点之间关系的DI算法的效果相对优秀。总的来说，实验结果证明了ID算法在BA网络中的有效性。上述实验得到了关于网络鲁棒性的指标R值，实验结果表明了在BA网络中ID算法的有效性，本节通过观察网络中最大连通子图的动态变化，来进一步验证ID算法在BA网络中的有效性。实验结果如图1.4所示。图1.4BA网络中ID算法与经典算法在移除边时对网络连通性的破坏变化Fig.1.4thedamageofIDalgorithmandclassicalalgorithmstonetworkconnectivitywhenremovingedgesinBAnetworks由图1.4中实验数据可知，与之前实验中得出的结论相符，在BA网络中，ID算法与其他四种算法相比都是最优的。在网络的动态实验中，ID算法在网络的规模为500，5000，50000；平均度为6，9，12的9个网络中可以保持全程最优，在五种算法中最大限度的还原了网络真实的边中心性序列。在平均度为3的网络中，ID算法在移除网络前70%时，可以保持在五种算法中对网络连通性的最大破坏。网络的动态实验结果与之前计算网络鲁棒性实验的结果相符，验证了ID算法在BA网络中的有效性。在上文中，本节已经验证了ID算法在BA网络中的有效性，同时，本节设计了网络规模为500，5000，50000三种规模，网络平均度分别为3，6，9，12的12个ER网络，进一步验证，ID算法在ER网络中的有效性。ER网络信息如表1.7所示。表1.7ER网络拓扑信息Table1.7ERnetworktopologicalinformation网络名网络节点数网络边数ER_500_35001491ER_500_65003021ER_500_95004390ER_500_125005962ER_5000_3500014895ER_5000_6500029816ER_5000_9500044512ER_5000_12500059889ER_50000_350000150065ER_50000_650000299365ER_50000_950000449571ER_50000_1250000599251为了验证ID算法的有效性，计算在不同平均度的ER网络中每种算法所对应的R值，最终结果如表1.8所示。表1.8ID算法与经典算法在ER网络中的对比实验Table1.8ComparativeexperimentofIDalgorithmandclassicalalgorithmsinERnetworks网络EBDPDITOIDER_500_30.72160.73760.7410.65430.6555ER_500_60.84550.8420.85580.77420.7848ER_500_90.89630.87210.88320.89570.8246ER_500_120.9220.89180.90420.92560.8635ER_5000_30.73260.73260.7340.64150.6619ER_5000_60.82340.83860.85690.68240.7645ER_5000_90.84870.86250.88420.7