网络属性

在本节中，我们将研究用于表征网络的关键属性：聚类系数，节点距离，度分布，联通子图和稳定性。 这些定义主要是针对无向图的，但可以将其扩展为有向图。

聚类系数（Cluster Coefficient）

聚类系数(针对无向图)用于衡量节点 $i$ 的邻居所占比例。

Local Cluster Coefficient

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

$$C_{i}=\frac{2e_{i}}{k_{i}(k_{i}-1)}$$

其中 $e_{i}$ 是节点 $i$ 的相邻节点之间的边数。 注意 $C_{i}\in[0,1]$ 。 此外，对于度数为0或1的节点，聚类系数是不确定的。

Global Cluster Coefficient

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

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

第二种方法，是先计算在图中已经关闭上的三角形的个数，除上没有闭上的三角形的个数。这种计算方法叫做 Transitivity。这两种方法并没有优劣之分，只是 Transitivity 会倾向于给 degree 大的节点较大的权重。

平均聚类系数

同样，可以计算平均聚类系数为：

$$C=\frac{1}{N}\sum_{i}^{N}C_{i}$$

平均聚类系数使我们能够看到边在网络的某些部分是否显得更加密集。 在社交网络中，平均聚类系数趋于很高，表明如我们期望的那样，朋友的朋友倾向于彼此认识。

节点距离

路径是一系列节点，其中每个节点都链接到下一个节点：

$$P_{n}=\left\{i_{0},i_{1},i_{2},...,i_{n}\right\}$$

其中 $\left\{(i_{0},i_{1}),(i_{1},i_{2}),(i_{2},i_{3}),…(i_{n-1},i_{n})\right\} \in E$

一对节点之间的距离(最短路径，geodesic)定义为沿着连接这些节点的最短路径的边数。 如果两个节点未连接，则距离通常定义为无限(或零)。 还可以将距离视为遍历从一个节点到另一个节点所需的最少节点数。为了获得最短距离，通常可以采用图的深度优先遍历，或者广度优先遍历。对于一个较大的网络，想要获得从一个节点到所有节点的距离，会推荐使用 广度优先遍历，因为广度优先遍历可以一层一层的进行计算距离。

在有向图中，路径需要遵循箭头的方向。 因此，有向图的距离不是对称的。 对于具有加权边的图，距离是从一个节点到另一个节点所需要遍历的最小边权重。

图的平均路径长度是所有连接的节点之间中最短路径的平均值。 我们将计算平均路径长度定义为

$$\hat{h}=\frac{1}{2 E_{max }} \sum_{i, j \neq i} h_{i j}$$

其中 $E_{max}$ 是边或节点对的最大数目；也就是说 $E_{max}=n(n-1)/2$ 和 $h_{ij}$ 是从 $i$ 节点到 $j$ 节点的距离。注意，我们仅计算连接的节点对上的平均路径长度，因此忽略了无限长度的路径。

下面是是几个用于描述网络节点距离的参数

• Average distance： 这个很好理解，就是所有两两节点之间的最短距离的平均值，最直接的描述了图的紧密程度
• Eccentricity：这个参数描述的是从任意一个节点，到达其他节点的最大距离
• Diameter：图中的最大两个节点间的距离
• Radius：图中的最小两个节点间的距离
• Periphery： 和 Diameter 对应，那些最大节点距离等于 diameter 的节点
• Center： 和 Radius 对应，那些最大节点距离等于 radius 的节点

度分布

度分布 $P(k)$ 表示随机选择的节点具有度 $k$ 的概率。 图 $G$ 的度分布可以通过归一化的直方图来概括，其中我们通过节点总数来归一化直方图。

我们可以通过 $P(k)=N_{k}/N$ 计算图的度分布。其中，$N_{k}$ 是度为 $k$ 的节点数，$N$ 为节点总数。可以将度分布视为随机选择的节点具有度 $k$ 的概率。

如果要将这些定义扩展为有向图，需要分别计算入度和出度的分布。

联通子图

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

• 子连通图中的每个节点都可以有路径可以连接到其他节点
• 任何其他非连通图单位的节点都没有路径可以连接到该连通图

图的连通性可衡量最大连通组件的大小。 最大的连通组件是可以通过路径将任意两个顶点连接在一起的图的最大的集合。

查找连接的组件：

1. 从随机节点开始并执行广度优先搜索(BFS)
2. 标记BFS访问的节点
3. 如果访问了所有节点，则表明网络是连通的
4. 否则，找到一个未访问的节点并重复BFS

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

1. 强联通图：每个节点 u 可以到 v，v 也可以到 u。
2. 弱联通图：只需要 u 可以到 v 即可，可以想象成，满足的条件就是将有向图变成无向图之后是强链接的即可。

   稳定性

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

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

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

1. 断开一个网络需要的最少的 Node Cuts
2. 断开一个网络需要的最少的 Edge Cuts

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

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

1. 断开两个节点的链接需要的最少的 Node Cuts
2. 断开两个节点的链接需要的最少的 Edge Cuts
   
   如上图所示，如果我们移除网络中的 A$\rightarrow$N 和 J$\rightarrow$O 连接，G$\rightarrow$L 的连接将会断开。