Computer Science ›› 2022, Vol. 49 ›› Issue (11A): 211100002-7.doi: 10.11896/jsjkx.211100002

• Big Data & Data Science • Previous Articles     Next Articles

Community Discovery Method Based on Influence of Core Nodes

YUAN Hui-lin1, HAN Zhen2, FENG Chong2, HUANG Bi2, LIU Jun-tao2   

  1. 1 College of Management,Northeastern University at Qinhuangdao,Qinhuangdao,Hebei 066004,China
    2 College of Information Science and Engineering,Northeastern University,Shenyang,110819,China
  • Online:2022-11-10 Published:2022-11-21
  • About author:YUAN Hui-lin,born in 1969,Ph.D,professor.Her main research interests include modeling and optimization of complex systems,information retrieval,artificial intelligence.
    HAN Zhen,born in 1998,postgraduate.His main research interests include complex network and artificial intelligence.
  • Supported by:
    Northeastern University:Industry University Research Strategic Cooperation Project(71971050).

Abstract: Community discovery is a hot topic in the field of complex networks.Many local community detection algorithms have been proposed to quickly discover high-quality communities,but most of them have seed-dependent or stability problems.Some algorithms try to accurately find the seed nodes according to the topology characteristics of the core nodes that they are highly surrounded by neighbors and far away from each other to avoid the above problems.But the calculation of distance makes its time complexity is high.In this paper,a community detection method based on influence of core nodes(CDIC) is proposed.This me-thod first searches for all possible core nodes according to the topological characteristics of core nodes and network adjacency information.Then it uses the higher influential of true core nodes and the idea of label propagation to expand the communities and eliminate nodes wrongly selected as the core to avoid the seed-dependent problems.Besides,the calculation without distance also ensures low time complexity.Finally,a community attraction to nodes based on the similarity theory is proposed to merge specific nodes to ensure the stability of the results.The normalized mutual information and purity of the proposed method,6 classic algorithms and 2 algorithms proposed in recent years are compared on 64 artificial networks and 4 real networks.The results show the effectiveness of CDIC.

Key words: Complex network, Community discovery, Core node, Influence, Community attraction

CLC Number: 

  • TP311
