基于链接相似性聚类的重叠社区识别

doi:10.3969/j.issn.0372-2112.2015.07.012

电子学报 ›› 2015, Vol. 43 ›› Issue (7): 1329-1335.DOI: 10.3969/j.issn.0372-2112.2015.07.012

基于链接相似性聚类的重叠社区识别

张桂杰^1,2, 张健沛¹, 杨静¹, 辛宇¹

1. 哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001;
2. 吉林师范大学计算机科学与技术学院, 吉林四平 136000

收稿日期:2014-04-08 修回日期:2015-01-09 出版日期:2015-07-25
- 通讯作者:
- 张健沛
- 作者简介:
- 张桂杰 女,1980年生于吉林白山.哈尔滨工程大学计算机学院博士研究生,吉林师范大学讲师.主要研究方向为数据挖掘、社会网络社团分析. E-mail:zhangguijie@hrbeu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61370083,No.61073043,No.61073041); 高等学校博士学科点专项科研基金 (No.20112304110011,No.20122304110012); 吉林省教育厅"十二五"科学技术研究基金 (No.吉教科合字2013[207])

Overlapping Community Detection Based on Link Similarity Clustering

ZHANG Gui-jie^1,2, ZHANG Jian-pei¹, YANG Jing¹, XIN Yu¹

1. College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China;
2. College of Computer Science and Technology, Jilin Normal University, Siping, Jilin 136000, China

Received:2014-04-08 Revised:2015-01-09 Online:2015-07-25 Published:2015-07-25
- Supported by:
- National Natural Science Foundation of China (No.61370083, No.61073043, No.61073041); Research Fund for the Doctoral Program of Higher Education of China (No.20112304110011, No.20122304110012); 12th Five-Year Science and Technology Project Fund of Education Department of Jilin Province (No.吉教科合字2013[207])

摘要/Abstract

摘要：

社区结构是社会网络最普遍和重要的拓扑属性之一,提出一种基于链接相似性聚类的重叠社区识别算法.该算法首先根据相邻链接的度分布状态,提出链接间的相似性度量方法;其次以链接相似性矩阵为输入,以链接社区的最优划分为目标,建立链接局部相似性聚类算法,实现了重叠社区的有效识别;然后对链接社区进行优化,解决了可能出现的过度重叠及孤立社区问题;最后在真实网络及人工合成网络上的实验验证了算法的高效性.

关键词: 社区识别, 链接社区, 局部链接相似性度量, 层次聚类, 重叠社区

Abstract:

Community structure is one of the most common and important social network topological properties.This paper proposes a link community detection algorithm based on hierarchical clustering.Firstly,the algorithm sets up similarity measure according to the degree distribution of links nearby;then sets up local link similarity clustering algorithm which takes the similarity matrix as input with the purpose of detecting the best link community;further more realizes link community detection effectively.And then,optimize the link community to solve the problem of excessive overlapping and isolated community.Experiment results based on real world and computer generated networks show that the algorithm is highly efficient.

Key words: community detection, link community, local link similarity metric, hierarchical clustering, overlapping community

中图分类号:

TP301

张桂杰, 张健沛, 杨静, 等. 基于链接相似性聚类的重叠社区识别[J]. 电子学报, 2015, 43(7): 1329-1335.

ZHANG Gui-jie, ZHANG Jian-pei, YANG Jing, et al. Overlapping Community Detection Based on Link Similarity Clustering[J]. Acta Electronica Sinica, 2015, 43(7): 1329-1335.

参考文献

[1] Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3):75-174.
[2] Evans T S,Lambiotte R.Line graphs,link partitions,and overlapping communities[J].Physical Review E,2009,80(1):016105.
[3] Ahn Y Y,Bagrow J P,Lehmann S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[4] Kim Y,Jeong H.Map equation for link communities[J].Physical Review E,2011,84(2):026110.
[5] Ball B,Karrer B,Newman M E J.Efficient and principled method for detecting communities in networks[J].Physical Review E,2011,84(3):036103.
[6] 刘旭,易东云.基于局部相似性的复杂网络社区发现方法[J].自动化学报,2011,37(12):1520-1529. LIU Xu,YI Dong-Yun.Complex network community detection by local similarity[J].Acta Automatica Sinica,2011,37(12):1520-1529.(in Chinese)
[7] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[8] Shen H,Cheng X,Cai K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A:Statistical Mechanics and its Applications,2009,388(8):1706-1712.
[9] Leskovec J,Lang K J,Mahoney M.Empirical comparison of algorithms for network community detection[A].Proceedings of the 19th International Conference on World Wide Web[C].ACM,2010.631-640.
[10] Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009,(03):P03024.
[11] Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[12] Danon L,Diaz-Guilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(09):P09008.

[1]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[2]	高雷阜, 张梦瑶, 赵世杰. 融合簇边界移动与自适应合成的混合采样算法[J]. 电子学报, 2022, 50(10): 2517-2529.
[3]	柳菁, 李琪. DisHAP：基于层次亲和聚类的分布式大图划分算法[J]. 电子学报, 2021, 49(10): 2002-2011.
[4]	张仰森, 段宇翔, 王建, 吴云芳. 基于多种词特征的微博突发事件检测方法[J]. 电子学报, 2019, 47(9): 1919-1928.
[5]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[6]	於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
[7]	马慧芳, 谢蒙, 何廷年, 蔺想红. 基于核心标签的可重叠微博网络社区划分方法[J]. 电子学报, 2017, 45(4): 769-776.
[8]	国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.
[9]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[10]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[11]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[12]	李泓波, 张健沛, 杨静, 白劲波, 初妍. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J]. 电子学报, 2014, 42(1): 62-69.
[13]	张健沛, 李泓波, 杨静, 白劲波, 张乐君, 初妍. 基于归属不确定性的变规模网络重叠社区识别[J]. 电子学报, 2012, 40(12): 2512-2518.
[14]	谈璐璐;杨汝良;商建. 利用Shannon熵参数的极化干涉SAR图像非监督分类[J]. 电子学报, 2010, 38(10): 2264-2267.
[15]	曹芳, 洪文, 吴一戎, . 基于Cloude-Pottier目标分解和聚合的层次聚类算法的全极化SAR数据的非监督分类算法研究[J]. 电子学报, 2008, 36(3): 543-546.

基于链接相似性聚类的重叠社区识别

Overlapping Community Detection Based on Link Similarity Clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics