【ネットワークの中心性】vol.3 グラフ理論
シリーズの目次
ネットワークとグラフ理論
この記事では,ネットワークの中心性を考える上で登場する諸概念に言葉を与えるグラフ理論 (Graph Theory) を見ていきます.グラフ理論は,18世紀の卓越した数学者レオンハルト・オイラー (Leonhard Euler) による一筆書き問題(ケーニヒスベルクの橋)に起源を持つとされています.筆者の理解では,グラフ理論はネットワーク分析(ネットワーク科学)の数学的な基礎になっています.ただし,グラフ理論が新たな問題の発見やその証明に重きを置くのに対して,ネットワーク科学は現実に観察されるさまざまな現象を分析し,応用するという物理学的・工学的な性格が強いように思います[1].
ネットワークとグラフの違い
世の中に「ネットワーク」という言葉はありふれていますが,その意味するところは様々です.人や組織のつながりを表すこともあれば,交通網や流通網などのインフラを指すこともあります.今の世の中を技術的に支えているインターネットは,多くの人にとって最も身近な例かもしれません.
これらに共通しているのは,いずれも何らかの要素が何らかの関係でつながっているということです.これらの要素や要素同士の関係が具体的に何を表しているかを問うことをやめ,要素間のつながりという構造だけを抜き出して抽象化したオブジェクトを数学的に調べるのがグラフ理論です.ですから,「グラフ」という言葉には純粋に数学的な対象というニュアンスがあります.それに対して,「ネットワーク」という言葉は現実のシステムを指し示すのに用いられ,ある程度の具体性を伴います.たとえば,"facebook のユーザーネットワーク"や"タンパク質の相互作用ネットワーク"などです.
この違いから,ネットワーク科学とグラフ理論の用語にも違いがあります[2].
ネットワーク科学 | グラフ理論 |
---|---|
ネットワーク | グラフ |
ノード(node) | 頂点(vertex) |
リンク(link) | 枝・辺・エッジ(edge) |
とはいえ,実際には厳密に使い分けられているというよりは,人によって使いやすいものを使用している印象です.ノード,エッジというように混ぜて使うケース(NetworkX とか)も見かけます.ネットワークとグラフについても,実際には同一のものを指しているので,ほぼ同義語として使われている印象があります.ただ前述のような抽象性の違いはあって,具体的な対象を特定しない場合には主に「グラフ」という語を使い,具体的な特定のネットワークを指す場合には「ネットワーク」という用語が使われる,という感じです.
グラフの定義
グラフ (graph) とは集合
図1:無向グラフ(左)と有向グラフ(右)
出所)Menczer et al. (2020)
ノードの特徴を表す用語
無向グラフにおいて,あるノードのペアが1本のエッジで直接つながっているとき,これら2つのノードは互いに隣接 (adjacent) しているといいます.隣接する異なる2つのノードに対して,片方はもう一方の近傍 (neighbour) であるといいます.グラフ
図2:有向グラフのエッジ
有向グラフになると話が少しややこしくなります.図2にあるように,エッジ
ネットワークの構造を表す用語
無向グラフにおいて,エッジに沿ってノードをたどったときのノードの並び(列)のことを歩道 (walk) といいます.歩道内の連続したノードのペアはグラフのエッジになっています.歩道は同じノードあるいはエッジを何回通っても良く,重複も含めて通るエッジの数を歩道の長さ (length) といいます.歩道の中で通るノードあるいはエッジがすべて異なるものをパス (path) といいます.パスの長さは通るエッジの数で定義されます.グラフのどの2つのノードについても,それらを結ぶ歩道が存在するとき,グラフは連結 (connected) であるといいます.
有向グラフに対しては少し異なる定義が必要です.有向歩道 (directed walk) とは,有向辺に沿ったノードの列のことで,同じノードあるいは同じ有向辺を何回通っても構いません.重複も含めて通る有向辺の数を有向歩道の長さといいます.有向パス (directed path) とは,通るノードがすべて異なる有向歩道のことです.有向パスの長さは通るエッジの数で定義されます.有向グラフにおいて,どのノードからどのノードへも有向辺に沿って移動できるとき,その有向グラフは強連結 (strongly connected) であるといいます.
図3:無向グラフ(左)においてグラフ全体は連結でないが,水色のノードからなるネットワークは連結している.有向グラフ(右)も同様に,グラフ全体は強連結でないが,濃い青色のノードからなるネットワークは強連結である.
出所)Menczer et al. (2020)
隣接行列
ネットワーク(グラフ)と行列が表裏一体の関係であることは,すでに前回簡単に述べました.任意のネットワークは隣接行列 (adjacency matrix) と呼ばれる行列を用いて記述することができます.まずは無向グラフの隣接行列について説明します.
無向グラフ
有向グラフにおいては,ノード
図4:無向グラフの隣接行列(左)と有向グラフの隣接行列(右)
出所)Menczer et al. (2020)
図4からわかるように,隣接行列でネットワークを記述する際は,ノードは常にラベル付けされている必要があります.隣接行列はどのノードとどのノードがつながっているかという情報を格納した行列なので,注目するノードのラベル
本連載では簡単化のため,エッジに重みのついた重み付きネットワーク (weighted network) は基本的に扱いません[4].重み付きネットワークの例としては,2国間の取引額がエッジに割り当てられた国際貿易ネットワークや遷移確率がエッジに割り当てられる World Wide Web (WWW) のネットワークなどが考えられます.重み付きネットワークでは,重みを考慮した次数を考えることができますが,これを重み付き次数 (weighted degree) あるいは強度 (strength) といいます[5].
A^k が意味するもの
隣接行列のべき乗 前回の線形代数の記事で,行列が対角化できるとべき乗が楽に計算できて嬉しいというお話をしました.ところで,隣接行列は
であり,たとえば
となります.
では,このようにして計算できる隣接行列のべき乗はネットワーク的には何を意味しているのでしょうか.まず,
証明
砕けた表現を使うと,隣接行列のべき乗
次に,
有向であれ無向であれ,ノード
となります.同様に,ノード
です.これを任意の長さ
となります.厳密な証明は Newman(2018) のp.132を参照してください.
以上をまとめると,隣接行列のべき乗
隣接行列とネットワークの構造
前回の記事で,行列の分類を紹介しました.非負行列や正行列,行列の既約性などです.ネットワークを表現する隣接行列が,これらのクラスに分類されるとき,ネットワークの様子がどうなっているかを確認します.隣接行列
であることでした.隣接行列の要素がゼロであることを許容するということなので,これはまさに現実のネットワークそのものです.ネットワーク上でつながっている人もいれば,つながっていない人もいるのは普通のことです.
これに対して極端なネットワークも存在します.隣接行列
であることですが,これはつまり自己ループも含めてノードが他のすべてのノードとつながっている完全グラフ (complete graph) であることを意味します.
行列が既約 (irreducible) であるとは,非負行列
証明
次回予告
本記事では,ネットワークの中心性を考える上で必要になるグラフ理論の知識をまとめました.ネットワークは行列で表現され,行列の演算がネットワーク的にはどういう意味を持つのか,行列の性質がネットワークの構造にどのように影響しているのかを議論しました.次回以降でここまで学んだことが活きてくるので,応用に興味がある方はぜひご覧になってください.間違いや誤植などがあれば,ご連絡いただけると幸いです.
次回は,ネットワークの中心性の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} -
本連載で直接重み付きネットワークを扱うことはありませんが,固有ベクトル中心性の回で説明のため便宜上重みを導入している部分があります. ↩︎
Discussion