Two-Stage Ensemble-Based Community Discovery Algorithm in Multilayer Networks

Zhao Xingwang; Zhang Yaopu; Liang Jiye

doi:10.7544/issn1000-1239.202220214

Journal of Computer Research and Development > 2023 > 60(12): 2832-2843. > DOI: 10.7544/issn1000-1239.202220214

Zhao Xingwang, Zhang Yaopu, Liang Jiye. Two-Stage Ensemble-Based Community Discovery Algorithm in Multilayer Networks[J]. Journal of Computer Research and Development, 2023, 60(12): 2832-2843. DOI: 10.7544/issn1000-1239.202220214

Citation:

PDF (1923 KB)

Two-Stage Ensemble-Based Community Discovery Algorithm in Multilayer Networks

School of Computer and Information Technology, Shanxi University, Taiyuan 030006
Key Laboratory of Computational Intelligence and Chinese Information Processing (Shanxi University) , Ministry of Education, Taiyuan 030006

Funds: This work was supported by the National Natural Science Foundation of China (62072293, U21A20473，61976128, 62272285).

More Information

Author Bio:
Zhao Xingwang: born in 1984. PhD, associate professor, PhD supervisor. Member of CCF. His main research interests include data mining and machine learning

Zhang Yaopu: born in 1997. Master. Student member of CCF. His main research interest includes network data mining

Liang Jiye: born in 1962. PhD, professor, PhD supervisor. Fellow of CCF. His main research interests include artificial intelligence, machine learning, and data mining
Received Date: March 13, 2022
Revised Date: January 29, 2023
Available Online: September 19, 2023

Graphical Abstract

Abstract

Abstract

Community discovery aims to uncover the community structure embedded in complex networks, which is one of the important tasks in complex network analysis. However, most of the existing community discovery methods are aimed at single-layer network data, and less research has been done on the widespread multi-layer networks in the real world. In order to solve the problem of community discovery in multi-layer networks, we propose a two-stage ensemble-based community discovery algorithm. The algorithm can improve the accuracy and interpretability of community discovery results. Firstly, after the base communities are obtained at each layer, the local ensemble is performed based on the base community structure information of each layer and the optimal base community structure of each other layer. Secondly, the stability of each community in the local community division of each layer is measured based on information entropy, and the accuracy of each local community division is evaluated through the results of other layer community division. Finally, a global weighted ensemble is carried out based on the importance of each community and the community structure to obtain the final community structure. A comparative analysis is carried out on artificial multi-layer networks and real multi-layer networks with existing multi-layer network community discovery algorithms. The experimental results show that our proposed algorithm is superior to the existing algorithms in terms of multi-layer modularity and normalized mutual information.
- multilayer network,
- community discovery,
- weighted ensemble,
- modularity,
- complex network analysis

FullText(HTML)

References (39)

References

[1]	Fortunato S, Hric D. Community detection in networks: A user guide[J]. Physics Reports, 2016, 659: 1−44 doi: 10.1016/j.physrep.2016.09.002
[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 doi: 10.1073/pnas.122653799
[3]	Menche J, Sharma A, Kitsak M, et al. Uncovering disease-disease relationships through the incomplete interactome[J]. Science, 2015, 347(6224): 1257601 doi: 10.1126/science.1257601
[4]	Wang Xiaoyang, Zhang Ying, Zhang Wenjie, et al. Efficient distance-aware influence maximization in geo-social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 29(3): 599−612
[5]	Zhang Fan, Zhang Wenjie, Zhang Ying, et al. OLAK: An efficient algorithm to prevent unraveling in social networks[J]. Proceedings of the VLDB Endowment, 2017, 10(6): 649−660 doi: 10.14778/3055330.3055332
[6]	Rahman M S, Ngom A. A fast agglomerative community detection method for protein complex discovery in protein interaction networks[C/OL] //Proc of the 8th IAPR Int Conf on Pattern Recognition in Bioinformatics. Berlin: Springer, 2013[2022-03-14].https://link.springer.com/chapter/10.1007/978−3-642−39159-0_1
[7]	Guo Lu, Cui Ying, Liang Haili, et al. Spectral bisection community detection method for urban road networks[C] //Proc of the 40th Chinese Control Conf (CCC). Piscataway, NJ: IEEE, 2021: 806−811
[8]	Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences, 2004, 101(9): 2658−2663 doi: 10.1073/pnas.0400054101
[9]	Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133 doi: 10.1103/PhysRevE.69.066133
[10]	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 doi: 10.1088/1742-5468/2008/10/P10008
[11]	Newman M E J. Spectral methods for community detection and graph partitioning[J]. Physical Review E, 2013, 88(4): 042822 doi: 10.1103/PhysRevE.88.042822
[12]	Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118−1123 doi: 10.1073/pnas.0706851105
[13]	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 doi: 10.1103/PhysRevE.76.036106
[14]	吴宗柠,狄增如,樊瑛. 多层网络的结构与功能研究进展[J]. 电子科技大学学报,2021,50(1):106−120 Wu Zongning, Di Zengru, Fan Ying. The structure and function of multilayer networks: Progress and prospects[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(1): 106−120 (in Chinese)
[15]	陈可佳,陈利明,吴桐. 多层网络社区发现研究综述[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 (in Chinese)
[16]	Huang Xinyu, Chen Dongming, Ren Tao. et al. A survey of community detection methods in multilayer networks[J]. Data Mining and Knowledge Discovery, 2021, 35(1): 1−45 doi: 10.1007/s10618-020-00716-6
[17]	Tagarelli A, Amelio A, Gullo F. Ensemble-based community detection in multilayer networks[J]. Data Mining and Knowledge Discovery, 2017, 31(5): 1506−1543 doi: 10.1007/s10618-017-0528-8
[18]	Mucha P J, Richardson T, Macon K, et al. Community structure in time-dependent, multiscale, and multiplex networks[J]. Science, 2010, 328(5980): 876−878 doi: 10.1126/science.1184819
[19]	Ma Xiaoke, Dong Di, Wang Quan. Community detection in multi-layer networks using joint nonnegative matrix factorization[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(2): 273−286
[20]	Kuncheva Z, Montana G. Community detection in multiplex networks using locally adaptive random walks [C] //Proc of the 2015 IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. New York: ACM, 2015: 1308−1315
[21]	Laishram R, Wendt J D, Soundarajan S. MCS+: An efficient algorithm for crawling the community structure in multiplex networks[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 16(1): 1−32
[22]	Berlingerio M, Coscia M , Giannotti F . Finding and characterizing communities in multidimensional networks[C] //Proc of the 2011 Int Conf on Advances in Social Networks Analysis & Mining. Piscataway, NJ: IEEE, 2011: 490−494
[23]	Zhu Guangyao, Li Kan. A unified model for community detection of multiplex networks[C] //Proc of the 15th Int Conf on Web Information Systems Engineering. Berlin: Springer, 2014: 31−46
[24]	Tang Lei, Wang Xufei, Liu Huan. Uncovering groups via heterogeneous interaction analysis[C] //Proc of the 9th IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2009: 503−512
[25]	Berlingerio M, Pinelli F, Calabrese F. Abacus: Frequent pattern mining-based community discovery in multidimensional networks[J]. Data Mining and Knowledge Discovery, 2013, 27(3): 294−320 doi: 10.1007/s10618-013-0331-0
[26]	Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113 doi: 10.1103/PhysRevE.69.026113
[27]	Bazzi M, Jeub L G S, Arenas A, et al. A framework for the construction of generative models for mesoscale structure in multilayer networks[J]. Physical Review Research, 2020, 2(2): 023100 doi: 10.1103/PhysRevResearch.2.023100
[28]	Magnani M, Micenkova B, Rossi L. Combinatorial analysis of multiple networks [J]. arXiv preprint, arXiv: 1303.4986, 2013
[29]	Cardillo A, Gómez-Gardenes J, Zanin M, et al. Emergence of network features from multiplexity[J]. Scientific Reports, 2013, 3(1): 1−6
[30]	Coleman J, Katz E, Menzel H. The diffusion of an innovation among physicians[J]. Sociometry, 1957, 20(4): 253−270 doi: 10.2307/2785979
[31]	Kapferer B. Strategy and Transaction in an African Factory: African Workers and Indian Management in a Zambian Town [M]. Manchester: Manchester University Press, 1972
[32]	De Domenico M, Nicosia V, Arenas A, et al. Structural reducibility of multilayer networks[J]. Nature Communications, 2015, 6(1): 1−9
[33]	De Domenico M, Porter M A, Arenas A. MuxViz: A tool for multilayer analysis and visualization of networks[J]. Journal of Complex Networks, 2015, 3(2): 159−176 doi: 10.1093/comnet/cnu038
[34]	Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9): P09008
[35]	Dong Xiaowen, Frossard P, Vandergheynst P, et al. Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds[J]. IEEE Transactions on Signal Processing, 2013, 62(4): 905−918
[36]	Mercado P, Gautier A, Tudisco F, et al. The power mean Laplacian for multilayer graph clustering[C] //Proc of the 21st Int Conf on Artificial Intelligence and Statistics. New York: PMLR, 2018: 1828−1838
[37]	Kumar A, Rai P, Daume H. Co-regularized multi-view spectral clustering[C] //Proc of the 25th Int Conf on Neural Information Processing Systems. La Jolla, CA: NIPS, 2011: 1413−1421
[38]	Nie Feiping, Tian Lai, Li Xuelong. Multiview clustering via adaptively weighted procrustes[C] //Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 2022−2030
[39]	Venturini S, Cristofari A, Rinaldi F, et al. Louvain-like methods for community detection in multiplex networks[J]. arXiv preprint, arXiv: 2106.13543, 2021

[1]	Lin Liansheng, Zheng Huanqin, Su Shen, Lei Kai, Chen Xiaofeng, Tian Zhihong. An On-Chain Mechanism Against DeFi Price Manipulation Attacks[J]. Journal of Computer Research and Development, 2025, 62(2): 443-457. DOI: 10.7544/issn1000-1239.202330291
[2]	Song Shuwei, Ni Xiaoze, Chen Ting. Gas Optimization for Smart Contracts: A Survey[J]. Journal of Computer Research and Development, 2023, 60(2): 311-325. DOI: 10.7544/issn1000-1239.202220887
[3]	Ying Chenhao, Xia Fuyuan, Li Jie, Si Xueming, Luo Yuan. Incentive Mechanism Based on Truth Estimation of Private Data for Blockchain-Based Mobile Crowdsensing[J]. Journal of Computer Research and Development, 2022, 59(10): 2212-2232. DOI: 10.7544/issn1000-1239.20220493
[4]	Feng Jingyu, Yang Jinwen, Zhang Ruitong, Zhang Wenbo. A Spectrum Sharing Incentive Scheme Against Location Privacy Leakage in IoT Networks[J]. Journal of Computer Research and Development, 2020, 57(10): 2209-2220. DOI: 10.7544/issn1000-1239.2020.20200453
[5]	Hai Mo, Zhu Jianming. A Propagation Mechanism Combining an Optimal Propagation Path and Incentive in Blockchain Networks[J]. Journal of Computer Research and Development, 2019, 56(6): 1205-1218. DOI: 10.7544/issn1000-1239.2019.20180419
[6]	He Yunhua, Li Mengru, Li Hong, Sun Limin, Xiao Ke, Yang Chao. A Blockchain Based Incentive Mechanism for Crowdsensing Applications[J]. Journal of Computer Research and Development, 2019, 56(3): 544-554. DOI: 10.7544/issn1000-1239.2019.20170670
[7]	He Haiwu, Yan An, Chen Zehua. Survey of Smart Contract Technology and Application Based on Blockchain[J]. Journal of Computer Research and Development, 2018, 55(11): 2452-2466. DOI: 10.7544/issn1000-1239.2018.20170658
[8]	Xiong Jinbo, Ma Rong, Niu Ben, Guo Yunchuan, Lin Li. Privacy Protection Incentive Mechanism Based on User-Union Matching in Mobile Crowdsensing[J]. Journal of Computer Research and Development, 2018, 55(7): 1359-1370. DOI: 10.7544/issn1000-1239.2018.20180080
[9]	Wang Bo, Huang Chuanhe, Yang Wenzhong, Dan Feng, and Xu Liya. An Incentive-Cooperative Forwarding Model Based on Punishment Mechanism in Wireless Ad Hoc Networks[J]. Journal of Computer Research and Development, 2011, 48(3): 398-406.
[10]	Yue Guangxue, Li Renfa, Chen Zhi, Zhou Xu. Analysis of Free-riding Behaviors and Modeling Restrain Mechanisms for Peer-to-Peer Networks[J]. Journal of Computer Research and Development, 2011, 48(3): 382-397.

Cited By

Cited by

Periodical cited type(2)

1.	李硕，王馨爽. 多场景融合的码号数据分发架构及关键技术研究. 数据通信. 2024(06): 1-3+11 .
2.	俞惠芳，李磊. 基于椭圆曲线签密的跨链医疗数据共享方案. 通信学报. 2024(12): 57-66 .