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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions

verfasst von : Remco van der Hofstad

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Due to its ease of use, as well as its enormous flexibility in its degree structure, the configuration model has become the network model of choice in many disciplines. It has the wonderful property, that, conditioned on being simple, it is a uniform random graph with the prescribed degrees. This is a beautiful example of a general technique called the probabilistic method that was pioneered by Erdős. It allows us to count rather precisely how many graphs there are with various degree structures. As a result, the configuration model is often used as a null model in network theory, so as to compare real-world network data to. When the degrees are sufficiently light-tailed, the asymptotic probability of simplicity for the configuration model can be explicitly computed. Unfortunately, when the degrees vary rather extensively and vertices with very high degrees are present, this method fails. Since such degree sequences are frequently reported in empirical work, this is a major caveat in network theory.
In this survey, we discuss recent results for the configuration model, including asymptotic results for typical distances in the graph, asymptotics for the number of self-loops and multiple edges in the finite-variance case. We also discuss a possible fix to the problem of non-simplicity, and what the effect of this fix is on several graph statistics. Further, we discuss a generalization of the configuration model that allows for the inclusion of community structures. This model removes the flaw of the locally tree-like nature of the configuration model, and gives a much improved fit to real-world networks.

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 On Bubble Generators in Directed Graphs
Literatur
1.
Angel, O., van der Hofstad, R., Holmgren, C.: Limit laws for self-loops and multiple edges in the configuration model. arXiv:​1603.​07172 [math.PR], Preprint (2016)
2.
3.
Bender, E., Canfield, E.: The asymptotic number of labelled graphs with given degree sequences. J. Comb. Theory (A) 24, 296–307 (1978)CrossRefMATH
4.
Bollobás, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb. 1(4), 311–316 (1980)CrossRefMathSciNetMATH
5.
Bollobás, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, vol. 73, 2nd edn. Cambridge University Press, Cambridge (2001)
6.
Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18(3), 279–290 (2001)CrossRefMathSciNetMATH
7.
Britton, T., Deijfen, M., Martin-Löf, A.: Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124(6), 1377–1397 (2006)CrossRefMathSciNetMATH
8.
Durrett, R.: Random Graph Dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2007)MATH
9.
10.
Erdős, P., Gallai, T.: Graphs with points of prescribed degrees. Mat. Lapok 11, 264–274 (1960). (Hungarian)
11.
12.
Erdős, P., Rényi, A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5, 17–61 (1960)
13.
Erdős, P., Rényi, A.: On the evolution of random graphs. Bull. Inst. Int. Stat. 38, 343–347 (1961)MathSciNetMATH
14.
Erdős, P., Rényi, A.: On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar. 12, 261–267 (1961)CrossRefMathSciNetMATH
15.
Faloutsos, C., Faloutsos, P., Faloutsos, M.: On power-law relationships of the internet topology. Comput. Commun. Rev. 29, 251–262 (1999)CrossRefMATH
16.
Federico, L., van der Hofstad, R.: Critical window for connectivity in the configuration model. Combin. Probab. Comput. 26(5), 660–680 (2017)CrossRefMathSciNetMATH
17.
18.
19.
van der Hofstad, R.: Random graphs and complex networks. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 1. Cambridge University Press, Cambridge (2017)
20.
21.
van der Hofstad, R., Hooghiemstra, G., Van Mieghem, P.: Distances in random graphs with finite variance degrees. Random Struct. Algorithms 27(1), 76–123 (2005)
22.
van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab. 12(25), 703–766 (2007). (Electronic)
23.
van der Hofstad, R., van Leeuwaarden, J., Stegehuis, C.: Hierarchical configuration model. arXiv:​1512.​08397 [math.PR], Preprint (2015)
24.
25.
26.
Kleinberg, J.M.: The small-world phenomenon: an algorithm perspective. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 163–170, May 2000
27.
Krioukov, D., Kitsak, M., Sinkovits, R., Rideout, D., Meyer, D., Boguñá, M.: Network cosmology. Sci. Rep. 2, Article number 793 (2012)
28.
Leskovec, J., Lang, K., Dasgupta, A., Mahoney, M.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)CrossRefMathSciNetMATH
29.
Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2–3), 161–179 (1995)CrossRefMathSciNetMATH
30.
Molloy, M., Reed, B.: The size of the Giant component of a random graph with a given degree sequence. Comb. Probab. Comput. 7(3), 295–305 (1998)CrossRefMathSciNetMATH
31.
Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010)
32.
Newman, M.E.J., Watts, D.: Scaling and percolation in the small-world network model. Phys. Rev. E 60, 7332–7344 (1999)CrossRef
33.
Stegehuis, C., van der Hofstad, R., van Leeuwaarden, J.: Epidemic spreading on complex networks with community structures. Sci. Rep. 6, 29748 (2016)
34.
Stegehuis, C., van der Hofstad, R., van Leeuwaarden, J.: Power-law relations in random networks with communities. Phys. Rev. E 94, 012302 (2016)
35.
Watts, D.J.: Small Worlds. The Dynamics of Networks Between Order and Randomness. Princeton Studies in Complexity. Princeton University Press, Princeton (1999)
36.
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)CrossRefMATH
Metadaten
Titel
Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions
verfasst von
Remco van der Hofstad
Copyright-Jahr
2017
Buch
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-319-68704-9

Electronic ISBN: 978-3-319-68705-6

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-68705-6_1