无标度网络模型构造精选.pdfVIP

课题：无标度网络模型构造 姓名 赵训 学号 201026811130 班级 实验班1001 一、 源起 无标度网络（或称无尺度网络）的概念是随着对复杂网络的研究而出现的。 “网络”其实就是数学中图论研究的图，由一群顶点以及它们之间所连的 边构成。在网络理论中则换一套说法，用“节点”代替“顶点”，用“连 结”代替“边”。复杂网络的概念，是用来描述由大量节点以及这些节点 之间错综复杂的联系所构成的网络。这样的网络会出现在简单网络中没有 的特殊拓扑特性。 自二十世纪60年代开始，对复杂网络的研究主要集中在随机网络上。随机 网络，又称随机图，是指通过随机过程制造出的复杂网络。最典型的随机 网络是保罗·埃尔德什和阿尔弗雷德·雷尼提出的ER模型。ER模型是基于 一种“自然”的构造方法：假设有 个节点，并假设每对节点之间相连的 可能性都是常数 。这样构造出的网络就是ER模型网络。科学家 们最初使用这种模型来解释现实生活中的网络。 ER模型随机网络有一个重要特性，就是虽然节点之间的连接是随机形成的， 但最后产生的网络的度分布是高度平等的。度分布是指节点的度的分布情 况。在网络中，每个节点都与另外某些节点相连，这种连接的数目叫做这 个节点的度。在网络中随机抽取一个节点，它的度是多少呢？这个概率分 布就称为节点的度分布。 在一般的随机网络（如ER模型）中，大部分的节点的度都集中在某个特殊 值附近，成钟形的泊松分布规律（见下图）。偏离这个特定值的概率呈指 数性下降，远大于或远小于这个值的可能都是微乎其微的，就如一座城市 中成年居民的身高大致的分布一样。然而在1998年，Albert-László Barab ási、Réka Albert等人合作进行一项描绘万维网的研究时，发现通过超链 接与网页、文件所构成的万维网网络并不是如一般的随机网络一样，有着 均匀的度分布。他们发现，万维网是由少数高连接性的页面串联起来的。 绝大多数（超过80%）的网页只有不超过4个超链接，但极少数页面（不到 总页面数的万分之一）却拥有极多的链接，超过1000个，有一份文件甚至 与超过200万个其他页面相连。与居民身高的例子作类比的话，就是说大多 数的节点都是“矮个子”，而却又有极少数的身高百丈的“巨人”。Barab ási等人将其称为“无标度”网络。 随机网络的度（a ）集中在某个平均值 附近，而无标度网络的度分布（b）则遵守幂 律分布 二、 描述与定义 无标度网络的特性，在于其度分布没有一个特定的平均值指标，即大多数节点的 度在此附近。在研究这个网络的度分布时，Barabási等人发现其遵守幂律分布（也 称为帕累托分布），也就是说，随机抽取一个节点，它的度 是自然数 的概率： 也就是说 的概率正比于 的某个幂次（一般是负的，记为 ）。因此 越 大， 的概率就越低。然而这个概率随 增大而下降的“速度”是比较缓慢 的：在一般的随机网络中，下降的速度是指数性的，而在无尺度网络中只是以多 项式类的速度下降。 在现实中许多大规模的无尺度网络中，度分布 的值介于2与3之间。在对数坐标 系中，度分布将会是一条斜率介于-2至-3之间的直线。如下图中，横坐标为节点 的度，从 一直到 ；纵坐标为找到这样的节点的概率从 一直到 。 最高度数的节点有882条连接。所有的蓝点大致成一条直线分布（绿色的直线）。 200,000个节点的无标度网络的度分布（对数坐标） 仅仅是将度分布的幂律分布作为无标度网络的定义有其不够完善之处。由于幂律 分布是方差可能无穷的高可变分布，对于度分布是同一个幂律分布的不同网络， 其拓扑结构和特性可能存在巨大的差异。2005年，Lun Li和大卫·阿尔德森（David Alderson）等人在论文《迈向无标度图的理论》（Towards a Theory of Scale Free Graphs）中提出了一种补充性的标度性测度。设 为所有具有（依照幂律分 布的）度分布