最近公司开始要做 Social Media 方面的项目了，为了能更好的做这个项目，我也开始了Social Network Analysis 的研究和学习，这一篇博客记录下我在学习社交网络分析时接触到的几个概念。

在谈到 Cluster Coefficient（聚类系数）之前，先介绍一个概念，叫做 Triadic Closure。Triadic Closure 指的是在一个三角形中，有两个边已经连接上了，只有一个边是断开的和一种情况。

不难看出，在一个图模型中，如果出现了上图所示的这种连接的话，未连接的两个节点会有趋势被连接上。那些在网络中快要形成三角形但是还没有形成的，就是我们需要的。在一个连接图中找 Triadic Closure，会非常的有用。比如可用于发现社交网络中，还未连接的，但可能成为好友的人。

基于 Tradic Closure，我们可以定义图的聚类参数。我们先从如何计算一个节点的聚类参数开始说起。

一个节点的聚类参数被称为 Local Cluster Coefficient。它的计算方法也是非常的简单粗暴。先计算所有与当前节点连接的节点中间可能构成的 link 有多少个，这个数会作为分母，然后计算实际上有多少个节点被连接上了，这个数会作为分子。最终的计算结果就是 Local Cluster Coefficient。

举个栗子，上图中的节点 C 的 Local Cluster Coefficient 就是 1⁄3。

知道了如何计算单个节点的聚类系数，现在来看如何计算整个图的 Cluster Coefficient。

一种最简单粗暴的方法是，先计算每一个节点的 Local Cluster Coefficient，然后取平均值。

第二种方法，是先计算在图中已经关闭上的三角形的个数，除上没有闭上的三角形的个数。这种计算方法叫做 Transitivity。

这两种方法并没有优劣之分，只是 Transitivity 会倾向于给 degree 大的节点较大的权重。

节点距离，指的是两个节点间的最短路径的长度。为了获得最短距离，通常可以采用图的深度优先遍历，或者广度优先遍历。对于一个较大的网络，想要获得从一个节点到所有节点的距离，会推荐使用 广度优先遍历，因为广度优先遍历可以一层一层的进行计算距离。

接下来介绍几个用于描述网络节点距离的参数

利用 Python 来计算这些参数的示例代码如下：

满足子联通图的充分必要条件有两个：

这里着重介绍一下在 Directed Graph 中的两种判断是否为联通图的方式

图的稳定性表现在，如果我移除任意节点，或者移除任意边，这个图的连接性是否仍然可以保证连通性。

图的稳定性分析在一些场景中非常有用，举个栗子，比如我们有一个航班图，我们需要分析如果某一个机场意外关闭，或者某一个航班意外取消，这会不会影响出行。 所以图的稳定性分析实际上描述的是一个图抵抗攻击的能力。同样的应用场景还有，电力网络，互联网攻击等。

那么如何定量的描述一个网络的稳定性呢，两个指标：

如上图所示，如果我们移除网络中的 A 节点，这个网络就会断开。

除了断开一个网络，有的时候我们也需要分析 A 节点到 B 节点之间的连接的稳定性，分析链接的稳定的指标也非常类似以上：

如上图所示，如果我们移除网络中的 A -> N 和 J -> O 连接，G -> L 的连接将会断开。

这篇博客一共介绍了图分析的四个方面：聚类系数，节点距离，联通子图和图和稳定性分析。并给出了相对应的参数来定量描述这些指数。他们会对应着不同的应用场景。