Continuum cascade model of directed random graphs: traveling wave analysis
Continuum cascade model of directed random graphs: traveling wave analysis
复制标题
有向随机图的连续级联模型：行波分析
DOI：
10.1088/1751-8113/45/45/455002
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Paul Krapivsky
中科院分区：
文献类型：
--
作者：
Yoshiaki Itoh;Paul Krapivsky
研究了一类有向随机图。在这些图中，区间[0，x]是顶点集，并且从每个y∈[0，x]，有向链路被绘制到区间（y，x]中的点，这些点以密度1均匀选择。我们分析了从原点开始的最长有向路的长度。在x→∞极限，我们采用行波技术来提取这个量的渐近行为。我们还研究了级联树的顶点，可以达到通过有向路径开始在原点的大小。
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 1. We analyze the length of the longest directed path starting from the origin. In the 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.