🌉

【ネットワークの中心性】vol.3 グラフ理論

2023/09/14に公開

math

シリーズの目次

ネットワークとグラフ理論

この記事では，ネットワークの中心性を考える上で登場する諸概念に言葉を与えるグラフ理論 (Graph Theory) を見ていきます．グラフ理論は，18世紀の卓越した数学者レオンハルト・オイラー (Leonhard Euler) による一筆書き問題（ケーニヒスベルクの橋）に起源を持つとされています．筆者の理解では，グラフ理論はネットワーク分析（ネットワーク科学）の数学的な基礎になっています．ただし，グラフ理論が新たな問題の発見やその証明に重きを置くのに対して，ネットワーク科学は現実に観察されるさまざまな現象を分析し，応用するという物理学的・工学的な性格が強いように思います^[1]．

ネットワークとグラフの違い

世の中に「ネットワーク」という言葉はありふれていますが，その意味するところは様々です．人や組織のつながりを表すこともあれば，交通網や流通網などのインフラを指すこともあります．今の世の中を技術的に支えているインターネットは，多くの人にとって最も身近な例かもしれません．

これらに共通しているのは，いずれも何らかの要素が何らかの関係でつながっているということです．これらの要素や要素同士の関係が具体的に何を表しているかを問うことをやめ，要素間のつながりという構造だけを抜き出して抽象化したオブジェクトを数学的に調べるのがグラフ理論です．ですから，「グラフ」という言葉には純粋に数学的な対象というニュアンスがあります．それに対して，「ネットワーク」という言葉は現実のシステムを指し示すのに用いられ，ある程度の具体性を伴います．たとえば，"facebook のユーザーネットワーク"や"タンパク質の相互作用ネットワーク"などです．

この違いから，ネットワーク科学とグラフ理論の用語にも違いがあります^[2]．

ネットワーク科学	グラフ理論
ネットワーク	グラフ
ノード(node)	頂点（vertex）
リンク(link)	枝・辺・エッジ（edge）

とはいえ，実際には厳密に使い分けられているというよりは，人によって使いやすいものを使用している印象です．ノード，エッジというように混ぜて使うケース（NetworkX とか）も見かけます．ネットワークとグラフについても，実際には同一のものを指しているので，ほぼ同義語として使われている印象があります．ただ前述のような抽象性の違いはあって，具体的な対象を特定しない場合には主に「グラフ」という語を使い，具体的な特定のネットワークを指す場合には「ネットワーク」という用語が使われる，という感じです．

グラフの定義

グラフ (graph) とは集合 $V$ と $E$ の組 $G(V,E)$ です． $V$ は非空の有限集合で， $E$ は直積集合 $V\times V$ の部分集合です． $V$ の要素はノード (node) や頂点 (vertex) などと呼ばれ， $E$ の要素をエッジ (edge) やリンク (link) などといいます．エッジ $(u,v) \in E$ の存在はノード $u$ と $v$ がつながっていることを意味しますが，ここでエッジの方向性を問うかどうかでグラフを区別することができます．すなわち，エッジがノード $u$ から $v$ に向かって張られている場合，エッジ $(u,v)$ 内の要素の順番が方向を表します．エッジが順序対 $(u,v)$ であるということです．向きのあるエッジ（有向辺）とノードからなるネットワークを有向グラフ (directed graph, digraph) といい，向きのないエッジ（無向辺）とノードからなるネットワークを無向グラフ (undirected graph) といいます．無向グラフにおいては，エッジ $(u,v)$ の要素の順番は問題にならず，エッジはただのノードの組み合わせ $\{u,v\}$ を表します^[3]．

図1：無向グラフ（左）と有向グラフ（右）
出所）Menczer et al. (2020)

ノードの特徴を表す用語

無向グラフにおいて，あるノードのペアが1本のエッジで直接つながっているとき，これら2つのノードは互いに隣接 (adjacent) しているといいます．隣接する異なる2つのノードに対して，片方はもう一方の近傍 (neighbour) であるといいます．グラフ $G$ におけるノード $v$ の近傍の集合を $N_G(v)$ と表記すると，ノード $v$ の次数 (degree) $k_v$ とは， $v$ に隣接するノードの数 $|N_G(v)|$ です．

図2：有向グラフのエッジ

