[1]郑文萍,毕欣琦,杨 贵.一种基于非对称三角形割的重叠社区发现算法[J].南京师范大学学报(工程技术版),2022,22(01):001-8.[doi:10.3969/j.issn.1672-1292.2022.01.001]
　Zheng Wenping,Bi Xinqi,Yang Gui.An Overlapping Community Detection AlgorithmBased on Asymmetric Triangle Cuts[J].Journal of Nanjing Normal University(Engineering and Technology),2022,22(01):001-8.[doi:10.3969/j.issn.1672-1292.2022.01.001]
点击复制

一种基于非对称三角形割的重叠社区发现算法
分享到：

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
22卷
期数:
2022年01期
页码:
001-8
栏目:
机器学习
出版日期:
2022-03-15

文章信息/Info

Title:
An Overlapping Community Detection AlgorithmBased on Asymmetric Triangle Cuts
文章编号:
1672-1292(2022)01-0001-08
作者:
郑文萍1; 2; 3; 毕欣琦1; 杨 贵1
(1.山西大学计算机与信息技术学院,山西 太原 030006)(2.山西大学计算智能与中文信息处理教育部重点实验室,山西 太原 030006)(3.山西大学智能信息处理研究所,山西 太原 030006)
Author(s):
Zheng Wenping1; 2; 3; Bi Xinqi1; Yang Gui1
(1.School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China)(2.Key Laboratory of Computation Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China)(3.Institute of Intelligent Information Processing,Shanxi University,Taiyuan 030006,China)
关键词:
复杂网络; 社区发现; 重叠社区发现算法; 非对称三角形割; 社区适应度
Keywords:
complex network; community detection; overlapping community detection algorithm; asymmetric triangle cut; community fitness
分类号:
TP39
DOI:
10.3969/j.issn.1672-1292.2022.01.001
文献标志码:
A
摘要:
发现由相似功能的个体所形成的社区结构是复杂网络分析的重要任务之一. 提出一种基于非对称三角形割的重叠社区发现算法,首先根据社区内三角形连接情况对社区质量进行评价,并根据节点与社区的三角形连接定义了节点对社区的归属度和连接强度. 考虑到网络不同部分连接密度的差异,在将节点从社区中移除或加入社区的过程中,为每个节点分别设置了不同的移除阈值和扩展阈值,以提高社区发现质量. 将每个节点与其邻居节点组成初始社区,将归属度低于移除阈值的边缘节点从社区中移除,将连接强度高于扩展阈值的外围节点加入社区,社区节点移除和扩展阶段迭代进行直至社区结构趋于稳定,最后去掉重叠率过高的社区得到最终结果. 在7个带社区标签的网络上将所提算法与其他7个经典重叠社区检测算法进行比较,通过重叠标准互信息和F1指标进行评价,结果表明所提算法可以较好地发现不同规模网络中的社区结构.
Abstract:
Overlapping community detection has attracted more and more attention in the research of complex networks. An overlapping community detection algorithm has been presented based on asymmetric triangle cuts(ATCO). The fitness of a community is defined as the ratio of the triangles within the community and the asymmetric triangle cuts. Furthermore,the membership and connection strength of a node to a community is defined according to the triangle connection between the node and the community. Considering that difference parts of the complex network usually have different link density,we compute specific removal threshold and extension threshold to each node in community reduction and expansion process. ATCO algorithm consists of three main processes:community initialization,node removal and extension,and high overlapping community removing. An initial community consists of a node and its neighbors,and the neighbors are the periphery of the initial community. A peripheral node will be removed from the community,if its membership to the community is lower than the predefined removal threshold. An external node will be added to a community,if its connection strength to the community is higher than the predefined extension threshold. The removal and extension process will be performed iteratively until a stable result is obtained. Finally,communities with high overlap will be postprocessed. Compared with other 7 classical overlapping community detection algorithms on 7 networks with ground-truth,the proposed algorithm ATCO shows good performance in overlapping standard mutual information and F1 index.

参考文献/References:

[1] JAVED M A,YOUNIS M S,LATIF S,et al. Community detection in networks:a multidisciplinary review[J]. Journal of Network and Computer Applications,2018,108:87-111.
[2]YANG J,LESKOVEC J. Defining and evaluating network communities based on ground-truth[J]. Knowledge and Information Systems,2015,42(1):181-213.
[3]杨蒙蒙,王水花,陈燚,等. 生物地理学优化算法与应用综述[J]. 南京师范大学学报(工程技术版),2018,18(2):50-55.
[4]王俊淑,张国明,胡斌. 基于深度学习的推荐算法研究综述[J]. 南京师范大学学报(工程技术版),2018,18(4):33-43.
[5]PALLA G,DERéNYI I,FARKAS I,et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature,2005,435(7043):814-818.
[6]MAGDON-ISMAIL M,PURNELL J. SSDE-Cluster:fast overlapping clustering of networks using sampled spectral distance embedding and GMMs[C]//Proceedings of the 2011 IEEE 3rd International Conference on Social Computing. Boston,USA:IEEE,2011:756-759.
[7]YANG J,LESKOVEC J. Overlapping community detection at scale:a nonnegative matrix factorization approach[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. Rome,Italy:ACM,2013:587-596.
[8]GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics,2010,12(10):2011-2024.
[9]XIE J R,SZYMANSKI B K,LIU X M. SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proceedings of the IEEE 11th International Conference on Data Mining Workshops. Vancouver,Canada:IEEE,2011:344-349.
[10]BAUMES J,GOLDBERG M K,KRISHNAMOORTHY M S,et al. Finding communities by clustering a graph into overlapping subgraphs[C]//Proceedings of the 2005 IADIS International Conference on Applied Computing. Algarve,Portugal:DBLP,2005:97-104
[11]CLAUSET A. Finding local community structure in networks[J]. Physical Review E,Statistical,Nonlinear,and Soft Master Physics,2005,72(2 Pt 2):026132.
[12]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.
[13]BANDYOPADHYAY S,CHOWDHARY G,SENGUPTA D. FOCS:fast overlapped community search[J]. IEEE Transactions on Knowledge and Data Engineering,2015,27(11):2974-2985.
[14]YADAV N. Community-affinity:measuring strength of memberships of nodes in network communities[D]. Salt Lake City:University of Utah,2015.
[15]SOUNDARAJAN S,HOPCROFT J E. Use of local group information to identify communities in networks[J]. ACM Transactions on Knowledge Discovery from Data,2015,9(3):1-27.
[16]EPASTO A,LATTANZI S,LEME R P. Ego-splitting framework:from non-overlapping to overlapping clusters[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax,Canada:ACM,2017:145-154.
[17]ZHANG Y,PARTHASARATHY S. Extracting analyzing and visualizing triangle k-core motifs within networks[C]//Proceedings of the 2012 IEEE 28th International Conference on Data Engineering. Arlington,USA:IEEE,2012:1049-1060.
[18]BENSON A R,GLEICH D F,LESKOVEC J. Higher-order organization of complex networks[J]. Science,2016,353(6295):163-166.
[19]REZVANI M,LIANG W F,LIU C F,et al. Efficient detection of overlapping communities using asymmetric triangle cuts[J]. IEEE Transactions on Knowledge and Data Engineering,2018,30(11):2093-2105.
[20]KANNAN R,VEMPALA S,VETA A. On clusterings-good,bad and spectral[J]. Journal of the ACM,2004,51(3):497-515.
[21]CHAKRABORTY T,DALMIA A,MUKHERJEE A,et al. Metrics for community analysis:a survey[J]. ACM Computing Surveys,2017,50(4):1-37.
[22]ROSSETTT G,PAPPALARDO L,RINZIVILLO S. A novel approach to evaluate community detection algorithms on ground truth[C]//Proceedings of the 7th Workshop on Complex Networks CompleNet. Dijon,France:Springer,2016:133-144.

相似文献/References:

[1]滕 野,张 莉,吴凤连.基于航空运输的中国城市体系等级结构与空间联系[J].南京师范大学学报(工程技术版),2020,20(02):072.[doi:10.3969/j.issn.1672-1292.2020.02.011]
　Teng Ye,Zhang Li,Wu Fenglian.Hierarchical Structure and Spatial Connection of Chinese UrbanSystem Based on Air Transportation[J].Journal of Nanjing Normal University(Engineering and Technology),2020,20(01):072.[doi:10.3969/j.issn.1672-1292.2020.02.011]
[2]刘胜久,伍小兵,曹小平,等.有向超图的超网络能量及其性质[J].南京师范大学学报(工程技术版),2022,22(04):036.[doi:10.3969/j.issn.1672-1292.2022.04.005]
　Liu Shengjiu,Wu Xiaobing,Cao Xiaoping,et al.Hypernetwork Energy of Directed Hypergraphs and Its Properties[J].Journal of Nanjing Normal University(Engineering and Technology),2022,22(01):036.[doi:10.3969/j.issn.1672-1292.2022.04.005]
[3]刘胜久,伍小兵,曹小平,等.交叉抽样在复杂网络中的研究与应用[J].南京师范大学学报(工程技术版),2023,23(01):084.[doi:10.3969/j.issn.1672-1292.2023.01.011]
　Liu Shengjiu,Wu Xiaobing,Cao Xiaoping,et al.Research and Application of Cross Sampling on Complex Network[J].Journal of Nanjing Normal University(Engineering and Technology),2023,23(01):084.[doi:10.3969/j.issn.1672-1292.2023.01.011]

备注/Memo

备注/Memo:
收稿日期:2021-08-31.
基金项目:国家自然科学基金项目(62072292、62006145)、山西省自然科学基金项目(201801D121123).
通讯作者:郑文萍,博士,教授,研究方向:复杂网络分析、图聚类算法. E-mail:wpzheng@sxu.edu.cn
更新日期/Last Update: 2022-03-15