Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-28T07:14:51.689Z Has data issue: false hasContentIssue false
  • English
  • Français

Degrees and distances in random and evolving apollonian networks

Part of: Markov processes Operations research and management science Graph theory

Published online by Cambridge University Press:  19 September 2016

István Kolossváry ,
Júlia Komjáthy;  and
Lajos Vágó
István Kolossváry*
Affiliation:
Budapest University of Technology and Economics and Inter-University Centre for Telecommunications and Informatics
Júlia Komjáthy;*
Affiliation:
Budapest University of Technology and Economics, Inter-University Centre for Telecommunications and Informatics and Eindhoven University of Technology
Lajos Vágó*
Affiliation:
Budapest University of Technology and Economics and Inter-University Centre for Telecommunications and Informatics
*
* Postal address: Budapest University of Technology and Economics, Inter-University Centre for Telecommunications and Informatics, 4028 Debrecen, Kassai út 26, Hungary.
*** Postal address: Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands. Email address: [email protected]
* Postal address: Budapest University of Technology and Economics, Inter-University Centre for Telecommunications and Informatics, 4028 Debrecen, Kassai út 26, Hungary.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study random Apollonian networks (RANs) and evolving Apollonian networks (EANs), in d dimensions for any d≥2, i.e. dynamically evolving random d-dimensional simplices, looked at as graphs inside an initial d-dimensional simplex. We determine the limiting degree distribution in RANs and show that it follows a power-law tail with exponent τ=(2d-1)/(d-1). We further show that the degree distribution in EANs converges to the same degree distribution if the simplex-occupation parameter in the nth step of the dynamics tends to 0 but is not summable in n. This result gives a rigorous proof for the conjecture of Zhang et al. (2006) that EANs tend to exhibit similar behaviour as RANs once the occupation parameter tends to 0. We also determine the asymptotic behaviour of the shortest paths in RANs and EANs for any d≥2. For RANs we show that the shortest path between two vertices chosen u.a.r. (typical distance), the flooding time of a vertex chosen uniformly at random, and the diameter of the graph after n steps all scale as a constant multiplied by log n. We determine the constants for all three cases and prove a central limit theorem for the typical distances. We prove a similar central limit theorem for typical distances in EANs.

Keywords

