复杂网络上的随机游走外文翻译资料

英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

复杂网络上的随机游走

Jae Dong Noh

Department of Physics, Chungnam National University, Daejeon 305-764, Korea

Heiko Rieger

Theoretische Physik, Universitauml;t des Saarlandes, 66041 Saarbruuml;cken, Germany

(Received 29 July 2003; published 18 March 2004)

我们研究复杂网络上的随机游走，得到平均首次穿越时间的精确表达式（MFPT）的两个节点。我们引入了每个节点的随机游走中心，这是它的协调数量和特征松弛时间之间的比例，并显示它确定本质的分析。节点的中心决定了一个节点的相对速度节点可以在一个随机游走的过程中接收和传播网络信息。数值模拟一个随机游走的移动聚合网络模型集成确认分析和预测。

从生物学到计算机科学到社会学到世界上丰富的网络，Watts和Strogatz表明，许多这些现实世界的网络构成特征，如小世界和集群属性。 自经典网络模型不显示这些功能，新的模型已经发展到了解结构的基本现实世界网络。重要的是无标度网络(SF)的发现，其特点是一个幂律分布，这也是万维网的一个特征（WWW），和其他许多各学科网络相似。SF网络有一个异构结构，例如在REF中的（WWW），包括节点从，异构型同时也导致了SF网络的可研究性。在渗流的背景下，网络是稳定的，对随机删除的节点，而他们是脆弱的故意攻击目标节点的高度 。关于SF网络的统计力学系统也显示有趣的相变 。在一个传输过程中，网络中的每个节点不可能有同样的贡献。 每个节点在这一过程中的重要性与中介中心性测量，具有广阔的幂律分布 。

在这篇文章中，我们研究了一个随机游走在一般的网络，特别是关注的SF网络。 随机游走是一个基本的动态过程。理论上有趣的是，研究结构的异质性如何影响的性质的随机游走的扩散和松弛动力学 。这些问题将在其他地方进行进一步的研究，随机游走也很有趣，因为它可能是一种运输和搜索网络的机制。这些过程将是最佳的，如果一个遵循两点之间的最短路径的考虑。 在连接2个节点的所有路径中，最短路径是由一个最小数量的链接给出的。然而，最短路径，可以发现，只有在全球的连接是已知的，在每个节点，这是不可能在实践中。随机游走在极端相反的情况下变得非常重要，只有本地连接是已知的在每个节点。我们还表明，在随机结构网络中，随机游走是一个有用的工具。

在运输和搜索的背景下，平均首次穿越时间（MFPT）是随机游走的一个重要特征。我们将从一个节点i到另一节点j，我得出的一个随机游走的MFPT的精确公式，这将表示为,在优化的过程中，它是由两个节点之间的最短路径中的链路的数目，和这两个运动的一个方向，并向其他方向是对称的。然而，一个随机游走运动从i到j是不是相反方向运动的对称。不对称的特点是取决于MFPT的差异。结果表明，不同的是一个潜在的像量确定将被称为随机游走中心（RWC）。RWC的链接结构的异质性，在动态的不对称。它还描述了集中的信息漫游网络。网络漫游。我们考虑一个任意的有限网络（或图），其中包括节点 ，我们假设网络是连接的[即，有一个路径之间的每对节点i和j]， 或者，我们只需单独考虑每一个部分。的连通性表示的邻接矩阵的元素 ，如果在i和j之间有一个链接的话，此时我们令。在目前的内容中，我们限制自己的一个无向网络，即 。链接相邻数目的程度，有关于节点i由决定，这里。

随机过程的离散时间，我们研究是一个随机游走在这个网络上描述的主方程。转换概率被定义为以下规则：于节点i和时刻t的一个随机游走点从它的相邻点中在时刻t 1选择一个最具有可能性的期望值，从节点i到节点j的过度概率为。假设随机游走者从节点j在时刻t=0开始运动，那么节点i在时间t到达节点j的概率方程则是：

相对于稳态分布，相应的时间演化算子是1，以下为节点i在t步内到达节点j的概率值得迭代函数：

比较的表达式可以看出：

这是网络结构所间接性导致的结果，为了找出固定的方案，式（3）表明，所以其中一个包含：

其中，，请注意，平稳分布是，高达正常化，等于节点i的度，网络中的一个节点对其他节点的连接越多，它就越经常被随机游走。 更多的时候，它会被一个随机的步行者访问。随机游动的速度有多快？要回答这个问题，我们研究分析MFPT。第一段的从节点i在t步内到达j需要满足条件：

Kronecker符号为初始条件。引进Laplace方程转换方程（5）化成，同时：

在有限的网络中随机游走是经常性的，所以这里的MFPT由。

可以被分化为：

联合式（6）可以得出：

方法在周期性晶格随机游走的MFPT是一个类似的表达。

需要注意的是，平均返回时间不依赖于网络的全球结构的细节很有趣 。它是由链接的总数和节点的程度。因为它是成反比的程度，在连通性的异质性是很好地反映在这个数量。在伴随程度分布在范围的SF网络中，在起点处的MFPT同样遵循一个守衡定律。MFPT的起源均匀分布在特殊情况2。

节点之间的随机游走运动是非对称的。在，的分别在于：

由（3）式解算得出：

这里将定义为：

这里，节点i的特殊松弛时间由下式定义：