有向グラフになると話が少しややこしくなります．図2にあるように，エッジ $(u,v)$ において $u$ を始点 (tail)， $v$ を終点 (head) と呼んで区別します．また，ノード同士の関係性に注目して， $u$ を $v$ の predecessor あるいは入近傍 (in-neighbor) と呼び， $v$ を $u$ の successor あるいは出近傍 (out-neighbor) と呼びます． $v$ の入近傍の集合を $N_G^{\text{in}}(v)$ ， $v$ の出近傍の集合を $N_G^{\text{out}}(v)$ と表記すると， $v$ の入次数 (in-degree) $k_v^{\text{in}}$ とは $v$ の入近傍の数 $|N_G^{\text{in}}(v)|$ であり，出次数 (out-degree) $k_v^{\text{out}}$ とは $v$ の出近傍の数 $|N_G^{\text{out}}(v)|$ です． $u$ のように入次数が $0$ であるノードはソース (source) と呼ばれ， $v$ のように出次数が $0$ であるノードはシンク (sink) と呼ばれます．

ネットワークの構造を表す用語

無向グラフにおいて，エッジに沿ってノードをたどったときのノードの並び（列）のことを歩道 (walk) といいます．歩道内の連続したノードのペアはグラフのエッジになっています．歩道は同じノードあるいはエッジを何回通っても良く，重複も含めて通るエッジの数を歩道の長さ (length) といいます．歩道の中で通るノードあるいはエッジがすべて異なるものをパス (path) といいます．パスの長さは通るエッジの数で定義されます．グラフのどの2つのノードについても，それらを結ぶ歩道が存在するとき，グラフは連結 (connected) であるといいます．

有向グラフに対しては少し異なる定義が必要です．有向歩道 (directed walk) とは，有向辺に沿ったノードの列のことで，同じノードあるいは同じ有向辺を何回通っても構いません．重複も含めて通る有向辺の数を有向歩道の長さといいます．有向パス (directed path) とは，通るノードがすべて異なる有向歩道のことです．有向パスの長さは通るエッジの数で定義されます．有向グラフにおいて，どのノードからどのノードへも有向辺に沿って移動できるとき，その有向グラフは強連結 (strongly connected) であるといいます．

図3：無向グラフ（左）においてグラフ全体は連結でないが，水色のノードからなるネットワークは連結している．有向グラフ（右）も同様に，グラフ全体は強連結でないが，濃い青色のノードからなるネットワークは強連結である．
出所）Menczer et al. (2020)

隣接行列

ネットワーク（グラフ）と行列が表裏一体の関係であることは，すでに前回簡単に述べました．任意のネットワークは隣接行列 (adjacency matrix) と呼ばれる行列を用いて記述することができます．まずは無向グラフの隣接行列について説明します．

無向グラフ $G(V,E),~|V|=n$ の隣接行列 $A = \left(a_{ij}\right)_{n \times n}$ は， $i$ 番目のノードと $j$ 番目のノードが隣接しているとき $a_{ij} = 1$ ，そうでない場合には $a_{ij} = 0$ の値をとります．ノードが自分自身とつながることを自己ループ (self loop) といいますが，自己ループのないネットワークにおいては対角要素 $a_{ii}$ は常にゼロです．無向グラフではノード $i$ が $j$ に隣接することとノード $j$ が $i$ に隣接することを区別しないので，隣接行列は対称行列（ $a_{ij} = a_{ji}$ ）になります．

有向グラフにおいては，ノード $i$ から $j$ に向かうエッジとノード $j$ から $i$ に向かうエッジを区別する必要があります．したがって，隣接行列 $A = \left(a_{ij}\right)_{n \times n}$ は，ノード $i$ から $j$ に向かうエッジ（有向辺）がある場合は $a_{ij} = 1$ ，そうでない場合には $a_{ij} = 0$ の値をとります．ノード間のつながりに非対称性があるので，隣接行列は対称行列ではなくなります．

図4：無向グラフの隣接行列（左）と有向グラフの隣接行列（右）
出所）Menczer et al. (2020)

図4からわかるように，隣接行列でネットワークを記述する際は，ノードは常にラベル付けされている必要があります．隣接行列はどのノードとどのノードがつながっているかという情報を格納した行列なので，注目するノードのラベル $i,j$ と行列の要素の添え字（ $a_{ij}$ ）が一致していなければなりません．

本連載では簡単化のため，エッジに重みのついた重み付きネットワーク (weighted network) は基本的に扱いません^[4]．重み付きネットワークの例としては，2国間の取引額がエッジに割り当てられた国際貿易ネットワークや遷移確率がエッジに割り当てられる World Wide Web (WWW) のネットワークなどが考えられます．重み付きネットワークでは，重みを考慮した次数を考えることができますが，これを重み付き次数 (weighted degree) あるいは強度 (strength) といいます^[5]．

隣接行列のべき乗 $A^k$ が意味するもの

