Wikipedia

「ネットワーク理論」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
→‎top: 72時間以上経過した工事中テンプレートを除去
m編集の要約なし
1行目:
[[ファイル: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. [[International Standard Book Number|ISBN]] [[%E7%89%B9%E5%88%A5%3ABookSources/0309653886|0309653886]].</ref>。
 
== 概論・歴史 ==
7行目:
ネットワーク理論は、複雑なデータを解析する手段としてさまざまな分野で言及される。この理論の最初期の論文は、[[1736年|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}}は、スケールフリーのネットワークを実現させた。これは多数の接続を持つハブ頂点を含むゆるやかに定広義されたのネットワークトポロジーであり、他のすべてのノードと接続の数の比率が一定に保たれるように成長する。インターネットなどの多くのネットワークはこの側面を維持しているように見えるが、他のネットワークではこの比率はノードの長いテール[[確率分布|分布]]に近似する。
 
== プロパティ ==
19行目:
 
=== 密度 ===
ネットワークの[[密度]]<math>D</math>は、[[二項係数]]<math>\tbinom N2</math>によって得られる、可能なすべての辺の数に対する辺の数<math>E</math>の比率として定義される：<math>D = \frac{2E}{N(N-1)}</math>。もう1つの表し方はとして、<math>T</math>が単方向性である場合は以下のように表せる <ref>Wasserman＆Faust、1994</ref><ref>http://psycnet.apa.org/journals/prs/9/4/172/</ref>：<math>D = \frac{2E}{N(N-1)}</math>。この方法では、関係が単方向のであるため測定が可能である。
 
=== 大きさ ===
28行目:
 
=== 平均距離 ===
平均距離（Path）は、すべてのノードのペア間の最短距離を見つけて加算し、ペアの総数で割ることで算出される。 これは、ネットワークのあるノードから別のノードに到達するまでの平均のステップの数を表している。
 
=== 直径 ===
35行目:
=== クラスター係数 ===
{{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>
 
=== 関連性 ===
ネットワークがどのようにリンクされているかは、ネットワーク解析の解釈の上で重要である。 ネットワークは以下の4つのカテゴリに分類される。
* ''Clique/Complete Graph（完全なグラフ）：完全にリンクされたネットワークで、すべてのノードが他のすべてのノードにリンクしている。この場合、すべてのノードが他のノードからの入り口と出口を有する点で対称的である。''
* ''Giant Component（大きいコンポーネント）''：ネットワーク内のほとんどのノードとリンクしている一つのノード。
45行目:
 
=== ノードの中心性 ===
中心性の指数は、ネットワークモデルにおいて最も重要なノードを特定するために使われる。中心性の指数で割り出される「重要度」とはネットワークによって意味が異なる。 例えば、中間中心性では、他の多くのノード間にブリッジを形成するノードを非常に重要とみなす。また、[[中心#Eigenvectorの中心|固有値の中心性]]は、他の多くの重要なノードがそれにリンクしている場合に重要とみなされる。 このように重要度の定義は数多くの文献で言及されている。中心性指数は、最も重要なノードを識別するためにのみ適用が可能であり、他のノード部分では無意味な場合がほとんどである<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>。▼
中心性の指数は、ネットワークモデルにおいて最も重要なノードを特定できるようなランキングを生成する。中心性の指数で割り出される「重要度」とはネットワークによって意味が異なる。 例えば、中間中心性では、他の多くのノード間にブリッジを形成するノードを非常に重要とみなす。また、[[中心#Eigenvectorの中心|固有値の中心性]]は、他の多くの重要なノードがそれにリンクしている場合に重要とみなされる。 このように重要度の定義は数多くの文献で言及されている。
▲中心性指数は、最も重要なノードを識別するためにのみ適用が可能であり、他のノード部分では無意味な場合がほとんどである<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>。
 
=== ノードの影響 ===
中心性指数の欠点を克服するため、より一般的な尺度がとして開発された。2つの例はが、[[アクセシビリティ]]（ネットワークの残りの部分があるノードからどの程度アクセスが可能であるかを測定するために、ランダムウォークの多様性を使用する）<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.png|サムネイル|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つのノード間でリンク{{math|<VAR >p</VAR >}}を形成する確率である。{{math|<VAR >E</VAR >}}をエッジ数の[[期待値]]とすると、 式の{{math|&lang;<VAR >k</VAR >&rang; {{=}} 2 &sdot; <VAR >E</VAR > / <VAR >N</VAR > {{=}} <VAR >p</VAR > &sdot; (<VAR >N</VAR > &minus; 1)}}を使って定数{{math|&lang;<VAR >k</VAR >&rang;}}を導き出せる。
 
Erdős-Rényiモデルには、他のグラフと比べるといくつかの興味深い特徴がある。 このモデルは特定のノードにバイアスをかけずに生成されるため、[[度数分布]]は次の式のように二項式となる：
: <math>P(\deg(v) = k) = {n-1\choose k} p^k (1-p)^{n-1-k}</math>
その結果、クラスター係数が{{math|0}}になる傾向にある。 このモデルは{{math|&lang;<VAR >k</VAR>&rang; > 1}}を「パーコレーション」と呼ばれるプロセスでgiant component（大きいコンポーネント）を生成する。 またこのモデルでは、平均距離はが比較的短く、{{math|log <VAR >N</VAR >}}に近くなる。
 
=== ワッツ・ストロガッツ ===
{{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>の値が高いほど、多くのエッジが再配線され、ワッツ・ストロガッツモデルは実質的にランダムなネットワークになる。
86 ⟶ 84行目:
<math>P(k)\sim k^{-3} \, </math>
 
ハブとなる重リンクされたノードは、ノード間の短い経路（Path）の存在を可能にする、高い中間中心性を示す。 結果として、BAモデルは平均距離が非常に短いくなる傾向がにある。 このモデルのクラスター係数も0になる傾向がある。Erdős Rényiモデルや、スモールワールド・ネットワークを含む多くのモデルの直径Dはlog Nに比例するが、BAモデルはD〜loglogNとなる。このときの平均距離はNを直径としたときの縮尺であることに注意。
 
==== 仲介駆動型接続（MDA） ====
93 ⟶ 91行目:
<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)}}
 
=== SIRモデル ===
 
=== マスター方程式 ===
 
== 相互ネットワーク ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}
 
== 多層ネットワーク ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}
 
== ネットワーク最適化 ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}
 
== 関連項目 ==
162 ⟶ 135行目:
 
== 参考文献 ==
{{節スタブ|date=2017年1月18日 (水) 22:28 (UTC)}}
[[Category:グラフ理論]]
[[Category:ネットワーク]]
「https://ja.wikipedia.org/wiki/ネットワーク理論」から取得