Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2023 | OriginalPaper | Buchkapitel

Modularity of the ABCD Random Graph Model with Community Structure

verfasst von : Bogumił Kamiński, Bartosz Pankratz, Paweł Prałat, François Théberge

Erschienen in: Complex Networks and Their Applications XI

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Artificial Benchmark for Community Detection graph (ABCD) is a random graph model with community structure and power-law distribution for both degrees and community sizes. The model generates graphs with similar properties as the well-known LFR one, and its main parameter \(\xi \) can be tuned to mimic its counterpart in the LFR model, the mixing parameter \(\mu \). In this paper, we investigate various theoretical asymptotic properties of the ABCD model. In particular, we analyze the modularity function, arguably, the most important graph property of networks in the context of community detection. Indeed, the modularity function is often used to measure the presence of community structure in networks. It is also used as a quality function in many community detection algorithms, including the widely used Louvain algorithm.

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!

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"

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
Nächstes Kapitel Learning Attribute Distributions Through Random Walks
Fußnoten
Literatur
1.
Aiello, W., Bonato, A., Cooper, C., Janssen, J., Prałat, P.: A spatial web graph model with local influence regions. Internet Math. 5(1–2), 175–196 (2008)CrossRefMATH
2.
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
3.
Bender, E.A., Canfield, E.R.: The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theor. Ser. A 24(3), 296–307 (1978)CrossRefMATH
4.
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mechan. Theor. Exper. 2008(10), P10008 (2008)CrossRefMATH
5.
Bollobás, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Euro. J. Combin. 1(4), 311–316 (1980)CrossRefMATH
6.
Chellig, J., Fountoulakis, N., Skerman, F.: The modularity of random graphs on the hyperbolic plane. J. Complex Netw. 10(1), cnab051 (2022)
7.
Chung Graham, F., Lu, L.: Complex Graphs and Networks, no. 107. American Mathematical Society (2006)
8.
Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004)CrossRef
9.
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)CrossRef
10.
Fortunato, S., Barthelemy, M.: Resolution limit in community detection. Proc. Nat. Acad. Sci. 104(1), 36–41 (2007)CrossRef
11.
Kamiński, B., Pankratz, B., Prałat, P., Théberge, F.: Modularity of the abcd random graph model with community structure. arXiv:​2203.​01480 (2022)
12.
Kamiński, B., Poulin, V., Prałat, P., Szufel, P., Théberge, F.: Clustering via hypergraph modularity. PloS One 14(11), e0224307 (2019)CrossRef
13.
Kamiński, B., Prałat, P., Théberge, F.: Community detection algorithm using hypergraph modularity. In: International Conference on Complex Networks and Their Applications, pp. 152–163. Springer (2020)
14.
Kamiński, B., Prałat, P., Théberge, F.: Artificial benchmark for community detection (ABCD)-fast random graph model with community structure. Netw. Sci. 1–26 (2021)
15.
Kamiński, B., Prałat, P., Théberge, F.: Mining Complex Networks (2021)
16.
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Boguná, M.: Hyperbolic geometry of complex networks. Phys. Rev. E 82(3), 036106 (2010)CrossRef
17.
Lambiotte, R., Schaub, M.: Modularity and dynamics on complex networks (2021)
18.
Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80(1), 016118 (2009)CrossRef
19.
Lancichinetti, A., Fortunato, S.: Limits of modularity maximization in community detection. Phys. Rev. E 84(6), 066122 (2011)CrossRef
20.
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)CrossRef
21.
Lichev, L., Mitsche, D.: On the modularity of 3-regular random graphs and random graphs with given degree sequences. arXiv:​2007.​15574 (2020)
22.
McDiarmid, C., Skerman, F.: Modularity of regular and treelike graphs. J. Complex Netw. 6(4), 596–619 (2018)CrossRefMATH
23.
McDiarmid, C., Skerman, F.: Modularity of erdős-rényi random graphs. Random Struct. Algorithms 57(1), 211–243 (2020)CrossRefMATH
24.
Newman, M.E.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69(6), 066133 (2004)CrossRef
25.
Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)CrossRef
26.
Prokhorenkova, L.O., Prałat, P., Raigorodskii, A.: Modularity of complex networks models. Internet Math. (2017)
27.
Wormald, N.C.: Generating random regular graphs. J. Algorithms 5(2), 247–280 (1984)CrossRefMATH
28.
Wormald, N.C., et al.: Models of random regular graphs. In: London Mathematical Society Lecture Note Series, pp. 239–298 (1999)
Metadaten
Titel
Modularity of the ABCD Random Graph Model with Community Structure
verfasst von
Bogumił Kamiński
Bartosz Pankratz
Paweł Prałat
François Théberge
Copyright-Jahr
2023
Buch
Complex Networks and Their Applications XI

Print ISBN: 978-3-031-21130-0

Electronic ISBN: 978-3-031-21131-7

Copyright-Jahr: 2023

DOI
https://doi.org/10.1007/978-3-031-21131-7_1

Premium Partner

    Bildnachweise