局部扩展的标签传播蚁群优化重叠社区发现

为了提升社区发现算法速度和高精度命题,提出一种局部扩展标签传播算法与蚁群优化结合的重叠社区发现框架(ELPA-ACO)。利用局部扩展的标签传播社区发现算法快速获得蚁群初始信息素和位置;结合网络中节点的拓扑结构、内部标签属性、历史信息和节点的传播相互影响力等因子改进蚂蚁转移概率,进一步提高划分精度。在未知网络和真实网络上验证,ELPA-ACO算法可适应多种网络划分,无论是速度还是精度都有显著提高。

一种结合节点局部影响力的标签传播算法

标签传播算法(LPA)作为一种简单高效的社区挖掘算法一直受到广泛的关注.但是标签传播过程中存在随机性,导致算法鲁棒性差、社区划分结果不稳定.为解决此类问题,本文提出一种结合节点局部影响力的算法(CRD-LPA).该算法综合考虑节点度、邻节点的消息传播能力、局部密度分布等因素,将近似集聚系数和节点局部密度引入到CRD系数的计算中,从而更精确的衡量节点在网络中的重要程度;然后,根据CRD系数对LPA算法的节点标签更新策略进行改进.实验结果表明,改进后的算法不仅提高了社区划分的质量,而且也表现出较好的鲁棒性.

一种局部强化的多标签传播社区发现算法

在社交网络中,社区和圈子均表现为一组内部连接相对紧密的节点,但后者规模较小。圈子是重要的局部社区信息,利用这一特点有助于进行社区发现。然而,现有的大部分基于标签传播的社区发现算法并没有考虑圈子的信息。为此,提出一种基于局部强化的多标签传播(LSMLP)社区发现算法。给出圈子的定义,提出一种基于圈子信息的迭代多标签传播策略,并从每个节点的多个标签中选择归属系数最大的标签作为其从属的临时社区。采用两步优化方法使模度最大化。在真实网络的数据实验结果表明,与已有的社区发现算法相比,LSMLP算法能更高效地发现社区。

基于节点影响值的社区网络稳定标签传播算法

针对社区网络标签传播准确性差的问题,提出基于节点影响值的社区网络稳定标签传播算法。该算法重设社区网络相邻节点相似度,结合链路加权思想将其变换为链路无向带权图;利用节点K-shell分解值判断节点影响力,计算种子节点的中心性度量值,升序排列节点更新顺序;根据越重要节点标签影响越大的规则,修正高频数标签,获取最佳社区网络划分结果。结果表明:该算法模块度在0.320以上,准确率达到99%,因此,经该方法划分后的网络结构清晰、准确,稳定性高。

基于随机游走的改进标签传播算法

社区发现是挖掘社交网络隐藏信息的一个有用的工具,而标签传播算法(LPA)是社区发现算法中的一种常见算法,不需要任何的先验知识,且运行速度快。针对标签传播算法有很强的随机性而导致的社区发现算法结果不稳定的问题,提出了一种基于随机游走的改进标签传播算法(LPARW)。首先,根据在网络上进行随机游走确定了节点重要性的排序,从而得到节点的更新顺序;然后,遍历节点的更新序列,对每个节点将其与排序在其之前的节点进行相似性计算,若该节点与排序在其之前的节点是邻居节点且它们之间的相似性大于阈值,则将排序在其之前的节点选为种子节点;最后,将种子节点的标签传播给其余的节点,得到社区的最终划分结果。将所提算法与一些经典的标签传播算法在4个有标签的网络和5个无标签的真实网络上进行比较分析,实验结果表明所提算法在标准互信息(NMI)、调整兰德系数(ARI)和模块度等经典的评价指标上的性能均优于其余对比算法,可见该算法具有很好的社区划分效果。

基于SLPA改进的重叠社团检测算法

标签传播算法(Speaker-Listener Label Propagation Algorithm,SLPA)在重叠社团检测任务上具有线性时间复杂度和优良的检测效果,但作为一种随机算法其多次的随机选择策略致使算法的精度受限且算法结果不稳定;此外,算法在选取的阈值较低时容易出现大量相互嵌套的小型社团和重叠节点。针对上述问题,提出一种精度更高、稳定性更好的改进算法。算法初始化阶段,使用节点局部结构熵(Local Structure Entropy,LE)计算的节点重要性排序升序作为节点更新序列;标签传播阶段,使用资源分配指标(Resource Allocation,RA)作为节点进一步选择的依据,引导标签传播的方向;后处理阶段,新增两两对比待选社团集以去除嵌套包含的社团。在真实网络与人工网络上验证算法的有效性,使用重叠标准互信息(Overlapping Normalized Mutual Information,NMIov)和扩展模块度(Extended Modularity,EQ)与5个经典算法进行对比。实验证明,改进算法在精度与经典算法相比具有优势,在真实网络和人工网络中均具备较好的鲁棒性;改进算法与原算法相比,算法的结果精度分布更为集中,算法的稳定性有提升。