02-Properties of NetWorks, Random Graph Models
2.1 如何衡量一个网络
2.1.1 关键的网络的参数
Degree distribution:\(P(k)\) （度分布）
Path length:\(h\) （路径长度）
Clustering coefficient:\(C\) (聚类系数)
Connected components:\(s\) (连通分量)
（1）Degree Distribution
Probability that a randomly chosen node has degree k
随机选择的节点的度为k的概率
Normalized histogram: 规范化的矩形图
\(P(k)=N_k/N\)
（2）Paths in a Graph
A path is a sequence of nodes in which each node is linked to the next one
A path can intersect（相交） itself and pass through the same edge multiple times
如：ACBDCDEG
距离（最短路径）：在一对节点中，通过最短路径经过的连接这些点的边。
如果两个节点没有被连接，那他们的距离经常被定义为无穷大或0
在有向图中，路径需要遵循箭头的方向。因此，距离就不是对称的了。B到C的距离不等于C到B的距离。
直径：在图的任意两个节点中的最大距离
平均路径长度：对于一个连通图或强连接有向图而言，
- 只计算连接的节点，不管路径长度为无限大或0的节点。
- 同样应用于一个图的连通分量。
（3）Clustering Coefficient（聚类系数）
对于无向图而言，聚类系数阐述的是节点i的邻居们的相互连接情况如何？
其中，节点i的度为 \(k_i\)
即用i的邻居们的实际相互连接的边的数目(\(e_i\))除以i的邻居们最大能相互连接的边的数目（\(k_i(k_i-1)/2\)）。
平均聚类系数：
例：
（4）Connectivity（连通性）
最大的连通分量：最大的节点集合，其中任意两个点都有路径可以到达
Largest component = Giant component
可以通过BFS来求出最大连通图。
2.2 用这些特性来衡量现实世界网络！
·
将该现实世界网络模型化作为一个无向图：
- 如果u和v交换了至少一条消息，那么它们间有一条边 \(Edge(u,v)\)
- N = 180 million people
- E = 1.3 billion edges
Degree Distribution
不够直观，无法分析出结果，因此采用对数来画图
Log-Log Degree Distribution
Clustering
Connected Components
Diameter of WCC
MSN: Key Network Properties
Another example: PPI Network
我们需要找到一个模型来对应现实世界网络，所以开启了如下的探索：
2.3 Erdo?s-Renyi Random Graph Model
最简单的图模型
两个变体：
- \(G_{np}\): 无向图，n个节点，每条边edges（u，v），以概率p独立分布（i.i.d）
- \(G_{nm}\)：无向图，n个节点，m条边被均匀的随机选择
Random Graph Model
n和p并不能独一无二地确定一个GNP图，因为该图是随机过程的结果。
相同的n和p可以生成许多不同的结果。
Properties of \(G_{np}\)
Degree Distribution
事实：Gnp图的度分布是二项分布。
用\(P（k）\)来表示节点度数为k的概率
理解：一个节点度数为k，就意味着要与k个节点有边，其他n-1-k个节点没有边。同时，这k个节点有很多种选择方法，要把所有选择方法的数目求出来。
方差和数学期望可以求出：
变异系数：
变异系数（Coefficient of Variation）：当需要比较两组数据离散程度大小的时候，如果两组数据的测量尺度相差太大，或者数据量纲的不同，直接使用标准差来进行比较不合适，此时就应当消除测量尺度和量纲的影响，而变异系数可以做到这一点，它是原始数据标准差与原始数据平均数的比。CV没有量纲，这样就可以进行客观比较了。事实上，可以认为变异系数和极差、标准差和方差一样，都是反映数据离散程度的绝对值。其数据大小不仅受变量值离散程度的影响，而且还受变量值平均水平大小的影响。
根据大数定律，随着网络变大， 分布会变窄，也就是趋于稳定，即变异系数趋近于0
Clustering Coefficient of Gnp
这个推导过程很很理解。要求 \(C_i\) 的数学期望，则先求 \(e_i\) 的数学期望。\(e_i\) 是i的邻居间的边数。所以，ei的数学期望是他的邻居的能有的最多的边数乘以每一条边的概率。
Path length
Def：Expansion
图G（V，E）有一个扩张系数 \(\alpha\) ,如果S是V的子图，那么从S离开的变数大于等于\(\alpha\) 乘以S与V\S边数的最小值。
Expansion: Random Graphs
事实：在一个节点个数为n，扩张系数为 \(\alpha\)的图中，对于所有的节点对，路径长度为 \(O((log\ n)/\alpha)\) 即路径最大为\((log\ n)/\alpha\)
因此，在Random Graph Gnp中，
（当然，扩展系数在Gnp图中是log np这个问题，由于我也想不明白为何（可能在课程的阅读资料Random Graph 里有但是过长的英语论文对我来说是个折磨），所以就当它是一个结论吧）
所以通过作图可以直观看到平均最短路径随着节点n的变化而变化的图
Connected components
"Evolution of a Random Graph"
Giant component 的形成：
当平均度小于1时，显然不可能会有Giant component出现。所以只有当平均度大于1时，才会有Giant component
Real Networks vs. Gnp
因此，Gnp与RealNetworks只能有部分满足，并不能拥有较好的拟合度。
- 度分布和真实网络不通
- 真实网络的巨型组件并不会通过n的变大而出现，而是一直出现。
- 没有局部结构。聚类系数太低。
因此，真实网络并不是Gnp图！
2.4 The Small-World Model
有没有一个模型，能有很大的聚类系数而直径却很小呢？
MSN网络比Gnp网络的聚类系数大了7个数量级！
如果只是偶然的话，可以看看其他例子：
还是同样的结果。
“矛盾”
扩张的结果
最短路径为O（log n），这是能得到的最小半径，如果保持度为常数的话。但聚类系数很小。
当网络有局部结构时
很大的聚类系数，但直径也很大
是否能有一个大聚类系数，小直径（log n 的直径）的模型呢？
聚类意味着边要有“局部性”
随机性实现了“捷径”，也就是小的直径
解决办法：The Small-World Model
模型的两个组成部分：
-
从低维晶格开始：在这个例子中，用一个环代表一个晶格。用着高聚类系数
-
重新连边：引入随机性（“捷径”）
添加/删除边来给边远的部分创造捷径
对每条边，都用概率 \(p\) 将另一个端点连到一个随机节点上
采用重新连线的方式让我们在晶格与随机图中插入了一个高聚类系数，低直径的网络！
破坏集群需要很大随机性，而创造捷径的随机性很小。
在绿色区域中取到的系数所构成的图就是我们想要的Small-World模型图！
总结
具有高集群的网络可以同时是一个Small-World吗？
可以，只需要几个随机连接就可以做到。
The Watts Strogatz Model
- 提供了集群和Small-World之间相互作用的见解
- 捕捉了很多现实网络的结构
- 考虑到了真实网络的高度集群
- 但没有导出正确的度分布
Kronecker Graph Model因为这个模型很重要，所以在下一篇笔记中会详细集合教授的论文和课程来解释。