Are randomly grown graphs really random? art. no. 041902
Are randomly grown graphs really random? art. no. 041902
复制标题
DOI：
10.1103/physreve.64.041902
复制
发表时间：
2001-10-01
影响因子：
2.4
通讯作者：
Strogatz, SH
中科院分区：
文献类型：
--
作者：
Callaway, DS;Hopcroft, JE;Strogatz, SH
我们分析了一个最小模型的增长网络。在每个时间步，添加一个新的顶点;然后，以概率delta，随机均匀地选择两个顶点，并通过无向边连接。该过程重复t个时间步长。在大t的限制下，结果图显示出令人惊讶的丰富特征。特别是，一个巨大的组件出现在一个无限阶相变在delta =1/8。在过渡处，平均分量大小不连续地跳跃，但保持有限。相反，具有相同度分布的静态随机图在delta =1/4处表现出二级相变，并且平均组分尺寸在那里发散。这些显着的差异之间的增长和静态的随机图源于一个正相关的程度之间的连接顶点的增长图老顶点往往有更高的程度，并与其他高度顶点链接，仅仅凭借他们的年龄。我们的结论是，成长的图形，但随机构造，是从根本上不同于他们的静态随机图对应。
We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined by an undirected edge. This process is repeated for t time steps. In the limit of large t, the resulting graph displays surprisingly rich characteristics. In particular, a giant component emerges in an infinite-order phase transition at delta =1/8. At the transition, the average component size jumps discontinuously but remains finite. In contrast, a static random graph with the same degree distribution exhibits a second-order phase transition at delta =1/4, and the average component size diverges there. These dramatic differences between grown and static random graphs stem from a positive correlation between the degrees of connected vertices in the grown graph-older vertices tend to have higher degree, and to link with other high-degree vertices, merely by virtue of their age. We conclude that grown graphs, however randomly they are constructed, are fundamentally different from their static random graph counterparts.