Computer Science ›› 2022, Vol. 49 ›› Issue (9): 83-91.doi: 10.11896/jsjkx.220400146

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

Community Detection Algorithm Based on Node Stability and Neighbor Similarity

ZHENG Wen-ping1,2,3, LIU Mei-lin1, YANG Gui1   

  1. 1 School of Computer & Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computation Intelligence and Chinese Information Processing,Ministry of Education,Shanxi University,Taiyuan 030006,China
    3 Institute of Intelligent Information Processing,Shanxi University,Taiyuan 030006,China
  • Received:2022-04-14 Revised:2022-06-03 Online:2022-09-15 Published:2022-09-09
  • 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 network science and bioinformatics,etc.
  • Supported by:
    National Natural Science Foundation of China(62072292) and 1331 Engineering Project of Shanxi Province,China.

Abstract: With the increase of the scale of complex network,community structure becomes more complex.The relationship between nodes and communities become more diversified.It is expected to improve community detection algorithm performance by effectively measuring the community structure and dealing with the nodes with different certainty of community belonging.This paper proposes a community detection algorithm based on node stability and neighbor similarity.Firstly,label entropy of nodes is defined to measure node stability and the nodes with low label entropy are selected as stable node sets.Then the neighbor simila-rity is defined according to the label of node neighbor and the community belonging consistency of nodes and their neighbors is measured.The initial network is constructed by using the node with the highest neighbor similarity between the stable node and its neighbor,and the initial community detection results with high reliability are obtained by running label propagation algorithm on the subnetwork.The unclustered nodes are allocated to the community of the node with the highest Katz similarity.The final result of community detection is obtained by merging small-scale communities.Compared with LPA,BGLL,Walktrap,Infomap,LPA-S and other classical algorithms,experimental results show that the NSNSA algorithm performs well in modularity and NMI.

Key words: Complex network, Community structure, Label entropy, Node stability, Neighbor similarity

CLC Number: 

  • TP391
[1]NEWMAN M E J.Networks:An Introduction[M].Oxford University Press,2010.
[2]JIA S W,GAO L,GAO Y,et al.Exploring triad-rich substructures by graph-theoretic characterizations in complex networks[J].Physica A:Statistical Mechanics and its Applications,2017,468(2017):53-69.
[3]HIDEHIKO I,MINEICHI K,ATSUYOSHI N.Partitioning of web graphs by community topology[C]//Proceedings of the 14th International Conference on World Wide.New York,ACM Press,2005:661-669.
[4]DENG K,ZHANG J P,YANG J.Mobile recommendation based on link community detection[J].The Scientific World Journal,2014:8(26):259156.
[5]FARUTIN V,ROBISON K,LIGHTCAP E,et al.Edge Count probabilities for the identification of local protein communities and their organization[J].Proteins:Structure,Function,and Bioinformatics,2006,62(3):800-818.
[6]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.
[7]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):P10008.
[8]TRAAG V A,WALTMAN L,VAN ECK N J.From Louvain to Leiden:guaranteeing well-connected communities[J].Scientific Reports,2019,9(1):1-12.
[9]FORTUNATO S,BARTHELEMY M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States of America,2007,104(1):36-41.
[10]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.
[11]WANG T,CHEN S S,WANG X X,et al.Label propagation algorithm based on node importance[J].Physica A:Statistical Mechanics and its Applications,2020,551(2020):124137.
[12]LI W,HUANG C,WANG M,et al.Stepping community detection algorithm based on label propagation and similarity[J].Physica A:statistical Mechanics and Its Applications,2017,472:145-155.
[13]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences of the United States of America,2008,105(4):1118-1123.
[14]PONS P,LATAPY M.Computing communities in large net-works using random walks[J].Journal of Graph Algorithms and Applications,2006,10(2):191-218.
[15]ZHENG W P,CHE C H,QIAN Y H,et al.A two-stage community detection algorithm based on label propagation[J].Journal of Computer Research and Development,2018,55(9):1959-1971.
[16]LANCICHINETTI A,FORTUNATO S,KERTESZ J.Detec-ting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[17]SHEN H W,CHENG X Q,CAI K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A:Statistical Mechanics and its Applications,2009,388(8):1706-1712.
[18]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[19]LUSSEAU D,NEWMAN M E J.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society B:Biological Sciences,2004,271(Suppl 6):S477-S481.
[20]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[1] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[2] YANG Bo, LI Yuan-biao. Complex Network Analysis on Curriculum System of Data Science and Big Data Technology [J]. Computer Science, 2022, 49(6A): 680-685.
[3] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[4] CHEN Shi-cong, YUAN De-yu, HUANG Shu-hua, YANG Ming. Node Label Classification Algorithm Based on Structural Depth Network Embedding Model [J]. Computer Science, 2022, 49(3): 105-112.
[5] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[6] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[7] MU Jun-fang, ZHENG Wen-ping, WANG Jie, LIANG Ji-ye. Robustness Analysis of Complex Network Based on Rewiring Mechanism [J]. Computer Science, 2021, 48(7): 130-136.
[8] HU Jun, WANG Yu-tong, HE Xin-wei, WU Hui-dong, LI Hui-jia. Analysis and Application of Global Aviation Network Structure Based on Complex Network [J]. Computer Science, 2021, 48(6A): 321-325.
[9] WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[10] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[11] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[12] HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30.
[13] LIU Sheng-jiu, LI Tian-rui, XIE Peng, LIU Jia. Measure for Multi-fractals of Weighted Graphs [J]. Computer Science, 2021, 48(3): 136-143.
[14] GONG Zhui-fei, WEI Chuan-jia. Link Prediction of Complex Network Based on Improved AdaBoost Algorithm [J]. Computer Science, 2021, 48(3): 158-162.
[15] GONG Zhui-fei, WEI Chuan-jia. Complex Network Link Prediction Method Based on Topology Similarity and XGBoost [J]. Computer Science, 2021, 48(12): 226-230.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!