一种基于局部路径信息的重叠社区发现算法

doi:10.11896/jsjkx.220500190

Computer Science ›› 2022, Vol. 49 ›› Issue (12): 155-162.doi: 10.11896/jsjkx.220500190

• Database & Big Data & Data Science • Previous Articles Next Articles

Overlapping Community Detection Algorithm Based on Local Path Information

ZHENG Wen-ping^1,2,3, WANG Ning¹, YANG Gui¹

1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
2 Key Laboratory of Computational 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

Received:2022-05-19 Revised:2022-08-27 Published:2022-12-14
About author:ZHENG Wen-ping,born in 1979,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.Her main research interests include graph theory algorithms and bioinformatics.
Supported by:
National Natural Science Foundation of China(62072292) and 1331 Engineering Project of Shanxi Province,China.

Abstract

Abstract: The detection of overlapping communities is one of the main tasks of complex network analysis.The performance of most existing methods based on local expansion and optimization are greatly affected by the selection of initial seed nodes and the community structure significance measurement.Aiming at these problems,an overlapping community detection algorithm is proposed based on local path information(LPIO).First,the local maximum degree points are selected as initial seeds,which will be updated according to the label consistency of node’s neighborhood in the community to reduce the influence of the selection of initial seeds.To measure the various connection patterns between nodes in networks,a community fitness function is defined based on local path information to obtain community structures from seed nodes.Finally,unclustered nodes are assigned to proper communities according to the number of non-repetitive paths between the unclustered nodes and the community seed sets.Comparative experiments on 4 labeled networks and 8 unlabeled networks with 7 classic overlapping community detection algorithms show that the proposed algorithm performs well on overlapping standard mutual information(ONMI),F₁ score,and extended modularity(EQ).

Key words: Overlapping community detection, Local expansion and optimization, Community fitness, Local path information

CLC Number:

TP391

ZHENG Wen-ping, WANG Ning, YANG Gui. Overlapping Community Detection Algorithm Based on Local Path Information[J].Computer Science, 2022, 49(12): 155-162.

References

[1]CHENG F,WANG C,ZHANG X,et al.A local-neighborhood information based overlapping community detection algorithm for large-scale complex networks[J].IEEE/ACM Transactions on Networking,2020,29(2):543-556.
[2]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.
[3]JABBOUR S,MHADHBI N,RADAOUI B,et al.Detectinghighly overlapping community structure by model-based maximal clique expansion[C]//2018 IEEE International Conference on Big Data(Big Data).IEEE,2018:1031-1036.
[4]GREGORY S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018.
[5]XIE J,SZYMANSKI B K,LIU X.SLPA:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//2011 IEEE 11th International Conference on Data Mining Workshops.IEEE,2011:344-349.
[6]LU M,ZHANG Z,QU Z,et al.LPANNI:Overlapping community detection using label propagation in large-scale complex networks[J].IEEE Transactions on Knowledge and Data Enginee-ring,2018,31(9):1736-1749.
[7]LUO W,ZHANG D,NI L,et al.Multiscale local community detection in social networks[J].IEEE Transactions on Knowledge and Data Engineering,2021,33(3):1102-1112.
[8]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.
[9]LEE C,REID F,MCDAID A,et al.Detecting highly overlapping community structure by greedy clique expansion[C]//Procee-dings of the 4th International Workshop on Social Network Mi-ning and Analysis(SNA-KDD).2010:33-42.
[10]WANG X,LIU G,LI J.Overlapping community detection based on structural centrality in complex networks[J].IEEE Access,2017,5:25258-25269.
[11]REZVANI M,LIANG W,LIU C,et al.Efficient detection of overlapping communities using asymmetric triangle cuts[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(11):2093-2105.
[12]CHOUMANE A,AWADA A,HARKOUS A.Core expansion:A new community detection algorithm based on neighborhood overlap[J].Social Network Analysis and Mining,2020,10(1):1-11.
[13]RADICCHI F,CASTELLANO C,CECCONI F,et al.Definingand identifying communities in networks[J].Proceedings of the National Academy of Sciences,2004,101(9):2658-2663.
[14]KANNAN R,VEMPALA S,VETTA A.On clusterings:Good,bad and spectral[J].Journal of the ACM(JACM),2004,51(3):497-515.
[15]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.
[16]CARNIVALI G S,VIEIRA A B,ZIVIANI A,et al.CoVeC:coarse-grained vertex clustering for efficient community detection in sparse complex networks[J].Information Sciences,2020,522:180-192.
[17]FORTUNATO S,BARTHELEMY M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences,2007,104(1):36-41.
[18]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.
[18]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.Demon:a local-first discovery method for overlapping communities[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2012:615-623.
[20]SOUNDARAJAN S,HOPCROFT J E.Use of local group information to identify communities in networks[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2015,9(3):1-27.
[21]CHAKRABORTY T,DALMIA A,MUKHERJEE A,et al.Metrics for community analysis:A survey[J].ACM Computing Surveys(CSUR),2017,50(4):1-37.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Overlapping Community Detection Algorithm Based on Local Path Information

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 8

Metrics

Comments

Recommended 0

[1]	DUAN Xiao-hu, CAO Fu-yuan. Node Local Similarity Based Two-stage Density Peaks Algorithm for Overlapping Community Detection [J]. Computer Science, 2022, 49(12): 170-177.
[2]	CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[3]	NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[4]	XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[5]	ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
[6]	ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model [J]. Computer Science, 2020, 47(10): 75-82.
[7]	LIU Chun, ZHANG Guo-liang. Software Feature Extraction Method Based on Overlapping Community Detection [J]. Computer Science, 2019, 46(12): 201-207.
[8]	ZHANG Zhong-zheng and LI Jian-wu. Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion [J]. Computer Science, 2016, 43(9): 61-65.