「ネットワーク理論」の版間の差分
削除された内容 追加された内容
加筆 |
m編集の要約なし |
||
2行目:
[[ファイル:Internet map 1024.jpg|サムネイル|インターネットのネットワーク]]
[[ファイル:Small_Network.png|右|サムネイル|ネットワークの例]]
'''ネットワーク理論'''（ねっとわーくりろん）とは、[[通信ネットワーク工学|通信]]、[[コンピュータネットワーク|コンピュータ]]、[[生物ネットワーク|生物]]、[[社会的ネットワーク|ソーシャル]]などの[[複雑
== 概論・歴史 ==
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>。この方法では、関係が単方向のため測定が可能である。
:ネットワークの大きさは、ノード<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つのノードが繋がっている確率である。▼
:平均距離は、すべてのノードのペア間の最短距離を見つけて加算し、ペアの総数で割ることで算出される。 これは、ネットワークのあるノードから別のノードに到達するまでの平均のステップの数を表している。▼
▲=== 大きさ ===
:ネットワークを測定する別の手段として[[径|直径]]が使われる。ネットワークの直径は、ネットワーク内の最短距離のうち最も長いものとして定義することができる。 これは、ネットワーク内の最も離れた2つのノード間の最短距離となる。 言い換えれば、各ノードから他のすべてのノードまでの最短距離を計算すると、直径はすべての距離のうち最も長いものとなる。 直径は、ネットワークの線形的な大きさを表す。▼
▲ネットワークの大きさは、ノード<math>N</math>の数か、もしくは（一般的ではないが）エッジ<math>E</math>の数で表す。エッジ<math>E</math>の数は <math>N-1</math> (ツリー) から <math>E_{\max}</math> (完全なグラフ)までさまざまである。
▲=== 平均次数 ===
:クラスタ係数とは、「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>▼
▲ノードの次数<math>k</math>とは、そのノードに接続している辺の数である。 ネットワークの密度にも密接に関連する[[平均次元|平均次数]]は、<math>\langle k\rangle = \tfrac{2E}{N}</math>である。 ERランダムグラフモデルでは、<math>\langle k \rangle = p(N-1)</math> を計算できる。ここでは、<math>p</math>は2つのノードが繋がっている確率である。
▲=== 平均距離 ===
:ネットワークがどのようにリンクされているかは、ネットワーク解析の解釈の上で重要である。 ネットワークは以下の4つのカテゴリに分類される。▼
▲平均距離は、すべてのノードのペア間の最短距離を見つけて加算し、ペアの総数で割ることで算出される。 これは、ネットワークのあるノードから別のノードに到達するまでの平均のステップの数を表している。
:* ''Clique/Complete Graph（完全なグラフ）：完全にリンクされたネットワークで、すべてのノードが他のすべてのノードにリンクしている。この場合、すべてのノードが他のノードからの入り口と出口を有する点で対称的である。''▼
:* ''Giant Component（大きいコンポーネント）''：ネットワーク内のほとんどのノードとリンクしている一つのノード。▼
:* ''Weakly Connected Component（弱い関連性を持つコンポーネント）：エッジの方向性を無視した場合に、どのノードからも他のノードへの経路が存在する。''▼
:* ''Strongly Connected Component（強い関連性を持つコンポーネント）：どのノードからも他のノードへの直接経路が存在する。''▼
▲=== 直径 ===
:中心性の指数は、ネットワークモデルにおいて最も重要なノードを特定できるようなランキングを生成する。中心性の指数で割り出される「重要度」とはネットワークによって意味が異なる。 例えば、betweennessの中心性では、他の多くのノード間にブリッジを形成するノードを非常に重要とみなす。また、[[中心#Eigenvectorの中心|固有値の中心性]]は、他の多くの重要なノードがそれにリンクしている場合に重要とみなされる。 このように重要度の定義は数多くの文献で言及されている。▼
▲ネットワークを測定する別の手段として[[径|直径]]が使われる。ネットワークの直径は、ネットワーク内の最短距離のうち最も長いものとして定義することができる。 これは、ネットワーク内の最も離れた2つのノード間の最短距離となる。 言い換えれば、各ノードから他のすべてのノードまでの最短距離を計算すると、直径はすべての距離のうち最も長いものとなる。 直径は、ネットワークの線形的な大きさを表す。
:中心性指数は、最も重要なノードを識別するためにのみ適用が可能であり、他のノード部分では無意味な場合がほとんどである<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人の若いメンバーは高いbetweennessの中心性を持つことになる。 しかし、彼らは若いため、おそらくコミュニティ内の重要ノードとはリンクが少なく、固有値の中心性は非常に低い。▼
:スタティックネットワークの文脈における中心性の概念は、経験的および理論的研究に基づいて、時間的ネットワークの文脈におけるダイナミック中心性<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>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" />。▼
▲クラスタ係数とは、「all-my-friends-know-each-other（すべての友達が互いを知っている）」特性を表す。 「友人の友人は友人である」とも表現される。 ノードのクラスタ係数は、ノードが近隣のノードと互いに実際に存在しているリンクと、可能なリンクの最大数の比率である。 ネットワーク全体でのクラスタ係数は、全ノードのクラスタ係数の平均である。 ネットワークのクラスタ係数が高いことは、[[スモール・ワールド]]である指標である。<math>i</math>番目のノードのクラスタ係数は
▲=== 関連性 ===
▲ネットワークがどのようにリンクされているかは、ネットワーク解析の解釈の上で重要である。 ネットワークは以下の4つのカテゴリに分類される。
▲* ''Clique/Complete Graph（完全なグラフ）：完全にリンクされたネットワークで、すべてのノードが他のすべてのノードにリンクしている。この場合、すべてのノードが他のノードからの入り口と出口を有する点で対称的である。''
▲* ''Giant Component（大きいコンポーネント）''：ネットワーク内のほとんどのノードとリンクしている一つのノード。
▲* ''Weakly Connected Component（弱い関連性を持つコンポーネント）：エッジの方向性を無視した場合に、どのノードからも他のノードへの経路が存在する。''
▲* ''Strongly Connected Component（強い関連性を持つコンポーネント）：どのノードからも他のノードへの直接経路が存在する。''
▲=== ノードの中心性 ===
▲中心性の指数は、ネットワークモデルにおいて最も重要なノードを特定できるようなランキングを生成する。中心性の指数で割り出される「重要度」とはネットワークによって意味が異なる。 例えば、betweennessの中心性では、他の多くのノード間にブリッジを形成するノードを非常に重要とみなす。また、[[中心#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人の若いメンバーは高いbetweennessの中心性を持つことになる。 しかし、彼らは若いため、おそらくコミュニティ内の重要ノードとはリンクが少なく、固有値の中心性は非常に低い。
▲スタティックネットワークの文脈における中心性の概念は、経験的および理論的研究に基づいて、時間的ネットワークの文脈におけるダイナミック中心性<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>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" />。
== ネットワークのモデル ==
77 ⟶ 66行目:
== 関連項目 ==
* [[グラフ理論]]
* [[複雑ネットワーク]]
== 脚注 ==
| |||