基于标签影响力的半同步社区发现算法

doi:10.11772/j.issn.1001-9081.2016.06.1573

计算机应用 ›› 2016, Vol. 36 ›› Issue (6): 1573-1578.DOI: 10.11772/j.issn.1001-9081.2016.06.1573

基于标签影响力的半同步社区发现算法

汪焱¹, 黄发良¹, 元昌安²

1. 福建师范大学软件学院, 福州 350108;
2. 科学计算与智能信息处理广西高校重点实验室, 南宁 530023

收稿日期:2015-11-04 修回日期:2015-12-21 出版日期:2016-06-10 发布日期:2016-06-08
通讯作者: 黄发良
作者简介:汪焱(1988-),男,湖北随州人,硕士,主要研究方向:数据挖掘、社区发现;黄发良(1975-),男,湖南永州人,副教授,博士,CCF会员,主要研究方向:数据挖掘、社交媒体处理;元昌安(1964-),男,安徽肥东人,教授,博士,CCF会员,主要研究方向:数据挖掘。
基金资助:
国家自然科学基金资助项目(61363037);教育部人文社会科学研究青年基金资助项目(12YJCZH074);福建省教育厅A类项目(JA13077)。

Semi-synchronous communities detection algorithm based on label influence

WANG Yan¹, HUANG Faliang¹, YUAN Chang'an²

1. Faculty of Software, Fujian Normal University, Fuzhou Fujian 350108, China;
2. Key Laboratory of Scientific Computing and Intelligent Information Processing in Universities of Guangxi, Nanning Guangxi 530023, China

Received:2015-11-04 Revised:2015-12-21 Online:2016-06-10 Published:2016-06-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61363037), the Youth Foundation of Humanities and Social Sciences of Ministry of Education (12YJCZH074), the Category A Project of Fujian Provincial Department of Education (JA13077).

摘要/Abstract

摘要： 微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法(LPA)虽然在时间复杂度上具有很大的优势,但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题,提出了一种基于影响力的半同步标签传播算法(ISLPA),能有效地避免振荡问题,巧妙地实现了相邻节点之间的同步更新,并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进,摒弃了原有的随机策略。真实网络和人工网络的实验结果表明,ISLPA具有较高的稳定性与有效性,与其他LPA相关算法相比存在明显的优势。

关键词: 社区发现, 标签传播法, 半同步, 节点影响力, 振荡

Abstract: It is a great challenge to discover communities in the fast growing large-scale interactive social information networks such as Weibo and social networks. Although Label Propagation Algorithm (LPA) has great advantage in time complexity, but its inherent multiple random strategies make the algorithm unstable. In order to solve the problem, a semi-synchronous label propagation algorithm named Influence-driven Semi-synchronous Label Propagation Algorithm (ISLPA) was proposed. The propagation oscillation was avoided effectively and the synchronous update between neighbor nodes was realized by abandoning the original random strategy and integrating node influence into label initialization, neighbor node selection and updated order determination. The experimental results from the real-world and artificial networks indicate that, in terms of validity and stability of generated communities from the networks, the proposed ISLPA outperforms the currently typical LPAs used in community detection.

Key words: community detection, Label Propagation Algorithm (LPA), semi-synchronization, node influence, oscillation

中图分类号:

TP393

汪焱, 黄发良, 元昌安. 基于标签影响力的半同步社区发现算法[J]. 计算机应用, 2016, 36(6): 1573-1578.

WANG Yan, HUANG Faliang, YUAN Chang'an. Semi-synchronous communities detection algorithm based on label influence[J]. Journal of Computer Applications, 2016, 36(6): 1573-1578.

