吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 242-248.doi: 10.13229/j.cnki.jdxbgxb201701035

• 论文 • 上一篇    下一篇

基于密度峰值的重叠社区发现算法

时小虎1, 2, 3, 4, 冯国香1, 2, 李牧1, 2, 李瑛1, 2, 吴春国1, 2, 3, 4   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012;
    3.吉林大学珠海学院 计算机科学与技术系,广东 珠海 519041;
    4.吉林大学珠海学院 符号计算与知识工程教育部重点实验室珠海分实验室,广东 珠海 519041
  • 收稿日期:2015-05-27 出版日期:2017-01-20 发布日期:2017-01-20
  • 通讯作者: 吴春国(1976-),男,副教授,博士.研究方向:机器学习.E-mail:wucg@jlu.edu.cn
  • 作者简介:时小虎(1974-),男,教授,博士生导师.研究方向:机器学习.E-mail:shixh@jlu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61373050); 吉林省科技发展计划项目(20130101070JC, 20130522118JH, 20130206003SF); 在线教育研究基金(全通教育)项目(2017YB129); 广东省优势重点学科建设项目; 珠海市优势学科建设项目.

Overlapping community detection method based on density peaks

SHI Xiao-hu1, 2, 3, 4, FENG Guo-xiang1, 2, LI Mu1, 2, LI Ying1, 2, WU Chun-guo1, 2, 3, 4   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;
    3.Department of Computer Science and Technology, Zhuhai College of Jilin University, Zhuhai 519041, China;
    4.Zhuhai Laboratory of Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Zhuhai College of Jilin University, Zhuhai 519041, China
  • Received:2015-05-27 Online:2017-01-20 Published:2017-01-20

RICH HTML

0   

PDF (PC)

411

摘要： 根据基于快速搜索和发现密度峰值的聚类方法的思想,提出了基于密度峰值的重叠社区发现算法。首先定义新的距离矩阵算法,克服了邻接矩阵元素为整数的缺陷。然后用概率形式刻画每个节点属于不同类别的可能性,从而实现了重叠社区的划分。基于真实网络的实验结果验证了本文算法的可行性和有效性。

关键词: 计算机应用, 复杂网络, 社区发现, 重叠社区, 小世界特性, 模块度

Abstract: Based on the idea of clustering method by fast search and find of density peaks, we put forward an overlapping community detection method based on density peaks. In the proposed algorithm, first a new distance matrix is defined to overcome the defects of adjacency matrix being filled with integers. Then, the probability form is used to depict the possibility of each node that belongs to different clusters. The experimental results on real network show that the proposed method performs very well.

Key words: computer application, complex network, community detection, overlapping community, small world feature, modularity

中图分类号: 

  • TP391
[1] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393: 440-442.
[2] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[3] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006.
[4] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2): 291-307.
[5] Simon H D. Partitioning of unstructured problems for parallel processing[J]. Computing Systems in Engineering, 1991, 2(2-3):135-148.
[6] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Science of the United States of America, 2002, 99(12): 7821-7826.
[7] Newman M E J, Grivan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[8] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[9] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[DB/OL].[2015-10-26].https:∥arxiv.org/abs/0803.0476.
[10] Gregory S. An algorithm to find overlapping community structure in networks[J]. Lecture Notes in Computer Science, 2007,4702: 91-102.
[11] Lee C, Reid F, Mc Daid A, et al. Detecting highly overlapping community structure by greedy clique expansion[DB/OL].[2015-10-26]. https:∥arxiv.org/abs/1002.1827.
[12] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks[DB/OL].[2015-10-26].https:∥arxiv.org/abs/0802.1218.
[13] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[14] Floyd Robert W. Algorithm 97:shortest path[J]. Communications of the ACM,1962,5(6):345.
[15] 杨荟蓉. 基于概率模型的重叠社区发现算法研究[D]. 北京: 北京交通大学计算机与信心技术学院, 2011.
Yang Hui-rong. Research on overlapping community detection algorithms based on probabilistic model[D]. Beijing: School of Computer and Information Technology, Beijing Jiaotong University, 2011.
[16] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physical A: Statistical Mechanics and its Applications, 2009, 388(8): 1706-1712.
[17] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[18] Lusseau D, Schneider K, Boisseay O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.
[19] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[20] Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
[21] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发