网络的4大关键属性
- 度分布（Dgree distribution：p(k)）
- 路径长度（Path length：h）
- 聚合系数（Clustering coefficient：C）
- 联通模块（Connected components：s）
以上4个属性主要针对无向图，如果以下笔记有特别针对有向图时，会主动提出
度分布
= 度为k的节点数，
= 总节点数
对于有向图我们分为出度和入度分布
路径长度
距离：两点间的最短路径（如果两点之间不连接，通常将距离定义为infinite）
直径：图中两点的最大距离
平均路径长度：针对无向图和有向图中的强连通图（强连通图代表任意两点间存在路径）
聚合系数
代表节点i的邻居间存在的边的数量，
代表节点i的邻居间可能存在的再大的边的数量，将这两个量相除就得到了聚合系数
联通模块
随机图模型
本课程主要介绍了模式（还有了
课程没有详细介绍）：对于拥有n个节点的无向图，每两个点间存在边的概率为p。对于给定的两个参数n和p，相同的参数可能会产生不同的图。
那么Gnp模型的四种网络属性又是怎么样的呢？先上结论。
- Degree distribution：
- Path length：
- Clustering coefficient：
- Connected components：暂略
度分布
slide中还提到，根据概率论中的另一个知识——大数定律，随着随机图的规模越来越大，节点的度越来越集中在平均度附近。
路径长度
这里Jure引入了扩展系数来证明随机网络的路径长度。直接给了结果，即一个有n个节点的网络，如果有扩展系数为
，则网络的路径长度的期望是：
,这是一个和
有关的值。
对于随机网络，路径长度的期望就是。对于固定的
，分母变成了常数，所以就是
级别。模拟实验的结果如下，也证明了这个结论。
聚合系数
由于点之间存在边的概率为p，所以给出了
另外slide中还提到随即图模型的聚合系数很小，如果我们生成越来越大的图，并且固定平均度，聚合系数会越来越小。
联通模块
由上图可知图的联通性会随着p的改变而改变
随着p值越来越大，节点的平均度也越来越大，最终最大联通块中囊括了图中大部分的节点。
sumary
将实际的图与随机图进行了比较，并给出了为什么我们要使用随即图的原因。
小世界图模型
随机网络是很简单的图模型，可以作为一个基准。但是更实际的模型有很多，其中小世界图模型非常有名。其核心思想就是，虽然随机网络的平均路径是比较短的，但聚合系数非常的低，这是由于随机网络假定的是大家都随机的和世界上其他人交朋友。但真实的网络的聚合系数都是很高的，节点的本地结构化非常明显。那么我们能否通过某种方式来产生这样的图——高聚合系数、低平均路径长度(或者就是低图直径)。
一种构造高聚合系数、低平均路径长度图的方式:
- 先构造一个左边的图
-
对每一条边，以概率p将该边的一个端点改为另一个随机节点
rewoire.PNG
Kronecker网络模型
Kroneck乘法：
随机Kronecker模型构造法：
- 构造一个
X
- 使用Kronecker乘法
次，生成矩阵
-
中每个元素代表一个概率值，即两个节点间生成边的概率
- 然后按照这个概率产生实际的邻接矩阵，就生成了一个大图
由于上面的方式要计算X
次才能得出目标矩阵，说是这样速度太慢了，又说了一种快速的方式，不过没怎么看懂，如果以后用到了再说吧。
