|Table of Contents|

An Overlapping Community Detection AlgorithmBased on Asymmetric Triangle Cuts(PDF)

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

Issue:
2022年01期
Page:
1-8
Research Field:
机器学习
Publishing date:

Info

Title:
An Overlapping Community Detection AlgorithmBased on Asymmetric Triangle Cuts
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
PACS:
TP39
DOI:
10.3969/j.issn.1672-1292.2022.01.001
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.

Memo

Memo:
-
Last Update: 2022-03-15