Aritalab:Lecture/NetworkBiology/Link Analysis

Centrality

無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality)という。いずれの値も0-1の間をとるように正規化する。有向グラフでも定義できるが、次に述べるprestigeを使った方がよい。

• Degree centrality ... 辺数が多い点を中心と考える。
• Closeness centrality ... 全頂点への平均最短距離が短い点を中心と考える。
• Betweenness centrality ... 全頂点間の最短経路に多く使われる点を中心と考える。同じ値で辺のbetweennessも定義できる。

Name	Undirected	Directed
Degree	$C_D(i)=\frac{d(i)}{n-1}$	$C_D(i)=\frac{d_{out}(i)}{n-1}$
Closeness	$C_C(i)=\frac{n-1}{\sigma^n_{j=1}d(i,j)}$
Betweenness	$C_B(i)=\sigma_{j<k}\frac{p_{jk}(i)}{p_{jk}} \times N_{paths}^{-1}$ ただしj,kはiと異なる頂点。iを除いた最短経路の本数は無向で$\frac{(n-1)(n-2)}{2}$、有向で$(n-1)(n-2)$。

Prestige

有向グラフにおいて頂点の傑出具合を測る尺度を傑出度(prestige)という。

• Degree prestige ... 多くの入力辺がある点を傑出していると考える。
• Proximity prestige ... より多くの頂点から到達できる点を傑出していると考える。Degree prestigeの拡張になっている。
• Rank prestige ... 高いランクの頂点に指されている頂点もランクが高いと考える。

Name
Degree	$P_D(i)=\frac{d_{in}(i)}{n-1}$
Proximity	$P_P(i)=\frac{|I_i|/(n-1)}{\sum_{j\in I_i}d(j,i)/|I_i|}$ $I_i$はiより到達できる頂点集合
Rank	$\mathbf{P_R=A^TP_R}$ $\mathbf{P_R}$は長さnの縦ベクトル、$\mathbf{A}$は隣接行列。つまり$\mathbf{P_R}$は$\mathbf{A}$の固有値。