Skip to main content
Erschienen in: Data Mining and Knowledge Discovery 5/2017

06.07.2017

Local community detection in multilayer networks

verfasst von: Roberto Interdonato, Andrea Tagarelli, Dino Ienco, Arnaud Sallaberry, Pascal Poncelet

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 5/2017

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Source code and evaluation data are available at http://​people.​dimes.​unical.​it/​andreatagarelli/​mllcd/​
 
3
As specified in the publicly available implementation from the repository at https://​github.​com/​YixuanLi/​LEMON
 
4
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} \)).
 
5
We do not include DBLP in this evaluation because the competitors incurred out-of-memory issues, though our methods did not.
 
6
For \(\textsf {LART} \) and \(\textsf {GL} \) we report only one performance score since they have a deterministic behavior.
 
Literatur
Zurück zum Zitat 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, 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
Zurück zum Zitat Berlingerio M, Pinelli F, Calabrese F (2013) ABACUS: frequent pattern mining-based community discovery in multidimensional networks. Data Min Knowl Discov 27(3):294–320MathSciNetCrossRefMATH Berlingerio M, Pinelli F, Calabrese F (2013) ABACUS: frequent pattern mining-based community discovery in multidimensional networks. Data Min Knowl Discov 27(3):294–320MathSciNetCrossRefMATH
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat Bourqui R, Ienco D, Sallaberry A, Poncelet P (2016) Multilayer graph edge bundling. In: Proc. IEEE Pac Visualization Symp (PacificVis), 184–188 Bourqui R, Ienco D, Sallaberry A, Poncelet P (2016) Multilayer graph edge bundling. In: Proc. IEEE Pac Visualization Symp (PacificVis), 184–188
Zurück zum Zitat Branting K (2012) Context-sensitive detection of local community structure. Soc Netw Anal Min 2(3):279–289CrossRef Branting K (2012) Context-sensitive detection of local community structure. Soc Netw Anal Min 2(3):279–289CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Carchiolo V, Longheu A, Malgeri M, Mangioni G (2010) Communities unfolding in multislice networks. In: Proc. Comp Netw, 187–195 Carchiolo V, Longheu A, Malgeri M, Mangioni G (2010) Communities unfolding in multislice networks. In: Proc. Comp Netw, 187–195
Zurück zum Zitat 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:1344CrossRef 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:1344CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026132CrossRef Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026132CrossRef
Zurück zum Zitat Dickison ME, Magnani M, Rossi L (2016) Multilayer social networks. Cambridge University Press, UKCrossRef Dickison ME, Magnani M, Rossi L (2016) Multilayer social networks. Cambridge University Press, UKCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Hmimida M, Kanawati R (2015) Community detection in multiplex networks: a seed-centric approach. Netw Heterogen Media 10(1):71–85MathSciNetCrossRefMATH Hmimida M, Kanawati R (2015) Community detection in multiplex networks: a seed-centric approach. Netw Heterogen Media 10(1):71–85MathSciNetCrossRefMATH
Zurück zum Zitat Jeub LGS, Mahoney MW, Mucha PJ, Porter MA (2015) A local perspective on community structure in multilayer networks. Netw Sci, 1–20 Jeub LGS, Mahoney MW, Mucha PJ, Porter MA (2015) A local perspective on community structure in multilayer networks. Netw Sci, 1–20
Zurück zum Zitat Kanawati R (2015) Empirical evaluation of applying ensemble methods to ego-centred community identification in complex networks. Neurocomputing 150:417–427CrossRef Kanawati R (2015) Empirical evaluation of applying ensemble methods to ego-centred community identification in complex networks. Neurocomputing 150:417–427CrossRef
Zurück zum Zitat Kim J, Lee J (2015) Community detection in multi-layer graphs: a survey. SIGMOD Rec 44(3):37–48CrossRef Kim J, Lee J (2015) Community detection in multi-layer graphs: a survey. SIGMOD Rec 44(3):37–48CrossRef
Zurück zum Zitat Kivela M, Arenas A, Barthelemy M, Gleeson JP, Moreno Y, Porter MA (2014) Mutilayer networks. J Complex Netw 2(3):203–271CrossRef Kivela M, Arenas A, Barthelemy M, Gleeson JP, Moreno Y, Porter MA (2014) Mutilayer networks. J Complex Netw 2(3):203–271CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat Michoel T, Nachtergaele B (2012) Alignment and integration of complex networks by hypergraph-based spectral clustering. Phis. Rev. E 85:056111CrossRef Michoel T, Nachtergaele B (2012) Alignment and integration of complex networks by hypergraph-based spectral clustering. Phis. Rev. E 85:056111CrossRef
Zurück zum Zitat 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–878MathSciNetCrossRefMATH 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–878MathSciNetCrossRefMATH
Zurück zum Zitat Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys. Rev. E 69(2):026113CrossRef Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys. Rev. E 69(2):026113CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Tang L, Wang X, Liu H (2009) Uncovering groups via heterogeneous interaction analysis. In: Proc. ICDM, 503–512 Tang L, Wang X, Liu H (2009) Uncovering groups via heterogeneous interaction analysis. In: Proc. ICDM, 503–512
Zurück zum Zitat Tang L, Wang X, Liu H (2012) Community detection via heterogeneous interaction analysis. Data Min Knowl Discov 25:1–33MathSciNetCrossRef Tang L, Wang X, Liu H (2012) Community detection via heterogeneous interaction analysis. Data Min Knowl Discov 25:1–33MathSciNetCrossRef
Zurück zum Zitat Yakoubi Z, Kanawati R (2014) LICOD: a leader-driven algorithm for community detection in complex networks. Vietnam J Comput Sci 1(4):241–256CrossRef Yakoubi Z, Kanawati R (2014) LICOD: a leader-driven algorithm for community detection in complex networks. Vietnam J Comput Sci 1(4):241–256CrossRef
Zurück zum Zitat 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 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
Metadaten
Titel
Local community detection in multilayer networks
verfasst von
Roberto Interdonato
Andrea Tagarelli
Dino Ienco
Arnaud Sallaberry
Pascal Poncelet
Publikationsdatum
06.07.2017
Verlag
Springer US
Erschienen in
Data Mining and Knowledge Discovery / Ausgabe 5/2017
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI
https://doi.org/10.1007/s10618-017-0525-y

Weitere Artikel der Ausgabe 5/2017

Data Mining and Knowledge Discovery 5/2017 Zur Ausgabe