Community detection in multiplex networks: A seed-centric approach

Previous Article
Characterizing ethnic interactions from human communication patterns in Ivory Coast
NHM Home
This Issue
Next Article
A simple and bounded model of population dynamics for mutualistic networks

March 2015, 10(1): 71-85. doi: 10.3934/nhm.2015.10.71

Community detection in multiplex networks: A seed-centric approach

Manel Hmimida ^1, and Rushed Kanawati ^2,

1.	DICEN-CNAM 292, rue St Martin, 75141 PARIS CEDEX 03, & & LIPN - CNRS UMR 7030, Paris, France
2.	PSC, UP13, LIPN, CNRS UMR 7030, Villetaneuse, France

Received July 2014 Revised December 2014 Published February 2015

Abstract
Related Papers

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.

Keywords: redundancy., multiplex networks, complex network, Mux-Licod, modularity, community detection.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: 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

References:

[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.

show all references

References:

[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.

[1]	Marco Sarich, Natasa Djurdjevac Conrad, Sharon Bruckner, Tim O. F. Conrad, Christof Schütte. Modularity revisited: A novel dynamics-based concept for decomposing complex networks. Journal of Computational Dynamics, 2014, 1 (1) : 191-212. doi: 10.3934/jcd.2014.1.191
[2]	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
[3]	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
[4]	Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094
[5]	Nataša Djurdjevac Conrad, Ralf Banisch, Christof Schütte. Modularity of directed networks: Cycle decomposition approach. Journal of Computational Dynamics, 2015, 2 (1) : 1-24. doi: 10.3934/jcd.2015.2.1
[6]	Xianmin Geng, Shengli Zhou, Jiashan Tang, Cong Yang. A sufficient condition for classified networks to possess complex network features. Networks and Heterogeneous Media, 2012, 7 (1) : 59-69. doi: 10.3934/nhm.2012.7.59
[7]	David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.
[8]	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
[9]	Maide Bucolo, Federica Di Grazia, Luigi Fortuna, Mattia Frasca, Francesca Sapuppo. An environment for complex behaviour detection in bio-potential experiments. Mathematical Biosciences & Engineering, 2008, 5 (2) : 261-276. doi: 10.3934/mbe.2008.5.261
[10]	Zhen Jin, Guiquan Sun, Huaiping Zhu. Epidemic models for complex networks with demographics. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1295-1317. doi: 10.3934/mbe.2014.11.1295
[11]	Guillaume Cantin, Alexandre Thorel. On a generalized diffusion problem: A complex network approach. Discrete and Continuous Dynamical Systems - B, 2022, 27 (4) : 2345-2365. doi: 10.3934/dcdsb.2021135
[12]	Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393
[13]	Mahendra Piraveenan, Mikhail Prokopenko, Albert Y. Zomaya. On congruity of nodes and assortative information content in complex networks. Networks and Heterogeneous Media, 2012, 7 (3) : 441-461. doi: 10.3934/nhm.2012.7.441
[14]	F. S. Vannucchi, S. Boccaletti. Chaotic spreading of epidemics in complex networks of excitable units. Mathematical Biosciences & Engineering, 2004, 1 (1) : 49-55. doi: 10.3934/mbe.2004.1.49
[15]	Chol-Ung Choe, Thomas Dahms, Philipp Hövel, Eckehard Schöll. Control of synchrony by delay coupling in complex networks. Conference Publications, 2011, 2011 (Special) : 292-301. doi: 10.3934/proc.2011.2011.292
[16]	Xiwei Liu, Tianping Chen, Wenlian Lu. Cluster synchronization for linearly coupled complex networks. Journal of Industrial and Management Optimization, 2011, 7 (1) : 87-101. doi: 10.3934/jimo.2011.7.87
[17]	Feng Tao, Hao Shao, KinKeung Lai. Pricing and modularity decisions under competition. Journal of Industrial and Management Optimization, 2020, 16 (1) : 289-307. doi: 10.3934/jimo.2018152
[18]	Jianfeng Jia, Xuewei Liu, Yixin Zhang, Zhe Li, Yanjie Xu, Jiaqi Yan. Rumor propagation controlling based on finding important nodes in complex network. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2521-2529. doi: 10.3934/jimo.2019067
[19]	Giacomo Albi, Lorenzo Pareschi, Mattia Zanella. Opinion dynamics over complex networks: Kinetic modelling and numerical methods. Kinetic and Related Models, 2017, 10 (1) : 1-32. doi: 10.3934/krm.2017001
[20]	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

2020 Impact Factor: 1.213

Tools

Metrics

Other articles
by authors

on AIMS
Manel Hmimida Rushed Kanawati
on Google Scholar
Manel Hmimida Rushed Kanawati

[Back to Top]