社会ネットワーク理論の地図（執筆中）

*1
ここに供養するので、誰か役立ててください。

＃とは

とても簡単に言うと社会科学×グラフ理論。

一般的な社会科学のツールでは主体間で具体的にどのようなやり取りの関係が構築されているかを考慮できていませんが、それをノード（点）とエッジ（辺）で定義されるグラフで表現して分析を行ってみよう、というものです。

個々の主体に着目するという性質上、経済学ではミクロ、特にゲーム理論の応用で用いられる事が多いように思われます*2。

参考書等

色々あると思いますが、私はめんどくさくて必要になるまで教科書を全然読まないので入門書のおすすめは分かりません。

神ゼミで使用したJacksonのSocial and Economic Networksは入門としては若干重いのと、同じChapter内に知っておくべき知識と発展的な内容が混在している（順番も適当）ので体系的に学ぶ上では効率が悪いように感じます（決して悪く言うわけではなく、重要かつ有用なヒントがたくさん詰まっていると思います）。
※一時界隈で話題になったツイート：https://twitter.com/twcu16_no5/status/754485229771956224

ゲーム理論との組み合わせに関しては、同氏のGames on Networksが面白かったです。ただし繰り返しゲームや進化ゲームに関してはほとんど無です。

後述する複雑ネットワークに関しては、増田、今野の複雑ネットワーク―基礎から応用までが最適だと思います。

さくっとグラフ理論

知識を与えるというより、知識に関する知識を与えるという感じで行こうと思います。出てきたキーワードを各自調べていただければだいたい網羅できるのではないでしょうか。
後で読んでもなんとかなる内容は極力畳みます。
※参考：Jackson Chap.2, Chap.3

隣接行列

工学系の人がグラフをどういう文脈で扱うのかよくわかりませんが、社会ネットワーク論ではグラフの持つ数学的性質に興味がある場合がほとんどなので、基本的に隣接行列でグラフを表現します。
隣接行列というのは

$g=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$

のような形のもので*3、 $i$ 行 $j$ 列目の数字が $x$ だった場合、ノード（点） $i$ とノード $j$ の間に重み $x$ のエッジ（辺）が存在するということを意味しています。
隣接行列の性質を見ると、グラフの持つ基本的な性質がいろいろわかります。

クリックで展開

※ネットワークを　 $\lt N,g\gt$ ,　 $N$ はノードの集合,　 $g:n\times n$ は隣接行列　と定義する。

$g'=g$ のとき、 $g$ は無向グラフ。それ以外の場合は有向グラフ。
$\forall i,j \in N,g_{ij}=\{1,0\}$ のとき、 $g$ は重みなし。それ以外の場合は重みあり。
$g_{ii}\neq0$ のとき、 $i$ 間にセルフループが存在する。

※多くの場合、社会ネットワーク理論で対象とするグラフは「セルフループなし*4」「多重辺なし*5」「重みなし*6」「無向グラフ*7」という仮定が置かれる。

