一种基于聚集系数的社区发现算法

J4 ›› 2016, Vol. 38 ›› Issue (02): 363-369.

一种基于聚集系数的社区发现算法

樊梦佳1,钮艳2,杜翠兰2,张仰森1

（1.北京信息科技大学智能信息处理研究所,北京 100192;2.国家计算机网络应急技术处理协调中心,北京 100190）

收稿日期:2015-10-16 修回日期:2015-12-13 出版日期:2016-02-25 发布日期:2016-02-25
基金资助:
国家自然科学基金（61370139）；北京市属高等学校创新团队建设与教师职业发展计划（IDHT20130519）；北京市教委专项（PXM2013_014224_000042,PXM2014_014224_000067）

A community detection method based on clustering coefficient

FAN Mengjia1,NIU Yan2,DU Cuilan2,ZHANG Yangsen1

（1.Institute of Intelligent Information Processing,Beijing Information Science and Technology University,Beijing 100192;
（2.National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100190,China）

Received:2015-10-16 Revised:2015-12-13 Online:2016-02-25 Published:2016-02-25

摘要/Abstract

摘要：

社区划分一直是复杂网络研究中的一个热门话题,社区的快速准确划分为研究复杂网络的性质提供了良好的基础。传统的社区发现方法都是在全局复杂网络的基础上进行社区划分,随着网络中节点的增加,网络规模的变大,社区发现变得更为复杂。提出了一种局部社区发现算法,该算法无需知道整个复杂网络的全部信息,只需从一个待求节点出发,考察其与邻接节点的紧密程度,逐步将邻接点添加到社区中,得到该节点所在的社区结构。同时，该算法还可实现全局网络的社区发现。利用该算法分别对Zachary空手道俱乐部网络和海豚社会网络进行社区发现,实验结果表明了该算法的准确性与可行性。

关键词: 局部社区, 社区发现, 聚集系数

Abstract:

Community detection has been a hot topic in complex network research. Fast and accurate community detection can provide a good foundation for studying the properties of complex networks. Traditional community detection methods are mainly based on the global community. However, as the number of nodes in the network increases, the network size becomes larger, so the community detection becomes more complex. We propose a local community detection method, which does not need to know the whole complex network information. Rather it just starts from an initial node and calculates the tightness between the initial node and the adjacent nodes. Adjacent nodes are gradually added to the community, and finally the community structure of the initial node is obtained. Meanwhile, this method can detect the global network community. We apply the proposed method to the Zachary karate club network and dolphin social network, and experimental results demonstrate its accuracy and feasibility.

Key words: local community;community detection;clustering coefficient

樊梦佳1,钮艳2,杜翠兰2,张仰森1. 一种基于聚集系数的社区发现算法[J]. J4, 2016, 38(02): 363-369.

FAN Mengjia1,NIU Yan2,DU Cuilan2,ZHANG Yangsen1. A community detection method based on clustering coefficient [J]. J4, 2016, 38(02): 363-369.

参考文献［10］

［1］	Huang Faliang,Zhang Shichao,Zhu Xiaofeng.Discovering network community based on multiobjective optimization［J］.Journal of Software,2013,24（9）:20622077.（in Chinese）
［2］	Newman M E J,Girvan M.Finding and evaluating community structure in networks ［J］.Phys Rev E,2004,69:026113.
［3］	Hu Jian,Yang Bingru.Community structure discovery algorithm based on edge clustering coefficient［J］.Application Research of Computers,2009,26（3）:858859.（in Chinese）
［4］	Wang Lei,Lü Qiang,Li Yafei,et al.A local optimised community discovery algorithm based on individualcentred theory［J］.Computer Applications and Software,2010,27 （10）:269271.（in Chinese）
［5］	Zhang Rui.Community detection algorithm based on node clustering coefficient and edge cluster coefficient［D］.Kunming:Yunnan University,2013.（in Chinese）
［6］	Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research,1977,33（4）:452473.
［7］	Li Kongwen,Gu Qing,Zhang Yao,et al.Local community detecting method based on the clustering coefficient［J］.Computer Science,2010,37（7）:4649.（in Chinese）
［8］	Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of longlasting associations—Can geographic isolation explain this unique trait？［J］.Behavioral Ecology and Sociobiology,2003,54（4）:396405.
［9］	Lusseau D,Newman M E J.Identifying the role that animals play in their social networks［J］.Proceeding of the Royal Society B:Biological Sciences,2004,271（Suppl_6）:S477S481.
［10］	Wang Xuekai,Ma Yinghong.Complex networks community detection algorithm based on clustering coefficient ［J］.Network Security Technology & Application,2012 （9）:5355.（in Chinese）
	附中文参考文献：
［1］	黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法［J］.软件学报,2013,24（9）:20622077.
［3］	胡健,杨炳儒.基于边聚集系数的社区结构发现算法［J］.计算机应用研究,2009,26（3）:858859.
［4］	王磊,吕强,李亚飞,等.一种基于个体中心论的局部优化社区发现算法［J］.计算机应用与软件,2010,27（10）:269271.
［5］	张睿.基于点聚集系数和边聚集系数的社区发现算法［D］.昆明：云南大学,2013.
［7］	李孔文,顾庆,张尧,等.一种基于聚集系数的局部社团划分算法［J］.计算机科学,2010,37（7）:4649.
［10］	王学凯,马英红.一种基于聚集系数的复杂网络社团划分算法［J］.网络安全技术与应用,2012 （9）:5355.

[1]	昌阳, 马慧芳, . 基于染色随机游走的可重叠社区发现[J]. 计算机工程与科学, 2022, 44(05): 834-844.
[2]	皇甫斐斐, 杨阳, 邓晓懿, . 基于节点影响力的理性节点标签传播算法[J]. 计算机工程与科学, 2022, 44(04): 713-722.
[3]	张士进, 张胜, 田纪彪, 吴志强, 戴维凯. 基于深度编码器的复杂网络社区发现算法 #br# [J]. 计算机工程与科学, 2020, 42(09): 1640-1648.
[4]	昌阳, 马慧芳, . 融合结构与属性视图的可重叠社区发现算法[J]. 计算机工程与科学, 2020, 42(08): 1506-1513.
[5]	邱云飞，陈昂. 微博社区的动态节点自适应增量交互优化[J]. 计算机工程与科学, 2019, 41(02): 370-377.
[6]	李慧，杨青泉，王慧慧. 一种基于局部扩展优化的重叠社区发现算法[J]. 计算机工程与科学, 2018, 40(12): 2258-2264.
[7]	郑伟涛1，吴永亮1，郭芳琳1，闫光辉1，何力2. 基于链接分析和用户兴趣的微博社区发现算法[J]. 计算机工程与科学, 2017, 39(04): 804-812.
[8]	吴永亮,郑伟涛,郭芳琳,闫光辉. 一种基于信息扩散的复杂网络重叠社区发现算法[J]. J4, 2016, 38(04): 792-799.