基本概念

除了一些常见的图的基本概念，如：连通图、度数、连通子图、强连通图、有向图、无向图、有向图连通性等之外，还有一些之前没有接触过的概念在此补充一下：

图直径：

图中两两结点之间的距离值的最大值。

度中心性：

$\text{度中心性}=\frac{N_{degree}}{n-1}$

特征向量中心性：

图对应一个邻接矩阵，求这个邻接矩阵的特征值和特征向量，最大特征值对应的特征向量就是特征向量中心性。比如上面例子中，求出来的特征值最大的是第一个，对应的特征向量是第一列，将第一列求负数（没影响），得到特征向量中心性。

下面观察一下“特征向量中心性”到底可以表征何种信息。

看节点1和节点5，其特征向量中心性的值是最大的，在图中可以看出来，两节点的度数也是最大的。2,3,4节点的特征向量中心性没有节点1和5大，从图中看出来是因为它们的度数为2<3。但是2,3,4之间也有大小关系，可以看到2,3,4虽然度数相同，但是所连接的结点的度数不同，具体来说是：4结点邻接点是1,5，它们都是读数为3的结点；2结点和3结点读数都为2，所连接的两个结点都是一个读数为2，一个读数为3，所以二者的度数相同。

从上述分析可以看出来，特征向量中心性不仅表征了一个节点的度数，还表征了其相邻节点的度数。

中介中心性

计算公式：

$Betweenness=\frac{\text{经过该结点的最短路径}}{\text{其余两两结点的最短路径}}$

比如下面的关系图中：

假设每一条边的权值为1。曹操的中介中心性计算如下：

$\text{曹操}_{betweenness}=\frac{(0+1+1+0.5) + (0+0+1+1)+(0+1+1+0.5)+4+4}{4*5}$

这表示什么含义呢？

首先蔡文姬结点，到达甄姬的最短路径为1，但是没有经过曹操，所以第一项的第一个值为0；蔡文姬到达夏侯惇的最短路径为

连接中心性

$Closeness=\frac{n-1}{\text{结点到其他结点最短路径之和}}$

还是上面的王者的图，

$\text{曹操}_{closeness}=\frac{6-1}{5}=1$

PageRank(网页排序算法)

HITS