基于改进标签传播算法的社区发现研究与应用

发布时间：2024-04-10 01:47

　　现实世界的大量复杂系统都可用复杂网络进行建模分析,而社区发现是复杂网络分析中的热门问题。社区发现能够帮助挖掘复杂系统内部个体间的聚集结构,分析个体与个体间的关联,掌握复杂系统的发展规律,发现复杂系统的隐藏功能等等,具有重要的研究价值和意义。社区发现算法中的标签传播算法由于其思想简单和实际复杂度低,而受到广泛关注。然而该算法对于标签的随机更新,导致了算法稳定性差和准确率低的情况,为了解决以上问题,本文主要做了如下几个方面工作:(1)本文对现有的标签传播算法进行了总结和分析,提出了一种改进的标签传播算法(Link Label Propagation Algorithm,简称LLPA),该算法分为三个部分,第一个部分为将原始网络图转换成边图,边图保留了原始网络图的所有的拓扑网络结构;第二部分是利用改进的标签传播模型来对边图进行非重叠社区划分,首先,计算节点的重要性程度并按照降序排列,然后利用节点的排序结果找出网络的极大团,作为初始的社区核心,在标签的初始化阶段,每一个初始社区都会被赋予一个唯一的标签;第三部分是将边图重新还原成原始的网络结构图,通过遍历第二部分划分出的社区,将社区里的每个节点...

【文章页数】：65 页

【学位级别】：硕士

【部分图文】：

图１．１社区结构示意图??复杂网络的诸多特性构成了“社区结构”通常而言，社区结构就是一组节点集??

集合内节点间的连接紧密，集合间节点连接稀疏。从物理角度而言，社区??内部节点间距离较小，社区间节点距离较大从功能角度而言，社区内部节点拥??有相似属性或功能，社区间节点的相似性较差［６］。图１．?１展示了一个小型网络的??三个社区结构，每个灰色圈代表一个社区结构。社区结构普遍存在....

图１．２模块度Ｑ对节点度的依赖??“Ｒｅｓｏｌｕｔｉｏｎｍｔ”

模块度Ｑ却面临以下缺点：??？模块度Ｑ强依赖于节点的度。这个缺陷已在文献［２９］［３（）］中被反复提及，图??１．４展示了这个缺陷。由图可知，图１．２ａ）、图１．２ｂ）、图１．２ｃ）３个网络??都包含１７条边，但节点数量不同。３个网络中２个黑色粗节点都拥有相??同的度７，且不直连....

图１．３?ＩｎｆｏｒＭａｐ算法过程示意图??１．４主要研究成果??

为求网络编码长度最短的编码压缩问题，目标函数为网络中所有随机游走路径的??总编码长度。因此，在求解过程中联系紧密的节点将被归为同一群组，以实现两??种编码的压缩量最大。图１．３描述了Ｉｎｆｏｍａｐ算法的基本过程。Ｉｎｆｏｍａｐ算法是目??前性能最优的社区发现算法之一，缺点在于时间....

图2.1标签传播过程示意图

是社区发现算法领域比较重要的算法之一。２００７用于用来发现社区的结构，从而提出了?ＬＰＡ算容易实现。本小节主要介绍ＬＰＡ算法的基本思算法概述??的详细步骤如下：??中的每一个节点，随机赋予一个唯一的标签。??络中的节点进行迭代并更新每一个节点的标签，不再发生改变为止。在每一轮的计....

本文编号：3949956