参考文献

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2009, 486(3/4/5): 75-174.
[2] COSCIA M, GIANNOTTI F, PEDRESCHI D. A classification for community discovery methods in complex networks[J]. Statistical Analysis & Data Mining the Asa Data Science Journal, 2011, 4(5): 512-546.
[3] 黄发良.信息网络的社区发现及其应用研究[J].复杂系统与复杂性科学,2010,7(1):64-74.(HUANG F L. Studies on community detection and its application in information network[J]. Complex Systems and Complexity Science, 2010, 7(1): 64-74.)
[4] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[5] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2004, 70(6 Pt 2): 066111.
[6] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2007, 76(3 Pt 2): 036106.
[7] SUBELJ L, BAJEC M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2011, 83(3 Pt 2): 036103.
[8] LEUNG I X, HUI P, LIO P, et al. Towards real-time community detection in large networks[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2009, 79(6 Pt 2): 066107.
[9] ZHANG X K, FEI S, SONG C, et al. Label propagation algorithm based on local cycles for community detection[J]. International Journal of Modern Physics B, 2015, 29(5): 1550029.
[10] LIN Z, ZHENG X, XIN N, et al. CK-LPA: efficient community detection algorithm based on label propagation with community kernel[J]. Physica A: Statistical Mechanics & Its Applications, 2014, 416: 386-399.
[11] 赵卓翔,王轶彤,田家堂,等.社会网络中基于标签传播的社区发现新算法[J].计算机研究与发展,2011,48(Z2):8-15.(ZHAO Z X, WANG Y T, TIAN J T, et al. A novel algorithm for community discovery in social networks based on label propagation[J]. Journal of Computer Research and Development, 2011, 48(Z2): 8-15.)
[12] BARBER M J, CLARK J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(2 Pt 2): 026129.
[13] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statistical Mechanics & Its Applications, 2010, 389(7): 1493-1500.
[14] SUBELJ L, BAJEC M. Robust network community detection using balanced propagation[J]. European Physical Journal B, 2011, 81(3): 353-362.
[15] LI S, LOU H, JIANG W, et al. Detecting community structure via synchronous label propagation[J]. Neurocomputing, 2015, 151(3): 1063-1075.
[16] LIU X, MURATA T. How does label propagation algorithm work in bipartite networks?[C]//Proceedings of the 2009 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. Piscataway, NJ: IEEE, 2009: 5-8.
[17] CORDASCO G, GARGANO L. Label propagation algorithm: a semi-synchronous approach[J]. International Journal of Social Network Mining, 2012, 1(1): 3-26.
[18] TIBÉLY G, KERTÉSZ J. Note on the equivalence of the label propagation method of community detection and a Potts model approach[J]. Physica A: Statistical Mechanics & Its Applications, 2008, 387(19): 4982-4984.
[19] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2008, 78(4 Pt 2): 046110.
[20] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2 Pt 2): 026113.
[21] DÍAZ-GUILERA A, DUCH J. Comparing community structure identification[J]. Journal of Statistical Mechanics Theory & Experiment, 2005, 24(9): 09008.

基于标签影响力的半同步社区发现算法

Semi-synchronous communities detection algorithm based on label influence

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	秦丽, 郝志刚, 李国亮. 国家食品安全标准图谱的构建及关联性分析[J]. 计算机应用, 2021, 41(4): 1005-1011.
[2]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[3]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[4]	陈发堂, 张友寿, 杜铮. 5G低密度奇偶校验码的低复杂度偏移最小和算法[J]. 计算机应用, 2020, 40(7): 2028-2032.
[5]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[6]	吴清寿, 陈荣旺, 余文森, 刘耿耿. 融合标签预处理与节点影响力的重叠社区发现算法[J]. 计算机应用, 2020, 40(12): 3578-3585.
[7]	李莎莎, 梁冬阳, 余杰, 纪斌, 马俊, 谭郁松, 吴庆波. 基于师门关系的研究团队挖掘算法[J]. 计算机应用, 2020, 40(11): 3198-3202.
[8]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[9]	张琪, 纪淑娟, 傅强, 张纯金. 基于带权评论图的水军群组检测及特征分析[J]. 计算机应用, 2019, 39(6): 1595-1600.
[10]	陈婉杰, 盛益强. 基于网络表示学习的非单一维度的社区发现算法[J]. 计算机应用, 2019, 39(12): 3467-3475.
[11]	杜航原, 裴希亚, 王文剑. 面向属性网络的重叠社区发现算法[J]. 计算机应用, 2019, 39(11): 3151-3157.
[12]	顾军华, 霍士杰, 王守彬, 田喆. 基于节点中心性和社区相似性的快速标签传播算法[J]. 计算机应用, 2018, 38(5): 1320-1326.
[13]	李雷, 闫光辉, 杨绍文, 张海韬. 基于孤立节点分离策略的改进鲁汶算法[J]. 计算机应用, 2017, 37(4): 970-974.
[14]	陈嶷瑛, 柴变芳, 李文斌, 贺毅朝, 吴聪聪. 基于迭代框架的主动链接选择半监督社区发现算法[J]. 计算机应用, 2017, 37(11): 3085-3089.
[15]	柴变芳, 王建岭, 许冀伟, 李文斌. 基于链接模型的主动半监督社区发现方法[J]. 计算机应用, 2017, 37(11): 3090-3094.