Abstract
The problem of local community detection in graphs refers to the identification of a community that is specific to a query node and relies on limited information about the network structure. Existing approaches for this problem are defined to work in dynamic network scenarios, however they are not designed to deal with complex real-world networks, in which multiple types of connectivity might be considered. In this work, we fill this gap in the literature by introducing the first framework for local community detection in multilayer networks (ML-LCD). We formalize the ML-LCD optimization problem and provide three definitions of the associated objective function, which correspond to different ways to incorporate within-layer and across-layer topological features. We also exploit our framework to generate multilayer global community structures. We conduct an extensive experimentation using seven real-world multilayer networks, which also includes comparison with state-of-the-art methods for single-layer local community detection and for multilayer global community detection. Results show the significance of our proposed methods in discovering local communities over multiple layers, and also highlight their ability in producing global community structures that are better in modularity than those produced by native global community detection approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
Source code and evaluation data are available at http://people.dimes.unical.it/andreatagarelli/mllcd/
As specified in the publicly available implementation from the repository at https://github.com/YixuanLi/LEMON
Experiments were carried out on an Intel Core i7-3960X CPU @3.30GHz, 64GB RAM machine. All our algorithms are written in Python. Original codes of competing methods are in Python (\(\textsf {LART} \)) and Matlab (\(\textsf {PMM} \) and \(\textsf {GL} \)).
We do not include DBLP in this evaluation because the competitors incurred out-of-memory issues, though our methods did not.
For \(\textsf {LART} \) and \(\textsf {GL} \) we report only one performance score since they have a deterministic behavior.
References
Berlingerio M, Coscia M, Giannotti F (2011) Finding and characterizing communities in multidimensional networks. In: Proc. IEEE/ACM Int. Conf. Adv Soc Netw Anal Min (ASONAM), 490–494
Berlingerio M, Pinelli F, Calabrese F (2013) ABACUS: frequent pattern mining-based community discovery in multidimensional networks. Data Min Knowl Discov 27(3):294–320
Boden B, Günnemann S, Hoffmann H, Seidl T (2012) Mining coherent subgraphs in multi-layer graphs with edge labels. In: Proc. ACM SIGKDD Int. Conf. Knowl Discovery and Data Min (KDD), 1258–1266
Bonchi F, Gionis A, Gullo F, Ukkonen A (2014) Distance oracles in edge-labeled graphs. In: Proc. Int. Conf. Ext Database Technol (EDBT), 547–558
Bourqui R, Ienco D, Sallaberry A, Poncelet P (2016) Multilayer graph edge bundling. In: Proc. IEEE Pac Visualization Symp (PacificVis), 184–188
Branting K (2012) Context-sensitive detection of local community structure. Soc Netw Anal Min 2(3):279–289
Cai D, Shao Z, He X, Yan X, Han J (2005) Community Mining from Multi-relational Networks. In: Proc. Europ Conf. Princ Pract Knowl Discov Databases (PKDD), 445–452
Carchiolo V, Longheu A, Malgeri M, Mangioni G (2010) Communities unfolding in multislice networks. In: Proc. Comp Netw, 187–195
Cardillo A, Gomez-Gardenes J, Zanin M, Romance M, Papo D, del Pozo F, Boccaletti S (2013) Emergence of network features from multiplexity. Sci Rep 3:1344
Chen J, Zaïane OR, Goebel R (2009) Local community identification in social networks. In: Proc. IEEE/ACM Int. Conf. Adv Soc Netw Anal Min (ASONAM), 237–242
Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026132
Dickison ME, Magnani M, Rossi L (2016) Multilayer social networks. Cambridge University Press, UK
Fagnan J, Zaïane OR, Barbosa D (2014) Using triads to identify local community structure in social networks. In: Proc. IEEE/ACM Int. Conf. on Adv Soc Netw Anal Min(ASONAM), 108–112
Hmimida M, Kanawati R (2015) Community detection in multiplex networks: a seed-centric approach. Netw Heterogen Media 10(1):71–85
Jeub LGS, Mahoney MW, Mucha PJ, Porter MA (2015) A local perspective on community structure in multilayer networks. Netw Sci, 1–20
Kanawati R (2015) Empirical evaluation of applying ensemble methods to ego-centred community identification in complex networks. Neurocomputing 150:417–427
Kim J, Lee J (2015) Community detection in multi-layer graphs: a survey. SIGMOD Rec 44(3):37–48
Kivela M, Arenas A, Barthelemy M, Gleeson JP, Moreno Y, Porter MA (2014) Mutilayer networks. J Complex Netw 2(3):203–271
Kuncheva Z, Montana G (2015) Community detection in multiplex networks using locally adaptive random walks. In: Proc. IEEE/ACM Int. Conf. on Adv Soc Netw Anal Min (ASONAM), 1308–1315
Li Y, He K, Bindel D, Hopcroft JE (2015) Uncovering the small community structure in large networks: a local spectral approach. In: Proc. ACM Conf. on World Wide Web (WWW), 658–668
Loe CW, Jensen HJ (2015) Comparison of communities detection algorithms for multiplex. Phys A 431:29–45
Michoel T, Nachtergaele B (2012) Alignment and integration of complex networks by hypergraph-based spectral clustering. Phis. Rev. E 85:056111
Mucha PJ, Richardson T, Macon K, Porter MA, Onnela J-P (2010) Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980):876–878
Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys. Rev. E 69(2):026113
Papalexakis EE, Akoglu L, Ienco D (2013) Do more views of a graph help? community detection and clustering in multi-graphs. In: Proc. Int. Conf. on Inform Fus, 899–905
Tang L, Wang X, Liu H (2009) Uncovering groups via heterogeneous interaction analysis. In: Proc. ICDM, 503–512
Tang L, Wang X, Liu H (2012) Community detection via heterogeneous interaction analysis. Data Min Knowl Discov 25:1–33
Yakoubi Z, Kanawati R (2014) LICOD: a leader-driven algorithm for community detection in complex networks. Vietnam J Comput Sci 1(4):241–256
Zakrzewska A, Bader DA (2015) A dynamic algorithm for local community detection in graphs. In: Proc. IEEE/ACM Int. Conf. Adv Soc Netw Anal Min (ASONAM), 559–564
Acknowledgements
D. Ienco would like to acknowledge the National French Center for Spatial Study (CNES), in the framework of the project “DYNAMITEF TOSCA 2016”, to support this study with the RemoteSensing dataset.
Author information
Authors and Affiliations
Corresponding author
Additional information
Responsible editor: Kurt Driessens, Dragi Kocev, Marko Robnik-Šikonja Myra Spiliopoulou.
Rights and permissions
About this article
Cite this article
Interdonato, R., Tagarelli, A., Ienco, D. et al. Local community detection in multilayer networks. Data Min Knowl Disc 31, 1444–1479 (2017). https://doi.org/10.1007/s10618-017-0525-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10618-017-0525-y