Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions | SpringerLink
Skip to main content
Springer Nature Link
Log in

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

  • Conference paper
  • First Online:
Graph-Theoretic Concepts in Computer Science (WG 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10520))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  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. Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bender, E., Canfield, E.: The asymptotic number of labelled graphs with given degree sequences. J. Comb. Theory (A) 24, 296–307 (1978)

    Article  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bollobás, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, vol. 73, 2nd edn. Cambridge University Press, Cambridge (2001)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  8. Durrett, R.: Random Graph Dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2007)

    MATH  Google Scholar 

  9. Erdős, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc. 53, 292–294 (1947)

    Article  MathSciNet  MATH  Google Scholar 

  10. Erdős, P., Gallai, T.: Graphs with points of prescribed degrees. Mat. Lapok 11, 264–274 (1960). (Hungarian)

    Google Scholar 

  11. Erdős, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6, 290–297 (1959)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  13. Erdős, P., Rényi, A.: On the evolution of random graphs. Bull. Inst. Int. Stat. 38, 343–347 (1961)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  15. Faloutsos, C., Faloutsos, P., Faloutsos, M.: On power-law relationships of the internet topology. Comput. Commun. Rev. 29, 251–262 (1999)

    Article  MATH  Google Scholar 

  16. Federico, L., van der Hofstad, R.: Critical window for connectivity in the configuration model. Combin. Probab. Comput. 26(5), 660–680 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  17. Gao, P., Wormald, N.: Enumeration of graphs with a heavy-tailed degree sequence. Adv. Math. 287, 412–450 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30, 1141–1144 (1959)

    Article  MATH  Google Scholar 

  19. van der Hofstad, R.: Random graphs and complex networks. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 1. Cambridge University Press, Cambridge (2017)

    Google Scholar 

  20. van der Hofstad, R.: Random graphs and complex networks, vol. 2 (2018+). In preparation, see http://www.win.tue.nl/~rhofstad/NotesRGCNII.pdf

  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)

    Google Scholar 

  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)

    Google Scholar 

  23. van der Hofstad, R., van Leeuwaarden, J., Stegehuis, C.: Hierarchical configuration model. arXiv:1512.08397 [math.PR], Preprint (2015)

  24. Janson, S., Luczak, M.: A new approach to the Giant component problem. Random Struct. Algorithms 34(2), 197–216 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  25. Kleinberg, J.M.: Navigation in a small world. Nature 406, 845 (2000)

    Article  Google Scholar 

  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

    Google Scholar 

  27. Krioukov, D., Kitsak, M., Sinkovits, R., Rideout, D., Meyer, D., Boguñá, M.: Network cosmology. Sci. Rep. 2, Article number 793 (2012)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  31. Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010)

    Google Scholar 

  32. Newman, M.E.J., Watts, D.: Scaling and percolation in the small-world network model. Phys. Rev. E 60, 7332–7344 (1999)

    Article  Google Scholar 

  33. Stegehuis, C., van der Hofstad, R., van Leeuwaarden, J.: Epidemic spreading on complex networks with community structures. Sci. Rep. 6, 29748 (2016)

    Google Scholar 

  34. Stegehuis, C., van der Hofstad, R., van Leeuwaarden, J.: Power-law relations in random networks with communities. Phys. Rev. E 94, 012302 (2016)

    Google Scholar 

  35. Watts, D.J.: Small Worlds. The Dynamics of Networks Between Order and Randomness. Princeton Studies in Complexity. Princeton University Press, Princeton (1999)

    Google Scholar 

  36. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)

    Article  MATH  Google Scholar 

Download references

Acknowledgement

This work is supported by the Netherlands Organisation for Scientific Research (NWO) through VICI grant 639.033.806 and the Gravitation Networks grant 024.002.003. This work has been for the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science WG2017, held from June 21–23, 2017 in Heeze. RvdH thanks the organisors for giving him the opportunity to speak there.

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands

    Remco van der Hofstad

Authors
  1. Remco van der Hofstad
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Remco van der Hofstad .

Editor information

Editors and Affiliations

  1. Utrecht University, Utrecht, The Netherlands

    Hans L. Bodlaender

  2. Rheinisch-Westfälische Technische Hochschule Aachen, Aachen, Germany

    Gerhard J. Woeginger

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

van der Hofstad, R. (2017). Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions. In: Bodlaender, H., Woeginger, G. (eds) Graph-Theoretic Concepts in Computer Science. WG 2017. Lecture Notes in Computer Science(), vol 10520. Springer, Cham. https://doi.org/10.1007/978-3-319-68705-6_1

Download citation

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

  • Published:

  • Publisher Name: Springer, Cham

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

  • Online ISBN: 978-3-319-68705-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation