【《基于节点相似性的重要边排序研究》9900字】

基于节点相似性的重要边排序研究目录TOC\o"1-3"\h\u21406基于节点相似性的重要边排序研究 1122631.1引言 1238131.2算法设计与示例分析 35561.3实验结果与分析 6301761.3.1真实网络实验 6305221.3.2生成网络实验 1030681.4节点相似性策略的应用效果分析 161.1引言由于真实网络存在异质性，有时仅仅移除网络中的一小部分节点就可以对整个网络的连通性造成巨大的破坏，许多重要节点排序算法都可以在短时间内快速破坏整个网络的连通性。但是实验证明，大多数重要边排序算法在移除了网络中大量的边后，网络的连通性依旧可以保持整体稳定的状态，最大连通子图的规模并没有大幅度降低。事实上，网络中边的移除和节点的移除对网络的破坏效果相差较大，是因为在移除一个节点的同时，也将这个节点所连接的一组边一同移除，对网络连通性造成的破坏远远大于移除单一的一条边。这种现象对重要边排序算法的研究本身造成了一定的影响，如何寻找到一个重要节点所连接的许多条边中影响力较大的边，并区分影响力相似的邻居节点与当前节点之间的边的影响力，成为了重要边排序研究中的热点。真实网络中由于一个节点本身存在大量的连边，破坏其中一条连边对节点在网络中连通性中发挥的影响不大，节点本身可以通过其他路径与网络中的其他节点保持联系，从而维持整体网络的连通性。由于网络中边与边之间，边与路径之间相互形成备份，当网络中一条边被删除时，网络中其他的一些边或者是边组成的路径对被删除的这条边原本的连通作用起到了替代的作用。事实上，节点本身影响力越大，通过节点的路径也就越多，它所连接的边的可替代性在某种程度上也就越强。因此，有些边虽然连接着两个在连通性问题上非常重要的节点，但是由于边本身起到的连通作用会被网络中其他的路径所分担，如果不将节点完全移除，仅仅移除边本身对网络的连通性破坏并不大。因此，如何识别边本身的不可替代性，寻找出其连通性作用被其他边与路径替代较小的边，成为了研究的难点。网络中节点的信息相对边更加全面，本文通过考虑分析网络中边两端节点的相似程度，来判断该条边的重要程度。分析节点之间相似性的方法有很多，最简单的方法就是直接利用节点本身的信息，两个节点在网络中的基本信息越相似，节点之间的相似性也就越高。随着网络科学的发展，能从网络中挖掘出来的网络信息也越来越丰富，越来越接近真实的网络信息，节点之间的相似性的应用也就越来越广泛。其中一个经典的应用场景就是用于网络中的链路预测。通过网络中已知的信息来评价网络中两个不相连的节点之间的相似性，进一步用于评估这两个节点之间存在连边的可能性。这种预测分为两种，一种是网络中两个节点之间未知连边的预测，即两个节点之间可能存在过连边，但这种存在不可探知；另一种是网络中两个节点之间并未存在连边，用于判断之后可能生成连边的可能性。除此之外，节点相似性在计算机领域有许多其他研究应用。节点相似性指标的评价可以分为以下三种。(1)基于网络局部信息的节点相似性。对于网络的局部信息来说，网络科学中经典的三元闭包原则认为，如果两个人拥有一个共同的朋友，那么他们俩彼此也很有可能成为朋友，从而三个人的关系构成一个闭合的三角形。根据三元闭包原则，基于局部信息的节点相似性算法认为，两个节点之间存在的共同邻居越多，这两个节点的相似性就越高。实际观察可以得知，一些度非常大的节点，它们很容易就和其他节点拥有非常多的共同邻居，简单的评估两个节点之间的共同邻居数量，不能真实的反应节点之间的相似性。因此，考虑共同邻居数在总邻居数量中所占的比例的节点相似性成为了更好的评价算法。(2)基于网络全局信息的节点相似性[48]。基于全局信息的节点相似性，主要考虑了网络中的路径信息，通过路径的延伸，考虑更大范围内节点信息的相似性，从而评价节点之间的相似性。基于全局信息的节点相似性主要指标为局部路径指标、Katz指标和LHN-II指标。(3)基于随机游走的节点相似性[49]。基于随机游走的节点相似性主要考虑通过随机游走来判断两个节点之间的联系，评价指标为平均通勤时间、基于随机游走的余弦相似性、重启的随机游走、SimRank指标、局部随机游走指标和叠加的局部随机游走指标。对于一个网络中的边的重要性排序问题而言，本文希望寻找到在网络连通性问题上影响力大的边，这种影响力一方面来源于边本身连接的节点的影响力，在第3章中本文通过了影响力分配的算法将边两端节点的影响力尽可能真实地分配给边。而在本章中，本文希望探究边在网络中的稀有性，即边所承担的功能在网络中的不可替代性。如果一条边所得到的来自节点的影响力非常大，但是与它在网络中一同承担功能的边同样非常多，那么这条边在网络连通性问题上的重要性就会被这些相同功能的边降低。因此考虑边的不可替代性，可以有效区分中心性值接近的边的重要程度。而网络中边的数量远远超过节点的数量，如果直接判断一条边与网络中其他边之间的相似程度，付出的计算代价过大，而考虑节点的信息，需要的计算资源相对有限。因此本文通过使用边两端节点的相似性来评估该条边的可替代性。本章提出了一种比较简单同时有效的重要边排序算法，即为结合了节点相似性策略的重要边排序算法。在第3章提出的影响力分配的基础上增加了节点相似性策略，通过添加边两端节点的不相似性值，得到新的边中心性值，将边按中心性值的大小排序，得到新的边重要性序列。实验证明，这种策略是有效的，可以提高ID算法的有效性，而且在其他的重要边排序算法中，这种策略也能提高算法的效率。1.2算法设计与示例分析复杂网络中，边的数量是远远大于节点的数量的，所以，如果去计算边与边之间的不相似性，计算的代价是实际应用中无法接受的，而实际上，通过实验的结果可以观察到，对于一条边两端的节点来说，两个节点之间的共同邻居越多，这条边相对应的备份路径也就越多，即使这条边被移除了，两个节点之间也可以通过它们之间的共同邻居来实现连通。如图1.1所示。图1.1节点i与节点j之间多路径相连Fig.1.1Multipathconnectionbetweennodeiandnodej图中节点i与节点j之间的边被移除后，两个节点之间依旧存在两条路径相连，实际上，共同邻居在两个节点之间起到了替代直接连边的作用。因此，对于一条边来说，边两端节点的共同邻居占总邻居数的比重越高，被认为这两个节点越相似，它们在网络中承担的结构功能也就越接近，同时它们之间的潜在其他路径也就过多，这样的边即使被移除，它两端节点之间的联系并不会轻易断开，它的备份路径也就越多。对于两个功能类似的节点，它们之间的连边的可替代性也较强。(1)节点相似性策略本章为了探究节点之间相似性对连接这两个节点的边的重要性的影响，考虑到算法的时间复杂度，选用了基于网络局部信息的节点相似性算法。通过计算节点之间的相似性，来判断网络中边两端节点之间的不相似程度，并通过节点之间的不相似程度来评价该边的不可替代程度。相比与计算边与边之间的相似性，用这种算法计算边的代价仅为O(m)。通过将得到的相似性与边本身的中心性指标结合，就可以得到更加高效的边中心性算法。不相似性值如式(1.1)所示（不相似性值=1-节点相似值）。DISIM(1.1)其中Ni是节点i的邻居节点，Ni∩Nj指代节点i和节点j的共同邻居节点。当一条边的两个节点所连接的其他节点完全一致时，两个节点的不相似性值为0。(2)基于节点相似性策略的重要边排序算法本章基于第3章使用的影响力分配算法，通过先计算节点的中心性值，作为该节点的影响力值。然后将边两端的节点的影响力加权分配给与节点相连的边。同时，将边两端节点的相似性与影响力分配算法得到的中心性值结合，得到新的边中心性值。算法的效率得到了明显的提升。同时，这种结合边两端节点相似性的策略在其他算法的应用中也有明显提升。根据式(1.1)可知，两个节点之间的共同邻居越多，节点之间的联系越紧密，那么连接两个节点之间的边的其他备用路径就越多，边的可替代性也就越高，边在网络连通性问题上的重要性相对应的就要降低。因此，基于节点相似性的边中心性算法的计算如式(1.2)所示。DID(1.2)其中CC(i)是第三节中的ID算法计算得到的边中心性值，DID(i,j)值是ID(i,j)和边(i,j)两端节点i和j节点不相似性值的乘积。本节通过一个包含10个节点和18条边的风筝网络[50]，来演示节点相似性策略在ID算法上应用的计算过程。风筝网络如图1.2所示。图1.2风筝网络Fig.1.2Kitenetwork首先，先计算风筝网络中每个节点的接近中心性值，计算结果如表1.1所示。表1.1风筝网络中各节点的中心性值Table1.1Centralityvaluesofeachnodeinkitenetwork节点接近中心性值A0.5294118B0.5294118表1.1（续表）风筝网络中各节点的中心性值ContinuedTable1.1Centralityvaluesofeachnodeinkitenetwork节点接近中心性值C0.5D0.6E0.5F0.6428571G0.6428571H0.6I0.4285714J0.3103448以边1为例，首先计算边1的ID值，边1两端的节点A和B对应的影响力都是0.5294117647058824。而节点A的邻居包括了节点B，C，D，和F。其中节点F对应的影响力最大，因此节点A影响力分配给边3的影响力也最大。边1得到的来自节点A的影响力为:Influence同理，由于网络是对称的，边1得到的来自节点B的影响力同样也为0.123。由此可以得到边1的ID值为0.0152。得到边1的ID值后，开始计算边1两端节点AB的相似性，作为边1的可替代性。节点A与节点B，C，D，F相连，节点B与节点A，D，E，G相连。节点对AB之间的共同邻居为节点D，邻居的交集个数为1，相似性为0.5，因此可以得到边1的中心性值为ID值乘以不可替代性值。即为0.0076。相对应的，本节给出了风筝网络中其他边的边中心性值。结果如表1.2所示。表1.2风筝网络中各条边的DID值Table1.2DIDvaluesofeachedgeinkitenetwork边边中心性值AB10.007607AC20.001166AF30.003282AD40.001076BD50.000986BG60.002363BE70.00103表1.2（续表）风筝网络中各条边的DID值ContinuedTable1.2DIDvaluesofeachedgeinkitenetwork边边中心性值CD80.002224DE90.00294CF100.001585DF110.002088DG120.00273EG130.002287FG140.003826FH150.007306GH160.009036HI170.012536IJ180.00664将表中的DID值从大到小排序，可以得到风筝网络的边中心性序列，结果为17，16，1，15，18，14，3，9，12，6，13，8，11，10，2，4，7，5。根据风筝网络的结构，可以观察到，边17是连通左右两个模块的必经之路，在网络中起到了桥梁的作用。边18的作用类似，但是明显重要性不如边17重要。同时，边4，5等，虽然连接了网络中较为重要的节点，但是由于节点本身连接多条边，节点之间的沟通路径多样，导致边4，5的重要性下降。边14作为连接网络中影响力最大的两个节点F和G，因为节点对本身的共同邻居比较多，同样使得边14的重要性下降。考虑了边两端节点相似性的DID算法，可以更好的反应网络中真实的边中心性序列。1.3实验结果与分析本章实验所使用的实验环境与本文第3章实验使用环境相同，所使用的网络与本文第3章实验使用网络相同。1.3.1真实网络实验本节选用了与第3章相同的9个真实网络，用于验证基于节点相似性的影响力分配算法(DID)的效率。本节通过对比DID算法和第3章相同的四种对比算法在9个真实网络中的性能，验证了DID算法的有效性。同时，本节还将在9个真实网络中将DID算法和ID算法作对比，验证了节点相似性策略的有效性。在实验过程中，本节依旧采用了第3章使用的关于网络连通性的指标，通过DID算法，得到边中心性序列，然后按照得到的边中心性序列从大到小依次删除网络中的边，并计算网络中最大连通子图的规模，最后计算得到关于网络鲁棒性的R值，作为本节实验的评价标准，实验结果如表1.3所示。表1.3DID算法与经典算法在真实网络中的对比实验Table1.3ComparativeexperimentofDIDalgorithmandclassicalalgorithmsinrealnetworks网络EBDPDITODIDDolphin0.5110.67450.61650.47090.4407Jazz0.6660.91360.80510.63980.6024Email0.62530.8090.76220.55330.4721as-7330.52620.5640.56750.44920.4934polblogs0.59560.93620.85370.48090.4379PG0.57640.73480.73770.60020.4504Sex0.52080.64160.63950.59250.3895CA-Condmat0.43950.92350.53130.41250.4143Facebook0.69790.92840.88240.7280.5156由表1.3中的数据可以看出，和四个经典算法相比，DID算法的性能相对更加优秀，在9个真实网络中，DID算法在Dolphin，Jazz，Email，polblogs，PG，Sex，Facebook七个网络中都是效果最好的，由于DID算法是基于ID算法的，在as-733和CA-Condmat网络中，DID算法的效果不如TO算法，但也和其他三个算法比，性能优势明显。TO算法在9个真实网络中的as-733和CA-Condmat网络中优于DID算法，在其他网络中仅次于DID算法。上述实验结果验证了DID算法的有效性。上述实验证明了DID算法的有效性。同时，本节也设计了动态网络的分析，来进一步观察DID算法的性能，所采用的指标和第3章相同，通过分析按照一定比例移除网络中的边后，观察网络中最大连通子图的变化，通过统计移除边后网络中最大连通子图和网络原始最大连通子图的规模的比例，来验证DID算法的有效性。网络的动态变化如图1.3所示。从图1.3中的网络的动态数据可以看出，在Facebook网络中，DID算法同样全程最优，对网络的破坏性明显高于其他四种算法。在as-733网络中，DID算法在移除网络中前20%的边时，性能和TO算法相当，而在剩余网络中，DID算法在移除网络前一半边的过程中，对网络的破坏性都高于其他算法。这说明了DID算法在探索网络中比较重要的边方面性能较为优秀。也验证了DID算法在真实网络中的有效性。本节还将DID算法与ID算法在上述真实网络中对比，验证节点相似性策略的有效性，实验结果如表1.4所示。图1.3真实网络中DID算法与经典算法在移除边时对网络连通性的破坏变化Fig.1.3ThedamageofDIDalgorithmandclassicalalgorithmstonetworkconnectivitywhenremovingedgesinrealnetworks表1.4DID算法与ID算法在真实网络中的对比实验Table1.4ComparativeexperimentofDIDalgorithmandIDalgorithminrealnetworks网络IDDIDDolphin0.45020.4407Jazz0.61820.6024Email0.47340.4721as-7330.49930.4934polblogs0.45750.4379PG0.44320.4504Sex0.38850.3895CA-Condmat0.45460.4143Facebook0.52590.5156与ID相比，DID算法采用了节点相似性的算法来评估边的不可替代性，使得算法的性能有了显著的提升。在9个真实网络中的Dolphin，Jazz，Email，as-733，polblogs，CA-Condmat，Facebook这7个网络中，相较于没有考虑节点相似性算法的ID算法，DID算法性能更加优秀。不过，在PG和Sex网络中，考虑了节点的相似性后，DID算法的效果反而不如ID算法，说明了这种简单考虑节点相似性的算法还存在一定的不足，但总体上，考虑了节点相似性之后，算法的效果有了明显的提升，实验结果验证了DID算法在真实网络中的有效性，在真实网络中，考虑了节点相似性的DID算法相较于ID算法有了较为明显的提升，但同时，这种策略依旧存在一定的局限性。上述实验证明了节点相似性策略的有效性。同时，本节也设计了动态网络的分析，来进一步观察DID算法的性能和这种策略的效果，网络的动态变化如图1.4所示。图1.4真实网络中DID算法与ID算法在移除边时对网络连通性的破坏变化Fig.1.4ThedamageofDIDalgorithmandIDalgorithmtonetworkconnectivitywhenremovingedgesinrealnetworks从图1.4中网络的动态数据可以看出，由于DID算法是ID算法与节点相似性策略结合得到的，因此DID算法和ID算法在探索网络中重要边方面的性能接近。在Email，as-733，PG，Sex和Facebook网络中，两者的动态曲线几乎重叠，同时在Jazz，polblogs和CA-Condmat网络中，DID算法稍微领先于ID算法，对网络有更强的破坏性。上述实验结果验证了在真实网络中节点相似性策略的有效性。本节通过对比了DID算法和四种对比算法以及DID算法和ID算法在真实网络中的表现，验证了DID算法在真实网络中的有效性，同时也验证了节点相似性策略在真实网络中的有效性。1.3.2生成网络实验在之前的实验中，本节验证了DID算法在真实网络中的有效性，同时，通过和ID算法作对比，验证了真实网络中节点相似性策略在ID算法上应用的效率。本节还将通过观察不同算法在生成网络中的效率，用于进一步验证DID算法的有效性。本节生成网络选用了同第3章使用的同样的生成网络，使用不同平均度和不同网络规模的BA网络和ER网络，通过检测删除边后的网络的鲁棒性R值和网络中最大连通子图规模的动态变化，来验证DID算法在生成网络中的效率。实验数据如表1.5所示。表1.5DID算法与经典算法在BA网络中的对比实验Table1.5ComparativeexperimentofDIDalgorithmandclassicalalgorithmsinBAnetworks网络EBDPDITODIDBA_500_30.73250.72510.72620.71030.6399BA_500_60.86510.8440.83060.77710.6877BA_500_90.8860.86610.85510.81610.725BA_500_120.90660.87280.86340.83840.7621BA_5000_30.73460.72570.72270.73520.6493BA_5000_60.86360.84450.83410.79820.7264BA_5000_90.89620.87020.85750.82980.7597BA_5000_120.90690.87880.86530.86930.7775BA_50000_30.73580.7230.72220.73790.6545BA_50000_60.85780.84450.83330.82140.7283BA_50000_90.89580.87150.85760.84840.775BA_50000_120.91540.88040.86550.8660.8131从表1.5中数据可以看出，在BA网络中，DID算法在性能上明显优于其他四种对比算法，在参与实验的12个BA网络中，DID算法全部优于其他算法，性能为5种算法中最优，有明显的优势。本节同样设计了针对BA网络的动态实验，通过观察DID算法和其他算法在BA网络中的对网络最大连通子图的动态影响，探究DID算法的有效性，实验结果如图1.5所示。由图1.5中所示的实验数据可知，DID算法对网络的动态影响和ID算法类似。在平均度为6，9，12的9个网络中，DID算法全程最优，对网络连通性的破坏效果明显优于其他四种算法。在平均度为3的三个网络中，DID算法在移除前70%的边时，它的性能是优于其他四种算法，证明了DID算法可以更好的找到网络中较为关键的边。总体上，DID算法在BA网络中，明显优于其他算法。图1.5BA网络中DID算法与经典算法在移除边时对网络连通性的破坏变化Fig.1.5ThedamageofDIDalgorithmandclassicalalgorithmstonetworkconnectivitywhenremovingedgesinBAnetworks本节还将DID算法与ID算法在上述BA网络中对比，验证节点相似性策略的有效性，实验结果如表1.6所示。表1.6DID算法与ID算法在BA网络中的对比实验Table1.6ComparativeexperimentofDIDalgorithmandIDalgorithminBAnetworks网络IDDIDBA_500_30.64260.6399BA_500_60.69070.6877BA_500_90.72880.725BA_500_120.76480.7621BA_5000_30.64940.6493BA_5000_60.72840.7264BA_5000_90.76140.7597BA_5000_120.7790.7775BA_50000_30.65430.6545BA_50000_60.72830.7283BA_50000_90.77630.775BA_50000_120.81390.8131由表1.6中的实验数据可知，在BA网络中，DID不仅在性能上优于其他四种对比算法，同时对于ID算法有显著提升。在实验采用的12个网络的10个网络中，考虑了节点相似性的DID算法都优于ID算法，仅在BA_50000_3网络中，DID算法的性能有降低，在BA_50000_6网络中，DID算法相较于ID算法没有明显提升。实验验证了节点相似性策略在BA网络中的效果，在大多数情况下可以提高算法的效率。本节同样设计了针对BA网络的动态实验，通过观察DID算法和ID算法在BA网络中的对网络最大连通子图的动态影响，探究节点相似性策略的有效性，实验结果如图1.6所示。图1.6BA网络中DID算法与ID算法在移除边时对网络连通性的破坏变化Fig.1.6ThedamageofDIDalgorithmandIDalgorithmtonetworkconnectivitywhenremovingedgesinBAnetworks由图1.6中的实验数据可知，在BA网络中，ID算法与DID算法对网络连通性的动态破坏效果类似，两种算法的曲线几乎重叠。总的来说，上述实验验证了DID算法在BA网络中的有效性，相较于四种对比算法，DID算法可以优先识别网络中的关键边，同时也验证了节点相似性策略在BA网络中的有效性，在12个BA网络中，这种策略可以提高算法在10个网络中的性能，效果较好。本节还通过在ER网络中不同算法移除网络边后对网络连通性破坏的效率，通过计算网络鲁棒性指标R值和观测网络动态连通子图规模变化，验证DID算法在ER网络中的有效性。鲁棒性指标R值实验数据如表1.7所示。表1.7DID算法与经典算法在ER网络中的对比实验Table1.7ComparativeexperimentofDIDalgorithmandclassicalalgorithmsinERnetworks网络EBDPDITODIDER_500_30.72160.73760.7410.65430.6625ER_500_60.84550.8420.85580.77420.7916ER_500_90.89630.87210.88320.89570.8307ER_500_120.9220.89180.90420.92560.8704ER_5000_30.73260.73260.7340.64150.6702ER_5000_60.82340.83860.85690.68240.77ER_5000_90.84870.86250.88420.7450.8317ER_5000_120.87330.87920.90050.83710.8568ER_50000_30.74060.73580.73810.64310.6664ER_50000_60.81860.8380.85650.66470.7695ER_50000_90.83260.86380.88580.67390.8222ER_50000_120.8390.87790.90040.66940.8454从表1.7中的实验数据中可以得知，在ER网络中，DID算法的效果相较于TO算法来说一般，在实验使用的12个ER网络中，TO算法在10个网络中效果最佳，DID算法仅仅在两个网络中效果相对TO算法较好，这与第3章中ID算法在ER网络中的表现类似，可见这种基于影响力分配的思想在ER网络中并不适用。本节同样通过设计对ER网络的动态实验，用于观察DID算法在ER网络中的对网络最大连通子图的动态影响，实验结果如图1.7所示。根据图1.7中实验结果可以看出，DID算法在少数几个网络中可以在早期较快地破坏网络的连通性，虽然和其他三种算法比，DID算法的性能相对依旧比较优秀，但是总体上，DID算法的效率不如TO算法，实验结果证明了这种算法在ER网络中效果一般。本节还将DID算法与ID算法在上述ER网络中对比，验证节点相似性策略的有效性，实验结果如表1.8所示。根据表1.8中数据可以看出，在ER网络中，DID算法在实验使用的12个ER网络中效果全部逊色于ID算法，验证了这种策略在ER网络中的局限性，这种策略并不能提升重要边排序算算法在ER网络中的性能，反而会产生反作用。通过设计对ER网络的动态实验，本节观察了DID算法和ID算法在ER网络中的对网络最大连通子图的动态影响，实验结果如图1.8所示。图1.7ER网络中DID算法与经典算法在移除边时对网络连通性的破坏变化Fig.1.7ThedamageofDIDalgorithmandclassicalalgorithmstonetworkconnectivitywhenremovingedgesinERnetworks由图1.8中实验数据可知，在ER网络中，ID算法与DID算法对网络连通性的动态破坏效果类似，两种算法的曲线几乎重叠。表1.8DID算法与ID算法在ER网络中的对比实验Table1.8ComparativeexperimentofDIDalgorithmandIDalgorithminERnetworks网络IDDIDER_500_30.65550.6625ER_500_60.78480.7916ER_500_90.82460.8307ER_500_120.86350.8704ER_5000_30.66190.6702ER_5000_60.76450.77ER_5000_90.82760.8317ER_5000_120.85440.8568表1.8（续表）DID算法与ID算法在ER网络中的对比实验ContinuedTable1.8ComparativeexperimentofDIDalgorithmandIDalgorithminERnetworks网络IDDIDER_50000_30.65860.6664ER_50000_60.76480.7695ER_50000_90.81890.8222ER_50000_120.84320.8454本节通过实验证明了DID算法和节点相似性策略在ER网络中的局限性，在ER网络中，DID算法的性能逊色于TO算法，同时这种节点相似性策略不能提升边中心性排序算法的性能。图1.8ER网络中DID算法与ID算法在移除边时对网络连通性的破坏变化Fig.1.8ThedamageofDIDalgorithmandIDalgorithmtonetworkconnectivitywhenremovingedgesinERnetworks上述实验通过观察DID算法与其他四种对比算法以及ID算法在真实网络和生成网络中的效果，验证了DID算法在真实网络和BA网络中的有效性，在真实网络和BA网络中，DID算法大大多数情况下都是优于其他五种算法的。实验结果同时也验证了节点相似性策略的有效性和局限性，在真实网络和BA网络的大多数网络中，节点相似性策略可以显著提升这种重要边排序算法的性能，但是在ER网络中却得到了相反的结论，使用这种策略不但不可以提升重要边排序算法的性能，反而有可能产生反作用。在1.4节中，本文将在经典重要边排序算法中验证节点相似性策略的性能。1.4节点相似性策略的应用效果分析在之前的实验中，本文验证了节点相似性策略与影响力分配算法结合的性能，这种策略在真实网络和BA网络中可以有效的提高重要边排序算法的效率，但是在ER网络中不适用，反而会降低影响力分配算法的效率。本节通过将节点相似性策略和前文实验中使用的经典算法相结合，观察这些算法在真实网络中的结果，进一步验证这种策略的效果，研究该策略的有效性和局限性。本节在真实网络中验证节点相似性策略的有效性。真实网络选用与之前实验相同的9个真实网络，本节分别对比了节点相似性策略和EB，DP，DI，TO四种经典算法结合后的重要边排序算法与原始重要边排序算法在真实网络中的效果。评价指标采用之前使用的关于网络连通性的指标R值。实验结果分别如表1.9，1.10，1.11，1.12所示。表1.9真实网络中节点相似性策略在EB算法上的实验效果Table1.9ExperimentaleffectofnodedissimilaritystrategyonEBalgorithminrealnetworks网络EBEB_disDolphin0.5110.4912Jazz0.6660.6514Email0.62530.6129as-7330.52620.5357polblogs0.59560.5778PG0.57640.613Sex0.52080.5446CA-Condmat0.43950.4449Facebook0.69790.7097根据表1.9中数据可以看出，在真实网络中EB算法和节点相似性结合的效果并不理想，仅仅在实验采用的9个真实网络的4个网络中，采用节点相似性策略的算法效果优于原始算法，在剩余5个网络中，采用节点相似性策略的算法的效果甚至不如原始的算法，产生了反作用，因此这种策略在真实网络中不适用于EB算法提升性能。根据表1.10中数据可以看出，在真实网络中，DP算法结合节点相似性策略之后，性能有明显提升，在实验采用的9个真实网络的8个网络中，这种策略都使DP算法的效果有明显优化，仅仅在Sex网络中没有明显提升，但并没有降低DP算法在Sex网络中的效果。上述实验结果可以证明，在真实网络中，这种策略可以明显提升DP算法的有效性。表1.10真实网络中节点相似性策略在DP算法上的实验效果Table1.10Experimentaleffectofnode