ネットワーク理論

ネットワーク理論︵ネットワークりろん︶は、通信、コンピュータ、生物、ソーシャルなどの複雑ネットワークを研究する分野。ネットワークは、ノードやエッジが属性︵例‥名前︶を持つグラフとして定義される。数学のグラフ理論、物理学の統計力学、コンピュータサイエンスのデータマイニングと情報視覚化、統計からの推論モデリング、社会学の社会構造などの理論や手法が使われる。

インターネットのネットワーク

ネットワークの例

概論・歴史

七つの橋の問題。

ネットワーク理論は、複雑なデータを解析する手段としてさまざまな分野で言及される。この理論の最初期の論文は、1736年にレオンハルト・オイラーによって書かれた有名な﹁七つの橋﹂の問題である。オイラーの頂点と辺による数学的証明はグラフ理論の基礎となった。グラフ理論は発展して化学に応用された。
 

小学一年生のソシオグラム。

1930年代、伝統的なゲシュタルト派の心理学者ヤコブ・モレノはアメリカで社会学を発展させ、1933年4月にソシオグラムを医療学者の会で発表した。モレノは﹁ソシオグラムの出現以前はあるグループでの対人関係の構造が正確にどのようなものか、誰も分かりませんでした。﹂と発表した。ソシオグラムの例が左の図で、小学1年生の社会的構造の表象である。男子と女子はそれぞれ同性が友達だったが、例外の1人の男子が女子を好きだと言ったが、相互的な関係ではないことが分かる︵図を参照︶。ソシオグラムは多くの用途を見出しており、社会ネットワーク解析という分野に発展している。

ネットワーク理論における確率論は、ポール・エルドシュとアルフレッド・レニーのランダムグラフに関する8つの有名なグラフ理論の論文から派生した。社会的ネットワークの場合は指数ランダムグラフのモデル︵p*︶がネットワークで発生する関係の確率空間を表すために使われる。ネットワーク確率論に対する別のアプローチは確率マトリックスである。確率マトリックスは、ネットワークのサンプルに見られるエッジの過去の有無に基づいて、ネットワーク全体に発生するエッジの確率をモデルにする。

1998年にデイビッド・クラックハートとキャサリン・カーリーは、PCANSモデルを用いたメタネットワークの概念を発表し、すべての組織は3つのドメイン‥個人・タスク・リソースから構成されるとした。該当の論文によると、ネットワークは複数のドメインにまたがって発生し、相互に関連する。この分野は、ダイナミックネットワーク解析と呼ばれる分野に発展した。

最近の動向としては、ネットワーク理論を使って位相幾何学を数学的に表す取り組みが注目を浴びている。ダンカン・ワッツは、数学的表現を持つネットワーク上で実験データを使ってスモールワールド現象を発表した。バラバーシ・アルベルト・ラースローとレカ・アルベルトは、スケールフリーのネットワークを実現させた。これは多数の接続を持つハブ頂点を含む広義のネットワークトポロジーであり、他のすべてのノードと接続の数の比率が一定に保たれるように成長する。インターネットなどの多くのネットワークはこの側面を維持しているように見えるが、他のネットワークではこの比率はノードの長いテール分布に近似する。

プロパティ

多くのネットワークには、その特性の解析に使われる性質がある。 これらの特性（プロパティ）は多くの場合、ネットワークモデルを定義することで特定のモデルとの対比の解析に使われる。 ネットワーク科学で使われる用語の定義の多くは、グラフ理論でも使われる。

密度

ネットワークの密度$D$ は、二項係数${\tbinom {N}{2}}$ によって得られる、可能なすべての辺の数に対する辺の数$E$ の比率として定義される‥$D={\frac {2E}{N(N-1)}}$ 。もう1つの表し方として、$T$ が単方向性である場合は以下のように表せる ‥$D={\frac {T}{N(N-1)}}$ 。この方法では、関係が単方向であるため測定が可能である。

大きさ

ネットワークの大きさは、ノード$N$の数か、もしくは（一般的ではないが）エッジ$E$の数で表す。エッジ$E$の数は $N-1$ (木) から $E_{\max }$ (完全グラフ)までさまざまである。

平均次数

ノードの次数$k$ とは、そのノードに接続している辺の数である。 ネットワークの密度にも密接に関連する平均次数は、$\langle k\rangle ={\tfrac {2E}{N}}$ である。ERランダムグラフモデルでは、$\langle k\rangle =p(N-1)$  を計算できる。ここでは、$p$ は2つのノードが繋がっている確率である。

平均距離

平均距離（Average path length）は、すべてのノードのペア間の最短距離を見つけて加算し、ペアの総数で割ることで算出される。 これは、ネットワークのあるノードから別のノードに到達するまでの平均のステップの数を表している。

直径

ネットワークを測定する別の手段として直径が使われる。ネットワークの直径は、ネットワーク内の最短距離のうち最も長いものとして定義される。 これは、ネットワーク内の最も離れた2つのノード間の最短距離となる。 言い換えれば、各ノードから他のすべてのノードまでの最短距離を計算すると、直径はすべての距離のうち最も長いものとなる。 直径は、ネットワークの線形的な大きさを表す。

クラスター係数

「複雑ネットワーク#クラスター性」も参照

クラスター係数とは、﹁all-my-friends-know-each-other︵すべての友達が互いを知っている︶﹂特性を表す。 ﹁友人の友人は友人である﹂とも表現される。 ノードのクラスター係数とは、ノードが近隣のノードと互いに実際に存在しているリンクと、可能なリンクの最大数の比率である。 ネットワーク全体でのクラスタ係数は、全ノードのクラスター係数の平均である。 ネットワークのクラスター係数が高いことは、スモール・ワールドであることの指標でもある。$i$ 番目のノードのクラスター係数は$C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,$ と表される。ここでは、$k_{i}$ は$i$ 番目のノードの隣人の数であり、${\textstyle e_{i}}$ はこれらの隣人間のリンクの数である。 隣人間の可能なリンクの最大数は以下のように表される‥${\binom {k}{2}}={{k(k-1)} \over 2}\,$ 

関連性

ネットワークがどのようにリンクされているかは、解析の解釈の上で重要である。 ネットワークは以下の4つのカテゴリに分類される。

• Clique/Complete Graph（完全グラフ）：完全にリンクされたネットワークで、すべてのノードが他のすべてのノードにリンクしている。この場合、すべてのノードが他のノードからの入り口と出口を有する点で対称的である。
• Giant Component（大きいコンポーネント）：ネットワーク内のほとんどのノードとリンクしている一つのノード。
• Weakly Connected Component（弱い関連性を持つコンポーネント）：エッジの方向性を無視した場合に、どのノードからも他のノードへの道が存在する。
• Strongly Connected Component（強い関連性を持つコンポーネント）：どのノードからも他のノードへの直接の道が存在する。

ノードの中心性

中心性の指数は、ネットワークモデルにおいて最も重要なノードを特定するために使われる。中心性の指数で割り出される﹁重要度﹂とはネットワークによって意味が異なる。 例えば、中間中心性では、他の多くのノード間にブリッジを形成するノードを非常に重要とみなす。また、固有値の中心性は、他の多くの重要なノードがそれにリンクしている場合に重要とみなされる。 このように重要度の定義は数多くの文献で言及されている。中心性指数は、最も重要なノードを識別するためにのみ適用が可能であり、他のノード部分では無意味な場合がほとんどである。例えば、2つの別々のコミュニティがあり、互いとのリンクはそれぞれの最も若いメンバー同士にしかないとする。すると、1つのコミュニティからもう1つのコミュニティへの移行するには必ずこのリンクを経由しなければならないので、2人の若いメンバーは高い中間中心性を持つことになる。 しかし、彼らは若いため、おそらくコミュニティ内の重要ノードとはリンクが少なく、固有値の中心性は非常に低い。スタティックネットワークの文脈における中心性の概念は、経験的および理論的研究に基づいて、時間的ネットワークの文脈におけるダイナミック中心性に拡張されている。

ノードの影響

中心性指数の欠点を克服するため、より一般的な尺度として開発されたのが、アクセシビリティ︵ネットワークの残りの部分があるノードからどの程度アクセスが可能であるかを測定するために、ランダムウォークの多様性を使用する︶と、影響力︵ノードの感染力の期待値から割り出される︶である。これらの測定値は、ネットワークの構造のみから計算することができる。

モデル

「スモールワールド現象#ネットワークモデル」も参照

ネットワークモデルは、複雑ネットワーク内に起こる相互作用の理解に役立つ。また、ランダムグラフから生成されたネットワーク構造のモデルは実際の複雑ネットワークと見比べられて使われる。

Erdős-Rényi（ER）

This Erdős–Rényi model is generated with N=5 nodes. For each edge in the complete graph formed by all N nodes, a random number is generated and compared to a given probability. If the random number is greater than p, an edge is formed on the model.

Paul ErdősとAlfréd Rényiの名前にちなんだErdős-Rényiモデルは、エッジが等しい確率のノード間に設定されたランダムグラフを生成する。 確率方法で、さまざまなプロパティを満たすグラフの存在を証明したり、多くのグラフに対してあるプロパティが持つ重要性を厳密に定義したりできる。Erdős-Rényiモデルを生成するには2つのパラメータが必要である。1つは、生成されたグラフ内のノード数Nと、ある2つのノード間でリンクpを形成する確率である。Eをエッジ数の期待値とすると、 式⟨k⟩ = 2 ⋅ E/ N= p⋅ (N − 1)を使って定数⟨k⟩を導き出せる。

Erdős-Rényiモデルには、他のグラフと比べるといくつかの興味深い特徴がある。 このモデルは特定のノードにバイアスをかけずに生成されるため、度数分布は次の式のように二項式となる‥

${\displaystyle P(\deg($v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}}  

その結果、クラスター係数が0になる傾向にある。 このモデルは⟨k⟩ >1を﹁パーコレーション﹂と呼ばれるプロセスでgiant component︵大きいコンポーネント︶を生成する。 またこのモデルでは、平均距離が比較的短く、log Nに近くなる。

ワッツ・ストロガッツ

「複雑ネットワーク#ワッツ・ストロガッツモデル」も参照

The Watts-Strogatz model uses the concept of rewire to achieve its structure.

ワッツ・ストロガッツのランダムグラフモデルは、スモール・ワールド特性を持つグラフを生成するモデルである。このモデルを生成するためにはまず格子構造が必要である。ネットワークの各ノードは、当初は、その$\langle k\rangle$ 隣のノードにリンクされている。もう1つのパラメータとして、再配線確率が必要である。各エッジは確率$p$ でランダムエッジとして再配線される。このモデルで再配線されるリンクの期待値は$pE=pN\langle k\rangle /2$ である。

このモデルは、最初は非ランダムの格子構造なので、平均距離が高いとともにクラスター係数が非常に高い。再配線の確率が上がるにつれて、クラスター係数は平均距離よりも遅く減少する。この特徴はクラスター係数の減少を抑えながら、ネットワークの平均距離が大幅に減少することを可能にする。確率$p$ の値が高いほど、多くのエッジが再配線され、ワッツ・ストロガッツモデルは実質的にランダムなネットワークになる。

バラバシ・アルバート（BA）

「複雑ネットワーク#バラバシ・アルバートモデル」も参照

Barabasi Albertモデルの生成

BAモデルは、優先的アタッチメント︵preferential attachment︶または﹁富裕層がより豊かになる﹂現象を実証できるランダムネットワークモデル。 このモデルでは、エッジはそれより高い度合いのノードに接続する可能性が高い。ネットワークは最初はm₀ 個のノードを持ち、m₀ ≥ 2でネットワークの各ノードの次数は 1以上でなければならない。そうでないと、ネットワークの残りの部分から常に孤立した状態になる。

BAモデルでは、新しいノードが1つずつネットワークに追加される。 各新しいノードは、既存のノードが既に持つリンクの数に比例する確率で、既存のノード$m$ 個にリンクされる。 まとめると、新しいノードがあるノード$i$ に接続される確率$p_{i}$ は以下のようになる。$k_{i}$ はノード$i$ の次数である。

$p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}}$ 

ここで、重リンクされたノード︵ハブと呼ばれる︶は、さらに多くのリンクを蓄積する傾向にあるが、少数のリンクしか持たないノードは新しいリンクの宛先として選択される可能性は低い。 つまり、新しいノードには、すでに多くリンクされたノードにリンクする傾向にある。
 

The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.

BAモデルから得られる次数分布はスケールフリーであり、べき乗則で表される‥

${\displaystyle P($k)\sim k^{-3}\,}  

ハブとなる重リンクされたノードは、ノード間の短い道︵Path︶の存在を可能にする、高い中間中心性を示す。 結果として、BAモデルは平均距離が非常に短くなる傾向にある。 このモデルのクラスター係数も0になる傾向がある。Erdős Rényiモデルや、スモールワールド・ネットワークを含む多くのモデルの直径Dはlog Nに比例するが、BAモデルはD〜loglogNとなる。このときの平均距離はNを直径としたときの縮尺であることに注意。

仲介駆動型接続（MDA）

Mediation-Driven Attachment︵MDA、仲介駆動型接続︶モデルでは、$m$ 個のエッジを持つ新しいノードが既にリンクされているノードをランダムに選択し、そのノードだけでなく、その隣人のノード$m$ 個にランダムにリンクする。 既存のノード$i$ が新しいノードに選ばれる確率${\displaystyle \Pi ($i)}  は以下のようになる‥

${\displaystyle \Pi ($i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}}  

この式の2つ目の因数は、調和平均︵IHM︶の逆数である。ノード$i$ の$k_{i}$ 近傍の次数︵IHM︶を計算する。 大規模な数値の研究によると、$m>14$ の場合、大きな限度$N$ における調和平均は定数となり、これは${\displaystyle \Pi ($i)\propto k_{i}}   と表せられる。これは、ノードが持っているリンク︵度数︶が高いほど、より多くのリンクが得られる傾向を意味し、﹁富裕層がより豊かになる﹂現象を説明する。したがって、MDAネットワークはPAの法則に密かに従っている。

$m=1$ の場合、﹁1人がすべてを手に入れる﹂メカニズムが見られる。ここでは、ノードのほぼ$99\%$ が次数1を持ち、1人が超富裕層となる。﹁富裕層がより豊かになる﹂現象は、$m>14$ から見られる。

フィットネス

Caldarelliらによって導入されたフィットネスモデルでは、頂点の性質が重視される。このモデルでは、2つの頂点$i,j$ の間のリンクが関数$f(\eta _{i},\eta _{j})$ によって算出される確率を持つ。頂点$i$ の度数は以下のように表せる‥

$k(\eta _{i})=N\int _{0}^{\infty }f(\eta _{i},\eta _{j})\rho (\eta _{j})\,d\eta _{j}$ 

$k(\eta _{i})$ が$\eta _{i}$ に逆数を持ち、かつ増加する関数である場合、確率分布${\displaystyle P($k)}  は以下のようになる‥

${\displaystyle P($k)=\rho (\eta (k))\cdot \eta '(k)}  

結果として、$\eta$ がべき乗則として分配される場合、ノード次数も同様になる。速い崩壊確率分布ではリンク関数と共に、$\rho (\eta )=e^{-\eta }$ と$f(\eta _{i},\eta _{j})=\Theta (\eta _{i}+\eta _{j}-Z)$ となる。

ヘヴィサイド関数の$Z$ 定数と$\Theta$ を使用すると、スケールフリーのネットワークとなる。

このモデルは、さまざまなノード$i,j$ に対するフィットネスにGDPを使用することによって、国家間の貿易を記述することに成功している‥

${\frac {\delta \eta _{i}\eta _{j}}{1+\delta \eta _{i}\eta _{j}}}$ 

関連項目

• グラフ理論
• 複雑ネットワーク