📢

【ネットワークの中心性】vol.1 Introduction

2023/09/08に公開

ネットワーク

ネットワーク分析

ネットワーク科学

tech

本連載について

以前ネットワーク分析に関する記事を書きました．

この記事ではネットワーク分析の雰囲気をつかむことを目的としていました．ですので，分析に使用したネットワークの中心性指標を完全にブラックボックス（NetworkX の関数を使用）として扱いました．もちろん，中身がわからなくてもコードを書いて実行すれば，コンピュータが各ノードの中心性をしっかり計算してくれます．ですが，中には「この計算結果はどういうロジックで出てきたのだろう？」とモヤモヤする方もいると思います．

また，実際の分析ではどういう意味で中心的なノードを見つけたいかを明確にした上で，その目的に適したアルゴリズムを選択する必要があります．したがって，各中心性指標の定義と特徴を理解しておくことは非常に重要です．そこで，本連載ではネットワークの中心性について，使用される数学にも触れながら記事を書いていきます．先に使用される数学を学んでから，その応用事例として各中心性を見ていきます．その際は【中心性指標の定義と特徴を確認→問題点（限界）を指摘→次の指標に拡張】という流れで進めていく予定です．以下，現時点での目次です．

本連載は自分の勉強のアウトプットでもあるので，間違いは遠慮なくご指摘いただけると助かります．
なお，各記事は Stachurski et al. (2022) をベースに作成しています．下記のリンクから無料でPDFをダウンロードできるので，気になった方は当たってみてください．
https://networks.quantecon.org/

Python による実装

本連載で取り上げる中心性はすでに NetworkX や graph-tool で実装されています．

ですが，自分で実装してみることで各中心性の理解は深まると思いますので，Python による実装も行います．各記事で実装する関数は次のとおりです．

第4回：次数中心性を計算するdegree_centrality()
第5回：固有ベクトル中心性を計算するeigenvector_centrality()
第6回：Katz 中心性を計算するkatz_centrality()
第7回：PageRankを計算するPageRank()

必要になる数学

ネットワークの中心性を考える上で必要になる数学は，ざっくり線形代数とグラフ理論です．行列とネットワークは表裏一体の関係にあるので，ネットワークを扱おうとするとどうしても線形代数が必要になるわけです．中心性においては特に，ノイマン級数の補題 (Neumann series lemma) とペロン＝フロベニウスの定理 (Perron–Frobenius theorem) が重要な役割を果たします．

初回はここまでにして，最後に本連載で使用する数式の表記一覧を記載しておきます．次回は，固有値・固有ベクトルの定義を確認し，上述の補題や定理の主張を確認します．

数学記法

本連載で使用する記号・記法の一覧です．

表記	意味
$\N$	自然数全体の集合
$\Z$	整数全体の集合
$\R$	実数全体の集合
$\Complex$	複素数全体の集合
$\R_+$	非負の実数全体の集合
$\R_{++}$	正の実数全体の集合
$\| B\|$	集合 $B$ の要素数
$\mathbb{M}^{m \times n}$	$m \times n$ 行列全体の集合
$\left< \bm{u}, \bm{v} \right>$	$\bm{u}$ と $\bm{v}$ の内積
$I$	単位行列
$\text{diag}(a_1,\dots,a_n)$	主対角線に $a_1,\dots,a_n$ が並んだ対角行列
$\bm{1}$	全ての要素が1のベクトル
$\bm{1}\{P\}$	指示関数；命題 $P$ が真なら $1$ ，偽なら $0$ ．
$A^\top$	行列 $A$ の転置行列
$\sigma(A)$	行列 $A$ の全ての固有値からなる集合
$\rho(A)$	行列 $A$ のスペクトル半径
$V$	ノードの集合
$E$	エッジの集合
$N_G(i)$	無向グラフ $G$ におけるノード $i$ の近傍の集合
$N_G^{\text{in}}(i)$	有向グラフ $G$ におけるノード $i$ の入近傍の集合
$N_G^{\text{out}}(i)$	有向グラフ $G$ におけるノード $i$ の出近傍の集合

参考文献

John Stachurski and Thomas J. Sargent. Economic Networks: Theory and Computation (QuantEcon, 2022). URL https://networks.quantecon.org/ .