导航菜单
首页 > 管理学论文 > 情报论文 » 正文

KiC:一种结合“结构洞”约束值与K壳分解的社交网络关键节点识别算法

通过上述表述可知通过式(3)的改进,在约束系数的计算中同时体现了节点的聚类性、邻居拓扑结构的扩散特性以及节点当前时刻状态对节点重要性的加强和削弱作用。

2.2  算法论证

本文所提出的KiC算法相较以往的K壳及其改进算法,能够从空间上以低时间复杂度识别一些重要的“桥节点”,能夠有效消除类核(局部聚类结构)的影响,能够更加细粒度、有区分度地识别节点的重要性,能够随着信息的传播从时间维度识别关键节点。本节以图1所示的小规模数据集为例,进行算法准确性分析,为保证实验结果的可对比性,论证一至论证三只考虑网络空间特性而不考虑时间特性,即网络是一个所有节点都处于S状态的静态网络;论证四中节点2为初始信息传播者(I状态),其余节点为不知情者(S状态),传播率β为0.41(网络的平均度=2.43,为保证传播能够进行,取传播率为1k),康复率γ为0.1。

论证一:提供细粒度化关键节点识别能力。针对图1的网络,本文分别用几种算法对其分解,进而获得了节点重要性的排序结果。表1所示的是节点重要性排序结果。从表中可以看出,度中心性、K壳分解、MDD分解存在大量排序相同的节点,区分度相对较低。EKSDN(点权中心性)、结构洞算法相对较好,本文提出的KiC算法相较上述两种算法区分度更大,相比于其他算法效果稍好。

论证二:能够有效过滤影响力较低的类核节点。类核节点是指局部与大量节点紧密相连,而与网络中其他节点连接较少的节点。通过类核节点的信息更容易在这个紧密社团内部扩散,而不容易将信息扩散出去,因此将其识别为影响力最大的节点是不准确的。表1的结果可以看出,传统的K壳分解算法和结构洞算法将节点1识别为最重要节点。

本文提出的算法可以从节点1、2、3和4组成的相互紧密连接的类核中过滤出影响力较小的节点1。因此本算法在过滤类核方面优于传统算法。

论证三:能够发现重要局部“桥”节点。KiC算法综合考虑了节点的聚集性和扩散性,使既有桥接特性也具有社区中心性的节点2和4排名靠前,同时本文提出的算法通过从局部二阶节点的角度来衡量节点的“桥”特征,使得能够识别出更重要的“桥”节点5,观察图1可知,将节点2和4排在首位,将“桥”特性明显的节点5排在节点1前显然更加合理,所以KiC算法在识别“桥”特性方面优于其他算法。

论证四:能够随着信息的传播从时间维度更加准确地识别关键节点。观察图3,在t=1时刻节点2为初始信息传播者,该节点既具备最重要的网络空间特性,又是该时刻唯一信息传播者,被识别为关键节点。随着信息的传播,在t=2时刻节点2变为R状态,节点3和节点5变为I状态,由于节点2不再具备传播特性,从舆情传播的角度来看,该节点重要性降为0,节点3变为最重要节点。当t=3时,由于节点6变为信息传播者,增强了节点5的信息传播特性,根据算法计算结果此时刻节点5重要程度超过节点3。在t=4时刻,由于节点6变为了R状态,此刻节点3重新变为最重要节点。从信息传播的时间维度来看,相较于静态空间网络,KiC算法充分结合网络时空特性,能够有效地根据节点的不同传播状态动态识别关键节点。

3  实验与结果分析

3.1  数据集及信息传播模型

在实验中采用的网络为:①Karate网络[17],美国一个大学空手道俱乐部成员;②Dophins网络[18],以声音相互联系的海豚社交网络;③Polbooks网络[19],美国政治书籍网络;④Football网络[20],经典的美国橄榄球俱乐部社会网络;⑤NetScience网络[21],从事网络理论和实验科学家合著的关系网络。表2为这5个网络的一些统计特性。

3.2  剔除关键节点后网络结构统计特性对比分析

