{
  "id": "1310.3864",
  "version": "v1",
  "published": "2013-10-14T21:43:22.000Z",
  "updated": "2013-10-14T21:43:22.000Z",
  "title": "Degrees and distances in random and evolving Apollonian networks",
  "authors": [
    "István Kolossváry",
    "Júlia Komjáthy",
    "Lajos Vágó"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "This paper studies Random and Evolving Apollonian networks (RANs and EANs), in d dimension for any d>=2, i.e. dynamically evolving random d dimensional simplices looked 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 n-th step of the dynamics is q_n->0 and sum_{n=0}^infty q_n =infty. This result gives a rigorous proof for the conjecture of Zhang et al. that EANs tend to show similar behavior as RANs once the occupation parameter q->0. We also determine the asymptotic behavior of shortest paths in RANs and EANs for arbitrary d dimensions. For RANs we show that the shortest path between two uniformly chosen vertices (typical distance), the flooding time of a uniformly picked vertex and the diameter of the graph after n steps all scale as constant times log n. We determine the constants for all three cases and prove a central limit theorem for the typical distances. We prove a similar CLT for typical distances in EANs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-10-14T21:43:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C82",
      "05C12",
      "90B15",
      "60J80"
    ],
    "keywords": [
      "evolving apollonian networks",
      "degree distribution",
      "typical distance",
      "shortest path",
      "initial d-dimensional simplex"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.3864K"
    }
  }
}