Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (2): 10-20.doi: 10.11896/jsjkx.190100214

Special Issue: Network and communication

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

Review on Community Detection in Complex Networks

ZHAO Wei-ji1,2,ZHANG Feng-bin1,LIU Jing-lian2,3   

  1. (School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China)1;
    (School of Information Engineering,Suihua University,Suihua,Heilongjiang 152061,China)2;
    (School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China)3
  • Received:2019-01-25 Online:2020-02-15 Published:2020-03-18
  • About author:ZHAO Wei-ji,born in 1980,doctorial student,associate professor,is member of China Computer Federation (CCF).His main research interests include community detection and data mining;ZHANG Feng-bin,born in 1965,Ph.D,professor,Ph.D supervisor,is member of China Computer Federation (CCF).His main research interests include network security and intrusion detection technology.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61172168, 61772122) and Fundamental Research Funds for the Universities of Heilongjiang Provincial Department of Education of China (KYYWF10236180104, KYYWF10236180207).

PDF (PC)

3505

Abstract: In recent years,with the rapid development of modern network communication and social media technologies,complex network has become one of the frontier hotspots of interdisciplinary research.As an important problem in the research of complex network,community detection has important theoretical significance and application value,and has attracted increasing attention.Many community detection algorithms and reviews have been proposed.However,most of the existing reviews on community detection focus on a particular direction or field.On the basis of previous work,this paper did deep research in the community detection algorithms,and gave a review on the research progress of community detection.Firstly,this paper gave the definition of community detection and evaluation measurements for different network structure.Then,this paper introduced the classic community detection algorithms on different network structure,including the global community detection and local community detection algorithms on homogeneous networks,community detection on heterogeneous network,and community detection on link structure combined with node content,as well as the dynamic network community detection and community evolution.Finally,this paper briefly introduced the typical applications of community discovery in the real world,including impact maximization,link prediction and emotion analysis application.In addition,this paper discussed the challenges in the current community discovery field.This paper try to draw a clearer and more comprehensive outline for the community detection research field,and provide a good guide for beginners in the community detection.

Key words: Community detection, Community structure, Dynamic network, Heterogeneous network, Homogeneous network

CLC Number: 

  • TP391