为了验证关键节点对信息传播的影响,本实验使用KiC算法对5个真实网络的关键节点进行识别,并分别将识别出的排名前3%的关键节点隔离(剔除与这些节点相连的边)。网络结构的统计特性变化情况如表3,从表中可见,网络的平均度和聚类系数有所降低,平均路径长度有所增加。从信息传播角度分析,聚类系数的降低使得网络社团紧密度降低,信息在社团内部传播阈值将随之降低,而平均路径长度的提升使信息更难传播到网络的其他部分。从网络统计特性的角度验证了控制KiC算法所识别的关键节点对抑制信息传播的有效性。

3.3  关键节点对网络鲁棒性影响的分析

为了进一步分析KiC算法识别的节点的重要性,本组实验分别通过KiC、度中心性、K壳、接近中心性、介数中心性和随机6种算法将Karate网络的所有节点按照重要性进行排序,然后按照重要性从大到小的顺序依次移除节点,通过对比网络中剩余节点所构成的最大连通子图的节点个数,评估不同算法在识别关键节点的差异。从信息传播角度来看,移除相同节点,最大连通子图变化越大,说明图的连通性越差,信息传播到网络其他部分的可行性越低,移除的节点越重要。从图4可知,初始时刻Karate网络是一个完全连通的网络,开始移除节点后,通过随机算法移除节点的网络变化较小,而其他5种算法移除关键节点后最大连通子图变化明显,其中KiC算法、介数中心性、接近中心性相较度中心性和K壳算法下降较快。当移除重要性前5%的节点时,5种算法的最大连通子图分别为初始时刻的76%、69%、79%、83%、85%,而当移除重要性前12%的节点时,最大连通子图分别较移除5%时下降36%、36%、32%、21%、22%至49%、44%、52%、83%、84%。通过实验数据可知KiC算法所识别的关键节点较K壳算法和度中心性算法更加准确,与介数中心性和接近中心性相近,KiC、介数中心性、接近中心性在控制10%左右的重要节点后最大连通子图降至50%左右,能够有效地降低网络连通性,降低信息传播能力。

3.4  网络传播动力学模型有效性验证

为了验证KiC算法识别的重要节点在社交网络上的传播能力,本节通过在真实社交网络上使用SIR模型模拟信息传播,对比不同信息传入节点平均信息传播范围和平均传播速度来考察节点的真实影响力。本实验共设置5组,对应5个不同的真实社交网络,每组实验设置一个对照组,分别以KiC算法识别的最重要节点和随机选取一个节点为初始感染节点,观察每一时间步网络中感染过的节点数目和最终稳定态时感染过的节点数目,为保证传播能够进行,取SIR模型中传播率为1k,康复率为0.1。

通过对比图5中的5个真实网络的传播情况可以发现,整体上看对于各个传播时间t通过KiC算法识别的重要节点传入的信息,其传播范围都明显大于随机传入网络的信息,并且最终稳定状态下受到信息影响的节点数量较多,其中Karate网络多6.2%,Dolphins网络多3.4%,Polbooks网络多6%,Football网络持平,NetScience网络多89%。同时从图5曲线斜率看,传播到达稳态之前通过KiC算法识别的节点传入的信息斜率要高于随机节点传入,表明本文提出的算法所识别的节点网络信息扩散速度较快。通过以上实验可知,以KiC算法获得的节点为初始感染源的传播又快又广,说明本算法能够识别网络中传播影响力高的节点。

4  总  结

在大规模社交网络中快速搜索关键节点对于信息的引导和传播控制具有重要的意义。实践表明,社交网络舆情传播不同于传统的复杂网络,具有明显的时空特性,在空间方面,要准确识别规模性社交網络中不同节点的传播能力,既要考虑节点所处的网络位置和邻居的拓扑结构,同时需兼顾计算的时间复杂度;在时间方面,要结合网络中节点的传播状态进行综合评判。基于以上考虑,本文提出一种结合节点局部中心性特征的K壳改进算法(KiC算法),该方法利用节点的聚集性特征及其邻居的扩散性特征,并结合节点传播状态的时序变化作为改进后的“结构洞”约束值,综合K壳算法对节点所处位置的高效识别能力,作为评价节点重要性的指标。该改进方法同时考虑了节点的自身属性、所处的网络位置及其局部拓扑、不同时刻节点传播状态属性,评价结果更加全面高效。

