Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis
arXiv:1206.3711
Abstract
We study a class of directed random graphs. In these graphs, the interval [0,x] is the vertex set, and from each y\in [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.
arXiv comment12 pages, 2 figures; figure added
References in corpus (9)
- The spread of epidemic disease on networks
- Front propagation into unstable states
- Degree Distributions of Growing Networks
- Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
- Universal algebraic relaxation of fronts propagating into an unstable state
- Traveling Waves, Front Selection, and Exact Nontrivial Exponents in a Random Fragmentation Problem
- Extremal properties of random trees
- Traveling Front Solutions to Directed Diffusion Limited Aggregation, Digital Search Trees and the Lempel-Ziv Data Compression Algorithm
- Random Sequential Generation of Intervals for the Cascade Model of Food Webs