[1]BARABASI A L,ALBERT R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.
[2]WATTS D J,STROGATZ S H.Collective Dynamics of Small-world Networks[J].Nature,1998,393(6684):440-442.
[3]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.
[4]CHENG X Q,SHEN H W.Community Structure of Complex Networks[J].Complex Systems & Complexity Science,2011,8(1):57-70.
[5]TYLER J R,WILKINSON D M,HUBERMAN B A.E-Mail as Spectroscopy:Automated Discovery of Community Structure within Organizations[J].The Information Society,2005,21(2):143-153.
[6]PALLA G,DERENYI I,FARKAS T,et al.Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society.Nature,2005,435(7043):814-818.
[7]JIN D,LIU J,JIA Z X,et al.K-nearest-neighbor Network based Data Clustering Algorithm[J].Pattern Recognition & Artificial Intelligence,2010,23(4):546-551.
[8]NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in networks[J].Physical Review E,2004,69(2):026113-1-026113-16.
[9]NEWMAN M E J.Fast Algorithm for Detecting Community Sructure in Networks.Physical Review E,2004,69(6):066133-1-066133-5.
[10]SHANG R H,BAI J J,LI C,et al.Community Detection based on Modularity and an Improved Genetic Algorithm[J].Physica A Statistical Mechanics & Its Applications,2013,392(5):1215-1231.
[11]NEWMAN M E J.Analysis of Weighted Networks[J].Physical Review E,2004,70(5):056131-1-056131-9.
[12]NICOSIA V,MANGIONI G,CARCHIOLO V,et al.Extending the Definition of Modularity to Directed Graphs with Overlapping Communities[J].Journal of Statistical Mechanics Theory and Experiment,2009,3:3166-3168.
[13]SHEN H,CHENG X,CAI K,et al.Detect Overlapping and Hierarchical Community Structure in Networks[J].Physica A,2009,388(8):1706-1712.
[14]LIU J L,WANG D L,ZHAO W J,et al.A Community Mining Algorithm based on Core Nodes Expansion[J].Journal of Shandong university(Natural Science),2016,51(1):106-114.
[15]FORTUNATO S.Community Detection in Graphs[J].Physics Reports,2010,486(3):75-174.
[16]XIE J,KELLEY S,SZYMANSKI B K.Overlapping Community Detection in Networks:The state-of-the-art and Comparative Study[J].Acm Computing Surveys,2013,45(4):1-35.
[17]LIU D Y,JIN D,HE D X,et al.Community Mining in Complex Networks[J].Journal of Computer Research & Development,2013,50(10):2140-2154.
[18]YANG Z,ALGESHEIMER R,TESSONE C J.A Comparative Analysis of Community Detection Algorithms on Artificial Networks[J].Scientific Reports,2016,6:30750.
[19]FORTUNATO S,HRIC D.Community Detection in Networks:A User Guide[J].Physics Reports,2016,659:1-44.
[20]BAGROW J P,BOLLT E M.Local Method for Detecting Communities[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72(2):046108.
[21]CLAUSET A.Finding Local Community Structure in Networks[J].Physical Review E,2005,72(2):026132.
[22]LUO F,WANG J Z,PROMISLOW E.Exploring Local Community Structures in Large Networks[C]∥IEEE/WIC/ACM International Conference on Web Intelligence.IEEE,2006:233-239.
[23]CHEN Q,WU T T,FANG M.Detecting Local Community Structures in Complex Networks Based on Local Degree Central Nodes[J].Physica A Statistical Mechanics & Its Applications,2013,392(3):529-537.
[24]YANG L,JI X S,LIU C X,et al.Detecting Local Community Structure Based on the Identification of Boundary Nodes in Complex Networks[J].Journal of Electronics & Information Technology,2014,36(12):2809-2815.
[25]LI Y X,HE K,BINDEL D,et al.Uncovering the Small Community Structure in Large Networks:A Local Spectral Approach[J].Computer Science,2015,36(6):658-668.
[26]TABARZAD M A,HAMZEH A.A Heuristic Local Community Detection Method(HLCD)[J].Applied Intelligence,2017,46(1):62-78.
[27]MA L H,HUANG H,HE Q,et al.GMAC:A Seed-Insensitive Approach to Local Community Detection[C]∥The 15th International Conference of Data Warehousing and Knowledge Discovery.Prague Czech Republic:Springer Press,2013:297-308.
[28]ZHAO W J,ZHANG F B,LIU J L.Local Community Detection via Edge Weighting[C]∥Asia Information Retrieval Sympo-sium.Springer International Publishing,2016:68-80.
[29]LIU J L,WANG D L,ZHAO W J,et al.A Unified Framework of Lightweight Local Community Detection for Different Node Similarity Measurement[C]∥Chinese National Conference on Social Media Processing.Springer International Publishing,2017:283-295.
[30]BARBER M J.Modularity and Community Detection in Bipar-tite Networks[J].Physical Review E,2007,76(6):066102.
[31]ZHANG P,WANG J L,LI X J,et al.Clustering Coefficient and Community Structure of Bipartite Networks[J].Physica A,2008,387(27):6869-6875.
[32]SCHWARTZM L S,HANSEN L K.Bi-clique Communities[J].Physical Review E,2008,78(1):108-118.
[33]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.
[34]LIU X,MURATA T.Evaluating Community Structure in Bi-partite Networks[C]∥IEEE Second International Conference on Social Computing.IEEE,2010:576-581.
[35]XU Y,CHEN L,LI B,et al.Density-based Modularity for Evaluating Community Structure in Bipartite Networks[J].Information Sciences,2015,317:278-294.
[36]ALZAHRANI T,HORADAM K J.Community Detection in Bipartite Networks:Algorithms and Case studies[M]∥Complex Systems and Networks.Springer Berlin Heidelberg,2016:25-50.
[37]ROGER G,MARTA S P,LUIS A,et al.Module Identification in Bipartite and Directed Networks[J].Physical Review E,2007,76(3):036102.
[38]SUZUKI K,WAKITA K.Extracting Multi-facet Community Structure from Bipartite Networks[C]∥Proceedings of the Computational Science and Engineering.Vancouver,Canada,IEEE Computer Society,2009:312-319.
[39]CAI D,SHAO Z,He X F,et al.Mining Hidden Community in Heterogeneous Social Networks[C]∥Proceedings of the 3rd international workshop on Link discovery.ACM,2005:58-65.
[40]NEUBAUER N,OBERMAYER K.Community Detection in Tagging-Induced Hypergraphs[C]∥Workshop on Information in Networks.NY,USA:New York University,2010:24-25.
[41]MURATA T.Detecting Communities from Tripartite Networks[C]∥International Conference on World Wide Web.Raleigh,North Carolina,USA:DBLP,2010:1159-1160.
[42]MURATA T.A New Tripartite Modularity for Detecting Communities[J].Information & Media Technologies,2011,28:154-161.
[43]MURATA T.Detecting Communities from Social Tagging Networks Based on Tripartite Modularity[C]∥Proc.Workshop on Link Analysis in Heterogeneous Information Networks.2011:1-4.
[44]XIN L,TSUYOSHI M.Detecting Communities in K -Partite K-Uniform (Hyper)Networks[J].Journal of Computer Science and Technology,2011,26(5):778-791.
[45]JI M,HAN J,DANILEVSKY M.Ranking-based Classification of Heterogeneous Information Networks[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2011:1298-1306.
[46]PAPADOPOULOS S,KOMPATSIARIS Y,VAKALI A,et al.Community Detection in Social Media[J].Data Mining and Knowledge Discovery,2012,24(3):515-554.
[47]TANG J L,WANG X,LIU H.Integrating Social Media Data for Community Detection[C]∥International Workshops MSM and MUSE.2011:1-20.
[48]BANGCHAROENSAP P,MURATA T,KOBAYASHI H, et al.Transductive Classification on Heterogeneous Information Networks with Edge Betweenness-based Normalization[C]∥ACM International Conference on Web Search and Data Mining.ACM,2016:437-446.
[49]ZHOU Y,CHENG H,YU J X.Graph Clustering based on Structural/Attribute Similarities[J].Proceedings of the Vldb Endowment,2009,2(1):718-729.
[50]ZHOU Y,CHENG H,YU J X.Clustering Large Attributed Graphs:An Efficient Incremental Approach[C]∥2010 IEEE International Conference on Data Mining.IEEE,2010:689-698.
[51]CHENG H,ZHOU Y,YU J X.Clustering Large Attributed Graphs:A Balance between Structural and Attribute Similarities[J].Journal of Information Processing,2011,5(2):12.
[52]XU Z,KE Y,WANG Y,et al.A Model-based Approach to Attributed Graph Clustering[C]∥ACM SIGMOD International Conference on Management of Data.ACM,2012:505-516.
[53]TANG A,VIENNET E.Community Detection based on Structural and Attribute Similarities[C]∥International Conference on Digital Society (ICDS).2012:7-12.
[54]RUAN Y,FUHRY D,PARTHASARATHY S.Efficient Community Detection in Large Networks using Content and Links[C]∥International Conference on World Wide Web.ACM,2013:1089-1098.
[55]YANG J,MCAULEY J,LESKOVEC J.Community Detection in Networks with Node Attributes[C]∥IEEE 13th International Conference on Data Mining.IEEE,2013:1151-1156.
[56]YANG T B,JIN R,CHI Y,et al.Combining Link and Content for Community Detection:a Discriminative Approach[C]∥KDD.2009:927-936.
[57]ZHANG Y,LEVINA E,ZHU J.Community Detection in Networks with Node Features[J].Electronic Journal of Statistics,2016,10(2):3153-3178.
[58]LIU L,XU L,ZHEN W,et al.Community Detection Based on Structure and Content:A Content Propagation Perspective[C]∥IEEE International Conference on Data Mining.IEEE,2015:271-280.
[59]BOTHOREL C,CRUZ J D,MAGNANI M,et al.Clustering Attributed Graphs:Models,Measures and Methods[J].Network Science,2015,3(3):408-444.
[60]NEWMAN M E,CLAUSET A.Structure and Inference in Annotated Networks[J].Nature Communications,2016,7(2):11863.
[61]LI Z,PAN Z,ZHANG Y,et al.Efficient Community Detection in Heterogeneous Social Networks[J].Mathematical problems in engineering,2016:1-15.
[62]ROSSETTI G,CAZABET R.Community Discovery in Dynamic Networks:a Survey[J].ACM Computer Survey,2017,51(2).
[63]TANG L,LIU H,ZHANG J,et al.Community Evolution in Dynamic Multi-mode Networks[C]∥Proc.14th ACM Sigkdd International Conference on Knowledge Discovery & Data Mi-ning.Las Vegas,NV,USA,2008:677-685.
[64]ZHANG C Y,GUO J F.The α Relationship Communities of Set Pair Social Networks and Its Dynamic Mining Algorithms[J].Chinese Journal of Computers,2013,36(8):1682-1692.
[65]LIN W Q,DENG L,DING Z Y,et al.A new Dynamic Hierarchical Parallel Computing Community[J].Chinese Journal of Computers,2013,35(8):1712-1725.
[66]SUO B,LI Z H,CHEN Q,et al.Dynamic Community Detection based on Information Flow Analysis[J].Journal of Software,2014,25(3):547-559.
[67]WANG L,CHENG X Q.Dynamic Community in Online Social Networks[J].Chinese Journal of Computers,2015,38(2):219-237.
[68]WANG C D,LAI J H,YU P S.Dynamic Community Detection in Weighted Graph Streams[C]∥Proceedings of the 2013 SIAM International Conference on Data Mining.Society for Industrial and Applied Mathematics,2013:151-161.
[69]CHEN Y Z,SHI S,ZHU W P,et al.An Incremental Community Discovery Algorithm Based on Neighborhood Following Relationship[J].Chinese Journal of Computers,2017,40(3):570-583.
[70]MENG X,TONG Y,LIU X,et al.A Novel Dynamic Community Detection Algorithm based on Modularity Optimization[C]∥IEEE International Conference on Software Engineering and Service Science.IEEE,2017:72-75.
[71] WANG P,GAO L,MA X.Dynamic Community Detection based on Network Structural Perturbation and Topological Similarity[J].Journal of Statistical Mechanics Theory & Experiment,2017,1(1):013401.
[72] SUN Y Z,HAN J W,YAN X,et al.PathSim:Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks[J].Proceedings of the VLDB Endowment,2011,4(11):992-1003.
[73]HUANG L B,LI D Y,MA Y T,et al.A Meta-Path -Based Link Prediction Model of Heterogeneous Information Networks[J].Chinese Journal of Computers,2014(4):848-858.
[74]ZHOU X,ZHAO X,LIU Y.A Multi Objective Discrete Bat Algorithm for Community Detection in Dynamic Networks[J].Applied Intelligence,2018,48(9):3081-3093.
[75]CAO T,WU X,WANG S,et al.OASNET:an Optimal Allocation Approach to Influence Maximization in Modular Social Networks[C]∥Proceedings of the 2010 ACM Symposium on Applied Computing.ACM,2010:1088-1094.
[76]WANG Y,CONG G,SONG G,et al.Community-based Greedy Algorithm for Mining Top-k Influential Nodes in Mobile Social Networks[C]∥Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2010:1039-1048.
[77]JI J C,HUANG L,WANG Z,et al.A New Approach to Maximizing the Spread of Influence Based on Community Structure[J].Journal of JiLin University(Science Edition),2011,49(1):93-97.
[78]LV J,GUO J,REN H.A Novel Community-Based Approach for Influence Maximization in Social Network[J].International Review on Computers & Software,2013,8(1):43-49.
[79]SHANG J,ZHOU S,LI X,et al.CoFIM:A community-based framework for influence maximization on large-scale networks[J].Knowledge-Based Systems,2017,117:88-100.
[80]BOZORGI A,SAMET S,KWISTHOUT J,et al.Community-based influence maximization in social networks under a compe-titive linear threshold model[J].Knowledge-Based Systems,2017,134:149-158.
[81]XIANG P.Link Prediction of Community Network[D].Xi’an:Xidian University,2015:1.
[82]GUIMERÁ R,SALES-PARDO M.Missing and Spurious Interactions and the Reconstruction of Complex Networks[J].Proceedings of the National Academy of Sciences,2009,106(52):22073-22078.
[83]VALVERDE R J,ANDRADE L A.Link Prediction in Complex Networks-based on Cluster Information[C]∥Proc of the 21st Brazilian Conference on Advances in Artificial Intelligence.2012:92-101.
[84]VALVERDEREBAZA J,LOPES A D A.Structural Link Pre-diction Using Community Information on Twitter[C]∥Fourth International Conference on Computational Aspects of Social Networks.IEEE,2013.
[85]BISWAS A,BISWAS B.Community-based Link Prediction[J].Multimedia Tools and Applications,2017,76(18):18619-18639.
[86]SOUNDARAJAN S,HOPCROFT J.Using Community Infor-mation to Improve the Precision of Link Prediction Methods[C]∥Proceedings of the 21st International Conference on World Wide Web.ACM,2012:607-608.
[87]吴斌,张云雷.虚拟社区发现与演化[M].北京:科学出版社,2018:173-188.
[88]YANG L,CAO X C,HE D X,et al.Modularity based Community Detection with Deep Learning[C]∥Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence.AAAI Press,2016:2252-2258.
[89]DING W,LIN C,ISHWAR P.Node Embedding via Word Embedding for Network Community Discovery[J].IEEE Transactions on Signal and Information Processing over Networks,2017,3(3):539-552.
[90]CAVALLARI S,ZHENG V W,Cai H,et al.Learning Community Embedding with Community Detection and Node Embedding on Graphs[C]∥Proceedings of the 2017 ACM on Confe-rence on Information and Knowledge Management.ACM,2017:377-386.
[1] HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[2] 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.
[3] 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.
[4] 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.
[5] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[6] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[7] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[8] YANG Lin, WANG Yong-jie. Application and Simulation of Ant Colony Algorithm in Continuous Path Prediction of Dynamic Network [J]. Computer Science, 2021, 48(6A): 485-490.
[9] HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30.
[10] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[11] CHENG Yun-fei, TIAN Hong-xin, LIU Zu-jun. Collaborative Optimization of Joint User Association and Power Control in NOMA Heterogeneous Network [J]. Computer Science, 2021, 48(3): 269-274.
[12] XU Xin-li, XIAO Yun-yue, LONG Hai-xia, YANG Xu-hua, MAO Jian-fei. Attributed Network Embedding Based on Matrix Factorization and Community Detection [J]. Computer Science, 2021, 48(12): 204-211.
[13] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[14] XIAO Yong, JIN Xin, FENG Jun-hao. Cross-layer Matching Mechanism of Link Communication Rate for Heterogeneous Communication in Power System [J]. Computer Science, 2021, 48(11A): 495-499.
[15] PAN Yu, ZOU Jun-hua, WANG Shuai-hui, HU Gu-yu, PAN Zhi-song. Deep Community Detection Algorithm Based on Network Representation Learning [J]. Computer Science, 2021, 48(11A): 198-203.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.