Skip to main content Accessibility help
×
Home

Degree correlations in scale-free random graph models

  • Clara Stegehuis (a1)

Abstract

We study the average nearest-neighbour degree a(k) of vertices with degree k. In many real-world networks with power-law degree distribution, a(k) falls off with k, a property ascribed to the constraint that any two vertices are connected by at most one edge. We show that a(k) indeed decays with k in three simple random graph models with power-law degrees: the erased configuration model, the rank-1 inhomogeneous random graph, and the hyperbolic random graph. We find that in the large-network limit for all three null models, a(k) starts to decay beyond and then settles on a power law , with the degree exponent.

  • View HTML
    • Send article to Kindle

      To send this article to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about sending to your Kindle. Find out more about sending to your Kindle.

      Note you can select to send to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be sent to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

      Find out more about the Kindle Personal Document Service.

      Degree correlations in scale-free random graph models
      Available formats
      ×

      Send article to Dropbox

      To send this article to your Dropbox account, please select one or more formats and confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your <service> account. Find out more about sending content to Dropbox.

      Degree correlations in scale-free random graph models
      Available formats
      ×

      Send article to Google Drive

      To send this article to your Google Drive account, please select one or more formats and confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your <service> account. Find out more about sending content to Google Drive.

      Degree correlations in scale-free random graph models
      Available formats
      ×

Copyright

Corresponding author

*Current address: Twente University, The Netherlands. Email address: c.stegehuis@utwente.nl

References

