节点相关的概念

centrality 中心度

centrality，中心度，可以用于回答“重要节点的特征是什么？”之类的问题。一般而言，有这三种度量方式比较常用：

• degree centrality[/#degree-度]
• betweenness centrality[/#betweenness-介数]
• closeness centrality[#closeness-亲密度]

betweenness 介数

节点的betweenness，可以定义为： \[ betweenness(v) = \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}} \] 其中\(\sigma_{st}\)指的是节点\(s, t\)之间的最短路的数量，而\(\sigma_{st}(v)\)则是其中经过节点\(v\)的路径数量。

上述定义可以阐述为：

计算网络中任意两个节点之间的所有最短路径，那么某个节点的bewteenness可以被定义为路过这个节点的最短路数量比例。

closeness 亲密度

节点的closeness centrality，可以被定义为： \[ closeness(v) = \frac{1}{\sum_u d(v,u)} \] 其中，\(d\)指两个节点之间的距离，也即它们之间的最短路长度。如果一个节点距离整个图的所有节点都很接近，那么它的closeness也就会很高。

degree 度

一个顶点的度（degree）指与该顶点关联的边的数目。当边有权重时，就是所有边的权重和。记做\(deg(v)\)。

在有向图中，还有出度（out-degree）和入度（in-degree）的概念。

出度（out-degree）指以该顶点为起点的边的权重和，入度（in-degree）指的是以该顶点为终点的边的权重和。