多层网络社区发现研究综述

doi:10.3778/j.issn.1673-9418.2004016

摘要/Abstract

摘要：

社区发现是复杂网络分析的重要任务之一。现有的社区发现方法大多面向单层网络，对现实世界中广泛存在的多层网络中的社区发现研究则稍显不足。首先给出了各种多层网络的定义，并对比了各网络在节点对齐、层间边和层间耦合方面的特点，接着介绍了各类传统的单层网络社区发现方法；在此基础上，深入调研了多层网络社区发现方法，将其大致分为基于聚合的方法和基于扩展的方法，对各方法在实现机制、优势、局限性、适用网络、复杂性等方面进行了分析比较；通过在现实和模拟数据集上的实验，进一步比较了部分代表性方法在模块度、标准化互信息和调整兰德指数等指标上的性能；最后对多层网络社区发现的工作进行了总结和展望。

关键词: 社区发现, 多层网络, 模块度, 复杂网络分析

Abstract:

Community detection is one of the most important tasks of complex network analysis. Most of the existing community detection methods are oriented to single-layer networks, and the research on community detection in multi-layer networks widely existing in the real world is slightly insufficient. This paper first presents the definition of various multi-layer networks, compares the characteristics of each network in terms of node alignment, inter-layer edges and inter-layer coupling, and then introduces various traditional single-layer network community discovery methods. On this basis, this paper deeply surveys the multi-layer network community detection methods, which are roughly divided into aggregation-based methods and extension-based methods. The methods are analyzed and compared in terms of mechanisms, advantages, limitations, application network, complexity, etc. Experiments are conducted on both real and simulated datasets, comparing the performance of several representative methods on indicators such as modularity, normalized mutual information, and adjustment of the Rand index. The work of multi-layer network community detection is summarized and prospected.

Key words: community detection, multi-layer network, modularity, complex network analysis

陈可佳，陈利明，吴桐. 多层网络社区发现研究综述[J]. 计算机科学与探索, 2020, 14(11): 1801-1812.

