复杂网络基础2(M.Chang)

k nn vi
i 1
knn (k) 与条件概率和联合概率之间具有如下关系：
knn
kmax
(k)
k 'Pc (k ' | k)
k ' kmin
1 qk
kmax
k
'
e k
k'
k' kmin
如果 knn (k) 是k的增函数，那么就意味着平均而言，度大的 节点倾向于与度大的节点连接，从而表明网络是同配的；反之，
第4章 度相关性与社团结构
4.1 引言
度分布尽管是网络的一个重要拓扑特征，但是不能由它唯一的刻画一个网 络，因为具有相同度分布的两个网络可能具有非常不同的其他性质或行为。 为进一步刻画网络的拓扑结构，需考虑包含更多结构信息的高阶拓扑特征。 本章介绍刻画网络的二阶度分布特性（也称度相关性）的几种不同方法，包 括最为一般但较为复杂的联合概率分布、更为简洁但不宜比较的条件概率和 余平均度以及可以定量刻画度相关性但过于粗略的相关系数。
kik j ) ij 2M i j
x x
1 2M
i, j
(kiij
kik j ) 2M
i
j
同配系数的定义就是归一化的协方差：
cov( , )
x x r
i
j
2
x
4.2.6 同配概念的一般化
令 xi x j ，得到 xi 的方差如下：
（a x x
2 x

1 2M
i, j
点i 的余平均度，即节点i的 ki 个邻居节点的平均度 knn i 如下：
knn
i
1 ki
ki
ki j .

特征: 连通性: 幂指数分布 非齐次性: 很少的节点有很多连 接，很多节点只有很 少的连接 节点数增加
(Hawoong Jeong)
27
几个基本概念
平均距离 聚类系数 度与度分布 节点介数
(Stephen G. Eick)
28
平均距离
节点 n 与 m的 距离 d(n,m) = 连接他们的最短路径的长度 直径 D = max{d(n,m)} 平均距离 L = 所有 d(n,m)的平均数
24
小世界网络
特征:
(Similar to ER Random Graphs)
齐次性: 每个节点有大约相同 的连接数 节点不增加
25
Scale-Free 网络 (Barabasi-Albert, Science, 1999)
由初始给定的一个具 m0个节点的网络开始 (i) 增加新节点:
With probability p, a new node is added into the network
My Erdös Number is 2:
P. Erdös – C. K. Chui – G. R. Chen
Erdös had a (scale-free) small-world network of mathematical research collaboration
46
小世界实验
Milgram小世界实验
大部分复杂网络有小的平均距离 L 小世界特征
29
例子:
一个具5个节点5个连接的网络:
.
∑ L
=
1
1 N(N
−1)
i> j
d ij
2
d12 = 1
d13 = 1

20
三、社区结构
整个网络是由若干个“社区"或“组’’构成的。每个社 区内部的结点间的连接相对非常紧密，但是各个社区之间 的连接相对来说却比较稀疏（网络中的顶点可以分成组, 组内连接稠密而组间连接稀疏）。我们将复杂网络的这种 结构特征称之为复杂网络的社团结构或社区结构。
社区结构是复杂网络的一个重要的特性，社区也被称为簇， 大量研究表明网络是由各种不同类型的节点构成的，一般 情况下，在不同类型的节点间存在较少的边，而在相同类 型的节点间会有较多的边。位于一个子图内的节点和边组 成一个社团。 复杂网络社区结构还有一个很重要的特性,即是它的层次特
复杂网络的统计特征
网络的聚类系数C：所有节点i的聚类系数Ci的平均值。
（0C1） C=0网络中所有节点都是孤立点 C=1网络中任意节点间都有边相连
★ 网络节点间联系的密切程度, 体现网络的凝聚力
★ 许多大规模的实际网络都具有明显的聚类效应。事实 上，在很多类型的网络(如社会关系网络)中，你的朋友同 时也是朋友的概率会随着网络规模的增加而趋向于某个非 零常数，即当N→∞时，C=O(1)。这意味着这些实际的复杂 网络并不是完全随机的，而是在某种程度上具有类似于社 会关系网络中“物以类聚，人以群分”的特性。
性现实中的网络是由一个个较小的社团组成,而这些社团又可 以包括更小的社团。发现网络中的社团结构,对于了解网络结 构，分析网络特性都具有很重要的意义。
复杂网络研究内容
1）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。
2）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。
节点的数目。
★ 直观上看，一个节点的度越大就意味着这个节点在

随机图——节点42，边118
平均度为5.62，集聚系数为0.133。
ER模型
Erdös和Rényi （ER）最早提出随机网络 模型并进行了深入研究，他们是用概率统 计方法研究随机图统计特性的创始人。
给定N个节点，没有边，以概率p用边连接 任意一对节点，用这样的方法产生一随机 网络。
ER模型
小世界实验--- 六度分离
米尔格伦的实验过程是：他计划通过人传人的送信方式来统 计人与人之间的联系。
首先把信交给志愿者A，告诉他信最终要送给收信人S。如果 他不认识S，那么就送信到某个他认识的人B手里，理由是A认 为在他的交集圈里B是最可能认识S的。但是如果B也不认识S， 那么B同样把信送到他的一个朋友C手中，……，就这样一步 步最后信终于到达S那里。这样就从A到B到C到……最后到S连 成了一个链。斯坦利•米尔格伦就是通过对这个链做了统计后 做出了六度分离的结论。
性现实中的网络是由一个个较小的社团组成,而这些社团又可 以包括更小的社团。发现网络中的社团结构,对于了解网络结 构，分析网络特性都具有很重要的意义。
复杂网络研究内容
1）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。
2）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。
度(degree)：节点 i 的度 ki 定义为与该节点连接的其他
节点的数目。
★ 直观上看，一个节点的度越大就意味着这个节点在
某种意义上越“重要”（“能力大”）。
网络的平均度：网络中所有节点的度和的平均值
dv
vV G
，记作<k>。
p
度分布函数p(k):随机选定节点的度恰好为k的概率