$g$ が重みなしグラフである場合、 $g^{k}$ の $ij$ 要素は $i$ から $j$ まで $k$ ステップで到達できる経路の数を示す。
$g$ が強連結（後述）であることと、 $g$ が既約であることは同値。
$g1$ の $i$ 番目の要素は $i$ の次数（後述）を表す（出次数。 $(1'g)'$ が入次数）。

ノードとエッジに関する知識もろもろ

適当に羅列しておくので必要な時に開いてください。
※ほとんどの項目でセルフループ/多重辺なしの重みなしネットワークを仮定しています

クリックで展開

次数

　あるノードの出（入）次数とはそのノードから（に）引かれるエッジの数で定義される。
　 $d^{out} = g1$ は出次数、 $d^{in}=(1'g)'$ は入次数のベクトルになる。

部分グラフ

　 $S \subset N$ に対して、 $g'$ を $g_{ij}' = 1\ if\ i,j \in N \land g_{ij}=1, 0\ otherwise$ と定めたものを部分グラフと呼ぶ。
　 $g'$ は $g$ に対して、 $i$ 行目と $i$ 列目を削除するという操作を $N\backslash S$ に含まれる全ての $i$ について行うことで得られる。

歩道、道、閉路

※語の定義が文献や言語によって異なる。ここではJacksonに倣う
　歩道（walk）とは、あるノードからあるノードまで連なるリンクを指す。
　道（経路, path）とは、歩道のうち同じノードが複数出現しないものを指す。
　閉道（閉路, cycle）とは、歩道のうち始点と終点が同じノードで、かつそれ以外のノードはすべて異なっているものを指す。

連結性

　無向グラフ $g$ が連結であるとは、全てのノード $i,j$ 間に道が存在することである。
　有効グラフ $g$ が強連結であることの定義は、無向グラフにおける連結の定義と同じ。
　有効グラフ $g$ が片方向連結であるとは、全てのノード $i,j$ に対して、 $i$ から $j$ への道または $j$ から $i$ への道が存在することである。
　有効グラフ $g$ が弱連結であるとは、全てのノード $i,j$ に対してあるノード $k$ が存在して、 $i$ から $k$ への道または $k$ から $i$ への道が存在し、かつ $j$ から $k$ への道または $k$ から $j$ への道が存在することである*8。

単純なグラフの構造

　木(tree)、円(circle)、星(star)、正則グラフ、完備グラフ(complete graph)など、グラフの構造によって名前がついている。しらべて

近傍

あるノードの近傍(neighbor)とは、そのノードと隣接している（間にエッジが存在する）ノードの集合である。

ノードの性質を調べる

視点の一つとして、個々のノードがネットワーク上でどのような立ち位置にあるかというものがあります。これを測る指標としては主に中心性になると思います。

ノードの中心性というのは、言葉の通りそのノードがネットワーク上の中心にいかに近いかを示すものです。
しかし何をもって「中心」とするのかによって、その定義は異なるものになります。
TJOのブログに個々の中心性指標の具体例と図が紹介されています。

※各項目をクリックで展開します

次数(degree)中心性↓

「より多くのノードと繋がっているノードこそ中心的である」という発想に由来するもので、次数に比例するのが次数中心性です。
多くの小さなノードと結びついているノードが高く評価される傾向にあります。

上で示した通り、 $d^{out} = g1$ は出次数、 $d^{in}=(1'g)'$ は入次数のベクトルになります。
このベクトルに $1'g1^{-1}$ （すべてのノードの次数の和の逆数）を掛けて基準化したものが次数中心性です。

媒介(betweeness)中心性↓

「他のノード同士を結ぶ路を仲介するノードこそ中心的である」という発想に由来する中心性です。
ノード $i$ の媒介中心性は、 $i$ 以外の異なる2つのノードを結ぶ最短経路の中から、 $i$ を含むものを全て数え上げたものに比例します。
Jacksonでは、
　 $C_{i}^{btw} = \sum_{j,k:i\neq j\neq k}\frac{\frac{P_{i}(jk)}{P(jk)}}{frac{(n-1)(n-2)}{2}}$
　 $P(jk)$ は $jk$ 間の最短経路の総数
　 $P_{i}(jk)$ は $jk$ 間の最短経路のうち $i$ を含むものの総数

と定義しています*9。

次数中心性と異なり、ノードの次数が低くても媒介中心性が非常に高くなるケースがあります。
分析でもしばしば用いられる指標ですが、隣接行列を使っている意味が殆どないので、媒介中心性と関連性のある面白い性質！みたいなのは生まれて来にくそうです。

近接中心性↓

「より多くのノードの近くにあるノードこそ中心的である」という発想に由来する中心性です。
他の全てのノードとの最短経路長の和の逆数に比例します。グラフが非連結の場合ちょっとした工夫が必要です。

あまり取り扱ったことはないです。

固有ベクトル中心性↓

「中心的なノードと隣接したノードは中心的である」という発想に由来する中心性です。
ノード $i$ の中心性を、 $i$ と隣接しているノードの中心性の和として表現します。

　 $C^{eig}=\lambda^{-1}gC^{eig}$ （ $\lambda$ は $g$ の固有値）

と定義することで、固有ベクトル中心性 $C^{eigen}$ は文字通り $g$ の固有ベクトルで表されます。
固有値は複数存在し得ますが、Perron-Frobeniusの定理より、

　- 既約な非負の実正方行列には、絶対値が最大の正の固有値 $\lambda$ （Perron根）がただ一つ存在する。
　- $\lambda$ に付随する固有ベクトルの要素はすべて正の実数である。

ということが保障されているため、Perron根を固有値として選ぶことで全ての要素が正の中心性を得られます。

しかし、上記の通りこの性質は非負行列が既約である場合にしか成立しません。上で紹介した通り隣接行列が既約であることはグラフが強連結であることと同値なので、固有ベクトル中心性は強連結グラフにしか適用できません。

冪中心性↓

固有ベクトル中心性の拡張の一つです。考案者の名前からKatz-Bonacich中心性と呼ばれます*10。
冪中心性のベクトルは、十分小さい $\phi$ を設定した（ $\lim_{k \to \infty}\phi^{k} g^{k} = 0$ が成り立つ）時、

　 $\begin{align}C^{KB} &= (\phi g+ \phi^{2}g^{2}+...)1\\ & = \phi g(I + \phi g+ \phi^{2}g^{2}+...)1\\ & = \phi g(I - \phi g)^{-1}1\\ (& = [(I - \phi g)^{-1}-I]1) \end{align}$

と定義されます。
$g^k$ が $k$ ステップのwalkの数を示していることから、ノード $i$ の冪中心性は $i$ を始点とする歩道の総数の加重和ということになります。

冪中心性は固有ベクトル中心性と異なり任意のネットワークに応用できるため、多くの分析において用いられています。
冪中心性を元にしたネットワークモデルも多数存在すると思います。

PageRank↓

Googleによる、Googleのための*11指標です。
こちらも固有ベクトル中心性の拡張と言えます。 $g$ の各列を各ノードの入次数の和で割ったもので置き換えた行列を $\hat{g}$ とすると、 $\hat{g}'$ に対して固有ベクトル中心性を計算したものがPageRankの最も基本的な形となります。

PageRankについてはLangville, MeyerのGoogle PageRankの数理―最強検索エンジンのランキング手法を求めて― が明るいと思われます*12。

その他

「新しい中心性考えたったｗｗｗｗｗｗ」系の論文はしばしばあるので、考え甲斐があるかもしれません（Ballester et al. 2006やQi et al. 2012等）。
但し「それいる？」という問いと常に戦う羽目になると思います。逆にそれをちゃんと指摘できればEconometricaに載るということではないでしょうか。

グラフ全体の性質を調べる

個々のノードに着目する以外に、ネットワーク全体がどのような性質を有しているかというものがあります。これに関しては考えることがたくさんあると思います。
※クリックで展開します

構造に関する諸々のパラメータ↓

次数分布

文字通りノードの次数がどのように分布しているかを示すものです。例えばk=2の正則グラフと星型グラフでは平均次数はどちらも2ですが、次数の分布は異なります。

次数相関

文字通り隣接するノードと自身の次数の相関がどれくらいあるかを示すものです。

クラスター係数

この文脈で「クラスター」とは「強連結な３つのノードの組」のことを指します*13。
クラスター係数 $Cl(g)$ は、「自分と隣接している２つの異なるノード同士も隣接している割合」のことで、

　　 $Cl(g)=\frac{\sum_{i,j,k:i\neq j,j\neq k, k\neq i}g_{ij}g_{jk}g_{ki}}{\sum_{i,j,k:i\neq j,j\neq k, k\neq i}g_{ij}g_{ik}}$

と表せます。
また、ノードごとのクラスター係数 $Cl_{i}(g)$ を

　　 $Cl_{i}(g)=\frac{\sum_{j,k:i\neq j,j\neq k, k\neq i}g_{ij}g_{jk}g_{ki}}{\sum_{j,k:i\neq j,j\neq k, k\neq i}g_{ij}g_{ik}}$

と定義し、ノードごとのクラスター係数の平均をとって平均クラスター係数として用いる場合もあります。

連結性

文字通りグラフが連結であるかどうかというものです。後述のランダムネットワークモデルでは連結性そのものをチェックする場合がありますが、大抵のネットワーク分析においては連結であった方が都合の良いことが多い*14ので、初めから連結性を仮定している場合があります*15。

ジャイアントコンポーネント

グラフが連結でない場合、当然グラフは複数のコンポーネント（連結成分）に分かれているということになります。
ジャイアントコンポーネントは*16、十分大きな*17 コンポーネントを指します。当然ながら、ジャイアントコンポーネントは存在するならば一つです。
グラフが連結でなくとも、ジャイアントコンポーネントが出現するかどうかがモデルにおいて重要な場合もあります。

平均経路長、直径

平均経路長はその名前の通り、全ての頂点間の距離の平均です。
直径は、全ての頂点間の距離の最大値です。

現実のネットワーク特有の性質↓

現実世界のネットワークでは、主に以下の３つの性質が成り立つと言われています。
Wikipediaの記述が分かりやすいかと思います。

スケールフリー性

次数分布がべき乗則である、という性質です。
次数 $c$ の割合と次数 $d$ の割合の比率が、 $k>0$ に関して次数 $kc$ と $kd$ の割合の比率と同じになるという点で「スケールフリー」と呼ばれています。

スモールワールド性

平均経路長がノードの数に比べて非常に小さい、という性質です。定義があいまいですが、概ね $n$ に対して平均経路長が高々 $log(n)$ に比例する場合、スモールワールド性を満たすと言われているようです。
簡単な例で言えば、Wikipediaの記事間のネットワークはスモールワールド性を満たしていると言えます。

クラスター性

クラスター係数が高い、という性質です。とても曖昧。

ネットワーク形成

アルゴリズムに基いてネットワークを生成するというものです。ランダムネットワークモデルが多いですが、ランダムでないモデルもあるにはあります。

Erdős–Rényi

最も原始的でシンプルなランダムネットワークモデルです。
$n$ 個のノード間全てのあり得るリンクが、それぞれ独立に確率 $p$ で張られるようなモデルを指します。
このランダムグラフの次数分布は二項分布の形を取るため、ポアソンネットワークと呼ばれる場合があります。
スモールワールド性を満たしますが、スケールフリー性やクラスター性は満たしません。

Watts–Strogatz

スモールワールド性に着目したランダムネットワークモデルです。
最初に全てのノードが近くのノードと隣接している格子状のネットワークを作り、その中のリンクを確率 $p$ で張り替える、という操作を行うことで、スモールワールド性を持ったグラフを形成することができる、というものです。
頻繁に紹介される割にあまり見かけないように感じます。明らかに使いにくいですね。

Barabási–Albert

最も有名と言っても過言ではないランダムネットワークモデルです。
上記の２種類と異なり、このモデルでは動的にネットワークを形成します。

毎期1つのノードが追加され、既存のノードのいくつかと繋がっていきます。
この時、既存のノードが新しいノードと繋がる確率がそのノードの次数に比例する、というのがBarabási–Albertのキモです（優先的選択と呼ばれる）。

このモデルによって作られるグラフはスケールフリー性を満たすという大変ありがたい性質があり、Barabási–Albertネットワークはしばしばスケールフリーネットワークと呼ばれます。
多くのネットワーク分析で用いられ、これ自身を発展させたモデルも多数存在します。
特に、このモデルはクラスター係数が0に近いという性質があるため、クラスター性を持たせる拡張をするというパターンが多いのではないでしょうか。

その他：戦略的ネットワーク形成

・各々のノードが戦略的にリンクを張るというモデルがいくつかあるかもしれないし、ないかもしれない。
Jackson Chap.6 を参照ください。

・他にもdeterministicなモデルのいくつかは増田今野を参照ください。

Applicationできそうなもの諸々

Diffusion

ネットワークでやりたいことと言えば情報拡散、みたいな所があるかもしれない。
Li et al. 2017が概観を知るには良いかもしれない。

Learning

「ネットワーク上のプレイヤーが」学習するという話。次の記事で取り上げます。

*1:あらゆる敬称を略しています。

*2:私は全くの専門外なので何も言えませんが、空間経済や都市経済のような分野でもあるんでしょうか。

*3:行列が小文字で表記されるのが気持ち悪いかもしれませんが、本記事ではJacksonに倣ってこう表記します。Gがグラフ全体の集合として使われる事があるからだと思います。

*4:セルフループが含まれるような状況があまり分析の対象に入らない

*5:隣接行列では多重辺を表現できない

*6:たぶんめんどくさいから

*7:同左、重みと有向性の仮定はしばしば弱められる

*8:たぶん間違ってはないと思いますが、これを定義としている文献が実際にあるかどうかはわかりません

*9:分母の(n-1)(n-2)/2はjとkの選び方の総数ですが、これで基準化しても中心性の和が1になりません。そもそも上だと重複許してるのに下だと許してないし、、輪読したときにどう解釈したか忘れました。

*10:Katzが考案し、Bonacichがより一般的に拡張しました。Katz中心性と呼ばれることが多いですが、Katzは別の中心性も考案しているため紛らわしいです。本記事では冪(power)中心性ないしKatz-Bonacich中心性と呼称していますが、取り上げているのはKatzのオリジナルのものです。

*11:"PageRankはGoogleの商標であり、またPageRankの処理は特許が取得されている" https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%A9%E3%83%B3%E3%82%AF

*12:読んだことないですが、同著者の別の本がとても良かったのでたぶんこれも良いのではないでしょうか

*13:クラスターという語は別の文脈で使われることもある。めんどくさい

*14:例えば上述の通り、固有ベクトル中心性は強連結グラフにしか適用できない

*15:連結でないノードはそもそもネットワークに含まれないとしても分析に大きな支障がないため

*16:definiteな定義がどうかはよく分からない

*17:教科書で用いられていたものではn^(2/3)以上のノードが含まれる

ぽへ

ぽへ