节点度数 (Node degree)
- 结点 \(v\) 的度数 \(k_v\) 是 \(v\) 所邻接到的节点数量。
- 平等对待所有邻居节点，没有考虑节点的重要性。
节点中心性 (Node centrality)
- 考虑了节点的重要性。
1.特征向量中心性 (Eigenvector centrality)
如果节点 \(v\) 的邻域 \(u \in N(v)\) 中有重要的节点，那么节点 \(v\) 也应该是重要的。
\[c_v = \frac{1}{\lambda} \sum_{u\in N(v)} c_u
\]
其中 \(\lambda\) 为某正常数。
上式也可表示为：
\[\lambda \mathbf{c} = \mathbf{Ac}
\]
其中 \(\mathbf{A}\) 是邻接矩阵，\(\mathbf{c}\) 是节点中心性向量。
2. 介数中心性 (Betweenness centrality)
如果一个节点在很多其它节点间的最短路上，那么该节点被认为是重要的。
\[c_v = \sum_{s\neq v\neq t} \frac{\#(含有v的s到t的最短路数量)}{\#(s到t的最短路数量)}
\]
3. 接近中心性 (Closeness centrality)
如果一个节点到所有其它节点的最短路之和是最短的，那么该节点被认为是重要的。
\[c_v = \frac{1}{\sum_{u\neq v} (u 到 v 的最短路长度)}
\]
聚类系数 (Clustering coefficient)
考虑了节点周围的局部结构，衡量了节点和其邻域连接的紧密程度。
\[e_v = \frac{\#(v的邻域节点之间的边数)}{\binom{k_v}{2}} \in [0, 1]
\]
聚类系数实际上计数了节点 \(v\) 及其邻域的导出子图中的三角形数量。
Graphlets
Graphlets: 一系列有根连通非同构子图。
Graphlet Degree Vector(GDV): 节点作为根的Graphlets数量向量。度量了节点在网络中的局部拓扑结构。
- 节点度数统计了和节点相连的边数。
- 聚类系数统计了 和节点相连的三角形数量。
- GDV 统计了和节点相连的 Graphlet 数量。
