American Institute of Mathematical Sciences

Advanced
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

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 & 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.  doi: 10.1162/153244303321897735.  Google Scholar

[2]

A. Amelio and C. Pizzuti, A cooperative evolutionary approach to learn communities in multilayer networks,, in Parallel Problem Solving from Nature-PPSN XIII, (8672), 222.  doi: 10.1007/978-3-319-10762-2_22.  Google Scholar

[3]

F. Battiston, V. Nicosia and V. Latora, Structural measures for multiplex networks,, Physical Review E, 89 (2014).  doi: 10.1103/PhysRevE.89.032804.  Google Scholar

[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), (2011), 490.  doi: 10.1109/ASONAM.2011.104.  Google Scholar

[5]

M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale and D. Pedreschi, Evolving networks: Eras and turning points,, Intell. Data Anal., 17 (2013), 27.   Google Scholar

[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.  doi: 10.1007/s10618-013-0331-0.  Google Scholar

[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).  doi: 10.1088/1742-5468/2008/10/P10008.  Google Scholar

[8]

P. Brodka and P. Kazienko, Encyclopedia of Social Network Analysis and Mining, Ch. Multi-layered Social Networks,, Springer, (2014).   Google Scholar

[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), (2011), 237.   Google Scholar

[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, (2005), 58.  doi: 10.1145/1134271.1134280.  Google Scholar

[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, (2013).   Google Scholar

[12]

J. Dahlin and P. Svenson, Ensemble approaches for improving community detection methods,, CoRR, (2013).   Google Scholar

[13]

M. De Domenico, A. Solé, S. Gómez and A. Arenas, Random walks on multiplex networks,, CoRR, (2013).   Google Scholar

[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, (2001), 613.  doi: 10.1145/371920.372165.  Google Scholar

[15]

S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75.  doi: 10.1016/j.physrep.2009.11.002.  Google Scholar

[16]

B. H. Good, Y.-A. de Montjoye and A. Clauset, Performance of modularity maximization in practical contexts,, Physical Review E, 81 (2010).  doi: 10.1103/PhysRevE.81.046106.  Google Scholar

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

[18]

R. Kanawati, YASCA: An ensemble-based approach for community detection in complex networks,, in Computing and Combinatorics, (8591), 657.  doi: 10.1007/978-3-319-08783-2_57.  Google Scholar

[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), (2010), 5.  doi: 10.1109/WI-IAT.2010.313.  Google Scholar

[20]

M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno and M. A. Porter, Multilayer networks,, preprint, (2013).   Google Scholar

[21]

S. Massoud, Coeurs Stables de Communautés dans les Graphes de Terrain,, Ph.D thesis, (2012).   Google Scholar

[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.  doi: 10.1126/science.1184819.  Google Scholar

[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.  doi: 10.1126/science.1184819.  Google Scholar

[24]

T. Murata, Modularity for heterogeneous networks,, in Proceedings of the 21st ACM Conference on Hypertext and Hypermedia, (2010), 129.  doi: 10.1145/1810617.1810640.  Google Scholar

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

[26]

J. Reichardt and S. Bornholdt, Statistical mechanics of community detection,, Physical Review E, 74 (2006).  doi: 10.1103/PhysRevE.74.016110.  Google Scholar

[27]

K. Rushed, Seed-centric approaches for community detection in complex networks,, in Social Computing and Social Media, (2014), 197.   Google Scholar

[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), (2013), 3262.  doi: 10.1109/HICSS.2013.179.  Google Scholar

[29]

L. Tang and H. Liu, Community detection and mining in social media,, Synthesis Lectures on Data Mining and Knowledge Discovery, 2 (2010), 1.  doi: 10.2200/S00298ED1V01Y201009DMK003.  Google Scholar

[30]

Y. Zied and K. Rushed, Licod: Leader-driven approach for community detection in complex networks,, Vietnam Journal of Computer Science, (2014).   Google Scholar

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.  doi: 10.1162/153244303321897735.  Google Scholar

[2]

A. Amelio and C. Pizzuti, A cooperative evolutionary approach to learn communities in multilayer networks,, in Parallel Problem Solving from Nature-PPSN XIII, (8672), 222.  doi: 10.1007/978-3-319-10762-2_22.  Google Scholar

[3]

F. Battiston, V. Nicosia and V. Latora, Structural measures for multiplex networks,, Physical Review E, 89 (2014).  doi: 10.1103/PhysRevE.89.032804.  Google Scholar

[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), (2011), 490.  doi: 10.1109/ASONAM.2011.104.  Google Scholar

[5]

M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale and D. Pedreschi, Evolving networks: Eras and turning points,, Intell. Data Anal., 17 (2013), 27.   Google Scholar

[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.  doi: 10.1007/s10618-013-0331-0.  Google Scholar

[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).  doi: 10.1088/1742-5468/2008/10/P10008.  Google Scholar

[8]

P. Brodka and P. Kazienko, Encyclopedia of Social Network Analysis and Mining, Ch. Multi-layered Social Networks,, Springer, (2014).   Google Scholar

[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), (2011), 237.   Google Scholar

[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, (2005), 58.  doi: 10.1145/1134271.1134280.  Google Scholar

[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, (2013).   Google Scholar

[12]

J. Dahlin and P. Svenson, Ensemble approaches for improving community detection methods,, CoRR, (2013).   Google Scholar

[13]

M. De Domenico, A. Solé, S. Gómez and A. Arenas, Random walks on multiplex networks,, CoRR, (2013).   Google Scholar

[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, (2001), 613.  doi: 10.1145/371920.372165.  Google Scholar

[15]

S. Fortunato, Community detection in graphs,, Physics Reports, 486 (2010), 75.  doi: 10.1016/j.physrep.2009.11.002.  Google Scholar

[16]

B. H. Good, Y.-A. de Montjoye and A. Clauset, Performance of modularity maximization in practical contexts,, Physical Review E, 81 (2010).  doi: 10.1103/PhysRevE.81.046106.  Google Scholar

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

[18]

R. Kanawati, YASCA: An ensemble-based approach for community detection in complex networks,, in Computing and Combinatorics, (8591), 657.  doi: 10.1007/978-3-319-08783-2_57.  Google Scholar

[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), (2010), 5.  doi: 10.1109/WI-IAT.2010.313.  Google Scholar

[20]

M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno and M. A. Porter, Multilayer networks,, preprint, (2013).   Google Scholar

[21]

S. Massoud, Coeurs Stables de Communautés dans les Graphes de Terrain,, Ph.D thesis, (2012).   Google Scholar

[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.  doi: 10.1126/science.1184819.  Google Scholar

[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.  doi: 10.1126/science.1184819.  Google Scholar

[24]

T. Murata, Modularity for heterogeneous networks,, in Proceedings of the 21st ACM Conference on Hypertext and Hypermedia, (2010), 129.  doi: 10.1145/1810617.1810640.  Google Scholar

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

[26]

J. Reichardt and S. Bornholdt, Statistical mechanics of community detection,, Physical Review E, 74 (2006).  doi: 10.1103/PhysRevE.74.016110.  Google Scholar

[27]

K. Rushed, Seed-centric approaches for community detection in complex networks,, in Social Computing and Social Media, (2014), 197.   Google Scholar

[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), (2013), 3262.  doi: 10.1109/HICSS.2013.179.  Google Scholar

[29]

L. Tang and H. Liu, Community detection and mining in social media,, Synthesis Lectures on Data Mining and Knowledge Discovery, 2 (2010), 1.  doi: 10.2200/S00298ED1V01Y201009DMK003.  Google Scholar

[30]

Y. Zied and K. Rushed, Licod: Leader-driven approach for community detection in complex networks,, Vietnam Journal of Computer Science, (2014).   Google Scholar

[1]

Guillaume Cantin, M. A. Aziz-Alaoui. Dimension estimate of attractors for complex networks of reaction-diffusion systems applied to an ecological model. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020283
[2]

Xiaoxian Tang, Jie Wang. Bistability of sequestration networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1337-1357. doi: 10.3934/dcdsb.2020165
[3]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011
[4]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020406
[5]

D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346
[6]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344
[7]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[8]

Pedro Aceves-Sanchez, Benjamin Aymard, Diane Peurichard, Pol Kennel, Anne Lorsignol, Franck Plouraboué, Louis Casteilla, Pierre Degond. A new model for the emergence of blood capillary networks. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021001
[9]

Leslaw Skrzypek, Yuncheng You. Feedback synchronization of FHN cellular neural networks. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021001
[10]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[11]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170
[12]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002
[13]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049
[14]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310
[15]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016
[16]

Hongfei Yang, Xiaofeng Ding, Raymond Chan, Hui Hu, Yaxin Peng, Tieyong Zeng. A new initialization method based on normed statistical spaces in deep networks. Inverse Problems & Imaging, 2021, 15 (1) : 147-158. doi: 10.3934/ipi.2020045
[17]

Susmita Sadhu. Complex oscillatory patterns near singular Hopf bifurcation in a two-timescale ecosystem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020342
[18]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060
[19]

Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155
[20]

Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164

2019 Impact Factor: 1.053

Tools

Metrics

  • PDF downloads (293)
  • HTML views (0)
  • Cited by (24)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences