nach oben

Computing

Erschienen in:

01.11.2014

Fast multi-scale detection of overlapping communities using local criteria

verfasst von: Erwan Le Martelot, Chris Hankin

Erschienen in: Computing | Ausgabe 11/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Many systems can be described using graphs, or networks. Detecting communities in these networks can provide information about the underlying structure and functioning of the original systems. Yet this detection is a complex task and a large amount of work was dedicated to it in the past decade. One important feature is that communities can be found at several scales, or levels of resolution, indicating several levels of organisation. Therefore a graph may have several community structures. Also networks tend to be large and hence require efficient processing. In this work, we present a new algorithm with linear complexity for the fast detection of communities across scales using a local criterion. We exploit the local aspect of the criterion to enable parallel computation and improve the execution speed further. The algorithm is tested against very large generated multi-scale networks and experiments demonstrate its efficiency and accuracy.

Nächster Artikel Multicast routing protocols in wireless mesh networks: a survey

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

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

The code developed for this work is available for download from http://www.elemartelot.org.

Arenas A, Fernandez A, Gomez S (2008) Analysis of the structure of complex networks at different resolution levels. N J Phys 10:053039. doi:10.1088/1367-2630/10/5/053039 MathSciNetCrossRef

Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):1742–5468

Courtois PJ, Heymans F, Parnas DL (1971) Concurrent control with “readers” and “writers”. Commun ACM 14(10):667–668. doi:10.1145/362759.362813 CrossRef

Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174. doi:10.1016/j.physrep.2009.11.002

Fred ALN, Jain AK (2003) Robust data clustering. IEEE Comput Soc Conf Comput Vis Pattern Recognit 2:128–133. doi:10.1109/CVPR.2003.1211462

Huang J, Sun H, Liu Y, Song Q, Weninger T (2011) Towards online multiresolution community detection in large-scale networks. PLoS One 6(8):e23829. doi:10.1371/journal.pone.0023829

Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80(1):016118. doi:10.1103/PhysRevE.80.016118 CrossRef

Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. N J Phys 11(3):033015

Le Martelot E, Hankin C (2013) Fast multi-scale detection of relevant communities in large scale networks. Comput J. doi:10.1093/comjnl/bxt002

10.

Le Martelot E, Hankin C (2013) Multi-scale community detection using stability optimisation. Int J Web Based Communities (IJWBC) (Special issue on community structure in complex networks) 9(3):323–348. doi:10.1504/IJWBC.2013.054907

11.

Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2008) Statistical properties of community structure in large social and information networks. In: Proceeding of the 17th international conference on world wide web. WWW ’08. ACM, New York, NY, USA, pp 695–704. doi:10.1145/1367497.1367591

12.

Leskovec J, Lang KJ, Mahoney M (2010) Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th international conference on world wide web. WWW ’10. ACM, New York, NY, USA, pp 631–640. doi:10.1145/1772690.1772755

13.

Newman MEJ (2010) Networks: an introduction, 1st edn. Oxford University Press, OxfordCrossRef

14.

Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113CrossRef

15.

Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106. doi:10.1103/PhysRevE.76.036106 CrossRef

16.

Reichardt J, Bornholdt S (2006) Statistical mechanics of community detection. Phys Rev E 74(1 Pt 2):016110

17.

Riedy EJ, Meyerhenke H, Ediger D, Bader DA (2012) Parallel community detection for massive graphs. In: Proceedings of 10th DIMACS implementation challenge—graph partitioning and graph clustering, Atlanta, Georgia

18.

Ronhovde P, Nussinov Z (2010) Local resolution-limit-free Potts model for community detection. Phys Rev E 81(4):046114. doi:10.1103/PhysRevE.81.046114 CrossRef

19.

Simon HA (1962) The architecture of complexity. Proc Am Philos Soc 106(6):467–482

20.

Soman J, Narang A (2011) Fast community detection algorithm with GPUs and multicore architectures. In: Proceedings of parallel distributed processing symposium (IPDPS), 2011 IEEE International, pp 568–579. doi:10.1109/IPDPS.2011.61

Titel: Fast multi-scale detection of overlapping communities using local criteria
verfasst von: Erwan Le Martelot
Chris Hankin
Publikationsdatum: 01.11.2014
Verlag: Springer Vienna
Erschienen in: Computing / Ausgabe 11/2014
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-014-0401-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 11/2014

Erratum to: Algebraic flux correction for nonconforming finite element discretizations of scalar transport problems

Improved scheduler for multi-core many-core systems

On the efficiency of several VM provisioning strategies for workflows with multi-threaded tasks on clouds

Multicast routing protocols in wireless mesh networks: a survey

Premium Partner