转载

无标度网络模型及其应用

龚哲徐思宇孙昊

一．前言

继1998年小世界网络理论被提出之后，1999年无标度网络理论被首次提出，这两个理论一脉相承，开创性地使用抽象的方法对现实世界中的网络数据进行了统计分析，更加符合现实世界中实际的网络特性，对传播过程产生了重要影响，也使复杂网络的研究发生了巨变。

二．文章作者及其简介

1. Albert-László Barabási

匈牙利裔美国物理学家，前圣母大学物理学教授，现任东北大学复杂网络研究中心（CCNR）主任,特聘教授。哈佛大学医学院教学附属丹娜法伯癌症研究院生物癌症中心（CCSB）准成员，中欧大学网络科学中心教授。在1999年引入了无标度网的概念，并提出了BA模型来解释在自然、技术以及社会体系中普遍出现的无标度网络。在网络理论的研究工作中成果颇丰。

2. Theodore J. Perkins

渥太华医学研究所帕金斯实验室的创立者，改进了Barabási提出的BA模型，提出随机游走并不完全遵循幂律分布，应有有限及拉伸指数这另两种路径分布的可能。

3. Michael P. H. Stumpf

帝国理工学院教授，综合系统生物学和生物信息学中心成员，站在一个生物信息学者的立场对证实幂率分布存在的行为的价值表示了质疑。

三．模型介绍与实际运用

1.几个基本概念

无标度网络：度分布符合幂律分布的复杂网络。
度分布：一个图（或网络）由一些顶点（节点）和连接它们的边（连结）构成。每个顶点（节点）连出的所有边（连结）的数量就是这个顶点（节点）的度。度分布是对一个图（网络）中顶点（节点）度数的总体描述。对于随机图，度分布指的是图中顶点度数的概率分布。
幂律分布：其通式可写成y=cx-r的分布（其中x，y是正的随机变量，c，r均为大于零的常数）。对上式两边取对数，可知lny与lnx满足线性关系lny=lnc-rlnx，即在双对数坐标下，幂律分布表现为一条斜率为幂指数的负数的直线，这一线性关系是判断给定的实例中随机变量是否满足幂律的依据。其共性是绝大多数事件的规模很小，而只有少数事件的规模相当大。

2.模型介绍

（1）经典模型

ER模型

指在给定N个顶点后，规定每两个顶点之间都有p概率连起来,而且这些判定间两两无关。除此以外，其表明随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q，要么几乎每一个图都不具有该性质。

WS（小世界）模型

主要展现出了完全规则网络向完全随机图的过渡。即在具有N个节点的环形网络中，每个节点与它初始的K个相邻点连接，再以概率P随机为网络的每条边重新布线，并且保证重新布线中没有自连接和重复连接。

（2）BA模型

Barabási和albert在1999年研究万维网结构的论文中指出，文件与文件之间链接的概率服从幂律分布，而非经典随机图论中的泊松分布。他们在进一步研究无标度网络形成机理的过程中发现增长和择优连接在网络演化过程中起重要作用。不同于ER和WS模型，大多数现实的网络都是开放的, 不断增添新点和新连线到系统中；而且网络不是完全随机连接的，它们往往具有择优连接倾向，即新加入的节点更有可能和拥有边数多的节点连接。因此，他们建立了BA模型，并定义如下：

增长: 开始有少量（$m_{0}$ 个）点, 每一步添加一个新点到系统, 新点与已存在于系统中的m(≤$m_{0}$) 个点相连接, 产生m条新边。
择优连接: 当选择旧点与新点相连接时, 假设新点连接到旧点i的概率 $/prod k_{i}$ 正比于旧点i的度数$k_{i}$，即：$/prod k_{i} = /frac{k_{i}}{/sum_{j} k_{j}}$

在t后, BA模型演化成一个有$N = m_{0}+t$个点和mt条边的随机网络。因为到了t时间步, 网络共增加了mt条边, 而每条边连通两个点,，在计算点的度数时共算了两次, 所以旧点的总数$/sum_{j}k_{j} = 2mt$ 。