前回の線形代数の記事で，行列が対角化できるとべき乗が楽に計算できて嬉しいというお話をしました．ところで，隣接行列は $n \times n$ の正方行列なので，もちろんべき乗が定義できます．実際， $\left(A^k\right)_{ij}$ を $A^k$ の $(i,j)$ 成分とし， $\left(A^k\right)_{ij} = a_{ij}^k$ とすれば，行列の積の演算規則より

\left(A^{s+t}\right)_{ij} = \left(A^sA^t\right)_{ij} = \sum_{\ell=1}^n \left(A^s\right)_{i\ell} \left(A^t\right)_{\ell j} = \sum_{\ell=1}^n a_{i\ell}^s a_{\ell j}^t

であり，たとえば $s=t=1$ では

\left(A^2\right)_{ij} = a_{ij}^2 = \sum_{\ell=1}^n a_{i\ell}a_{\ell j}

となります．

では，このようにして計算できる隣接行列のべき乗はネットワーク的には何を意味しているのでしょうか．まず， $\left(A^k\right)_{ij}$ が非ゼロであるとき何が言えるかを考えます． $G$ を隣接行列 $A \in \mathbb{M}^{n \times n}$ で表される有向グラフとします．相異なるノード $i$ と $j$ ，自然数 $k$ について $\left(A^k\right)_{ij} = a_{ij}^k > 0$ であることと，有向グラフ $G$ においてノード $i$ から $j$ に向かう長さ $k$ の有向歩道が存在することは同値です．つまり，

a_{ij}^k > 0 \iff \text{there exists a directed walk of length } k \text{ from } i \text{ to } j.

証明

$(\impliedby)$ 帰納法で示す． $k=1$ のときは定義より成立． $(\impliedby)$ が $k-1$ の時成り立つと仮定し，ノード $i$ から $j$ に向かう長さ $k$ の有向歩道 $(i,\ell,\dots,m,j)$ を考える．仮定からノード $i$ から $m$ に向かう長さ $k-1$ の有向歩道が存在するとき， $a_{im}^{k-1} > 0$ である．いま $(m,j)$ は歩道の一部であるから $a_{mj}>0$ ．よって， $a_{ij}^k = \sum_{m=1}^n a_{im}^{k-1}a_{mj} > 0$ ．

$(\implies)$ 帰納法で示す． $k=1$ のときは定義より成立． $(\implies)$ が $k-1$ の時成り立つと仮定すると， $a_{im}^{k-1}>0$ のときノード $i$ から $m$ に向かう長さ $k-1$ の有向歩道 $(i,\ell,\dots,m)$ が存在する． $a_{ij}^k = \sum_{m=1}^n a_{im}^{k-1}a_{mj} > 0$ を考える． $a_{mj} = 0~\forall m$ を仮定すると， $a_{ij}^k = 0$ となり $a_{ij}^k > 0$ に反する．よって， $a_{mj} > 0$ となる $m$ が存在する．したがって，エッジ $(m,j)$ が存在し，ノード $i$ から $j$ に向かう長さ $k$ の有向歩道 $(i,\ell,\dots,m,j)$ が存在する．

砕けた表現を使うと，隣接行列のべき乗 $A^k$ の $(i,j)$ 成分が正であるとき，ノード $i$ から $j$ までエッジの方向に沿って $k$ ステップで移動できるということです．（「 $k$ ステップで移動できる」とは，ノード $i$ から $j$ に移動するとき $k$ 本のエッジを通るという意味です．）

次に， $a_{ij}^k$ の値そのものが何を表しているかを考えます．

有向であれ無向であれ，ノード $i$ から $j$ に向かうエッジ $(i,j)$ があれば $a_{ij} = 1$ です．よって，ノード $i$ から $m$ を経由して $j$ に至る長さ $2$ の（有向）歩道があるとき， $a_{im}a_{mj} = 1$ が成立します．したがって，ノード $i$ から $j$ に至る長さ $2$ の（有向）歩道の数 $N_{i\to j}^{(2)}$ は，

N_{i\to j}^{(2)} = \sum_{m=1}^n a_{im}a_{mj} = \left(A^2\right)_{ij}

となります．同様に，ノード $i$ から $\ell$ と $m$ を経由して $j$ に至る長さ $3$ の（有向）歩道が存在するとき $a_{i\ell}a_{\ell m}a_{mj} = 1$ 　であり，その（有向）歩道の数は

N_{i\to j}^{(3)} = \sum_\ell\sum_m a_{i\ell}a_{\ell m}a_{mj} = \left(A^3\right)_{ij}

です．これを任意の長さ $k$ を持つ（有向）歩道に一般化すると