Hide All
[1] Albert, R., Jeong, H. and Barabási, A.-L. (1999). Internet: diameter of the world-wide web. Nature 401, 130131. CrossRef | Library Links | Google Scholar
[2] Barabási, A.-L. (2016). Network Science. Cambridge University Press. Library Links | Google Scholar
[3] Barrat, A., Barthélemy, M., Pastor-Satorras, R. and Vespignani, A. (2004). The architecture of complex weighted networks. Proc. Natl Acad. Sci. USA 101, 37473752. CrossRef | Library Links | Google Scholar | PubMed
[4] Bhamidi, S., Dhara, S., van der Hofstad, R. and Sen, S. (2017). Universality for critical heavy-tailed network models: metric structure of maximal components. Available at arXiv:1703.07145. Library Links | Google Scholar
[5] Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2017). Universality for first passage percolation on sparse random graphs. Ann. Probab. 45, 25682630. CrossRef | Library Links | Google Scholar
[6] Bhamidi, S., Sen, S. and Wang, X. (2017). Continuum limit of critical inhomogeneous random graphs. Probab. Theory Related Fields 169, 565641. CrossRef | Library Links | Google Scholar
[7] Bode, M., Fountoulakis, N. and Müller, T. (2015). On the largest component of a hyperbolic model of complex networks. Electron. J. Combin. 22, P3.24. Library Links | Google Scholar
[8] Bode, M., Fountoulakis, N. and Müller, T. (2016). The probability of connectivity in a hyperbolic model of complex networks. Random Structures Algorithms 49, 6594. CrossRef | Library Links | Google Scholar
[9] Boguñá, M. and Pastor-Satorras, R. (2003). Class of correlated random networks with hidden variables. Phys. Rev. E 68, 036112. CrossRef | Library Links | Google Scholar | PubMed
[10] Boguñá, M., Pastor-Satorras, R. and Vespignani, A. (2003). Absence of epidemic threshold in scale-free networks with degree correlations. Phys. Rev. Lett. 90, 028701. CrossRef | Library Links | Google Scholar | PubMed
[11] Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin . 1, 311316. CrossRef | Library Links | Google Scholar
[12] Bringmann, K., Keusch, R. and Lengler, J. (2015). Sampling geometric inhomogeneous random graphs in linear time. In 25th European Symposium on Algorithms (ESA 2017) (Leibniz International Proceedings in Informatics 87), art. 20. Leibniz-Zentrum für Informatik, Schloss Dagstuhl. Library Links | Google Scholar
[13] Britton, T., Deijfen, M. and Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124, 13771397. CrossRef | Library Links | Google Scholar
[14] Candellero, E. and Fountoulakis, N. (2014). Clustering and the hyperbolic geometry of complex networks. In Algorithms and Models for the Web Graph (WAW 2014) (Lecture Notes in Computer Science 8882), pp. 112. Springer, Cham. Library Links | Google Scholar
[15] Catanzaro, M., Boguñá, M. and Pastor-Satorras, R. (2005). Generation of uncorrelated random scale-free networks. Phys. Rev. E 71, 027103. CrossRef | Library Links | Google Scholar | PubMed
[16] Chung, F. and Lu, L. (2002). The average distances in random graphs with given expected degrees. Proc. Natl Acad. Sci. USA 99, 1587915882.10.1073/pnas.252631999 CrossRef | Library Links | Google Scholar | PubMed
[17] Colomer-de Simon, P. and Boguñá, M. (2012). Clustering of random scale-free networks. Phys. Rev. E 86, 026120. CrossRef | Library Links | Google Scholar | PubMed
[18] van den Esker, H., van der Hofstad, R. and Hooghiemstra, G. (2008). Universality for the distance in finite variance random graphs. J. Stat. Phys. 133, 169202. CrossRef | Library Links | Google Scholar
[19] Faloutsos, M., Faloutsos, P. and Faloutsos, C. (1999). On power-law relationships of the internet topology. In ACM SIGCOMM Computer Communication Review, vol. 29, pp. 251262. ACM. Library Links | Google Scholar
[20] Friedrich, T. and Krohmer, A. (2015). Cliques in hyperbolic random graphs. In INFOCOM Proceedings 2015, pp. 15441552. IEEE. Library Links | Google Scholar
[21] Gradshteyn, I. and Ryzhik, I. (2015). Table of Integrals, Series, and Products. Elsevier. Library Links | Google Scholar
[22] Gugelmann, L., Panagiotou, K. and Peter, U. (2012). Random hyperbolic graphs: degree sequence and clustering. In ICALP Proceedings 2012, Part II, pp. 573585. Springer, Berlin and Heidelberg. Library Links | Google Scholar
[23] van der Hofstad, R. (2017). Random Graphs and Complex Networks, vol. 1. Cambridge University Press. CrossRef | Library Links | Google Scholar
[24] van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms 27, 76123. CrossRef | Library Links | Google Scholar
[25] van der Hofstad, R., van der Hoorn, P., Litvak, N. and Stegehuis, C. (2017). Limit theorems for assortativity and clustering in the configuration model with scale-free degrees. Available at arxiv:1712.08097. Library Links | Google Scholar
[26] van der Hofstad, R., Janssen, A. J. E. M., van Leeuwaarden, J. S. H. and Stegehuis, C. (2017). Local clustering in scale-free networks with hidden variables. Phys. Rev. E 95, 022307.10.1103/PhysRevE.95.022307 CrossRef | Library Links | Google Scholar | PubMed
[27] van der Hofstad, R., van Leeuwaarden, J. S. H. and Stegehuis, C. (2017). Optimal subgraph structures in scale-free configuration models. Available at arXiv:1709.03466. Library Links | Google Scholar
[28] van der Hoorn, P. and Litvak, N. (2015). Upper bounds for number of removed edges in the erased configuration model. In Algorithms and Models for the Web Graph (WAW 2015) (Lecture Notes in Computer Science 9479), pp. 5465. Springer, Cham. CrossRef | Library Links | Google Scholar
[29] Janson, S. and Luczak, M. J. (2007). A simple solution to the k-core problem. Random Structures Algorithms 30, 5062. CrossRef | Library Links | Google Scholar
[30] Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. and Barabási, A.-L. (2000). The large-scale organization of metabolic networks. Nature 407, 651654. CrossRef | Library Links | Google Scholar | PubMed
[31] Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A. and Boguná, M. (2010). Hyperbolic geometry of complex networks. Phys. Rev. E 82, 036106. CrossRef | Library Links | Google Scholar | PubMed
[32] Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. Available at http://snap.stanford.edu/data. Library Links | Google Scholar
[33] Maslov, S., Sneppen, K. and Zaliznyak, A. (2004). Detection of topological patterns in complex networks: correlation profile of the internet. Phys. A 333, 529540.10.1016/j.physa.2003.06.002 CrossRef | Library Links | Google Scholar
[34] Mayo, M., Abdelzaher, A. and Ghosh, P. (2015). Long-range degree correlations in complex networks. Comput. Social Networks 2, 4. CrossRef | Library Links | Google Scholar
[35] Newman, M. E. J. (2002). Assortative mixing in networks. Phys. Rev. Lett. 89, 208701. CrossRef | Library Links | Google Scholar | PubMed
[36] Ostilli, M. (2014). Fluctuation analysis in complex networks modeled by hidden-variable models: necessity of a large cutoff in hidden-variable models. Phys. Rev. E 89, 022807. CrossRef | Library Links | Google Scholar | PubMed
[37] Park, J. and Newman, M. E. J. (2003). Origin of degree correlations in the internet and other networks. Phys. Rev. E 68, 026112. CrossRef | Library Links | Google Scholar | PubMed
[38] Pastor-Satorras, R., Vázquez, A. and Vespignani, A. (2001). Dynamical and correlation properties of the internet. Phys. Rev. Lett. 87, 258701. CrossRef | Library Links | Google Scholar | PubMed
[39] Ravasz, E. and Barabási, A.-L. (2003). Hierarchical organization in complex networks. Phys. Rev. E 67, 026112. CrossRef | Library Links | Google Scholar | PubMed
[40] Serrano, M. Á. and Boguñá, M. (2006). Percolation and epidemic thresholds in clustered networks. Phys. Rev. Lett. 97, 088701. CrossRef | Library Links | Google Scholar | PubMed
[41] Stegehuis, C., van der Hofstad, R., van Leeuwaarden, J. S. H. and Janssen, A. J. E. M. (2017). Clustering spectrum of scale-free networks. Phys. Rev. E 96, 042309. CrossRef | Library Links | Google Scholar | PubMed
[42] Vázquez, A. (2003). Growing network with local rules: preferential attachment, clustering hierarchy, and degree correlations. Phys. Rev. E 67, 056104. CrossRef | Library Links | Google Scholar | PubMed
[43] Vázquez, A., Pastor-Satorras, R. and Vespignani, A. (2002). Large-scale topological and dynamical properties of the internet. Phys. Rev. E 65, 066130. CrossRef | Library Links | Google Scholar | PubMed
[44] Whitt, W. (2006). Stochastic-Process Limits. Springer, New York. Library Links | Google Scholar
[45] Yao, D., van der Hoorn, P. and Litvak, N. (2018). Average nearest neighbor degrees in scale-free networks. Internet Mathematics 2018. doi:10.24166/im.02.2018. CrossRef | Library Links | Google Scholar

Keywords

MSC classification