Random graphrandom networktypical distancediameterhopcountdegree distribution

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C82: Small world graphs, complex networks 05C12: Distance in graphs 90B15: Network models, stochastic 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 3 , September 2016 , pp. 865 - 902
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Albenque, M. and Marckert, J.-F. (2008).Some families of increasing planar maps.Electron. J. Prob. 13,1624–1671.CrossRefGoogle Scholar
[2] Andrade, J. S., Jr.,Herrmann, H. J.,Andrade, R. F. S. and da Silva, L. R. (2005).Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs.Phys. Rev. Lett. 94,018702.Google Scholar
[3] Athreya, K. B. and Ney, P. E. (2004).Branching Processes.Dover,Mineola, NY.Google Scholar
[4] Barabási, A.-L. and Albert, R. (1999).Emergence of scaling in random networks.Science 286,509–512.CrossRefGoogle ScholarPubMed
[5] Bhamidi, S. and van der Hofstad, R. (2012).Weak disorder asymptotics in the stochastic mean-field model of distance.Ann. Appl. Prob. 22,29–69.Google Scholar
[6] Bhamidi, S.,van der Hofstad, R. and Hooghiemstra, G. (2010).First passage percolation on random graphs with finite mean degrees.Ann. Appl. Prob. 20,1907–1965.Google Scholar
[7] Bhamidi, S.,van der Hofstad, R. and Hooghiemstra, G. (2011).First passage percolation on the Erdős‒Rényi random graph.Combin. Prob. Comput. 20,683–707.CrossRefGoogle Scholar
[8] Bhamidi, S.,van der Hofstad, R. and Hooghiemstra, G. (2012).Universality for first passage percolation on sparse random graphs. Preprint. Available at http://arxiv.org/abs/1210.6839.Google Scholar
[9] Bingham, N. H.,Goldie, C. M. and Teugels, J. L. (1989).Regular Variation (Encyclopedia Math. Appl. 27).Cambridge University Press.Google Scholar
[10] Bollobás, B. and Riordan, O. (2004).The diameter of a scale-free random graph.Combinatorica 24,5–34.CrossRefGoogle Scholar
[11] Bollobás, B.,Janson, S. and Riordan, O. (2007).The phase transition in inhomogeneous random graphs.Random Structures Algorithms 31,3–122.Google Scholar
[12] Bollobás, B.,Borgs, C.,Chayes, J. and Riordan, O. (2003).Directed scale-free graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,ACM,New York, pp. 132–139.Google Scholar
[13] Bollobás, B.,Riordan, O.,Spencer, J. and Tusnády, G. (2001).The degree sequence of a scale-free random graph process.Random Structures Algorithms 18,279–290.CrossRefGoogle Scholar
[14] Boyd, D. W. (1982).The sequence of radii of the Apollonian packing.Math. Comput. 39,249–254.CrossRefGoogle Scholar
[15] Broutin, N. and Devroye, L. (2006).Large deviations for the weighted height of an extended class of trees.Algorithmica 46,271–297.Google Scholar
[16] Bühler, W. J. (1971).Generations and degree of relationship in supercritical Markov branching processes.Z. Wahrscheinlichkeitsth. 18,141–152.Google Scholar
[17] Choi, V. and Golin, M. J. (2001).Lopsided trees. I. Analyses.Algorithmica 31,240–290.CrossRefGoogle Scholar
[18] Cooper, C.,Frieze, A. and Uehara, R. (2014).The height of random k-trees and related branching processes.Random Structures Algorithms 45,675–702.Google Scholar
[19] Darrasse, A. and Soria, M. (2007).Degree distribution of random Apollonian network structures and Boltzmann sampling. In 2007 Conference on Analysis of Algorithms, AofA 07,Association of Discrete Mathematics and Theoretical Computer Science,Nancy, pp. 313–324. Google Scholar
[20] Dembo, A. and Zeitouni, O. (2010).Large Deviations Techniques and Applications (Stoch. Modelling Appl. Prob. 38),2nd edn.Springer,Berlin.CrossRefGoogle Scholar
[21] Doye, J. P. K. and Massen, C. P. (2005).Self-similar disk packings as model spatial scale-free networks.Phys. Rev. E 71, 016128.Google Scholar
[22] Ebrahimzadeh, E. et al. (2013).On the longest paths and the diameter in random Apollonian networks.Electron. Notes Discrete Math. 43,355–365.CrossRefGoogle Scholar
[23] Feller, W. (1968).An Introduction to Probability Theory and Its Applications, Vol. 1,3rd edn.John Wiley,New York.Google Scholar
[24] Frieze, A. and Tsourakakis, C. E. (2012).On certain properties of random Apollonian networks. In Algorithms and Models for the Web Graph,Springer,Berlin, pp. 93–112.CrossRefGoogle Scholar
[25] Graham, R. L. et al. (2003).Apollonian circle packings: number theory.J. Number Theory 100,1–45.CrossRefGoogle Scholar
[26] Janson, S. (1999).One, two and three times log n/n for paths in a complete graph with random weights.Combinatorics Prob. Comput. 8,347–361.CrossRefGoogle Scholar
[27] Kapoor, S. and Reingold, E. M. (1989).Optimum lopsided binary trees.J. Assoc. Comput. Mach. 36,573–590.Google Scholar
[28] Karamata, J. (1930).Über die Hardy‒Littlewoodschen Umkehrungen des Abelschen Stetigkeitssatzes.Math. Z. 32,319–320.Google Scholar
[29] Kolossváry, I. and Komjáthy, J. (2015).First passage percolation on inhomogeneous random graphs.Adv. Appl. Prob. 47,589–610.Google Scholar
[30] Van der Hofstad, R. (2016).Random graphs and complex networks. To appear in Cambridge Series in Statistical and probabilistic Mathematics, Vol. 1,Cambridge University Press,Cambridge.Google Scholar
[31] Zhang, Z. et al. (2008).Analytical solution of average path length for Apollonian networks.Phys. Rev. E 77, 017102.Google Scholar
[32] Zhang, Z.,Rong, L. and Comellas, F. (2006).High-dimensional random Apollonian networks.Physica A 364,610–618.Google Scholar
[33] Zhang, Z.,Rong, L. and Zhou, S. (2006).Evolving Apollonian networks with small-world scale-free topologies.Phys. Rev. E 74, 046105.CrossRefGoogle ScholarPubMed
[34] Zhang, Z.,Comellas, F.,Fertin, G. and Rong, L. (2006).High-dimensional Apollonian networks.J. Phys. A 39,1811–1818.CrossRefGoogle Scholar
[35] Zhou, T.,Yan, G. and Wang, B.-H. (2005).Maximal planar networks with large clustering coefficient and power-law degree distribution.Phys. Rev. E 71, 046141.Google Scholar