[1]SUN Z,SUN Y,CHANG X,et al.Community detection based on the Matthew effect[J].Knowledge-Based Systems,2020,205:106256.
[2]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[3]ZHANG Y,LIU Y,LI Q,et al.Lilpa:A label importance based label propagation algorithm for community detection with application to core drug discovery[J].Neurocomputing,2020,413:107-133.
[4]CHEN Z,XIE Z,ZHANG Q.Community detection based on local topological information and its application in power grid[J].Neurocomputing,2015,170:384-392.
[5]BAHULKAR A,SZYMANSKI B K,BAYCIK N O,et al.Community detection with edge augmentation in criminal networks[C]//2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining(ASONAM).IEEE,2018:1168-1175.
[6]ALSINI A,DATTA A,HUYNH D Q,et al.Community aware personalized hashtag recommendation in social networks[C]//Australasian Conference on Data Mining.Singapore:Springer,2018:216-227.
[7]ZHAO W J,ZHANG F B,LIU J L,Research progress of complex network community discovery[J].Computer Science,2020,47(2):10-20.
[8]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2004,69(6):066133.
[9]YUAN Q,LIU B.Community detection via an efficient nonconvex optimization approach based on modularity[J].Computational Statistics & Data Analysis,2021,157:107163.
[10]GUIMERA R,AMARAL L A N.Functional cartography ofcomplex metabolic networks[J].Nature,2005,433(7028):895-900.
[11]SHANG R,BAI J,JIAO L,et al.Community detection based on modularity and an improved genetic algorithm[J].Physica A,2013,392(5):1215-1231.
[12]FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486(3/4/5):75-174.
[13]NEWMAN M E J.Finding community structure in networksusing the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.
[14]NEWMAN M E J,LEICHT E A.Mixture models and exploratory analysis in networks[J].Proceedings of the National Aca-demy of Sciences,2007,104(23):9564-9569.
[15]PONS P,LATAPY M.Computing communities in large net-works using random walks[C]//International Symposium on Computer and Information Sciences.Berlin:Springer,2005:284-293.
[16]FANRONG M,MU Z,YONG Z,et al.Local Community Detection in Complex Networks Based on Maximum Cliques Extension [J].Mathematical Problems in Engineering,2014(2014):1-12.
[17]QI X,TANG W,WU Y,et al.Optimal local community detection in social networks based on density drop of subgraphs[J].Pattern Recognition Letters,2014,36:46-53.
[18]BERAHMAND K,BOUYER A,VASIGHI M.Community detection in complex networks by detecting and expanding core nodes through extended local similarity of nodes[J].IEEE Transactions on Computational Social Systems,2018,5(4):1021-1033.
[19]LIU S,XIA Z.A two-stage BFS local community detection algorithm based on node transfer similarity and Local Clustering Coefficient[J].Physica A:Statistical Mechanics and its Applications,2020,537:122717.
[20]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.
[21]BAGROW J P,BOLLT E M.Local method for detecting communities[J].Physical Review E,2005,72(4):046108.
[22]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[23]YOU X,MA Y,LIU Z.A three-stage algorithm on community detection in social networks[J].Knowledge-Based Systems,2020,187:104822.
[24]DENG Z H,QIAO H H,GAO M Y,et al.Complex networkcommunity detection method by improved density peaks model[J].Physica A:Statistical Mechanics and its Applications,2019,526:121070.
[25]HENNIG C,HAUSDORF B.Design of dissimilarity measures:A new dissimilarity between species distribution areas[M]//Data Science and Classification.Berlin:Springer,2006:29-37.
[26]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.
[27]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.
[28]PAN X,XU G,WANG B,et al.A novel community detection algorithm based on local similarity of clustering coefficient in social networks[J].IEEE Access,2019,7:121586-121598.
[29]PARÉS F,GASULLA D G,VILALTAA,et al.Fluid communities:A competitive,scalable and diverse community detection algorithm[C]//International Conference on Complex Networks and Their Applications.Cham:Springer,2017:229-240.
[30]SHANG R,ZHANG W,JIAO L.Circularly searching corenodes based label propagation algorithm for community detection[J].International Journal of Pattern Recognition and Artificial Intelligence,2016,30(8):1659024.
[31]BERAHMAND K,BOUYER A.LP-LPA:A link influence-based label propagation algorithm for discovering community structures in networks[J].International Journal of Modern Physics B,2018,32(6):1850062.
[32]YAKOUBI Z,KANAWATI R.LICOD:A Leader-driven algo-rithm for community detection in complex networks[J].Vietnam Journal of Computer Science,2014,1(4):241-256.
[33]YIN C,ZHU S,CHEN H,et al.A method for community detection of complex networks based on hierarchical clustering[J].International Journal of Distributed Sensor Networks,2015,11(6):849140.
[34]WANG X,LIU G,LI J,et al.Locating structural centers:A density-based clustering method for community detection[J].PloS One,2017,12(1):e0169355.
[35]STREHL A,GHOSH J.Cluster ensembles-a knowledge reuseframework for combining multiple partitions[J].Journal of Machine Learning Research,2002,3(Dec):583-617.
[36]ZHAO Y,KARYPIS G.Empirical and theoretical comparisons of selected criterion functions for document clustering[J].Machine Learning,2004,55(3):311-331.
[37]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[38]ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[39]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[40]ADAMIC L A,GLANCE N.The political blogosphere and the 2004 US election:divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery.2005:36-43.
[1] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[2] KONG Shi-ming, FENG Yong, ZHANG Jia-yun. Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph [J]. Computer Science, 2022, 49(9): 221-227.
[3] HE Qiang, YIN Zhen-yu, HUANG Min, WANG Xing-wei, WANG Yuan-tian, CUI Shuo, ZHAO Yong. Survey of Influence Analysis of Evolutionary Network Based on Big Data [J]. Computer Science, 2022, 49(8): 1-11.
[4] 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.
[5] HE Yi-chen, MAO Yi-jun, XIE Xian-fen, GU Wan-rong. Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation [J]. Computer Science, 2022, 49(6A): 272-279.
[6] 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.
[7] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[8] 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.
[9] TANG Chun-yang, XIAO Yu-zhi, ZHAO Hai-xing, YE Zhong-lin, ZHANG Na. EWCC Community Discovery Algorithm for Two-Layer Network [J]. Computer Science, 2022, 49(4): 49-55.
[10] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[11] 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.
[12] SHAO Yu, CHEN Ling, LIU Wei. Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model [J]. Computer Science, 2022, 49(2): 204-215.
[13] 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.
[14] PAN Yu, WANG Shuai-hui, ZHANG Lei, HU Gu-yu, ZOU Jun-hua, WANG Tian-feng, PAN Zhi-song. Survey of Community Detection in Complex Network [J]. Computer Science, 2022, 49(11A): 210800144-11.
[15] YUAN Hui-lin, FENG Chong. Ranking and Recognition of Influential Nodes Based on k-shell Entropy [J]. Computer Science, 2022, 49(11A): 210800177-5.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!