复杂网络度分布的研究

1. 复杂网络的研究对象    1

2. 复杂网络的研究内容    1

3. 复杂网络中的三个概念    1

4. 复杂网络的几何量    1

5. 社会网络与其它网络的判别指标    2

6. 随机网络－ER模型    2

7. 随机网络的研究宗旨    2

8. 子图出现的临界概率    3

9. 子图临界概率存在的证明    3

10. BA模型与度的幂指分布    4

11. BA模型构造的网络度符合幂指形式的证明    4

复杂网络度分布的研究

－ 复杂网络度分布的研究 河北工大硕士论文 陈德伟 指导教师：何文辰

1. 复杂网络的研究对象

用来描述真实网络统计特征的物理量主要有度分布、平均路径长度、聚集系数、相关系数等，都是力求更加详细、精确的描述复杂的真实网络。寻找网络各种宏观统计性质的微观生成机制一直都是网络研究中一项极具意义而且也是极具挑战性的工作。现在人们已经对复杂网络的小世界性质和无标度特征的微观生成机制有了一定的认识，但是度的相关性、团体性质、分层结构等更为复杂的宏观统计性质的微观生成机制的探索还处于起步阶段。对不同结构复杂网络的鲁棒性和脆弱性(vulnerability)的研究也是一个具有广泛应用价值的课题。

2. 复杂网络的研究内容

目前，复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。

3. 复杂网络中的三个概念

三种概念在当代对复杂网络的思考中占有重要地位。第一，小世界概念；第二，集群即集聚系数的概念；第三，幂律的度分布概念。

4. 复杂网络的几何量

直径：网络的直径是指任意两个顶点之间最短路径的最长长度(包含的边数)。

集聚系数：对于网络中的任意一个节点来说，其集聚系数表示与相连的节点中任意两点之间相互连接的概率。它可定义如下：如果与节点相连的点的数目为，则在这个节点之间最多存在条边，而实际存在的可能只有条边，则得到的集聚系数为

.

对具有个节点的网络来说，网络的集团系数则被定义为网络中所有节点的集聚系数的平均值。

.

随机图的度分布：令随机网络中度的平均值为，随机图的度分布服从下列泊松分布

.

泊松分布的形式在处达到峰值，小世界网络的度分布类似泊松分布。

无标度网络的度分布：许多大的网络不服从泊松分布，如WWW，新陈代谢网络，这些网络都服从幂律分布形式，这样的网络称为无标度网络。度分布函数反映了网络的宏观统计性质，是现阶段网络分类的主要依据之一。

介数：介数分为边介数和节点介数。节点的介数为网络中所有的最短路径中经过该节点的数量比例；边介数的含义与之类似。介数反映了相应的节点或者边在整个网络中的作用和影响力。

5. 社会网络与其它网络的判别指标

两种相关性－不同度数的节点之间的相关性、节点度分布与其集聚系数之间的相关性，在判别中起重要作用。社会网络中为正而为负，其它类型的网络则相反。

6. 随机网络－ER模型

Erdos和Renyi在1959年提出了随机网络ER模型。ER模型中有个标了号的节点，个节点中任意两个点被连接的概率为。因此，所有边的数目是一个随机变量，期望值为。如果是一个有个节点和条边构成的图，则出现的概率即为各边出现的概率，亦即

.

7. 随机网络的研究宗旨

从个孤立的节点开始，分别取和，并以相同的概率连接每一对节点，从图中可看到树和圈等结构的出现。

随机图论研究具有个节点的随机图在时概率空间的性质。随机图的大部分性质可用概率论的方法加以确定。Erdos和Renyi定义：当时，如果拥有性质的概率接近1，那么几乎每个随机图都存在性质。随机图理论的目的就是确定在多大连接概率时网络的特殊结构(或性质)最容易体现出来。在数学中，随机图的构建称之为演化。从个孤立的节点开始，通过连续加大随机连接概率使系统演化。Erdos和Renyi最重要的发现就是，随机图的很多重要性质都是在演化过程中突然出现的。也就是说对某种性质(或结构)存在一个临界概率，如果当时，则几乎可以肯定网络没有性质；相反，如果当时，则几乎可以肯定网络具有性质。