同时，为了处理无标度网络的动力学性质，Barabási等人发展了一种可以解析计算度分布p(k)的连续性理论。在BA模型中，点i被新点连接的概率为$m/prod k_{i}$假定$k_{i}(t)$是连续的，那么概率$m/prod k_{i}$可以解释为$k_{i}(t)$的连续变化率, 从而$k_{i}(t)$满足动力方程：$/frac{/partial k_{i}}{/partial t} = m/prod k_{i} = m /frac{k_{i}}{/sum_{j} k_{j}} = /frac{k_{i}}{2t}$

由此可以推导出如下两个主要结果:

(l)点i的度数$k_{i}$依时间t的变化为 $k_{i}(t) = m (/frac{t}{t_{i}})^/beta$, $/beta = /frac{1}{2}$。其中指数β称为动力指数，$t_{i}$ 为点i加入系统的时间。
(2)度分布p(k)具有幂律尾部$P(k) = /frac{/partial P{k_{i}(t) < k}}{/partial k} = /frac{2m^2t}{m_{0} + t}/frac{1}{k^3} /sim 2m^2k^{-/gamma}$, $/gamma = 3$，其中指数$/gamma$称为度指数。

由上述公式推导，我们可以得从BA模型的两个基本特性（增长和择优连接）中，得出了符合BA模型随机图的显著特点，即：随时间推移，出现了少量的有用大量边的节点；而大部分节点只拥有极少数的边。

Barabási指出模型仍存在一些问题：

（1）这一模型的一个主要假设是使用ki和(ki)间的线性关系。不过现在没有什么能保证(ki)是线性的，因而这一假设留待与真实网络拓扑结构对照来证实。
（2）如果边数增加过快，则系统会完全连接。但作者相信只要增长率足够大，系统能够保持无标度特征。
（3）与（2）相似，如果系统内链接断裂并重新链接支配了增长，系统也会完全连接，该系统就成了例外。但如果系统是以其生长过程为主导，无标度网络仍有适用性。
（4）普适性的概念还没有得到足够的探索。 ##3.BA模型的应用及前景在谈及BA模型的应用及前景时，Barabási表示：“事实上，大型可靠网络数据图的出现在过去的十年中促进了网络理论的发展。如果近几年我们能够有方法获取网络系统动力学过程中的详细数据。那时唯一的限制因素就只有我们的想象力。如果让我对接下来的十年做一个大胆的预测，我想，随着我们每天使用的电器设备数量的增长，从手机到全球定位系统和因特网，它们已经捕获了我们生活中的一切行踪，在一个真正量化的方式下，我们首先能够认识的复杂系统，不是细胞也不是因特网，而是我们人类社会。今天，对网络系统的认识已经成为一系列传统学科的共同目标：细胞生物学家使用网络来研究信号传导和代谢过程，并命名在这一领域的一些应用；计算机科学加正在绘制互联网和万维网的结构；流行病学家追踪病毒的传播网络；脑研究者正在致力于研究连接体--一种神经水平的大脑连接图。虽然复杂系统的许多研究热潮来了又走，但是有一件事情日益清楚：对于复杂系统而言，组元之间内在的相互连接是如此的重要---这正是我们现在关注网络的原因。”

总结起来，我们可以发现BA模型在万维网、电影明星、论文引用、蛋白质结构、病毒传播、美国西部电网等诸多方面有着广泛的适用性。而目前在获取网络系统动力学过程中的详细数据的技术难题，已经成为了制约网络理论发展的最大瓶颈。

四．关于BA模型的其他声音

1.Michael P. H. Stumpf的观点

Stumpf在其《Critical Truths About Power Laws》一文中，提出了对于Barabási认为复杂网络中运动遵循幂律分布的观点提出了质疑。总结起来可以归纳为如下的三点：

(l)其现实操作中存在着很大的统计困难；
(2)即使超越统计障碍，也往往缺乏生成机制；
(3)对证实幂律分布存在的行为的价值持怀疑态度。

Stumpf在文中这样说道：“即便是声称统计的幂率做得正确，并且有理论支持它的生成机制，并且它还得到了丰富的、无争议的经验支持，一个关键性的问题仍然存在：通过找到一个鲁棒的、机械支持的，并在别的方面都很出色的幂率，我们能得到什么真正的新的深刻见解呢？我们相信这种见解十分罕见。”也就是说证明网络的幂律分布不但可疑，而且没有用处。

2. Theodore J. Perkins的观点

有限网络上的随机游走的路径分布不止幂律分布一种，还存在着有限，拉伸指数的路径分布。所以有限网络上随机游走的路径分布有且只有三种，这三种分布被合称为新的标度法则。

