solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看132次
Typical distances in the directed configuration model. (arXiv:1511.04553v2 [math.PR] UPDATED)
来源于:arXiv
We analyze the distribution of the distance between two nodes, sampled
uniformly at random, in digraphs generated via the directed configuration
model, in the supercritical regime. Under the assumption that the covariance
between the in-degree and out-degree is finite, we show that the distance grows
logarithmically in the size of the graph. In contrast with the undirected case,
this can happen even when the variance of the degrees is infinite. The main
tool in the analysis is a new coupling between a breadth-first graph
exploration process and a suitable branching process based on the
Kantorovich-Rubinstein metric. This coupling holds uniformly for a much larger
number of steps in the exploration process than existing ones, and is therefore
of independent interest. 查看全文>>