8. 子图出现的临界概率

    Erdos和Renyi研究随机图的第一个性质就是子图的出现，比如环、树和完全图。为研究一般情形下子图出现的临界概率，令图中有个节点，某子图由个点和条边构成。图中可能存在很多这样的子图，下面来研究到底存在多少这样的子图。从个节点中取出个节点可以有种方式，形成条边的概率为(注意，当研究网络中是否具有某种结构(如环)时，非研究对象的边(如圈内部的边)是否存在不影响结果)，交换个节点的位置共可以得到个子图，其中是相互同构的子图的数目。因此，图中存在子图数目的期望为

.          (1)

可证，几乎所有个节点的随机图都包含上述子图(个点条边)的临界概率为。因此有下列结论：

I. 存在一个阶树的临界概率为，(树满足)；

II. 存在一个阶环的临界概率为，(环满足)；

III. 存在一个阶完全图的临界概率为。

从上图中可以看出，当，随机图中只存在孤立的节点和边，当，四阶树开始出现，当，各阶树都开始出现，同时，各阶环也开始出现，等等。

9. 子图临界概率存在的证明

    由式(1)知，当，，进而，这就意味着几乎所有的随机图中都不包含子图。当，从而时，子图的期望值就会存在一个有限值，用表示。考察子图数目分布的概率，

图中包含至少一个子图的概率为

.    (2)

当增大时，(2)式的值趋于1，这表明几乎所有的随机图都包含；而，(2)式的值趋于0，这表明几乎所有的随机图都不包含。

(杨：从(2)式看，似乎对大的，是个临界点。)

10. BA模型与度的幂指分布

近年来在复杂网络研究上的一个重大发现就是许多真实复杂网络具有幂指数形式的度分布函数，即。1999年Barabasi、Albert和H. Jeong在Physica A上给出了一个宏观上度分布符合幂指形式的(微观)产生或构造方式。这种方式具有两个重要因素，即增长机制和优先连接机制(马太效应)。增长机制即网络规模不断扩大，优先连接机制是指一个新加入网络中的点更有可能与网络中已存在的具有较高连接度的点建立连接。例如，新发表的文章更倾向于引用一些已经被广泛引用的一些重要文献。

假定初始网络包含个节点，且没有任何边存在，定义如下：

(1) 增长机制：在每一个时间步，一个新的节点被加入到网络中来并与(，为常数)个网络中已经存在的节点建立连接；

(2) 优先连接：新增加的点与网络中某点进行连接的概率，被假定为正比于点的度。

    根据以上规则，在经过时间之后，可以得到一个具有个点以及条边的网络。

11. BA模型构造的网络度符合幂指形式的证明

    (采用连续性方法)首先计算节点的度随时间的演化。假设是一个连续的变量，因为每个节点的加入与原有网络中的个节点连接，因此，在时刻，原有节点集合中总的度的增加值为。又已知网络中节点度值的增加正比于其度分布概率(是否此处度为的节点数目不一定仅有一个，因此在新节点加入后，其增长并非为1？)，由于节点总数为，经过归一化后有

.  当有.

考虑到初始条件，上式的解为

，.

节点的度小于的概率为

.                    (3)

假设向网络中加入节点的时间间隔都相同，当，值的概率密度可视为接近均匀分布，即

.                         (4)

将(4)式代入(3)式，可得

.

因此，度分布可表示为

.

当，有

..

可以看到，度分布不依赖于，也不依赖于时间，即BA模型的度分布不依赖于模型的尺寸。这表明，尽管网络尺寸在一直增大，但它却达到了一个稳定的无标度状态，这一点和实际中观察到的现实世界的一些网络特点相一致。