我们称为随机游走中心，因为它量化了中央一个节点，我是如何在其潜在的接收信息随机扩散网络。为了更加精确，考虑到两个节点i和j同时，假设他们每个人同时发射一个信号，这是在网络上漫游。以方程（9）为基础，一个希望较大的RWC节点将接收发射的合作伙伴早期信号。因此，RWC可以作为节点间通信的有效性的措施。在一个具有平移对称均匀的网络，所有节点具有相同的值的相对含水量。另一方面，在异构网络中的含水量有分布，导致随机动态过程的不对称性。

这里的RWC由决定。的特征弛豫时间的数量级是第二最大特征值相关的时间演化算子 。（1）：，这里是左右特征向量，因此松弛时间有一个节点依赖通过权重因子表现出来。另一方面，程度依赖是明确的。

我们研究了在巴拉巴acute;寺艾伯特含水量的分布（BA）网络。这是一个不断增长的SF网络模型，在每一个时间点，一个新的节点会增加与其他节点之间的链接，这与他们的程度比重是比例的概率性选择。我们增长了网络，解决了主方程的初始条件：，并计算么一个K的松弛时间，图（1）a展示了相对于K在BA网络中在参数2的条件下节点数为的变化情况。其尺度范围在，另一方面，松弛时间是分布非常窄的范围内1到2。我们还研究了不同尺寸的BA网络，但没有发现任何显着扩大的分布。因此，相对含水量分布的度分布主要决定 ，在图(1)b中，展示了在同一个BA网络中的关系。

图1 （a）VS K和（b）C VS K在BA网络中，节点数为N=10000和参数M=2时的分布情况

我们进行了数值模拟研究之间的含水量与这个效率的关系。要量化它，我们考虑的情况下，最初在网络中的所有节点占用不同的随机游走量。它们从时刻t=0开始运动，我们用来统计，已通过节点i的步行者的情况，用时间t来衡量。这是理想的随机游走者不相互作用的情况下进行的。他们可能被视为一个信使提供信息，以每个节点访问。在前一段的论点表明，典型节点的值越大，含水量在任何给定的时间内有更大的价值。

BA网络和劳沃斯和巴拉巴acute;四层次网络在模拟中考虑。 分层网络是一个确定的网络，通过迭代，在每次迭代的网络乘以一个因子M。突发网络是无标度时，为Mgt;3。因为它是一个确定的网络，一些结构特性是众所周知的。我们在BA网络中用参数M=2和节点N=512来衡量并且在分层网络中用M=5，N=来描述，此时，

图2表示通过一个节点作为一个函数（从上到下）的节点索引i的分数的时间演化 涉及范围K和RWC在BA网络和分层网络中的情况，每个时间t的n值表示在每一个图的右边框上描绘的灰度/颜色代码。

的时间演变提出了三种不同的方式。在第一行中，节点被安排在节点索引的递增顺序中。在BA网络中，节点索引对应于在网络中添加节点的时间步长。接下来，节点中有度K中的降阶第三排它们排列的顺序性C 。 在给定的时间t，在第一排的情节表明，N是非单调的，很不规则，节点的索引功能。作为一个程度变得光滑函数，但仍然保持单调的倾向。然而，作为一种含水量的功能，它显得更平滑且近乎单调。在每个节点i的松弛时间，当增幅超过1/2时，在BA网络中，所有的节点（i,j）都满足，只有3%的可能性存在，此时，超过的节点数将增加到原来的5倍。

总之，我们研究了复杂网络的随机游走过程。我们推导出一个确切的表达的平均第一次通道时间。MFPT两节点之间的不同，一般是分布于异构网络的两个方向。在两个节点之间的随机游走运动，步行到节点的值比其他更大。此外，也有人认为，在给定的一个时间间隔节点具有较大的值的随机游走者被访问的几率分布会更加均匀。我们证实了这一数值模拟的BA和分层网络。一个可以把随机行走者视为信息通过网络扩散，我们的研究结果表明，信息不均匀分布在异构网络：信息是集中的节点具有更大的值。具有高值的节点具有比其他节点更早的新信息的优势。另一方面，它也意味着，这样的节点在信息分布或传输过程中的负载很重。如果网络中有一个有限的容量，负荷较重的节点可能造成拥堵。因此，应采取的网络管理中的节点具有高的值。在当前的工作中，我们考虑随机游动的无向网络。向有向网络的推广是有趣的。为了学习交通拥堵，随机游走与许多相互作用的随机步行者也很有趣。我们把这样的结论以及探究留给未来的工作。

参考文献:

[1] D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).

[2] R. Albert and A.-L. Baraba acute;si, Rev. Mod. Phys. 74, 47 (2002).

[3] S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. 51, 1079 (2002).

[4] R. Albert, H. Jeong, and A.-L. Baraba acute;si, Nature (London) 401, 130 (1999).

[5] R. Albert, H. Jeong, and A.-L. Baraba acute;si, Nature (London) 406, 378 (2000).

[6] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 85, 4626 (2000).

[7] R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001).

[8] S. N. Dorogovtsev, A.V. Goltsev, and J. F. F. Mendes, Phys. Rev. E 66, 016104 (2002).

[9] F. Iglo acute;i and L. Turban, Phys. Rev. E 66, 036140 (2002).

[10] M. E. J. Newman, Phys. Rev. E 64, 016131 (2001); 64, 016132 (2001).

[11] K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278701 (2001);K.-I. Goh, E. S. Oh, H. Jeong, B. Kahng, and D. Kim, Proc. Natl. Acad. Sci. U.S.A. 99, 12583 (2002).

[12] R. D. Hughes, Random Walks: Random Walks and Random Environments (Clarendon, Oxford, 1995),Vol

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[32017]，资料为PDF文档或Word文档，PDF文档可免费转换为Word