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:
Modularity of the ABCD Random Graph Model with Community Structure Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

Correcting Output Degree Sequences in Chung-Lu Random Graph Generation

verfasst von : Christopher Brissette, David Liu, George M. Slota

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

Random graphs play a central role in network analysis. The Chung-Lu random graph model is one particularly popular model, which connects nodes according to their desired degrees to form a specific degree distribution in expectation. Despite its popularity, the standard Chung-Lu graph generation algorithms are susceptible to significant degree sequence errors when generating simple graphs. In this manuscript, we suggest multiple methods for improving the accuracy of Chung-Lu graph generation by computing node weights which better recreate the desired output degree sequence. We show that each of our solutions offer a significant improvement in degree sequence accuracy.

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
Vorheriges Kapitel A Stochastic Approach for Extracting Community-Based Backbones
Nächstes Kapitel Switching In and Out of Sync: A Controlled Adaptive Network Model of Transition Dynamics in the Effects of Interpersonal Synchrony on Affiliation
Fußnoten
Literatur
1.
Alam, M., Khan, M., Vullikanti, A., Marathe, M.: An efficient and scalable algorithmic method for generating large-scale random graphs. In: SC’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. pp. 372–383. IEEE (2016)
2.
Batagelj, V., Brandes, U.: Efficient generation of large random networks. Phys. Rev. E 71(3), 036113 (2005)CrossRef
3.
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
4.
Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: Numerical Optimization: Theoretical and Practical Aspects. Springer Science & Business Media (2006)
5.
Brissette, C., Slota, G.M.: Limitations of Chung Lu random graph generation. In: International Conference on Complex Networks and Their Applications. pp. 451–462. Springer (2021)
6.
Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. Proc. Nat. Acad. Sci. 99(25), 15879–15882 (2002)CrossRefMATH
7.
Drobyshevskiy, M., Turdakov, D.: Random graph modeling: a survey of the concepts. ACM Comput. Surveys (CSUR) 52(6), 1–36 (2019)CrossRef
8.
Durak, N., Kolda, T.G., Pinar, A., Seshadhri, C.: A scalable null model for directed graphs matching all degree distributions: in, out, and reciprocal. In: 2013 IEEE 2nd Network Science Workshop (NSW). pp. 23–30. IEEE (2013)
9.
Fosdick, B.K., Larremore, D.B., Nishimura, J., Ugander, J.: Configuring random graph models with fixed degree sequences. SIAM Rev. 60(2), 315–355 (2018)CrossRefMATH
10.
Garbus, J., Brissette, C., Slota, G.M.: Parallel generation of simple null graph models. In: The 5th IEEE Workshop on Parallel and Distributed Processing for Computational Social Systems (ParSocial) (2020)
11.
Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using network. Tech. rep., Los Alamos National Lab. (LANL), Los Alamos, NM (United States) (2008)
12.
Holland, P.W., Laskey, K.B., Leinhardt, S.: Stochastic blockmodels: first steps. Soc. Netw. 5(2), 109–137 (1983)CrossRef
13.
Kolda, T.G., Pinar, A., Plantenga, T., Seshadhri, C.: A scalable generative graph model with community structure. SIAM J. Sci. Comput. 36(5), C424–C452 (2014)CrossRefMATH
14.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824–827 (2002)CrossRef
15.
Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2–3), 161–180 (1995)CrossRefMATH
16.
Newman, M.E.: Modularity and community structure in networks. Proc. Nat. Acad. Sci. 103(23), 8577–8582 (2006)CrossRef
17.
Slota, G.M., Berry, J., Hammond, S.D., Olivier, S., Phillips, C., Rajamanickam, S.: Scalable generation of graphs for benchmarking HPC community-detection algorithms. In: IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC) (2019)
18.
Slota, G.M., Garbus, J.: A parallel LFR-like benchmark for evaluating community detection algorithms. In: The 5th IEEE Workshop on Parallel and Distributed Processing for Computational Social Systems (ParSocial) (2020)
19.
Winlaw, M., DeSterck, H., Sanders, G.: An in-depth analysis of the Chung-Lu model. Tech. rep., Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States) (2015)
20.
Zaki, M.J., Meira Jr, W., Meira, W.: Data Mining and Analysis: Fundamental Concepts and Algorithms. Cambridge University Press (2014)
Metadaten
Titel
Correcting Output Degree Sequences in Chung-Lu Random Graph Generation
verfasst von
Christopher Brissette
David Liu
George M. Slota
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_6

Premium Partner

    Bildnachweise