N_{i\to j}^{(k)} = \left(A^k\right)_{ij}

となります．厳密な証明は Newman(2018) のp.132を参照してください．

以上をまとめると，隣接行列のべき乗 $A^k$ の $(i,j)$ 成分 $\left(A^k\right)_{ij} = a_{ij}^k$ が正であれば，ノード $i$ から $j$ に至る長さ $k$ の（有向）歩道が存在し，その数 $N_{i\to j}^{(k)}$ は $a_{ij}^k$ で与えられるということです．

隣接行列とネットワークの構造

前回の記事で，行列の分類を紹介しました．非負行列や正行列，行列の既約性などです．ネットワークを表現する隣接行列が，これらのクラスに分類されるとき，ネットワークの様子がどうなっているかを確認します．隣接行列 $A \in \mathbb{M}^{n\times n}$ が非負行列であるとは，

A \geqslant O \iff a_{ij} \geqslant 0~~\forall i,j

であることでした．隣接行列の要素がゼロであることを許容するということなので，これはまさに現実のネットワークそのものです．ネットワーク上でつながっている人もいれば，つながっていない人もいるのは普通のことです．

これに対して極端なネットワークも存在します．隣接行列 $A$ が正行列であるとは

A \gg O \iff a_{ij} > 0~~\forall i,j

であることですが，これはつまり自己ループも含めてノードが他のすべてのノードとつながっている完全グラフ (complete graph) であることを意味します． $\mathbb{X}$ （旧 Twitter）上のすべてのユーザーとつながっていることは，まずあり得ないでしょう．現実のネットワークは，同じノード数の完全グラフに比べて，ごくわずかのエッジ数しかもちません．現実のネットワークはスパースであるということです．

行列が既約 (irreducible) であるとは，非負行列 $A \geqslant O$ について， $\sum_{m=0}^\infty A^m \gg O$ が成り立つことを言うのでした．無向グラフの場合，隣接行列が既約であるための必要十分条件はグラフが連結であることです．有向グラフの場合はグラフが強連結であることと同値です．いずれも任意のノードの間に（有向）歩道が存在することから示すことができます．ここでは有向グラフの場合を示します．

証明

$A$ を有向グラフ $G(V,E)$ の隣接行列だとする．

\begin{align*} G\text{ is strongly connected.} &\iff \forall i,j \in V,~~\exists k \in \N~~\text{s.t.}~~\left(A^k\right)_{ij} = a_{ij}^k > 0. \\ &\iff \sum_{m=0}^\infty A^m \gg O. \\ &\iff A\text{ irreducible} \end{align*}

次回予告

本記事では，ネットワークの中心性を考える上で必要になるグラフ理論の知識をまとめました．ネットワークは行列で表現され，行列の演算がネットワーク的にはどういう意味を持つのか，行列の性質がネットワークの構造にどのように影響しているのかを議論しました．次回以降でここまで学んだことが活きてくるので，応用に興味がある方はぜひご覧になってください．間違いや誤植などがあれば，ご連絡いただけると幸いです．

次回は，ネットワークの中心性の2つの考え方と，最も素朴な中心性である次数中心性を取り上げる予定です．

参考文献

Barabási, A.-L. Network science (Cambridge University Press, 2016). URL http://barabasi.com/networksciencebook/.
John Stachurski and Thomas J. Sargent. Economic Networks: Theory and Computation (QuantEcon, 2022). URL https://networks.quantecon.org/ .
Menczer, F., Fortunato, S. & Davis, C. A. A First Course in Network Science (Cambridge University Press, 2020). URL https://cambridgeuniversitypress.github.io/FirstCourseNetworkScience/.
Newman, M. (2018). Networks. Oxford university press.
小林みどり(2021)『よくわかる！グラフ理論入門』，共立出版
J.A.ボンディ, U.S.R.マーティ（2022）『グラフ理論』山下登茂紀, 千葉周也（訳），丸善出版

脚注

たとえば，生成されるネットワークがスケールフリー性を持つBAモデルは，本来離散である次数を連続体近似してモデルを展開するところに精神性の違いが現れています． ↩︎
表は Barabási(2016) を参考に作成しました． ↩︎
一般に，順序を問題にする際は $(,)$ を用い，順序を問わない場合は $\{,\}$ を用います ↩︎
拡張自体は簡単で，エッジ $(i,j)$ に重み $w_{ij}$ があるとき，隣接行列では $a_{ij} = w_{ij}$ となります． ↩︎
本連載で直接重み付きネットワークを扱うことはありませんが，固有ベクトル中心性の回で説明のため便宜上重みを導入している部分があります． ↩︎