复杂网络模型.ppt

复杂网络模型
什么是网络?
网络: 一个通过链接互相关联的实体的集合.
互为朋友的人
互相链接的
互相指向的网页
互相作用的蛋白质
图
在数学世界, 网络被称作图, 实体被称作结点, 而它们之间的链接被称作边。
关于图的理论(2,3),(3,4),(4,5)}
图理论
Graph G=(V,E)
V = 顶点的集合
E = 边的集合
1
2
3
4
5
有向图
E={‹1,2›, ‹2,1› ‹1,3›, ‹3,2›, ‹3,4›, ‹4,5›}
无向图
1
2
3
4
5
结点i的度数d---d(i)
与结点i相连的边数
度序列
[d(i),d(2),d(3),d(4),d(5)]
[2,2,2,1,1]
度分布
[(1,2),(2,3)]
有向图
1
2
3
4
5
结点i的入度
指向结点i的边数
结点i的出度
以结点i为起始点的边数
入度序列
[1,2,1,1,1]
出度序列
[2,1,2,1,0]
路径
从结点i到结点j的路径: 一段连续的边 (有向或无向从结点i到结点j的连接)
路径长度: 路径上的边数
结点i和结点j是相连的
循环: 一段初始和结束结点是同一个结点的路径
1
2
3
4
5
1
2
3
4
5
最短路径
从结点i到结点j的最短路径
也被称作BFS路径, 或短线程路径
1
2
3
4
5
1
2
3
4
5
直径
途中距离最长的一条最短路径
1
2
3
4
5
1
2
3
4
5
无向图
1
2
3
4
5
连通图: 任意两个结点都存在连接的图
非连通图: 一个无连接的图
连通区域: 包含相连顶点的子图
完全连通图
Clique Kn
一个最多有 n(n-1)/2 条边的图（n为顶点数）
1
2
3
4
5
连通图
1
2
3
4
5
强连通图: 任意两个顶点之间存在一条路径
弱连通图: 边没有指向时图就是连通的
子图
1
2
3
4
5
子图: 给定V’  V, E’  E,
图 G’=(V’,E’) 就是G的一个子图.
生成子图: 给定 V’  V, E’  E 是V’中结点连成的边的集合. 则图 G’=(V’,E’), 是G的一个生成子图
树
没有循环的无向连通图
1
2
3
4
5
二分图
集合V可以被分割成两个集合L和R的图, 而所有的边由L和R的结点连接而成，在集合L和R内部不存在边。
线性代数
邻接矩阵
对称矩阵的无向图
1
2
3
4
5
线性代数
邻接矩阵
非对称矩阵的无向图
1
2
3
4
5
特征值与特征向量
若值 λ是矩阵A的特征值，且存在不为零向量的向量X，使得, Ax=λx. 向量 x 是矩阵A的一个特征向量
最大的特征向量被称为主特征值
对应的特征向量被称为主特征向量
对应最大值方向的变动
特征值
随机游动
从一个结点开始,它的连接结点一律是随机的。
平稳分布: 你访问结点i次数的分数, 随着随机游动经过边数的增逐渐加接近无穷大
如果一个图是强连通图, 它的平稳分布收敛与一个唯一的一个向量。
随机游动
平稳分布: 标准邻接矩阵左边的主特征向量
x = xP
无向图的度分布
1
2
3
4
5
概率论
概率空间: 给定一对‹Ω,P›
Ω: 样本空间
P: Ω的子集的测量概率
随机变量 X: Ω→R
概率分布函数 P[X=x]
数学期望
随机图的类
随机图的类 被定义为一对 ‹Gn,P› ，Gn 是 所有大小为n的图的集合, P 是集合Gn的概率分布
Erdös-Renyi 图: 每条边出现的概率为 p
当 p=1/2时, 我们得到一个统一的分布
渐近符号
对于两个函数 f(n)和g(n)
若存在正数 c 和 N, 使得 f(n) ≤ c g(n), 则对于所有的 n≥N，有f(n) = O(g(n))
若存在正数 c 和 N, 使得 f(n) ≥ c g(n), 则对于所有的 n≥N，有 f(n) = Ω(g(n))
若f(n)=O(g(n))并且f(n)=Ω(g(n)) ，则有f(n)