题目：复杂网络上的随机行走

摘 要
复杂网络能很好地描述人类社会和自然界的一些复杂系统的结构，例如互联网、万维、科学家协作网络以及神经网络[1]。近年来复杂网络的研究表明在真实网络中节点连接遵循一定的规则，而不是随机网络。一个重要的特征是少数的节点往往拥有大量的连接，而大部分节点的连接却很少，节点的连接度符合幂律分布。度分布符合幂律分布的复杂网络被称为无标度网络。真实网络还有另外一个特点就是节点的连接度之间具有关联性。如果网络中连接度大的节点更倾向于和连接度大的节点相连，这种网络被称为正关联网络。如果连接度大的节点更倾向于和连接度小的节点相连，这种网络被称为负关联网络。例如万维网、互联网等通讯网络都是具有无标度特性的负关联网络[2-3]。
研究复杂网络上随机行走是解决真实网络中的一些问题的有效方法。例如通讯高峰时网络中数据包出现阻塞现象导致数据包传输速度缓慢。在复杂网络上随机行走模拟研究，有利于寻找提高通讯网络效率的方法。目前，通讯网络中数据包的路由策略是最短路径传输策略，该策略存在连接度大的点易堵塞的弊端。一种可能的替代策略是本地路由策略，即每个节点只知道自己邻居节点的信息，数据包根据一定的规则从一个节点发送到它的一个邻居节点，如此循环直到到达目标节点为止[4]。这种策略可以克服最短路径传输策略的缺点，已经引起了很大的研究兴趣。

有倾向随机行走是研究数据包本地路由策略的有效方法。以前的工作研究了非关联的无标度网络模型上的有倾向随机行走行为。因为许多真实的技术网络包括互联网都具有负的度关联特征，所以本文研究有倾向随机行走在这种网络上的性质。
我们的研究表明在负关联网络上随机行走粒子可以在连接度较大的节点上均匀的分布，而连接度小的节点上粒子较少。负关联网络上的随机行走的速度比非关联网络更快。我们找到了负关联网络上的最佳倾向性系数，在此情况下随机行走的速度远快于非关联网络。我们的分析表明负关联网络既可以利用度小的节点容纳粒子又可以利用度大的节点快速传输，这是负关联网络上高的行走效率产生的机制。