CHEN Kejia, CHEN Liming, WU Tong. Survey on Community Detection in Multi-layer Networks[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(11): 1801-1812.

参考文献

[1] Fortunato S, Hric D. Community detection in networks: a user guide[J]. Physics Reports, 2016, 659: 1-44.
[2] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Aca-demy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
[3] Menche J, Sharma A, Kitsak M, et al. Uncovering disease relationships through the incomplete interactome[J]. Science, 2015, 347(6624): 841-850.
[4] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453(7191): 98-101.
[5] Zhang F, Zhang W, Zhang Y, et al. OLAK: an efficient algo-rithm to prevent unraveling in social networks[J]. Procee-dings of the VLDB Endowment, 2017, 6(10): 649-660.
[6] Rahman M S, Ngom A. A fast agglomerative community detection method for protein complex discovery in protein interaction networks[C]//LNCS 7986: Proceedings of the 8th IAPR International Conference on Pattern Recognition in Bioinformatics, Nice, Jun 17-20, 2013. Berlin, Heidel-berg: Springer, 2013: 1-12.
[7] Wang X, Zhang Y, Zhang W, et al. Efficient distance-aware influence maximization in geo-social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(3): 599-612.
[8] Schaeffer S E. Survey: graph clustering[J]. Computer Science Review, 2007, 1(1): 27-64.
[9] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70: 066111.
[10] Pothen A. Graph partitioning algorithms with applications to scientific computing[J]. Parallel Numerical Algorithms Norfolk, 1997, 4: 323-368.
[11] Newman M E J, Girvan M. Finding and evaluating com-munity structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[12] Newman M E J. Spectral methods for community detection and graph partitioning[J]. Physical Review E, 2013, 88(4): 042822.
[13] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and so-ciety[J]. Nature, 2005, 435: 814-818.
[14] Marya B, Mason A P, Stacy W. Community detection in temporal multilayer networks, with an application to correla-tion networks[J]. Multiscale Modeling & Simulation, 2016, 14(1): 1-41.
[15] Bollobás B. Modern graph theory[M]. Berlin, Heidelberg: Springer, 1998.
[16] Berlingerio M, Coscia M, Giannotti F, et al. Foundations of multidimensional network analysis[C]//Proceedings of the 2011 International Conference on Advances in Social Net-works Analysis and Mining, Kaohsiung, China, Jul 25-27, 2011. Washington: IEEE Computer Society, 2011: 485-489.
[17] Cai D, Shao Z, He X F, et al. Community mining from multi-relational networks[C]//LNCS 3721: Proceedings of the 9th European Conference on Principles and Practice of Know-ledge Discovery in Databases, Porto, Oct 3-7, 2005. Berlin, Heidelberg: Springer, 2005: 445-452.
[18] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multi-scale complexity in networks[J]. Nature, 2010, 466: 761-764.
[19] Sun Y, Han J. Mining heterogeneous information networks a structural analysis approach[J]. ACM SIGKDD Explorations Newsletter, 2013, 14(2): 20-28.
[20] 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): 43.
[21] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell Labs Technical Journal, 1970, 49(2): 291-307.
[22] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[23] Luxburg U V. A tutorial on spectral clustering[J]. Statistics & Computing, 2007, 17(4): 395-416.
[24] Zlati V, Gabrielli A, Caldarelli G. Topologically biased random walk and community finding in networks[J]. Physical Review E, 2010, 82(6): 066109.
[25] Palla G, ábel D, Illés J F, et al. k-clique percolation and clustering[J]. Handbook of Large-Scale Random Networks, 2010, 18(5): 369-408.
[26] Lancichinetti A, Fortunato S. Community detection algori-thms: a comparative analysis[J]. Physical Review E, 2009, 80(5): 056117.
[27] Gregory S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10): 103018.
[28] Xie J, Szymanski B K, Liu X. SLPA: uncovering overlapping communities in social networks via a speaker-listener interac-tion dynamic process[C]//Proceedings of the 11th International Conference of Data Mining Workshop, Vancouver, Dec 11, 2011. Piscataway: IEEE, 2011: 344-349.
[29] Berlingerio M, Coscia M, Giannotti F. Finding and characte-rizing communities in multidimensional networks[C]//Procee-dings of the 2011 International Conference on Advances in Social Networks Analysis and Mining, Kaohsiung, China, Jul 25-27, 2011. Washington: IEEE Computer Society, 2011: 490-494.
[30] Zhu G Y, Li K. A unified model for community detection of multiplex networks[C]//LNCS 8786: Proceedings of the 15th International Conference on Web Information Systems Engineering, Thessaloniki, Otc 12-14, 2014. Berlin, Heidel-berg: Springer, 2014: 31-46.
[31] Tang L, Wang X, Liu H. Uncovering groups via heterogeneous interaction analysis[C]//Proceedings of the 9th IEEE Inter-national Conference on Data Mining, Miami, Dec 6-9, 2009. Washington: IEEE Computer Society, 2009: 530-512.
[32] Lancichinetti A, Fortunato S. Consensus clustering in complex networks[J]. Scientific Reports, 2012, 2: 336.
[33] Berlingerio M, Pinelli F, Calabrese F. ABACUS: frequent pattern mining-based community discovery in multidimen-sional networks[J]. Data Mining & Knowledge Discovery, 2013, 27(3): 294-320.
[34] Mucha P J, Richardson R, Macon R, et al. Community struc-ture in time-dependent, multiscale, and multiplex networks[J]. Science, 2010, 328(5980): 876-878.
[35] Ma X, Dong D, Wang Q. Community detection in multi-layer networks using joint nonnegative matrix factorization[J]. IEEE Transactions on Knowledge?and Data Engineering, 2019, 31(2): 273-286.
[36] Bródka P, Filipowski T, Kazienko P. An introduction to community detection in multi-layered social network[C]//Proceedings of the 4th World Summit on the Knowledge Society Information Systems, E-learning, and Knowledge Management Research, Mykonos, Sep 21-23, 2011. Berlin, Heidelberg: Springer, 2011: 185-190.
[37] Hmimida M, Kanawati R. Community detection in multiplex networks: a seed-centric approach[J]. Networks & Hetero-geneous Media, 2015, 10(1): 71-85.
[38] Yakoubi Z, Kanawati R. LICOD: a leader-driven algorithm for community detection in complex networks[J]. Vietnam Journal of Computer Science, 2014, 1(4): 241-256.
[39] Alimadadi F, Khadangi E, Bagheri A. Community detection in facebook activity networks and presenting a new multilayer label propagation algorithm for community detection[J]. Inter-national Journal of Modern Physics B, 2019, 33(10): 1950089.
[40] Afsarmanesh N, Magnani M. Finding overlapping commu-nities in multiplex networks[J]. arXiv:1602.03746, 2016.
[41] Interdonato R, Tagarelli A, Ienco D, et al. Local community detection in multilayer networks[J]. Data Mining Knowledge Discovery, 2017, 31(5): 1444-1479.
[42] Yang J, Leskovec J. Overlapping community detection at scale: a nonnegative matrix factorization approach[C]//Pro-ceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, Feb 4-8, 2013. New York: ACM, 2013: 587-596.
[43] Ma X K, Dong D. Evolutionary nonnegative matrix factori-zation algorithms for community detection in dynamic net-works[J]. IEEE Transactions on Knowledge & Data Engi-neering, 2017, 29(5): 1045-1058.
[44] Esraa A S, Mahmood A K, Selin A. Tensor based temporal and multi-layer community detection for studying brain dyna-mics during resting state fMRI[J]. IEEE Transactions on Bio-medical Engineering, 2019, 66(3): 695-709.
[45] Gauvin L, Panisson A, Cattuto C. Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach[J]. PLoS One, 2014, 9(1): e86028.
[46] De Domenico M, Lancichinetti A, Arenas A, et al. Identif-ying modular flows on multilayer networks reveals highly overlapping organization in social systems[J]. Physical Review X, 2015, 5: 011027.
[47] Kuncheva Z, Montana G. Community detection in multiplex networks using locally adaptive random walks[C]//Procee-dings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, Aug 23-27, 2015. New York: ACM, 2015: 1308-1315.
[48] Pons P, Latapy M. Computing communities in large networks using random walks[J]. Computer and Information Sciences, 2005, 10(1): 284-293.
[49] Ebrahimi M, Shahmoradi M R, Heshmati Z, et al. A novel method for overlapping community detection using multi-objective optimization[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 505: 825-835.
[50] Bazzi M, Jeub L G S, Arenas A, et al. Generative benchmark models for mesoscale structure in multilayer networks[J]. arXiv:1608.06196, 2016.
[51] Amelio A, Pizzuti C. Is normalized mutual information a fair measure for comparing community detection methods?[C]//Proceedings of the 2015 IEEE/ACM International Con-ference on Advances in Social Networks Analysis & Mining, Paris, Aug 23-27, 2015. New York: ACM, 2015: 1584-1385.
[52] Steinley D, Brusco M J, Hubert L. The variance of the ad-justed rand index[J]. Psychological Methods, 2016, 21(2): 261-272.
[53] Xu K, Hu W H, Leskovec J, et al. How powerful are graph neural networks?[J]. arXiv:1810.00826, 2019.
[54] Kang Y, Gu X Y, Yu B, et al. A multilevel community detec-tion algorithm for large-scale social information networks[J]. Chinese Journal of Computers, 2016, 39(1): 169-182. 康颖, 古晓艳, 于博, 等. 一种面向大规模社会信息网络的多层社区发现算法[J]. 计算机学报, 2016, 39(1): 169-182.
[55] Lee J, Lee I, Kang J. Self-attention graph pooling[J]. arXiv:1904.08082, 2019.