论文标题
共同发展的动态网络
Co-evolving dynamic networks
论文作者
论文摘要
我们提出了由本地探索驱动的一类共同发展的树网络模型，其中新顶点通过随机采样顶点附加到当前网络，然后探索图形，以在根方面的随机数量，连接到终端顶点。勘探步骤分布的特定选择导致了良好的仿射优先附件和均匀的附件模型，以及具有全球附件功能（例如Pagerank得分）的动态网络模型，例如Pagerank分数[Chebolu-Melsted（Chebolu-Melsted（2008）]）。我们获得了此类网络的局部弱限制，并使用它们来得出渐近的经验程度和Pagerank分布。我们还为固定顶点（包括根部和网络高度）的程度和pagerank量化了渐近学。基于传入顶点的预期探索距离，我们称之为“边缘”和“非frigring”制度，可以看到两个不同的制度。这些制度显示出具有不同的定性和定量特性。尤其是，非争议状态中的网络会经历“冷凝”，其中根级以与网络大小相同的速率增长。边缘制度中的网络不表现出凝结。对于高度和pagerank分布，显示了非平凡的相变现象，后者连接到众所周知的幂律假说。在此过程中，我们开发了一组涉及局部限制，无限二维的URN模型，相关的多元分支过程以及相应的Perron-Frobenius理论，分支随机步行，尤其是各种功能的尾部指数与相关随机步行的标度分布的各种功能指数的相关尾部指数。这些技术有望阐明其他各种共同发展的网络模型。
We propose a general class of co-evolving tree network models driven by local exploration where new vertices attach to the current network via randomly sampling a vertex and then exploring the graph for a random number of steps in the direction of the root, connecting to the terminal vertex. Specific choices of the exploration step distribution lead to the well-studied affine preferential attachment and uniform attachment models, as well as less well understood dynamic network models with global attachment functionals such as PageRank scores [Chebolu-Melsted (2008)]. We obtain local weak limits for such networks and use them to derive asymptotics for the limiting empirical degree and PageRank distribution. We also quantify asymptotics for the degree and PageRank of fixed vertices, including the root, and the height of the network. Two distinct regimes are seen to emerge, based on the expected exploration distance of incoming vertices, which we call the `fringe' and `non-fringe' regimes. These regimes are shown to exhibit different qualitative and quantitative properties. In particular, networks in the non-fringe regime undergo `condensation' where the root degree grows at the same rate as the network size. Networks in the fringe regime do not exhibit condensation. Non-trivial phase transition phenomena are displayed for the height and the PageRank distribution, the latter connecting to the well known power-law hypothesis. In the process, we develop a general set of techniques involving local limits, infinite-dimensional urn models, related multitype branching processes and corresponding Perron-Frobenius theory, branching random walks, and in particular relating tail exponents of various functionals to the scaling exponents of quasi-stationary distributions of associated random walks. These techniques are expected to shed light on a variety of other co-evolving network models.
