图论基础

简介

边描述两节点的关系，上图为无向图。图可以通过邻接矩阵来表示，若节点1到节点2之间存在边，那么邻接矩阵的第一行的第二列为1，第二行的第一列也为1。因为无向图的表示应该是双向的。

图的性质

度$d(v_i)$：与节点$v_i$相连的边的数量

节点的邻域

邻域$N(v_i)$：与节点$v_i$相连的节点的集合

途径Walk

途径是节点和边交替的序列，从一个节点开始，以一个节点结束，其中每条边与紧邻的节点相连。
途径的长度：途径中包含的边的数量
两种特殊的途径：
trail迹：边各不相同的途径
path路：节点各不相同的途径

连通图

给定一个图，如果图中的任意两个节点之间都至少存在一条路，则这个图是一个连通图。
最短路：给定连通图中的任意两点，连接着两点的长度最小的路（经过的边个数最少）被称为这两个点之间的最短路。最短路的长度被称为两点之间的距离。

图的直径：图中最远的两点间的距离（最长的最短路的边的个数？）

节点中心性

节点的中心行用来衡量节点在图上的重要程度
将每个节点映射到一个标量，那么每个节点对应一个分数。这个分数就可以用来衡量节点在图中的重要性。

度中心性
利用节点的度来衡量节点的中心性，度越高就认为其更重要，但是比如在社将网络中，你有很多粉丝但都是僵尸粉，相比粉丝没有那么多，但都是优质粉丝的用户来说，你就没有那么重要。因此，单纯度中心性不能很好的衡量节点中心性。
$c_d\left(v_i\right)=d\left(v_i\right)={\sum }_{j=1}^N{\mathbf{A}}_{i,j}$

特征向量中心性
衡量节点的中心性同时考虑邻居节点的中心性
$c_e\left(v_i\right)=\frac{1}{\lambda }{\sum }_{j=1}^N{\mathbf{A}}_{i,j}\cdot c_e\left(v_j\right)$ --> $\lambda \cdot {\mathbf{c}}_e=\mathbf{A}\cdot {\mathbf{c}}_e$

Katz中心性
Katz是特征向量中心性的一个变种，beta其实是针对节点i自身的一个重要性
$c_k\left(v_i\right)=\alpha {\sum }_{j=1}^N{\mathbf{A}}_{i,j}{c}_k\left(v_j\right)+\beta$

${\mathbf{c}}_k=(\mathbf{I}-\alpha \cdot \mathbf{A}{)}^{-1}\mathbf{\beta }$

$0<\alpha <\frac{1}{\lambda }$