@uminchu987さんと輪読会を開催したので、資料の内容をまとめました。
3章 ネットワークの性質を知る
3.1. どのようなノードか
中心的な役割を測る指標
ノードがどれぐらい中心的な役割を果たしているかをあらわす中心性指標をまとめます。
次数中心性
- つながっている数が多いほど中心的な役割を持つ
- あるノードに接続されているエッジの数
$$ 次数中心性: d_i = \sum_{j}{A_{i,j}} $$
出次数
$$ d_{in, i} = \sum_{j}{A_{j,i}} $$
入次数
$$ d_{out, i} = \sum_{j}{A_{i,j}} $$
固有ベクトル中心性
重要なノードにつながっている数が多いほど中心的な役割を持つ
$$ s_{eigen,i} = \sum_{j}{A_{i,j} s_{eigen,j}} $$
Katz中心性
$$ s_{katz,i} = \sum_{j}{A_{i,j} s_{katz,j}} + \beta $$
ページランク中心性
$$ s_{PageRank,i} = \sum_
{j}{A_{i,j}
\frac{s_{PageRank,j}}{d^{out}_{j}}}
(1-\beta) + \frac{\beta}{N_V}
$$
「密になっているか」を測る指標
局所クラスター係数
C_i = \frac{
2 \left|\left\{ e_{jk} : v_j, v_k \in N(v_i),\ e_{jk} \in E \right\} \right|
}{d_i (d_i - 1)}
または
C_i = \frac{2e_i}{k_i(k_i - 1)}
中心性指標の正規化
- ２つのネットワークを比較したいとき、規模が違うネットワークで中心性指標を比較することは難しい
- その場合は「ノードのペアの総数」やminmax正規化をすることで対処が可能
3.2. ノードの関係性を表す指標
最短経路長
- ネットワーク内の2つのノード間の最短距離のこと
- 情報伝達の影響や拡散の速さを測ることができる
同類性
- 類似しているノードは接続しやすい性質のこと
- ノード同士の類似性を調べることで、エッジの形成にどう影響するかを調べたりする。
最短経路長を用いた中心性
媒介中心性
- あるノードがネットワーク内の他のノード間の最短経路長にどれだけ現れるか
$$
S_{betweeness,i} = \sum_{u≠v≠i}{\frac{\sigma_{u,v}(i)}{\sigma_{u,v}}}
$$
近接中心性
- ネットワークの位置的な中心さに注目した指標。
- 他のすべてのノードに対する平均最短経路長の逆数
$$
S_{closeness,i} = \frac{N_{V}-1}{\sum_{j}d(i,j)}
$$
3.3. どのようなネットワークか
ネットワークの大きさ
- ネットワークの大きさは基本的にはノードの数で表す。
- エッジの数はあまりつかわない
- $N_V=|V|$
ネットワークの密度
- 無向ネットワークの密度は下記で表現できる。（有向は2で割る）
$$
\frac{2|E|}{N_V(N_V - 1)}
$$ - これはエッジの数$|E|$をエッジの数の最大値$\frac{N_V(N_V - 1)}{2}$で割った数。
- 要するに「最大引けるエッジ〇本のうち、実際にエッジがどれだけ引かれているか」
中心性指標の分布
次数分布
- 次数頻度の分布
- とあるネットワークについて次数の分布をみることで、ネットワーク全体の特徴がわかる。
スケールフリーネットワーク
- ごく少数のノードが多くのエッジを持ってハブのように機能するネットワークのこと。
大域的クラスター係数
- 大域的クラスター係数は下記の手順で計算する
- あるノードが、ほかの2つのノードとつながっているような部分グラフ（三つのノードからなる経路）をすべて抽出する
- 抽出された部分グラフのうち、閉路を形成しているもの（三角形）の割合
直径・平均距離
-
直径
- ネットワーク内で最も離れた2つのノード間の最短距離
- 部分的に長いネットワークの場合は数値が引っ張られる点に注意
-
平均距離
- 全ての最短経路長の平均値
同類性係数・次数相関
-
同類性係数
- 任意のノード$v$の持つ指標$f(v)$についてのピアソンの積率相関係数
- つまり-1.0~+1.0の値をとる
- 任意のノード$v$の持つ指標$f(v)$についてのピアソンの積率相関係数
-
次数相関
- ノードの次数
試しに計算してみる。
下記のようなデータがあったとする。
表1
| ノード | 年齢 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 6 |
| 4 | 8 |
表2
| エッジ | 属性1 | 属性2 |
|---|---|---|
| (1,2) | 2 | 4 |
| (2,3) | 4 | 6 |
| (3,4) | 6 | 8 |
| (1,3) | 2 | 6 |
- 属性1の平均
- $(2+4+6+2)/4 = 3.5$
- 属性2の平均: 4.0
- $(4+6+8+6)/4 = 6.0$
- 属性1の偏差平方和
- $(2.0-3.5)^2+(4.0-3.5)^2+(6.0-3.5)^2+(2.0-3.5)^2= 11.0$
- 属性2の偏差平方和
- $(4.0-6.0)^2+(6.0-6.0)^2+(8.0-6.0)^2+(6.0-6.0)^2= 8.0$
- 属性1,2の偏差平方和
- (2.0-3.5)(4.0-6.0)+(4.0-3.5)(6.0-6.0)+(6.0-3.5)(8.0-6.0)+(2.0-3.5)(6.0-6.0)
- = 8.0
-
同類性係数
- $r = \frac{8.0}{\sqrt{11.0*8.0}} = 0.853$