网络重要节点排序方法
赞
踩
研究背景
复杂网络的重要节点是指相比网络其他节点而言，能够在更大程度上影响网络的结构与功能的一些特殊节点。
近年来，节点重要性（中心性）排序研究受到越来越广泛的关注，不仅因为其重大的理论研究意义，更因为其广泛的实际应用价值。由于应用领域极广，且不同类型的网络中节点的重要性评价方法各有侧重，学者们从不同的实际问题出发设计出各种各样的方法。
提前约定
一个网络的拓扑图记为 G ( V ， E ) G(V，E) G(V，E)
V = { v 1 , v 2 , ⋅ ⋅ ⋅ , v n } V=\{v_1,v_2,···,v_n\} V={
v1,v2,⋅⋅⋅,vn} ：节点集合， n n n 为节点数
E = { e 1 , e 2 , ⋅ ⋅ ⋅ , e m } E=\{e_1, e_2,···,e_m\} E={
e1,e2,⋅⋅⋅,em}：边的集合， m m m 为边数
一个图的邻接矩阵为： A n × n = ( a i j ) \boldsymbol A_{n×n}=(a_{ij}) An×n=(aij)
| 无向网络 | 有向网络 |
|---|---|
| a i j = { 1 , v i 与 v j 之间有连边 0 , v i 与 v j 之间无连边 a_{ij}=\left\{ |
a i j = { 1 , 存在一条从 v i 到 v j 的有向边 0 , 不存在一条从 v i 到 v j 的有向边 a_{ij}=\left\{ |
特别的，一个含权图的邻接矩阵为： W n × n = ( w i j ) \boldsymbol W_{n×n}=(w_{ij}) Wn×n=(wij)
w i j = { 连边上的权值, v i 与 v j 之间有连边 0 , v i 与 v j 之间无连边 w_{ij}=\left\{
同时约定所有在网络中传播的信息、病毒、车流、人流、电流等统称为网络流。
网络中的一条路径是类似这样的一组节点和边的交替序列： v 1 v_1 v1, e 1 e_1 e1, v 2 v_2 v2, e 2 e_2 e2,···, e n 1 e_{n1} en1, v n v_n vn, 其中 v i v_i vi， v i + 1 v_{i+1} vi+1 是 e i e_i ei 的两个端点。如果任意一对节点之间都存在一条路径使它们相连, 就称这个网络是连通的。
基于节点近邻的排序方法
度中心性（degree centrality, DC）
观点：一个节点的邻居数目越多，影响力就越大，就越重要。
刻画角度：节点的直接影响力
节点 v i v_i vi 的度： k i = ∑ j a i j k_i=\sum_j{a_{ij}} ki=∑jaij，表示与 v i v_i vi 直接相连的节点的数目。在有向网络中, 根据连边的方向不同, 节点的度有入度和出度之分。在含权网络中节点度又称为节点的强度(strength)，定义为与节点相连的边的权重之和。
节点 v i v_i vi 的归一化度中心性指标为： D C ( i ) = k i
