基于节点影响力的标签传播算法的稳定性研究

发布时间：2024-05-18 11:39

　　网络中具有相似属性的节点可以构成社区,社区结构在复杂网络中普遍存在。面对如今超大规模的网络,快速检测网络中的社区结构有助于发现复杂网络内在的属性及规律。标签传播社区检测算法(LPA)具有思想简单、近线性时间复杂度等优点,但也存在随机性强、结果稳定性差的问题。本文主要针对LPA存在的问题,研究节点影响力对标签传播的影响,并改进了LPA检测结果的稳定性。本文的主要工作包括:(1)提出了基于节点影响力的标签传播社区检测算法:算法在标签初始化时只选择了部分影响力大的节点分配标签,减少了标签数量;在节点更新标签时如果出现多个待选标签,则以待选标签对应节点的影响力大小为依据进行选择,避免了经典LPA算法的随机性。使用真实网络数据集证明了所提算法复杂度近线性,算法的稳定性和社区检测的质量有所提高,并且减少了算法迭代次数。(2)提出了节点影响力在社区检测标签传播算法中的应用:在传播初始时,利用了节点影响力最大化算法选取网络中影响力大的节点作为传播源,提高了标签传播的效率;其次,在综合考虑节点影响力指标的基础上提出了新的衡量节点影响力指标,并指导标签更新顺序;最后,利用真实网络数据集验证了改进算法的随机...

【文章页数】：47 页

【学位级别】：硕士

【部分图文】：

图2.1K-shell分解示意图

图2.1K-shell分解示意图新的节点影响力度量指标被提出。Chen等人[29]在中心性（Sime-localCentrality）指标。任卓明等[30上提出基于度和集聚系数的节点影响力度量方法。分其影响力的问题，Zeng等人[31]考虑了K-shell分分解方....

图3.1Karate网络以节点K-shell值获得种子节点集合

图3.1Karate网络以节点K-shell值获得种子节点集合略算法在标签更新过程中，待更新节点遇到邻接节点中有机选择标签更新。为了降低算法的随机性，KLPA算法进一步衡量频数最多的标签影响力，选择影响力最大的网络G(V,E)，标签更新公式如下：()....

图4.1Karatenetwork以CCA算法获得种子节点集合

中北大学学位论文邻接节点集9101415161920212324272829303132i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i前未被覆盖的节点中K-shell....

图4.2Karate网络节点传播结果

图4.2Karate网络节点传播结果.4结果显示，利用CCA算法选取的种子节点以及按照节点G响能力均优于随机选取种子节点，并且当传播达到稳定状态在改进的LPA社区检测算法中，对节点标签初始化时选取有利于标签的传播并且能够降低迭代次数，使标签传播结果

本文编号：3976879