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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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-jie1,2, ZHANG Jian-pei1, YANG Jing1, XIN Yu1   

  1. 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:

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

中图分类号: