Search Advanced

Networks and Heterogeneous Media

2015, Volume 10, Issue 1: 71-85. doi: 10.3934/nhm.2015.10.71
Previous Article Next Article

Community detection in multiplex networks: A seed-centric approach

  • 1.
    DICEN-CNAM 292, rue St Martin, 75141 PARIS CEDEX 03, & & LIPN - CNRS UMR 7030, Paris
  • 2.
    PSC, UP13, LIPN, CNRS UMR 7030, Villetaneuse
  • Received: 01 July 2014 Revised: 01 December 2014

  • Primary: 58F15, 58F17; Secondary: 53C35.

  • Multiplex network is an emergent model that has been lately proposed in order to cope with the complexity of real-world networks. A multiplex network is defined as a multi-layer interconnected graph. Each layer contains the same set of nodes but interconnected by different types of links. This rich representation model requires to redefine most of the existing network analysis algorithms. In this paper we focus on the central problem of community detection. Most of existing approaches consist on transforming the problem, in a way or another, to the classical setting of community detection in a monoplex network. In this work, we propose a new approach that consists on adapting a seed-centric algorithm to the multiplex case. The first experiments on heterogeneous bibliographical networks show the relevance of the approach compared to the existing algorithms.

    Citation: Manel Hmimida, Rushed Kanawati. Community detection in multiplex networks: A seed-centric approach[J]. Networks and Heterogeneous Media, 2015, 10(1): 71-85. doi: 10.3934/nhm.2015.10.71

    Related Papers:

    [1] Manel Hmimida, Rushed Kanawati . Community detection in multiplex networks: A seed-centric approach. Networks and Heterogeneous Media, 2015, 10(1): 71-85. doi: 10.3934/nhm.2015.10.71
    [2] Manisha Pujari, Rushed Kanawati . Link prediction in multiplex networks. Networks and Heterogeneous Media, 2015, 10(1): 17-35. doi: 10.3934/nhm.2015.10.17
    [3] Mary Luz Mouronte, Rosa María Benito . Structural properties of urban bus and subway networks of Madrid. Networks and Heterogeneous Media, 2012, 7(3): 415-428. doi: 10.3934/nhm.2012.7.415
    [4] Hirotada Honda . On a model of target detection in molecular communication networks. Networks and Heterogeneous Media, 2019, 14(4): 633-657. doi: 10.3934/nhm.2019025
    [5] Rosa M. Benito, Regino Criado, Juan C. Losada, Miguel Romance . Preface: "New trends, models and applications in complex and multiplex networks". Networks and Heterogeneous Media, 2015, 10(1): i-iii. doi: 10.3934/nhm.2015.10.1i
    [6] Regino Criado, Rosa M. Benito, Miguel Romance, Juan C. Losada . Preface: Mesoscales and evolution in complex networks: Applications and related topics. Networks and Heterogeneous Media, 2012, 7(3): i-iii. doi: 10.3934/nhm.2012.7.3i
    [7] Yuntian Zhang, Xiaoliang Chen, Zexia Huang, Xianyong Li, Yajun Du . Managing consensus based on community classification in opinion dynamics. Networks and Heterogeneous Media, 2023, 18(2): 813-841. doi: 10.3934/nhm.2023035
    [8] Francisco Pedroche, Regino Criado, Esther García, Miguel Romance, Victoria E. Sánchez . Comparing series of rankings with ties by using complex networks: An analysis of the Spanish stock market (IBEX-35 index). Networks and Heterogeneous Media, 2015, 10(1): 101-125. doi: 10.3934/nhm.2015.10.101
    [9] Massimiliano Zanin, Ernestina Menasalvas, Pedro A. C. Sousa, Stefano Boccaletti . Preprocessing and analyzing genetic data with complex networks: An application to Obstructive Nephropathy. Networks and Heterogeneous Media, 2012, 7(3): 473-481. doi: 10.3934/nhm.2012.7.473
    [10] Matthieu Canaud, Lyudmila Mihaylova, Jacques Sau, Nour-Eddin El Faouzi . Probability hypothesis density filtering for real-time traffic state estimation and prediction. Networks and Heterogeneous Media, 2013, 8(3): 825-842. doi: 10.3934/nhm.2013.8.825
  • Multiplex network is an emergent model that has been lately proposed in order to cope with the complexity of real-world networks. A multiplex network is defined as a multi-layer interconnected graph. Each layer contains the same set of nodes but interconnected by different types of links. This rich representation model requires to redefine most of the existing network analysis algorithms. In this paper we focus on the central problem of community detection. Most of existing approaches consist on transforming the problem, in a way or another, to the classical setting of community detection in a monoplex network. In this work, we propose a new approach that consists on adapting a seed-centric algorithm to the multiplex case. The first experiments on heterogeneous bibliographical networks show the relevance of the approach compared to the existing algorithms.


    [1] S. Alexander and G. Joydeep, Cluster ensembles a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3 (2003), 583-617. doi: 10.1162/153244303321897735
    [2] A. Amelio and C. Pizzuti, A cooperative evolutionary approach to learn communities in multilayer networks, in Parallel Problem Solving from Nature-PPSN XIII, Lecture Notes in Computer Science, 8672 Springer International Publishing, Switzerland, 2014, 222-232. doi: 10.1007/978-3-319-10762-2_22
    [3] F. Battiston, V. Nicosia and V. Latora, Structural measures for multiplex networks, Physical Review E, 89 (2014), 032804. doi: 10.1103/PhysRevE.89.032804
    [4] M. Berlingerio, M. Coscia and F. Giannotti, Finding and characterizing communities in multidimensional networks, in 2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM), IEEE, 2011, 490-494. doi: 10.1109/ASONAM.2011.104
    [5] M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale and D. Pedreschi, Evolving networks: Eras and turning points, Intell. Data Anal., 17 (2013), 27-48.
    [6] M. Berlingerio, F. Pinelli and F. Calabrese, Abacus: frequent pattern mining-based community discovery in multidimensional networks, Data Mining and Knowledge Discovery, 27 (2013), 294-320. doi: 10.1007/s10618-013-0331-0
    [7] V. D. Blondel, J.-l. Guillaume and E. Lefebvre, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, 2008 (2008), P10008. doi: 10.1088/1742-5468/2008/10/P10008
    [8] P. Brodka and P. Kazienko, Encyclopedia of Social Network Analysis and Mining, Ch. Multi-layered Social Networks, Springer, 2014.
    [9] P. Bródka, K. Skibicki, P. Kazienko and K. Musial, A degree centrality in multi-layered social network, in 2011 International Conference on Computational Aspects of Social Networks (CASoN), IEEE, 2011, 237-242.
    [10] D. Cai, Z. Shao, X. He, X. Yan and J. Han, Mining hidden community in heterogeneous social networks, in Proceedings of the 3rd International Workshop on Link Discovery, ACM, 2005, 58-65. doi: 10.1145/1134271.1134280
    [11] E. Cozzo, M. Kivelä, M. De Domenico, A. Solé, A. Arenas, S. Gómez, M. A. Porter and Y. Moreno, Clustering coefficients in multiplex networks, CoRR, arXiv:1307.6780, 2013.
    [12] J. Dahlin and P. Svenson, Ensemble approaches for improving community detection methods, CoRR, arXiv:1309.0242, 2013.
    [13] M. De Domenico, A. Solé, S. Gómez and A. Arenas, Random walks on multiplex networks, CoRR, arXiv:1306.0519, 2013.
    [14] C. Dwork, R. Kumar, M. Naor and D. Sivakumar, Rank aggregation methods for the web, in Proceedings of the 10th International Conference on World Wide Web, ACM, 2001, 613-622. doi: 10.1145/371920.372165
    [15] S. Fortunato, Community detection in graphs, Physics Reports, 486 (2010), 75-174. doi: 10.1016/j.physrep.2009.11.002
    [16] B. H. Good, Y.-A. de Montjoye and A. Clauset, Performance of modularity maximization in practical contexts, Physical Review E, 81 (2010), 046106, 19pp. doi: 10.1103/PhysRevE.81.046106
    [17] R. Jäschke, L. Marinho, A. Hotho, L. Schmidt-Thieme and G. Stumme, Tag recommendations in social bookmarking systems, AI Communications, 21 (2008), 231-247.
    [18] R. Kanawati, YASCA: An ensemble-based approach for community detection in complex networks, in Computing and Combinatorics, Lecture Notes in Computer Science, 8591, Springer International Publishing, Switzerland, 2014, 657-666. doi: 10.1007/978-3-319-08783-2_57
    [19] P. Kazienko, P. Brodka and K. Musial, Individual neighbourhood exploration in complex multi-layered social network, in 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), Vol. 3, IEEE, 2010, 5-8. doi: 10.1109/WI-IAT.2010.313
    [20] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno and M. A. Porter, Multilayer networks, preprint, arXiv:1309.7233, 2013.
    [21] S. Massoud, Coeurs Stables de Communautés dans les Graphes de Terrain, Ph.D thesis, 2012.
    [22] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, Community structure in time-dependent, multiscale, and multiplex networks, Science, 328 (2010), 876-878. doi: 10.1126/science.1184819
    [23] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, Community structure in time-dependent, multiscale, and multiplex networks, Science, 328 (2010), 876-878. doi: 10.1126/science.1184819
    [24] T. Murata, Modularity for heterogeneous networks, in Proceedings of the 21st ACM Conference on Hypertext and Hypermedia, ACM, 2010, 129-134. doi: 10.1145/1810617.1810640
    [25] A. Potgieter, R. J. E. Cooke, K. A. April and I. O. Osunmakinde, Temporality in link prediction: Understanding social complexity, Emergence: Complexity & Organization, 11 (2009), 69-83.
    [26] J. Reichardt and S. Bornholdt, Statistical mechanics of community detection, Physical Review E, 74 (2006), 016110, 14pp. doi: 10.1103/PhysRevE.74.016110
    [27] K. Rushed, Seed-centric approaches for community detection in complex networks, in Social Computing and Social Media, Springer, 2014, 197-208.
    [28] D. Suthers, J. Fusco, P. Schank, K.-H. Chu and M. Schlager, Discovery of community structures in a heterogeneous professional online network, in 2013 46th Hawaii International Conference on System Sciences (HICSS), IEEE, 2013, 3262-3271. doi: 10.1109/HICSS.2013.179
    [29] L. Tang and H. Liu, Community detection and mining in social media, Synthesis Lectures on Data Mining and Knowledge Discovery, 2 (2010), 1-137. doi: 10.2200/S00298ED1V01Y201009DMK003
    [30] Y. Zied and K. Rushed, Licod: Leader-driven approach for community detection in complex networks, Vietnam Journal of Computer Science, (2014), p30.

  • This article has been cited by:

    1. Arash Amini, Marina Paez, Lizhen Lin, Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks, 2022, -1, 1936-0975, 10.1214/22-BA1355
    2. Lijia Ma, Maoguo Gong, Jianan Yan, Wenfeng Liu, Shanfeng Wang, Detecting composite communities in multiplex networks: A multilevel memetic algorithm, 2018, 39, 22106502, 177, 10.1016/j.swevo.2017.09.012
    3. Parisa Rastin, Rushed Kanawati, 2015, A multiplex-network based approach for clustering ensemble selection, 9781450338547, 1332, 10.1145/2808797.2808825
    4. Manel Hmimida, Rushed Kanawati, 2016, A Graph-Coarsening Approach for Tag Recommendation, 9781450341448, 43, 10.1145/2872518.2889415
    5. Yiwei Xie, Feng Jiao, Shihan Li, Qingfu Liu, Yiuman Tse, Systemic risk in financial institutions: A multiplex network approach, 2022, 73, 0927538X, 101752, 10.1016/j.pacfin.2022.101752
    6. Ehsan Pournoor, Zaynab Mousavian, Abbas Nowzari Dalini, Ali Masoudi-Nejad, Identification of Key Components in Colon Adenocarcinoma Using Transcriptome to Interactome Multilayer Framework, 2020, 10, 2045-2322, 10.1038/s41598-020-59605-z
    7. Dewan F. Wahid, Elkafi Hassini, A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis, 2022, 3, 2662-2556, 10.1007/s43069-022-00156-6
    8. Wenjun Li, Ting Li, Kamal Berahmand, An effective link prediction method in multiplex social networks using local random walk towards dependable pathways, 2023, 45, 1382-6905, 10.1007/s10878-022-00961-z
    9. P.V. Bindu, P. Santhi Thilagam, Deepesh Ahuja, Discovering suspicious behavior in multilayer social networks, 2017, 73, 07475632, 568, 10.1016/j.chb.2017.04.001
    10. Amani Chouchane, Mohamed Bouguessa, 2017, Identifying Anomalous Nodes in Multidimensional Networks, 978-1-5090-5004-8, 601, 10.1109/DSAA.2017.55
    11. Maoguo Gong, , 2017, An improved multiobjective evolutionary approach for community detection in multilayer networks, 978-1-5090-4601-0, 443, 10.1109/CEC.2017.7969345
    12. Hamed Kalantari, Mehdi Ghazanfari, Mohammad Fathian, Kamran Shahanaghi, Multi-objective optimization model in a heterogeneous weighted network through key nodes identification in overlapping communities, 2020, 144, 03608352, 106413, 10.1016/j.cie.2020.106413
    13. Meilian Lu, Zhihe Qu, Ziheng Wang, Zhenglin Zhang, Hete_MESE: Multi-Dimensional Community Detection Algorithm Based on Multiplex Network Extraction and Seed Expansion for Heterogeneous Information Networks, 2018, 6, 2169-3536, 73965, 10.1109/ACCESS.2018.2883638
    14. Issam Falih, Rushed Kanawati, 2015, MUNA, 9781450338547, 757, 10.1145/2808797.2808804
    15. Roberto Interdonato, Andrea Tagarelli, Dino Ienco, Arnaud Sallaberry, Pascal Poncelet, Local community detection in multilayer networks, 2017, 31, 1384-5810, 1444, 10.1007/s10618-017-0525-y
    16. Wala Rebhi, Nesrine Ben Yahia, Narjes Bellamine Ben Saoud, 2016, Hybrid community detection approach in multilayer social network: Scientific collaboration recommendation case study, 978-1-5090-4320-0, 1, 10.1109/AICCSA.2016.7945701
    17. Rushed Kanawati, Martin Atzmueller, 2019, Modeling and Mining Feature-Rich Networks, 9781450366755, 1306, 10.1145/3308560.3320098
    18. Desheng Lyu, Bei Wang, Weizhe Zhang, Large-Scale Complex Network Community Detection Combined with Local Search and Genetic Algorithm, 2020, 10, 2076-3417, 3126, 10.3390/app10093126
    19. Oualid Boutemine, Mohamed Bouguessa, Mining Community Structures in Multidimensional Networks, 2017, 11, 1556-4681, 1, 10.1145/3080574
    20. LUCAS G. S. JEUB, MICHAEL W. MAHONEY, PETER J. MUCHA, MASON A. PORTER, A local perspective on community structure in multilayer networks, 2017, 5, 2050-1242, 144, 10.1017/nws.2016.22
    21. Mirco Schoenfeld, Juergen Pfeffer, 2020, Chapter 8, 978-3-030-31462-0, 115, 10.1007/978-3-030-31463-7_8
    22. Tanmoy Chakraborty, Ramasuri Narayanam, 2016, Cross-layer betweenness centrality in multiplex networks with applications, 978-1-5090-2020-1, 397, 10.1109/ICDE.2016.7498257
    23. Manel Hmimida, Rushed Kanawati, 2017, Chapter 25, 978-3-319-50900-6, 309, 10.1007/978-3-319-50901-3_25
    24. Seema Rani, Mukesh Kumar, Ranking community detection algorithms for complex social networks using multilayer network design approach, 2022, 18, 1744-0084, 310, 10.1108/IJWIS-02-2022-0040
    25. Félicité Gamgne Domgue, Norbert Tsopzé, René Ndoundam, Correlation and dimension relevance in multidimensional networks: a systematic taxonomy, 2021, 11, 1869-5450, 10.1007/s13278-021-00801-8
    26. Tsuyoshi Murata, 2015, Comparison of Inter-Layer Couplings of Multilayer Networks, 978-1-4673-9721-6, 448, 10.1109/SITIS.2015.122
    27. Aghdas Badiee, Hamed Kalantari, Mehdi Ghazanfari, Mohammad Fathian, Kamran Shahanaghi, Introducing drivers' collaboration network: A two-layers social network perspective in road transportation system analysis, 2020, 37, 22105395, 100532, 10.1016/j.rtbm.2020.100532
    28. Fatemeh Alimadadi, Ehsan Khadangi, Alireza Bagheri, Community detection in facebook activity networks and presenting a new multilayer label propagation algorithm for community detection, 2019, 33, 0217-9792, 1950089, 10.1142/S0217979219500899
    29. Andrea Tagarelli, Alessia Amelio, Francesco Gullo, Ensemble-based community detection in multilayer networks, 2017, 31, 1384-5810, 1506, 10.1007/s10618-017-0528-8
    30. Qiumin Wu, Ziqi Zhu, Jiahui Tang, Yukang Xia, Fault diagnosis of printing press bearing based on deformable convolution residual neural network, 2023, 18, 1556-1801, 622, 10.3934/nhm.2023027
    31. Zhana Kuncheva, Giovanni Montana, 2015, Community Detection in Multiplex Networks using Locally Adaptive Random Walks, 9781450338547, 1308, 10.1145/2808797.2808852
    32. Hamza Labbaci, Brahim Medjahed, Youcef Aklouf, A social network approach for recommending interoperable Web services, 2020, 38, 0926-8782, 927, 10.1007/s10619-020-07308-9
    33. Hamza Labbaci, Brahim Medjahed, Youcef Aklouf, Zaki Malik, 2016, Chapter 50, 978-3-319-46294-3, 705, 10.1007/978-3-319-46295-0_50
    34. Xiaoming Li, Guagquan Xu, Litao Jiao, Yinan Zhou, Wei Yu, Multi-layer network community detection model based on attributes and social interaction intensity, 2019, 77, 00457906, 300, 10.1016/j.compeleceng.2019.06.010
    35. Dérick G. F. Borges, Roberto F. S. Andrade, Finding modular structure in multiplex networks by sequential intra-layer edge elimination, 2020, 93, 1434-6028, 10.1140/epjb/e2020-100075-1
    36. Rokia Missaoui, Abir Messaoudi, Mohamed Hamza Ibrahim, Talel Abdessalem, 2022, Chapter 5, 978-3-030-90286-5, 77, 10.1007/978-3-030-90287-2_5
    37. Fatemeh Karimi, Shahriar Lotfi, Habib Izadkhah, Multiplex community detection in complex networks using an evolutionary approach, 2020, 146, 09574174, 113184, 10.1016/j.eswa.2020.113184
    38. Changzheng Liu, Fengling Huang, Ruixuan Li, Qi Yang, Yuhua Li, Shui Yu, Community detection using multitopology and attributes in social networks, 2022, 34, 1532-0626, 10.1002/cpe.6028
    39. Ruchi Mittal, M. P. S. Bhatia, 2019, chapter 12, 9781522558521, 290, 10.4018/978-1-5225-5852-1.ch012
    40. Giuseppe Giordano, Giancarlo Ragozini, Maria Prosperina Vitale, Analyzing multiplex networks using factorial methods, 2019, 59, 03788733, 154, 10.1016/j.socnet.2019.07.005
    41. Alessia Amelio, Gianluca Bonifazi, Enrico Corradini, Domenico Ursino, Luca Virgili, A Multilayer Network-Based Approach to Represent, Explore and Handle Convolutional Neural Networks, 2023, 15, 1866-9956, 61, 10.1007/s12559-022-10084-6
    42. Maël Canu, Marie-Jeanne Lesot, Adrien Revault d’Allonnes, 2017, Chapter 22, 978-3-319-50900-6, 275, 10.1007/978-3-319-50901-3_22
    43. Elahe Nasiri, Kamal Berahmand, Yuefeng Li, A new link prediction in multiplex networks using topologically biased random walks, 2021, 151, 09600779, 111230, 10.1016/j.chaos.2021.111230
    44. Zhou Zhou, Hongwei Wei, Houliang Xie, Improved community structure discovery algorithm based on penalised matrix decomposition for complex networks, 2020, 75, 01419331, 103047, 10.1016/j.micpro.2020.103047
    45. Chengyun Song, Weiyi Liu, Zhining Liu, Xiaoyang Liu, He Debiao, User abnormal behavior recommendation via multilayer network, 2019, 14, 1932-6203, e0224684, 10.1371/journal.pone.0224684
    46. Wala Rebhi, Nesrine Ben Yahia, Narjès Bellamine Ben Saoud, Stable Communities Detection Method for Temporal Multiplex Graphs: Heterogeneous Social Network Case Study, 2021, 64, 0010-4620, 418, 10.1093/comjnl/bxaa162
    47. Ehsan Pournoor, Zaynab Mousavian, Abbas Nowzari-Dalini, Ali Masoudi-Nejad, Leto Peel, A propagation-based seed-centric local community detection for multilayer environment: The case study of colon adenocarcinoma, 2021, 16, 1932-6203, e0255718, 10.1371/journal.pone.0255718
    48. Chao LIU, KieSu KIM, Construction and application of data-driven knowledge adjacency network for product CMF design, 2023, 17, 1881-3054, JAMDSM0032, 10.1299/jamdsm.2023jamdsm0032
    49. Yunwei Chen, Xin Zhang, Lu Jiang, Hongshen Pang, 2024, The Concept and Application of Scientific Communities Detection within Academic Mixed-Network, 9798400717550, 139, 10.1145/3675669.3675679
    50. Bagher Zarei, Bahman Arasteh, Mehdi Asadi, Vahid Majidnezhad, Saeid Taghavi Afshord, Asgarali Bouyer, Jesus Manuel Munoz-Pacheco, Multiplex Community Detection in Social Networks Using a Chaos‐Based Hybrid Evolutionary Approach, 2024, 2024, 1076-2787, 10.1155/2024/1016086
    51. Chao Lyu, Yuhui Shi, Lijun Sun, Chin-Teng Lin, Community Detection in Multiplex Networks Based on Evolutionary Multitask Optimization and Evolutionary Clustering Ensemble, 2023, 27, 1089-778X, 728, 10.1109/TEVC.2022.3184988
    52. Rui Zhang, Bin Shuai, Pengfei Gao, Yue Zhang, Driver’s journey from historical traffic violations to future accidents: A China case based on multilayer complex network approach, 2025, 211, 00014575, 107901, 10.1016/j.aap.2024.107901
  • Reader Comments
  • © 2015 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Networks and Heterogeneous Media
1.2 1.8

Metrics

Article views(6071) PDF downloads(768) Cited by(52)

Preview PDF
Download XML
Export Citation
Article outline
Abstract
References

Other Articles By Authors

Related pages

Tools

Copyright © AIMS Press

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog