一种基于完全子图与标签传播的重叠社区检测算法

社区内部节点相互连接紧密，而不同社区间节点 法引入边介数 （ｂｅｔｗｅｅｎｎｅｓｓ）的概念，采用聚类分
连接相对稀疏。社区结构发现能在一定程度上反 析，将边介数作为节点间连接是否紧密的度量，依
映出真实网络的拓扑关系，同时可以挖掘网络中 次删除网络中边介数高的边，并最终将网络划分成
隐藏信息，帮助人们更好地利用和改造网络。然 若干个社区。此算法能够完成社区检测的任务，但
３８（３）：５６１－５６９．
５６２
桂 林 理 工 大 学 学 报 ２０１８年
个单独的社区，然后筛选出模块度增值最大的社 许一个节点可以同时被赋予多个标签，将原来单独
区，对其进行合并，当网络中的顶点都被合并到一 的社区标识符 ｃ改成了（ｃ，ｂ）的结构，其中 ｃ是社
个社区中时，算法终止。Ｇｒｅｇｏｒｙ在 ２００７年提出了 区标识符，ｂ是归属系数，ｂ的值越大，表示该节点
摘 要：提出了一种基于完全子图和标签传播的重叠社区检测 ＣＬＰＯＡ算法。该算法首先搜寻完全子图， 并为每个子图分配唯一标签，实现快速标签预处理；然后根据每个节点的邻接节点标签来更新该节点的标 签，同时提出接触频数优化标签选择策略降低标签随机传播概率；最后，通过网络标签分布情况进行社区 划分。选取两个小规模标准数据集和两个大规模网络数据集进行实验，结果表明 ＣＬＰＯＡ算法能保持和 ＣＯＰＲＡ算法相同社区划分质量，同时具有更好的算法稳定性和时间性能。 关键词：复杂网络；社区发现；完全子图；标签传播 中图分类号：ＴＰ３１１ 文献标志码：Ａ
第 ３８卷 第 ３期
桂林理工大学学报
Ｖｏｌ３８Ｎｏ３
２０１８年 ８月
ＪｏｕｒｎａｌｏｆＧｕｉｌｉｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ
Ａｕｇ ２０１８

文章编号：１６７４－９０５７（２０１８）０３－０５６１－０９
等［６］在 ２００２年提出了 ＬＰＡ算法（ｌａｂｅｌｐｒｏｐａｇａｔｉｏｎ
② 遍历所有节点，根据每个节点的所有邻接节
ａｌｇｏｒｉｔｈｍ，基于图的半监督学习方法），该算法首次 点在上一次迭代中的标签来更新当前节点的标签
将标签传播技术运用到社区检测领域当中。Ｒａｇｈａ ｖａｎ等［７］提出了 ＲＡＫ（Ｒａｇｈａｖａｎ＆ Ａｌｂｅｒｔ＆ Ｋｕｍａ
∑ ｂｔ（ｃ，ｘ） ＝
ｙ∈Ｓ（ｘ）ｂｔ－１（ｃ，ｙ）， ｜Ｓ（ｘ）｜
（１）
ｒａ），该算法基于 ＬＰＡ算法进行了改进，具有接近 其中：Ｓ（ｘ）表示节点 ｘ的邻接节点集合；｜Ｓ（ｘ）｜
线性的时间复杂度，算法流程简单，没有参数，但 则表示邻接节点个数；ｔ表示迭代次数。
它与 ＬＰＡ算法一样，只能用于检测非重叠社区，而
而，许多复杂网络社区存在重叠现象，重叠节点 在边介数的计算过程中性能损耗太大，只能应用在
同时属于多个社区，重叠社区的出现对社区发现 一些中小型规模网络上。２００３年，Ｐａｌｌａ等［３］提出
领域提出新的挑战。
派系过滤 算 法 （ｃｌｉｐｕｅｐｅｒｃｏｌａｔｅｍｅｔｈｏｄ，ＣＰＭ），分
目前，许多重叠社区检测算法已被相继提出， 析重叠群体相互交织集合的主要统计特征方法，通
基于 ＧＮ算法进行改进的 ＣＯＮＧＡ算法用来检测重 归属于该社区的可能性就越大。
叠 社 区 （ｃｌｕｓｔｅｒｏｖｅｒｌａｐ ｎｅｗｍａｎ ｇｉｒｖａｎ ａｌｇｏｒｉｔｈｍ， ＣＯＰＲＡ算法的执行步骤：
ＣＯＮＧＡ）［５］。
① 算法初始化，对任意的节点 ｘ分配一个唯一
不同于文献 ［２］的模块度和边介数思想，Ｚｈｕ 的标签（ｃｘ 的 增 大， 对 重 叠 社 区 检 测 算法时间性能要求越来越严格，算法需要在合理
随着互联网和通信技术迅速发展，网络规模 的时间内处理数百万乃至数千万个顶点的网络。
不断扩大，节点 间 关 系 越 来 越 复 杂， 从 而 形 成 大
Ｇｉｒｖａｎ和 Ｎｅｗｍａｎ作 为 社 区 发 现 领 域 的 奠 基
大多算法处理无定向、无加权边的不可分割网络， 过检测网络中派系来实现社区发现。Ｎｅｗｍａｎ等［４］
采用模块度优化、去除高介边、检测密集子图与 提出一种基于贪心的快速社区发现算法，该算法首
统计推断等技术，这些算法在性能和速度上各有 次引入模块度的概念，将网络中的每个顶点视为一
收稿日期：２０１８－０３－２３ 基金项目：国家自然科学基金项目（６１８６２０１９；６１６６２０１７；６１２６２０７５）；广西自然科学基金项目（２０１７ＧＸＮＳＦＡＡ１９８２２３） 作者简介：桂 琼 （１９７２—），女，副教授，研究方向：数据挖掘与信息安全，ｇｕｉｌｕｃｋｙ＠１６３ｃｏｍ。 通讯作者：程小辉，教授，ｃｘｉａｏｈｕｉ＠ｇｌｕｔｅｄｕｃｎ。 引文格式：桂琼，邓锐，程小辉，等．一种基于完全子图与标签传播的重叠社区检测算法 ［Ｊ］．桂林理工大学学报，２０１８，
量复杂网络。近年来，复杂网络研究引起众多学 人，在 ２０００年首次提出社区结构的概念，提出一
者广泛关注，涉及系统科学、统计物理学、社会 种社区检测方法，该方法建立在利用中心指数来寻
科学、生物学等多个领域，大多复杂网络都存在 找社区边界的思想基础上。随后，进一步提出了经
社区结构这一特性［１］。社区结构是指网络中每个 典的 ＧＮ算法（Ｇｉｒｖａｎ＆ Ｎｅｗｍａｎ，ＧＮ）［１－２］；该算
ｄｏｉ：１０３９６９／ｊ．ｉｓｓｎ１６７４－９０５７２０１８０３０２９
一种基于完全子图与标签传播的重叠社区检测算法
桂 琼１，２，邓 锐１ａ，程小辉１，吕永军１ａ
（１桂林理工大学 ａ信息科学与工程学院；ｂ广西嵌入式技术与智能系统重点实验室，广西 桂林 ５４１００４； ２武汉理工大学 信息工程学院，武汉 ４３００７０）
③ 比较 ｂｔ（ｃ，ｘ）与阈值的大小，如果小于阈
且这两种算法是基于标签传播实现，由于标签传播 值，则舍弃该标签。
过程有较 强 的 随 机 性，运 行 结 果 存 在 不 稳 定。对