ネットワーク理論のソースを表示

[[ファイル:Internet map 1024.jpg|サムネイル|インターネットのネットワーク]]
[[ファイル:Small_Network.png|右|サムネイル|ネットワークの例]]
'''ネットワーク理論'''（ネットワークりろん）は、[[通信ネットワーク工学|通信]]、[[コンピュータネットワーク|コンピュータ]]、[[生物ネットワーク|生物]]、[[社会的ネットワーク|ソーシャル]]などの[[複雑ネットワーク]]を研究する分野。ネットワークは、[[ノード (ネットワーク)|ノード]]や[[辺|エッジ]]が属性（例：名前）を持つグラフとして定義される。数学の[[グラフ理論]]、物理学の[[統計力学]]、コンピュータサイエンスの[[データマイニング]]と情報視覚化、統計からの推論[[モデリング (科学的)|モデリング]]、社会学の[[社会構造]]などの理論や手法が使われる<ref>Committee on Network Science for Future Army Applications (2006). [http://www.nap.edu/catalog/11516.html ''Network Science'']. National Research Council. {{ISBN2|0309653886}}.</ref>。

== 概論・歴史 ==
[[ファイル:7 bridges.svg|サムネイル|七つの橋の問題。]]
ネットワーク理論は、複雑なデータを解析する手段としてさまざまな分野で言及される。この理論の最初期の論文は、[[1736年]]に[[レオンハルト・オイラー]]によって書かれた有名な「[[一筆書き#ケーニヒスベルクの七つの橋問題|七つの橋]]」の問題である。オイラーの[[頂点]]と[[辺]]による数学的証明は[[グラフ理論]]の基礎となった。グラフ理論は発展して化学に応用された<ref>シルベスター、1878</ref>。
[[ファイル:Moreno Sociogram 1st Grade.png|左|サムネイル|160x160ピクセル|小学一年生のソシオグラム。]]
[[1930年代]]、伝統的な[[ゲシュタルト心理学|ゲシュタルト]]派の[[心理学]]者[[ヤコブ・モレノ]]はアメリカで社会学を発展させ、[[1933年]]4月に[[ソシオグラム]]を医療学者の会で発表した。モレノは「ソシオグラムの出現以前はあるグループでの対人関係の構造が正確にどのようなものか、誰も分かりませんでした。」と発表した<ref>モレノ、1953</ref>。ソシオグラムの例が左の図で、小学1年生の社会的構造の表象である。男子と女子はそれぞれ同性が友達だったが、例外の1人の男子が女子を好きだと言ったが、相互的な関係ではないことが分かる（図を参照）。ソシオグラムは多くの用途を見出しており、社会ネットワーク解析という分野に発展している。

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

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

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

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

=== 密度 ===
無向ネットワークの[[密度]]<math>D</math>は、辺の数<math>E</math>と、[[二項係数]]<math>\tbinom N2</math>によって得られる可能な辺の数の比として定義される：

<math>D = \frac{2E}{N(N-1)}.</math>

ネットワークが有向である場合、可能な辺の数は<math>N (N-1)</math>となるため、密度は次のように定義される：

<math>D = \frac{E}{N(N-1)}.</math>

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

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

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

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

=== クラスター係数 ===
{{See also|複雑ネットワーク#クラスター性}}
クラスター係数とは、「all-my-friends-know-each-other（すべての友達が互いを知っている）」特性を表す。 「友人の友人は友人である」とも表現される。 ノードのクラスター係数とは、ノードが近隣のノードと互いに実際に存在しているリンクと、可能なリンクの最大数の比率である。 ネットワーク全体でのクラスタ係数は、全ノードのクラスター係数の平均である。 ネットワークのクラスター係数が高いことは、スモール・ワールドであることの指標でもある。<math>i</math>番目のノードのクラスター係数は<math>C_i = {2e_i\over k_i{(k_i - 1)}}\,</math>と表される。ここでは、<math>k_i</math>は<math>i</math>番目のノードの隣人の数であり、<math display="inline">e_i</math>はこれらの隣人間のリンクの数である。 隣人間の可能なリンクの最大数は以下のように表される：<math>{\binom {k}{2}} = {{k(k-1)}\over 2}\,</math>

=== 連結性 ===
ネットワークがどのように[[連結グラフ|連結]]されているか、すなわちノードの間にエッジを伝う[[道 (グラフ理論)|道]]があるかは、ネットワークやその部分グラフの重要な特徴の一つである。連結性に応じて、以下のようなネットワークや部分グラフの種類がある。
* [[完全グラフ]]・[[クリーク (グラフ理論)|クリーク]]：すべてのノードが他のすべてのノードとリンクで直接つながっているネットワークを完全グラフといい、ネットワークに含まれる、完全グラフをなす部分グラフをクリークという。
* 巨大連結成分：ネットワークの一定割合を占める[[連結グラフ|連結成分]]。厳密には、大きさがネットワーク全体の大きさに比例する連結成分を指す。ランダムグラフでは巨大連結成分が高々1つしか存在しないことが知られている。
* 弱連結成分：有向ネットワークで、エッジの方向を無視した場合、どのノードからも他のノードへの道が存在する連結成分。
* 強連結成分：有向ネットワークで、エッジの方向を考慮した場合、どのノードからも他のノードへの道が存在する連結成分。

=== ノードの中心性 ===
中心性の指数は、ネットワークモデルにおいて最も重要なノードを特定するために使われる。中心性の指数で割り出される「重要度」とはネットワークによって意味が異なる。 例えば、中間中心性では、他の多くのノード間にブリッジを形成するノードを非常に重要とみなす。また、固有値の中心性は、他の多くの重要なノードがそれにリンクしている場合に重要とみなされる。 このように重要度の定義は数多くの文献で言及されている。中心性指数は、最も重要なノードを識別するためにのみ適用が可能であり、他のノード部分では無意味な場合がほとんどである<ref>Lawyer, Glenn (March 2015). [http://www.nature.com/articles/srep08665 "Understanding the spreading power of all nodes in a network"]. ''Scientific Reports''. '''5''' (O8665): 8665. [[Bibcode]]:[[bibcode:2015NatSR...5E8665L|2015NatSR...5E8665L]]. [[Digital object identifier|doi]]:[[doi:10.1038/srep08665|10.1038/srep08665]]. [[PubMed Central|PMC]] [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4345333 4345333]. [[PubMed Identifier|PMID]] [https://www.ncbi.nlm.nih.gov/pubmed/25727453 25727453].</ref><ref name=":0">Lawyer, Glenn (March 2015). [http://www.nature.com/articles/srep08665 "Understanding the spreading power of all nodes in a network"]. ''Scientific Reports''. '''5''' (O8665): 8665. [[Bibcode]]:[[bibcode:2015NatSR...5E8665L|2015NatSR...5E8665L]]. [[Digital object identifier|doi]]:[[doi:10.1038/srep08665|10.1038/srep08665]]. [[PubMed Central|PMC]] [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4345333 4345333]. [[PubMed Identifier|PMID]] [https://www.ncbi.nlm.nih.gov/pubmed/25727453 25727453].</ref><ref>Borgatti, Stephen P. (2005). "Centrality and Network Flow". ''Social Networks''. Elsevier. '''27''': 55–71. [[Digital object identifier|doi]]:[[doi:10.1016/j.socnet.2004.11.008|10.1016/j.socnet.2004.11.008]].</ref>。例えば、2つの別々のコミュニティがあり、互いとのリンクはそれぞれの最も若いメンバー同士にしかないとする。すると、 1つのコミュニティからもう1つのコミュニティへの移行するには必ずこのリンクを経由しなければならないので、2人の若いメンバーは高い中間中心性を持つことになる。 しかし、彼らは若いため、おそらくコミュニティ内の重要ノードとはリンクが少なく、固有値の中心性は非常に低い。静的ネットワークの文脈における中心性の概念は、経験的および理論的研究に基づいて、時間的ネットワークの文脈におけるダイナミック中心性<ref>Braha, D.; Bar-Yam, Y. (2006). "From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks". ''Complexity''. '''12''': 59–63. [[Digital object identifier|doi]]:[[doi:10.1002/cplx.20156|10.1002/cplx.20156]].</ref>に拡張されている<ref>Hill, S.A.; Braha, D. (2010). "Dynamic Model of Time-Dependent Complex Networks". ''Physical Review E''. '''82''': 046105. [[Digital object identifier|doi]]:[[doi:10.1103/physreve.82.046105|10.1103/physreve.82.046105]].</ref><ref>Holme, P. and Saramäki, J. 2013. ''Temporal Networks.'' Springer.</ref>。

=== ノードの影響 ===
中心性指数の欠点を克服するため、より一般的な尺度として開発されたのが、[[アクセシビリティ]]（ネットワークの残りの部分があるノードからどの程度アクセスが可能であるかを測定するために、ランダムウォークの多様性を使用する）<ref>Travençolo, B. A. N.; da F. Costa, L. (2008). "Accessibility in complex networks". ''Physics Letters A''. '''373''' (1): 89–95. [[Bibcode]]:[[bibcode:2008PhLA..373...89T|2008PhLA..373...89T]]. [[Digital object identifier|doi]]:[[doi:10.1016/j.physleta.2008.10.069|10.1016/j.physleta.2008.10.069]].</ref>と、[[影響|影響力]]（ノードの感染力の期待値から割り出される）である。これらの測定値は、ネットワークの構造のみから計算することができる<ref name=":0" />。

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

===  Erdős-Rényi（ER） ===
[[ファイル:ER model.svg|サムネイル|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つは、生成されたグラフ内のノード数 {{mvar|N}} と、ある2つのノード間でリンク {{mvar|p}} を形成する確率である。{{mvar|E}} をエッジ数の[[期待値]]とすると、 式 {{math|&lang;''k''&rang; {{=}} 2 &sdot; ''E'' / ''N'' {{=}} ''p'' &sdot; (''N'' &minus; 1)}} を使って定数 {{math|&lang;''k''&rang;}} を導き出せる。

Erdős-Rényiモデルには、他のグラフと比べるといくつかの興味深い特徴がある。 このモデルは特定のノードにバイアスをかけずに生成されるため、次数分布は次の式のように二項式となる：
: <math>P(k) = {n-1\choose k} p^k (1-p)^{n-1-k}</math>
また平均次数{{math|&lang;''k''&rang;}}が一定で、ノード数 {{mvar|N}} が増えるにつれ、クラスター係数が{{math|0}}へと小さくなる。 このモデルでは {{math|&lang;''k''&rang; > 1}} において、巨大連結成分が存在する（この現象を「パーコレーション」と呼ぶ）。 またこのモデルでは、平均距離が比較的短く、{{math|log ''N''}} に近くなる。

=== ワッツ・ストロガッツ ===
{{See also|複雑ネットワーク#ワッツ・ストロガッツモデル}}
[[ファイル:Watts-Strogatz-rewire.png|サムネイル|200x200ピクセル|The Watts-Strogatz model uses the concept of rewire to achieve its structure.]]
ワッツ・ストロガッツのランダムグラフモデルは、[[スモールワールド性|スモール・ワールド特性]]を持つグラフを生成するモデルである。このモデルを生成するためにはまず[[格子構造]]が必要である。ネットワークの各ノードは、当初は、その<math>\langle k\rangle</math>隣のノードにリンクされている。もう1つのパラメータとして、再配線確率が必要である。各エッジは確率<math>p</math>でランダムエッジとして再配線される。このモデルで再配線されるリンクの期待値は<math>pE = pN\langle k\rangle/2</math>である。

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

=== バラバシ・アルバート（BA） ===
{{See also|複雑ネットワーク#バラバシ・アルバートモデル}}
[[ファイル:Barabasi Albert model.gif|サムネイル|Barabasi Albertモデルの生成]]
BAモデルは、優先的アタッチメント（preferential attachment）または「富裕層がより豊かになる」現象を実証できるランダムネットワークモデル。 このモデルでは、エッジはそれより高い度合いのノードに接続する可能性が高い。ネットワークは最初は''m''<sub>0</sub>&nbsp;個のノードを持ち、''m''<sub>0</sub>&nbsp;≥&nbsp;2でネットワークの各ノードの次数は&nbsp;1以上でなければならない。そうでないと、ネットワークの残りの部分から常に孤立した状態になる。

BAモデルでは、新しいノードが1つずつネットワークに追加される。 各新しいノードは、既存のノードが既に持つリンクの数に比例する確率で、既存のノード<math>m</math>個にリンクされる。 まとめると、新しいノードがあるノード<math>i</math>に接続される確率<math>p_i</math>は以下のようになる<ref>R. Albert; A.-L. Barabási (2002). [http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf "Statistical mechanics of complex networks"] (PDF). ''[[Reviews of Modern Physics]]''. '''74''': 47–97. [[arXiv]]:[https://arxiv.org/abs/cond-mat/0106096 cond-mat/0106096]. [[Bibcode]]:[[bibcode:2002RvMP...74...47A|2002RvMP...74...47A]]. [[Digital object identifier|doi]]:[[doi:10.1103/RevModPhys.74.47|10.1103/RevModPhys.74.47]].</ref>。<math>k_i</math>はノード<math>i</math>の次数である。

<math>p_i = \frac{k_i}{\sum_j k_j}</math>

ここで、重リンクされたノード（ハブと呼ばれる）は、さらに多くのリンクを蓄積する傾向にあるが、少数のリンクしか持たないノードは新しいリンクの宛先として選択される可能性は低い。 つまり、新しいノードには、すでに多くリンクされたノードにリンクする傾向にある。
[[ファイル:Barabasi-albert model degree distribution.svg|サムネイル|The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.]]
BAモデルから得られる次数分布はスケールフリーであり、[[冪乗|べき乗]]則で表される：

<math>P(k)\sim k^{-3} \, </math>

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

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

<math> \Pi(i) = \frac{k_i} N \frac{ \sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}</math>

この式の2つ目の[[約数|因数]]は、[[調和平均]]（IHM）の[[逆数]]である。ノード<math>i</math>の<math>k_i</math>近傍の次数（IHM）を計算する。 大規模な数値の研究によると、<math>m>14</math>の場合、大きな限度<math>N</math>における調和平均は定数となり、これは<math> \Pi(i)\propto k_i </math> と表せられる。これは、ノードが持っているリンク（度数）が高いほど、より多くのリンクが得られる傾向を意味し、「富裕層がより豊かになる」現象を説明する。したがって、MDAネットワークはPAの法則に密かに従っている<ref>Hassan, M. K.; Islam, Liana; Arefinul Haque, Syed (2017;). "Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks". ''Physica A''. '''469''': 23–30. [[Digital object identifier|doi]]:[[doi:10.1016/j.physa.2016.11.001|10.1016/j.physa.2016.11.001]]</ref>。

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

=== フィットネス ===
Caldarelliらによって導入されたフィットネスモデルでは、頂点の性質が重視される<ref>Caldarelli G., A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 (2002)</ref>。このモデルでは、2つの頂点<math>i,j</math>の間のリンクが関数<math>f(\eta_i,\eta_j)</math>によって算出される確率を持つ。頂点<math>i</math>の度数は以下のように表せる<ref>Servedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 (2004)</ref>：

<math>k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j </math>

<math>k(\eta_i)</math>が<math>\eta_i</math>に逆数を持ち、かつ増加する関数である場合、確率分布<math>P(k)</math>は以下のようになる：

<math>P(k)=\rho(\eta(k)) \cdot \eta'(k)</math>

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

[[ヘヴィサイドの階段関数|ヘヴィサイド関数]]の<math>Z</math>定数と<math>\Theta</math>を使用すると、スケールフリーのネットワークとなる。

このモデルは、さまざまなノード<math>i,j</math>に対するフィットネスにGDPを使用することによって、国家間の貿易を記述することに成功している<ref>Garlaschelli D., M I Loffredo Physical Review Letters 93, 188701 (2004)</ref><ref>Cimini G., T. Squartini, D. Garlaschelli and A. Gabrielli, Scientific Reports 5, 15758 (2015)</ref>：

<math> \frac{\delta \eta_i\eta_j}{1+ \delta \eta_i\eta_j}</math>

== 解析 ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}

== コンテンツ普及 ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}

== 相互ネットワーク ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}

== 多層ネットワーク ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}

== ネットワーク最適化 ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}

== 関連項目 ==
* [[グラフ理論]]
* [[複雑ネットワーク]]

== 脚注 ==
{{Reflist}}

== 参考文献 ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}

{{DEFAULTSORT:ねつとわあくりろん}}
[[Category:グラフ理論]]
[[Category:ネットワーク]]