Perkins具体解释了三种分布的形式，可以看出a只能由起点走向终点，b中路径可能发生临近节点间的循环，c中则还有跨临近节点的循环可能。他指出在网络a中，从s节点开始到e节点结束的路线只有四种。其他网络中，由于允许路过之前经过的节点，就可能产生无限种可能的路线。在网络b和c中，走较长的路线的可能性一般比走短路线低，但是路线长短和选择概率之间并没有严格的相关关系，因为不同步数出现的可能性也不一样。假设我们按可能性降序排列这些路线，p1 p2 p3 …这里的Pr是第R种情况下最可能的路径。图4d表现了在三种网络中Pr和r的可能性关系。在网络c中，在log-log的图示上的关系接近于线性，说明了路径的分布呈大约呈幂律关系：$/log P_{r} ≈ a+b/log r$ 或者 $p_{r}≈cr^b$ ，而对于网络b来说，其关系是明显的曲线，这幂律分布路径概率不一致。不过，在网络b中，$log P_{r}$于r的平方根之间的是接近线性的关系（图4e），表明路径分布是拉伸指数关系：$log P_{r} /approx a + b/sqrt r$，或者 $P_{r} /approx ce^{b/sqrt[a]{r}}$。”

无标度网络模型及其应用

关于拉伸指数分布，Perkins给出了一个关于美国垒球的实例：他基于垒球的规则，将每一个半场中每个击球手造成对方出局的数量进行简单的数据化，例如第一个击球手造成了一个出局，第二人没有造成出局，第三人造成两个出局，则那么总出局顺序记作0113。同时，他分析了在retrosheet.com上能看到的所有2012赛季大联盟比赛，共30602个半局（1700场左右）的出局顺序，并计算了不同的出局顺序的观测频率，发现数据并不始终符合幂律分布，基于每个击球手不论造成了多少出局，总数最多不会超过3个，可以得出如图中的游走结构。通过这个结构，我们就可以知道概率Pr∝exp(br^1/3),通过上图我们可以看出，观测概率实际上是与作为次数的立方根的对数图像形成一条斜率为负的直线，且预测斜率接近观测斜率。这表明美国垒球的例子中，出局顺序不是幂率分布，但却符合Perkins提出的新标度理论中拉伸指数分布这种简单的随机游走模型。

五．对未来研究的展望

现今，我们在系统理论在基本概念、理论和方法等方面均已取得了许多重要成果，而系统科学已取得的成就和无标度网络的研究的结合业已进行的如火如荼，这些成果和无标度网络拓扑特性的研究形成了双向互动，两方面也都取得了不少进展。但是，将复杂网络理论应用于谣言传播等社会网络现象和特征的研究，还仅仅停留在理论探索的阶段，至今还缺乏比较成熟的研究成果。我们小组认为，将来的研究应向社会网络传播的权值性、方向性，其在动态无标度网络中的传播以及在规则网络、随机网络、小世界网络等上的应用有待进一步研究。

参考文献

[1]Barabási A L, Albert R. Emergence of Scaling in Random Networks［J］.Science,1999(286):509－512．

[2]Perkins T J, Foxall E, Glass L, Edwards R. A scaling law for random walks on networks［J］. NATURE COMMUNICATIONS,2014,DOI:10.1038/ncomms6121 DOI: 10.1038/nc

[3]Barabási A L. Internet Diameter of the world wide web［J］．Science,1999(401)

[4]Barabási A L, Albert R, Jeong H. Mean-_eld theory for scale-free random networks［J］.Physica A,1999(272):173－187．

[5] Stumpf M P H, Porter M A. Critical truth about power law［J］. Science,2012，335，665

[6]杨珉，张家玥，张达敏复杂网络拓扑结构的网络模型研究综述［J］通信技术，2014，47（12）：1354-1359

[7]王筱莉，赵来军，谢婉林无标度网络中遗忘率变化的谣言传播模型研究［J］系统工程理论与实践，2015,35（02）：458-465

[8]车宏安，顾基发无标度网络及其系统科学意义［J］系统工程理论与实践，2004,4：11-15

Date: 2015-05-01; Category:计算传播学讲义; Tags:徐思宇,龚哲,孙昊

正文到此结束