×

Some properties of random Apollonian networks. (English) Zbl 1461.05187

Summary: In this work, we analyze fundamental properties of random Apollonian networks [Z. Zhang et al., J. Phys. A, Math. Gen. 39, No. 8, 1811–1818 (2006; Zbl 1086.68017); T. Zhou, G. Yan and B.-H. Wang, “Maximal planar networks with large clustering coefficient and power-law degree distribution”, Phys. Rev. E (3) 71, No. 4, Article ID 046141, 12 p. (2005; doi:10.1103/PhysRevE.71.046141)], a popular random graph model that generates planar graphs with power-law properties. Specifically, we analyze the degree distribution, the \(k\) largest degrees, the \(k\) largest eigenvalues, and the diameter, where \(k\) is a constant.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1086.68017
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [ Aiello et al. 01] W. Aiello, F. Chung, and L. Lu. “A Random Graph Model for Power Law Graphs.” Experimental Mathematics 10 (2001), 53-66. · Zbl 0971.05100
[2] [ Albenque and Marckert 08] M. Albenque and J. F. Marckert. “Some Families of Increasing Planar Maps.” Electronic Journal of Probability 13 (2008), 1624-1671. · Zbl 1192.60019
[3] [ Alon and Spencer 08] N. Alon and J. Spencer. The Probabilistic Method. Wiley-Interscience, 2008.
[4] [ Andrade and Miranda 05] R. F. S. Andrade and J. G. V. Miranda. “Spectral Properties of the Apollonian Network.” Physica A 356, (2005), 1-5.
[5] [ Andrade et al. 05] J. S. Andrade, H. J. Herrmann, R. F. S. Andrade, and L. R. da Silva. “Apollonian Networks: Simultaneously Scale-Free, Small World Euclidean, Space Filling, and with Matching Graphs.” Phys. Rev. Lett. 94 (2005), 018702.
[6] [ Azuma 67] K. Azuma. “Weighted Sums of Certain Dependent Variables.” Tohoku Math. J. 3 (1967), 357-367. · Zbl 0178.21103
[7] [ Barabási and Albert 99] A. Barab ási and R. Albert. “Emergence of Scaling in Random Networks.” Science 286 (1999), 509-512. · Zbl 1226.05223
[8] [ Bodini et al. 07] O. Bodini, A. Darrasse, and M. Soria. “Distances in Random Apollonian Network Structures.” arXiv abs/0712.2129, 2007. · Zbl 1393.05247
[9] [ Bollobás 98] B. Bollobás. Modern Graph Theory. Springer, 1998.
[10] [ Bollobás and Riordan 04] B. Bollobás and O. Riordan. “The Diameter of a Scale-Free Random Graph.” Combinatorica 24 (2004), 5-34. · Zbl 1047.05038
[11] [ Bollobás et al. 01] B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. “The Degree Sequence of a Scale Free Random Graph Process.” Random Struct. Algorithms 18 (2001), 279-290. · Zbl 0985.05047
[12] [ Boyd 82] D. W. Boyd. “The Sequence of Radii of the Apollonian Packing.” Mathematics of Computation 19 (1982), 249-254. · Zbl 0492.52009
[13] [ Broutin and Devroye 06] N. Broutin and L. Devroye. “Large Deviations for the Weighted Height of an Extended Class of Trees.” Algorithmica 46 (2006), 271-297. · Zbl 1106.68027
[14] [ Chung et al. 03] F. Chung, L. Lu, and V. H. Vu. “Spectra of Random Graphs with Given Expected Degrees.” Proc. Natl. Acad. Sci. USA 100 (2003), 6313-6318. · Zbl 1064.05138
[15] [ Chung Graham 97] F. Chung Graham. Spectral Graph Theory. American Mathematical Society, 1997.
[16] [ Chung Graham and Lu 06] F. Chung Graham and L. Lu. Complex Graphs and Networks. American Mathematical Society, 2006. · Zbl 1114.90071
[17] [ Cooper and Frieze 03] C. Cooper A. and A. Frieze. “A General Model of Web Graphs.” Random Structures and Algorithms 22 (2003), 311-335. · Zbl 1018.60007
[18] [ Cooper and Uehara 10] C. Cooper and R. Uehara. “Scale Free Properties of Random \(k\)-Trees.” Mathematics in Computer Science 3 (2010), 489-496. · Zbl 1205.05211
[19] [ Darrasse and Soria 07] A. Darrasse and M. Soria. “Degree Distribution of Random Apollonian Network Structures and Boltzmann Sampling.” In 2007 Conference on Analysis of Algorithms, AofA 07, DMTCS Proceedings, pp. 313-324, 2007. · Zbl 1192.68953
[20] [ Darrasse et al. 10] A. Darrasse, H.-K. Hwang, O. Bodini, and M. Soria. “The Connectivity-Profile of Random Increasing \(k\)-Trees.” In ANALCO, 99-106. SIAM, 2010. · Zbl 1430.68187
[21] [ Doye and Massen 05] J. P. K Doye and C. P. Massen. “Self-Similar Disk Packings as Model Spatial Scale-Free Networks.” Phys. Rev. E 71 (2005) 016128.
[22] [ Ebrahimzadeh et al. 13] E. Ebrahimzadeh, L. Farczadi, P. Gao, A. Mehrabian, C. M. Sato, N. Wormald, and J. Zung. “On the Longest Paths and the Diameter in Random Apollonian Networks.” Electron. Notes Discrete Math. 43 (2013), 355-365. · Zbl 1314.05185
[23] [ Fabrikant et al. 02] A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. “Heuristically Optimized Trade-offs.” In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 110-122, 2002. · Zbl 1056.68503
[24] [ Flaxman et al. 05] A. Flaxman, A. Frieze, and T. Fenner. “High Degree Vertices and Eigenvalues in the Preferential Attachment Graph.” Internet Mathematics 2 (2005), 1-19. · Zbl 1077.05091
[25] [ Gao 09] Y. Gao. “The Degree Distribution of Random \(k\)-Trees.” Theoretical Computer Science 410 (2009), 688-695. · Zbl 1162.68024
[26] [ Gao and Hobson 06] Y. Gao and C. Hobson. “Random k-Tree as a Model for Complex Networks.” In Workshop on Algorithms and Models for the Web-Graph (WAW), 2006.
[27] [ Graham et al. 03] R. L. Graham, J. C. Lagarias, C. L. Mallows, A. R. Wilks, and C. H. Yan. “Apollonian Circle Packings: Number Theory.” J. Number Theory 100 (2003), 1-45. · Zbl 1026.11058
[28] [ Hoeffding 63] W. Hoeffding. “Probability Inequalities for Sums of Bounded Random Variables.” J. Amer. Statist. Assoc. 58 (1963), 13-30. · Zbl 0127.10602
[29] [ Klein 14] P. Klein. “Optimization Algorithms for Planar Graphs.” Available online http://planarity.org/, 2014.
[30] [ Kloks 94] T. Kloks. Treewidth: Computations and Approximations. Springer, 1994. · Zbl 0825.68144
[31] [ Leskovec and Faloutsos 07] J. Leskovec and C. Faloutsos. “Scalable Modeling of Real Graphs Using Kronecker Multiplication.” In Machine Learning Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvalis, Oregon, USA, June 20-24, 2007, pp. 497-504, 2007.
[32] [ Mihail and Papadimitriou 02] M. Mihail and C. Papadimitriou. “On the Eigenvalue Power Law.” RANDOM ’02, pp. 254-262, 2002. · Zbl 1028.68569
[33] [ Panholzer and Seitz 10] A. Panholzer and G. Seitz. “Ordered Increasing \(k\)-Trees: Introduction and Analysis of a Preferential Attachment Network Model.” DMTCS Proc. AofA ’10, pp. 549-564, 2010. · Zbl 1355.05227
[34] [ Pralat and Wormald 07] P. Pralat and N. Wormald. “Growing Protean Graphs.” Internet Mathematics 4 (2007), 1-16. · Zbl 1167.05047
[35] [ Strang 05] G. Strang. Linear Algebra and Its Applications Brooks Cole, 2005.
[36] [ Wu et al. 06] Z.-X. Wu, X.-J. Xu, and Y.-H. Wang. “Comment on ‘Maximal Planar Networks with Large Clustering Coefficient and Power-Law Degree Distribution.’ ” Physical Review E 73 (2006), 058101.
[37] [ Zhang et al. 06] Z. Z. Zhang, F. Comellas, G. Fertin, and L. Rong. “High Dimensional Apollonian Networks.” J. Phys. A-Math. Gen. 39 (2006), 1811-1818. · Zbl 1086.68017
[38] [ Zhou et al. 05] T. Zhou, G. Yan, and B. H. Wang. “Maximal Planar Networks with Large Clustering Coefficient and Power-Law Degree Distribution.” Phys. Rev. E 71 (2005), 046141.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.