CS224W 第二讲 衡量图的性质

衡量图性质的四种指标

有些性质是在所有图（不同种类）中都适用的

度的分布（Degree Distribution）

P(k) = Nk/N
如果是有向图的的话，会有两个分布图分别代表 入度 和 出度

这里老师讲到，以后会看到，这个degree distribution 会呈一条直线，这个直线会有很重要的性质值得探讨

以后会有一整皆课来探讨

图中的通路（path）

我们关注的是最短路径

这里关注的是最短路径

• 距离：一对节点间最短路径所包含的边的个数，如果无法连接，距离为正无穷（在有向图中，要沿着边的指向走，也就导致了路径并不是对称的）（在有权图中，距离定义为最短消耗的路径）

• 网络直径：最大的最短路径
• 平均路径：把所有路径加起来，除以边的数量再除以2（如果图不是连接的，会把这个hij 忽略为0）

聚集参数（clustering coefficient）

这里聚集参数的大概意思就是，我的邻居是不是也互相是邻居，比如下面举得这个例子：
聚集参数定义在每个点上，对于点 i 来说，他的四个邻居总共可能有六条边，在第一个图中，这六条边都存在，所以 i 的聚集参数是1，而在第二张图中，六条边存在三条，所以聚集参数是 3，同理第三张图中，四个邻居互不认识，所以聚集参数为零

这里，PPT上给了第二个例子，可供参考

连接性（connectivity）

对于无向图来说，就是最大连通分量 包含的节点数
对于有向图，又分为强连接性和非强连接性

MSN 社交图考量

如何构建网络

这么大的图如何建图？

用一个无向图来表示，如果没有联系就没有边，同时，边的数量代表交换消息的次数

MSN图的度分布

点几乎都分布在 轴线上，这说明：

• 有很多人的度数很小
• 有甚少的人的度数很大

这样看起来似乎很无用，但是如果用 log 图展示出来呢？

说明 degree 聚集低度数上

MSN图的聚集参数

说明十分之一的朋友们相互认识

MSN图的连接性

这里看到，有一个非常巨大的连通分量，10的八次方，然后还有很多小个的连通分量

MSN图的连接直径

我们惊讶的发现，陌生人原来也就与我们相隔6层关系

蛋白质反应模型（PPI）模型

我们需要一个模型来解释上述那些系数

我们发现 蛋白质的情况和MSN很相似

Erdos-Renyi 随机图模型

定义如下

两个参数 n ， p：

• n 代表节点个数
• p代表两个边连接在一起的概率

模型的性质

1. Gnp的分布是二项分布
   这里我们可以说：如果图的节点足够多，那么到最后，方差除以均值会无限趋近于零，这就是告诉我们，在无限图中，每个点的度几乎都是一样的
2. Gnp 的聚集参数 是 C = p = k/n （如果保持k 不变，不断提高n的值，那么C会逐渐趋近于零）
3. 路径。为了说明这个问题，定义一个概念 Expansion
   
   就是任意分成两个集合，α 代表这两个集合间的边的最小值，而在Gnp中，这个α很大。
   定义了这个α，我们有结论如下：
   在一个 Expansion 为 α，节点数为n的图中，每两对节点间有一条长度为O（（logn）/α）的路径
   具体到 Gnp 他的图半径为O（logn/log(np)
   下面这个图很好的解释了这个log的来由
4. 连通分量：
   这里，横坐标代表 图中平均度数，纵坐标代表最大连通分量所占全图分量
   

模型与 MSN 比较

小世界模型（The Small-World Model)

我们可以同时有 高 聚集系数 和 小 直径吗？

随机模型总是有更小的聚集参数，我们可以把它提高吗？


如图，我们可以首先找到一个 高聚集系数+高半径的图，然后以某个概率把把重新连接，把高半径打碎，同时不破坏 高聚集的性质，就得到了小世界模型

Kronecker Graph Model

就是同一个矩阵重复出现


这里给出 Kronecker product 的定义，可以看出，确实是B矩阵重复出现 A 的元素个数 次
但是这样还是太死板了，如果再加上概率：

每个数字代表这条边出现的概率，现在的问题就是，这样的Kronecker product 太费时了，时间复杂度太高，有没有什么解决办法呢？

这样一个一个的放，由于矩阵非常稀疏，所以复杂度大大下降（这里没有听明白）
大概是首先找到有多少需要填进去的边，然后根据概率只放最大的

这里可以发现这个模型非常接近实际数据。
最后讲的这个是2008年的一篇论文提出的，这里放上连接，等以后有时间看一看：
https://arxiv.org/abs/0812.4905