Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis

2012/06/30 by Yoshiaki Itoh, P. L. Krapivsky · 1 citation
Mathematics · Physics and Astronomy · Biochemistry, Genetics and Molecular Biology · #math.PR #cond-mat.stat-mech #q-bio.PE

paper · pdf

published as J. Phys. A 45, 455002 (2012) · 12 pages, 2 figures; figure added

arxiv created 2012/10/02 · arxiv updated 2012/10/31

Abstract

We study a class of directed random graphs. In these graphs, the interval [0,x] is the vertex set, and from each y∈ [0,x], directed links are drawn to points in the interval (y,x] which are chosen uniformly with density one. We analyze the length of the longest directed path starting from the origin. In the large x limit, we employ traveling wave techniques to extract the asymptotic behavior of this quantity. We also study the size of a cascade tree composed of vertices which can be reached via directed paths starting at the origin.

Cited by

• Continuum Cascade Model: Branching Random Walk for Traveling Wave
• The rank and layer distributions in random recursive trees

Related

• The scaling limit of a critical random directed graph
• Limit theorems for a random directed slab graph
• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• Direct Paths in the Temporal Hypercube
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps