The average distances in random graphs with given expected degrees
The average distances in random graphs with given expected degrees
复制标题
DOI：
10.1073/pnas.252631999
复制
发表时间：
2002-12-10
影响因子：
11.1
通讯作者：
Lu, LY
中科院分区：
文献类型：
--
作者：
Chung, F;Lu, LY
随机图论用于检验“小世界现象”；任何两个陌生人都通过一条短的相互熟人链联系在一起。我们将证明，对于具有给定期望度数的某些随机图族，平均距离几乎肯定是波浪号上的 log n/log (d) 量级，其中波浪号上的 (d) 是期望度数平方和的加权平均值。特别令人感兴趣的是幂律随机图，其中对于某个固定指数 beta，k 次顶点的数量与 1/k(beta) 成正比。对于 beta > 3 的情况，我们证明幂律图的平均距离几乎肯定是 log n/log d 的量级。然而，许多互联网、社交和引文网络都是指数在 2 < beta < 3 范围内的幂律图，其中幂律随机图几乎肯定具有阶 log log n 的平均距离，但具有阶 log n 的直径（假设对平均距离和最大度有一些温和的约束）。特别是，这些图包含一个密集子图，我们称之为核心，具有 n(c/log log n) 个顶点。几乎所有顶点都在距离核心的 log log n 范围内，尽管也有一些顶点距核心的距离为 log n。
Random graph theory is used to examine the "small-world phenomenon"; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees the average distance is almost surely of order log n/log (d) over tilde, where (d) over tilde is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1/k(beta) for some fixed exponent beta. For the case of beta > 3, we prove that the average distance of the power law graphs is almost surely of order log n/log d. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < beta < 3 for which the power law random graphs have average distance almost surely of order log log n, but have diameter of order log n (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, which we call the core, having n(c/log log n) vertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.