A Two-Stage Community Detection Algorithm Based on Label Propagation
-
摘要: 针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题，提出一种基于标签传播的两阶段社区发现算法(a two-stage community detection algorithm based on label propagation, LPA-TS)，通过参与系数确定节点更新顺序，并在标签传播过程中依据节点间相似性更新节点标签，得到初始社区划分.将社区看作节点，社区间连边数作为边权重，得到社区关系网络.按照参与系数由低到高的顺序合并社区关系网络中的节点，得到最终社区划分结果.算法LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性；在第2阶段，将不符合弱社区定义的初始社区与连边最多的相邻社区合并，再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量.通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS算法表现了良好的稳定性，在NMI、ARI、模块性等方面表现良好.Abstract: Due to the random process in node selection and label propagation, the stability of the results of traditional LPA is poor. A two-stage community detection algorithm is proposed based on label propagation, abbreviated as LPA-TS. In the first step of LPA-TS, the labels of nodes are updated according to their participation coefficients in non-decreasing order, and the node label is determined according to the similarity of nodes in the process of node label updating. Some clusters found by Step1 might not satisfy the weak community condition. If a cluster is not a weak community, in the beginning of Step2, we will merge it with the cluster that has most connections with it. Next, we treat each community as a node, and the number of edges between two communities as their edge weights between corresponding nodes. We compute the participation coefficients of each node of the resulted network, and use similar process to get the final results of the communities. The proposed algorithm LPA-TS reduces the randomness in the process of node selection and label propagation; hence, we might obtain stable communities by LPA-TS. In addition, LPA-TS combines small scale communities with adjacent communities in the second phase of the algorithm to improve the quality of community detection. Compared with other classical community detection algorithms on some real networks and artificial networks, the proposed algorithm shows preferable performance on stability, NMI, ARI and modularity.
-
尊敬的各位审稿专家：
岁序常易，华章日新。《计算机研究与发展》向过去一年为期刊审稿的400余位专家致以最诚挚的谢意！感谢您凭借深厚的专业造诣与严谨态度从众多来稿中披沙拣金，让优质成果脱颖而出。愿新岁里，我们继续携手共进，助力计算机领域蓬勃发展！祝您新的一年里身体健康、生活幸福、工作顺利、巳巳如意！
《计算机研究与发展》编委会
《计算机研究与发展》编辑部
2025年元月
2024年本刊主要审稿专家（按拼音序）：
艾浩军 白 亮 蔡志平 曹华伟 曹家乐 曹 娟 曹军威 曹 强 曹仰杰 曹子宁 车武军 陈 果 陈海明 陈慧敏 陈佳伟 陈建铭 陈 矜 陈晋鹏 陈镜超 陈俊颖 陈 恺 陈 琳 陈 强 陈强龙 陈 思 陈 厅 陈咸彰 陈晓丰 陈 昕 陈亚楠 陈玉明 陈 震 陈智能 成秀珍 程 塨 程显毅 崔 莉 崔逊学 戴望辰 单丹枫 邓 全 邓晓衡 邓梓焌 邸志雄 丁尧相 丁 勇 东昱晓 窦 勇 杜四春 鄂金龙 范贵生 冯 君 冯 瑞 冯 勇 冯志勇 付安民 付彦伟 付印金 盖珂珂 高聪明 高 胜 高 伟 高 尉 高 祥 高云君 高志鹏 葛仕明 宫云战 郭虎升 郭晓新 郭迎春 郭玉东 哈亚军 韩 彪 韩京宇 韩先培 韩亚洪 何 强 何世柱 何水兵 何相腾 何 源 何云华 和红杰 贺 旭 侯臣平 侯越先 胡 军 胡瑞珍 胡玉鹏 胡燏翀 虎嵩林 华 宇 郇丹丹 黄 华 黄书强 黄 兴 黄萱菁 黄振亚 姬晓鹏 计卫星 冀伟清 贾 杰 贾世杰 鉴 萍 江建慧 姜进磊 蒋 瀚 蒋树强 蒋万春 金澈清 琚生根 康 凯 孔兰菊 雷 震 李 波 李城龙 李红燕 李华伟 李建江 李 京 李涓子 李绿周 李佩雅 李 强 李仁发 李树栋 李 拓 李彤阳 李 暾 李 伟 李文斌 李向阳 李小勇 李晓红 李兴权 李永伟 李友焕 李宇峰 李振华 李振宇 李直旭 李子臣 梁 彬 梁久祯 廖士中 廖 勇 林春雨 林亦波 刘 斌 刘大江 刘党辉 刘国华 刘海洋 刘 杰 刘 杰 刘惊雷 刘 凯 刘 鹏 刘 淇 刘青凯 刘 全 刘日升 刘胜蓝 刘世光 刘书昌 刘向阳 刘学艳 刘 彦 刘云浩 刘知远 卢 冶 鲁 辉 鲁明羽 陆 杰 罗剑文 罗 娟 罗四维 骆伟祺 骆祖莹 吕亚丽 吕勇强 吕志强 马 川 马多贺 马菲菲 马海平 马恒太 马华东 马千里 马晓星 毛文涛 倪巍伟 宁建廷 欧阳丹彤 潘 恒 潘伟丰 裴玉茹 彭国军 彭 蓉 彭晓晖 彭宇新 祁 磊 钱 超 钱 鸿 秦 兵 秦 波 秦 川 秦小麟 秦 宇 秦志光 邱锡鹏 瞿有利 全睿杰 任丰原 邵 超 邵奇峰 申德荣 申富饶 沈 超 沈 蒙 沈晴霓 沈艳艳 盛泳潘 施新刚 石 川 石 源 石志强 时 鹏 史颖欢 舒 坚 宋传鸣 宋凤义 宋凌云 苏 申 孙 聪 孙 新 孙毓忠 孙 哲 谭玉娟 陶建华 田海博 田志宏 童向荣 万丽莉 万少华 汪德刚 汪建平 王昌栋 王 川 王 东 王红兵 王红军 王继龙 王利民 王良民 王 凌 王 梅 王庆林 王 冉 王 睿 王 卅 王生生 王 胜 王士同 王文剑 王晓峰 王兴伟 王意洁 王 毅 王正群 魏笔凡 魏立斐 魏 巍 魏秀参 温文媖 翁 健 邬贵明 邬鸿杰 吴 斌 吴陈旺 吴晨涛 吴 飞 吴俊敏 吴 乐 吴黎兵 吴素贞 吴 英 夏道勋 向 乔 肖利民 肖晓明 肖晓强 谢鹏瑾 谢 勇 谢 昭 邢立宁 熊 虎 熊金波 徐 彬 徐 辰 徐金安 徐明伟 徐 宁 徐秋亮 徐睿峰 徐 童 许方敏 许建秋 许新征 许 莹 许长桥 玄跻峰 薛瑞尼 薛向阳 薛 霄 严 飞 严 严 颜 波 阳王东 杨 博 杨 柳 杨 威 杨潇潇 杨 燕 杨 杨 杨育彬 姚 迪 姚海龙 姚念民 姚望舒 叶翰嘉 叶青青 叶笑春 殷丽华 殷 树 殷赵霞 于彦伟 余国先 余志文 袁 博 袁 夏 原继东 岳银亮 詹乃军 张 超 张承义 张春旭 张扶桑 张福新 张广艳 张红斌 张 虎 张华平 张佳乐 张金祥 张 晶 张敬伟 张 静 张 琨 张苗苗 张敏灵 张明喆 张宁豫 张三峰 张姗姗 张 胜 张世辉 张 腾 张天成 张天明 张 彤 张 骁 张小旺 张 晓 张晓龙 张啸剑 张亚飞 张岩峰 张 颖 张悠慧 张 召 章隆兵 章 毅 赵佳琦 赵 捷 赵 姝 赵思蕊 赵 翔 郑霄龙 周江平 周 俊 周 权 周 薇 周晓波 周雅倩 朱 斐 朱海萍 朱红松 朱培栋 祝继华 祝烈煌 庄福振 邹柏贤 邹德清 因时间仓促，整理时可能有疏漏，敬请谅解!
计量
- 文章访问数: 1492
- HTML全文浏览量: 1
- PDF下载量: 636
下载:
