Degrees and distances in random and evolving Apollonian networks. (English) Zbl 1348.05192

Kolossváry, István; Komjáthy, Júlia; Vágó, Lajos

Adv. Appl. Probab. 48, No. 3, 865-902 (2016).

Summary: In this paper we study random Apollonian networks (RANs) and evolving Apollonian networks (EANs), in \(d\) dimensions for any \(d\geq 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 \(\tau=(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 Z. Zhang, L. Rong and {S. Zhou} [“Evolving Apollonian networks with small-world scale-free topologies”, Phys. Rev. E (3) 74, No. 4, Article ID 046105 (2006; doi:10.1103/PhysRevE.74.046105) 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\geq 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.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C82	Small world graphs, complex networks (graph-theoretic aspects)
05C12	Distance in graphs
90B15	Stochastic network models in operations research
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)

Keywords:

random graph; random network; typical distance; diameter; hopcount; degree distribution