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

发布时间：2021-12-18 23:00

　　[目的/意义]在大规模社交网络中快速搜索关键节点对于舆情的引导和控制具有重要意义。[方法/过程]本文提出一种适用于社交网络的局部中心性关键节点识别算法,该方法综合评估了节点的K壳、自身的聚集特性以及邻居的扩散特性和节点自身传播状态,同时体现了节点在空间上的网络位置和邻居的拓扑结构以及在时间上演化特征,评价指标更加全面高效。[结果/结论]实验结果表明,该方法识别的关键节点对网络鲁棒性的影响与介数中心性接近,但计算仅基于节点局部信息,时间复杂度低。剔除这些节点后网络的连通性受到较大影响,网络聚类系数降低,平均路径长度增加。同时,利用SIR传播模型模拟验证,以该算法识别的关键节点为初始传播源可提升信息传播范围和平均传播速度。 

【文章来源】：现代情报. 2020,40(12)CSSCI

【文章页数】：9 页

【部分图文】：

网络及K壳分解算法示意图

式(3)中τi代表了节点i的邻居节点的集合，pij定义为边eij的聚集系数，qij定义为边eij的扩散系数，TFi(t)表示节点的时间演化因子(Time Evolution Factor)。其中:1)边eij的聚集特性[14-16]可通过节点i和j的邻居节点与eij构成的三角形的占比来表示，无法构成三角形的邻居节点占比表示边eij的聚集特性。如图2所示，当信息从节点i经过边eij传播时，可通过扩散特性中的节点2和节点3将信息传播到网络中的其他节点，也可通过聚类特性中的节点1回传至节点j，因此边的聚类与扩散特性通过点的二阶邻居信息，有效地描述了对信息传播的影响作用。

论证三:能够发现重要局部“桥”节点。Ki C算法综合考虑了节点的聚集性和扩散性，使既有桥接特性也具有社区中心性的节点2和4排名靠前，同时本文提出的算法通过从局部二阶节点的角度来衡量节点的“桥”特征，使得能够识别出更重要的“桥”节点5，观察图1可知，将节点2和4排在首位，将“桥”特性明显的节点5排在节点1前显然更加合理，所以Ki C算法在识别“桥”特性方面优于其他算法。论证四:能够随着信息的传播从时间维度更加准确地识别关键节点。观察图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重新变为最重要节点。从信息传播的时间维度来看，相较于静态空间网络，Ki C算法充分结合网络时空特性，能够有效地根据节点的不同传播状态动态识别关键节点。

【参考文献】：
期刊论文
[1]基于点权的混合K-shell关键节点识别方法[J]. 王环,朱敏.  华东师范大学学报(自然科学版). 2019(03)
[2]考虑边聚类与扩散特性的信息传播网络结构优化算法[J]. 杨李,宋玉蓉,李因伟.  物理学报. 2018(19)
[3]利用邻域“结构洞”寻找社会网络中最具影响力节点[J]. 苏晓萍,宋玉蓉.  物理学报. 2015(02)



本文编号：3543321