实验结果表明:①该算法在网络结构上能够消除类核影响,细粒度的识别重要的“桥节点”,并充分结合网络时空特性,有效地根据节点的不同传播状态动态识别关键节点。②移除该算法所识别的重要节点后,网络聚类系数降低、平均路径长度增加,这些网络特征的变化能够控制信息传播范围的扩大。移除该算法所识别的10%的重要节点,能够将网络最大连通子图的节点数降低50%,对于网络鲁棒性的影响与介数中心性、接近中心性接近,但其计算仅基于节点局部信息,时间复杂度低。③通过基于SIR模型的信息传播验证,以该算法识别的重要节点为初始传播源可提升信息传播范围和平均传播速度,以Karate网络为例,其传播范围平均扩大6.2%,到达最大影响范围时传播时间平均缩短50%。

本文所提出的KiC算法是通过经典社交网络进行仿真验证的,但我们相信本文所做的研究对于政府决策部门对舆情的扩散和控制具有一定的参考价值。后续我们将重点根据实验仿真结果抓取真实社交网络数据进行验证。

参考文献

[1]Bonacich P.Factoring and Weighting Approaches to Status Scores and Clique Identification[J].Journal of Mathematical Sociology,1972,2(1):113-120.

[2]Freeman L C.A Set of Measures of Centrality Based on Betweenness[J].Sociometry,1977,40(1):35-41.

[3]Latora V,Marchiori M.Efficient Behavior of Small-World Networks[J].Physical Review Letters,2001,87(19).

[4]Chen D,Lu L,Shang M,et al.Identifying Influential Nodes in Complex Networks[J].Physica A-statistical Mechanics and Its Applications,2012,391(4):1777-1787.

[5]Burt R S.Structural Holes:The Social Structure of Competition[M].Cambridge,MA,USA:Harvard Univ,Press,2009.

[6]苏晓萍,宋玉蓉.利用邻域“结构洞”寻找社会网络中最具影响力节点[J].物理学报,2015,64(2):5-15.

[7]Ruan Y,Lao S,Xiao Y,et al.Identifying Influence of Nodes in Complex Networks with Coreness Centrality:Decreasing the Impact of Densely Local Connection[J].Chinese Physics Letters,2016,33(2).

[8]Kitsak M,Gallos L K,Havlin S,et al.Identification of Influential Spreaders in Complex Networks[J].Nature Physics,2010,6(11):888-893.

[9]Zeng A,Zhang C.Ranking Spreaders By Decomposing Complex Networks[J].Physics Letters A,2013,377(14):1031-1035.

[10]王环,朱敏.基于点权的混合-shell关键节点识别方法[J].华东师范大学学报:自然科学版,2019,(3):101-109.

[11]Cheng X,Ren F,Shen H,et al.Bridgeness:A Local Index on Edge Significance in Maintaining Global Connectivity[J].Physics,2010,(5).

[12]Liu Y,Tang M,Zhou T,et al.Core-like Groups Result in Invalidation of Identifying Super-spreader By K-shell Decomposition[J].Scientific Reports,2015,5(1):9602-9602.

[13]Pastor-Satorras R,Vespignani A.Epidemic Spreading in Scale-Free Networks[J].Physical Review Letters,2001,86(14):3200-3203.

[14]Malliaros F D,Rossi M G,Vazirgiannis M,et al.Locating Influential Nodes in Complex Networks[J].Scientific Reports,2016,6(1):19307-19307.

[15]杨李,宋玉蓉,李因伟.考慮边聚类与扩散特性的信息传播网络结构优化算法[J].物理学报,2018,67(19):92-102.

[16]Liu Y,Tang M,Do Y,et al.Accurate Ranking of Influential Spreaders in Networks Based on Dynamically Asymmetric Link Weights[J].Physical Review E,2017,96(2).

[17]Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups1[J].Journal of anthropological research,1976,33(4):452-473.

[18]Lusseau D,Schneider K,Boisseau O,et al.The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-lasting Associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.

[19]V Krebs.http://www.orgnet.com/[EB].

[20]Girvan M,Newman M E.Community Structure in Social and Biological Networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[21]Newman M E.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review E,2006,74(3).

(责任编辑:陈  媛)

收藏此文 赞一个 ( ) 打赏本站

如果本文对您有所帮助请打赏本站

  • 打赏方法如下:
  • 支付宝打赏
    支付宝扫描打赏
    微信打赏
    微信扫描打赏
留言与评论(共有 0 条评论)
   
验证码:
二维码