Aritalab:Lecture/NetworkBiology/Link Analysis

Centrality

各頂点がどれくらいネットワークの中心にあるかを測る尺度を中心度(centrality)という。いずれの値も0-1の間をとるように正規化する。有向グラフと無向グラフとで数式が少し異なるが意味する内容は同じ。

• Degree centrality ... リンク数が多い点を中心と考える
• Closeness centrality ... 全頂点への平均最短距離が短い点を中心と考える
• Betweenness centrality ... 全頂点間の最短経路に多く使われる点を中心と考える

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)$。