複雑ネットワークとは?

Weblio 辞書 > 学問 > OR事典 > 複雑ネットワークの意味・解説 

複雑ネットワーク

読み方ふくざつねっとわーく
【英】:complex network

概要

現実世界観察される, 何らかの特徴的性質を持つグラフのこと. もしくは一般にそのような性質を持つグラフのこと. インターネットWWWハイパーリンク構造交友知人関係,論文引用関係,ニューラル・ネットワークたんぱく質代謝反応など, グラフとして表現される現実構造多く一見複雑な形状をしているが, 自明でない特徴的性質を持つ. このようなグラフ構造総称して複雑ネットワークという.

詳説

 現実世界観察される, 何らかの特徴的性質を持つグラフのこと. もしくは一般にそのような性質を持つグラフのこと.

 インターネット, WWWハイパーリンク構造, 交友知人関係, 論文引用関係, ニューラル・ネットワーク, たんぱく質代謝反応など, グラフとして表現される現実構造多く一見複雑な形状をしているが, 自明でない特徴的性質を共通して持つことが近年分かってきた. そこで, 現実大規模グラフ構造の持つ特徴調べ, その特徴現れる原理解明する研究が急速に進展している.

 なお, グラフにおいて点や辺に容量長さなどの属性がある場合は特にネットワークと言うが, 複雑ネットワークの研究領域では, その区別は明確ではない. また, 特徴的性質というものも明確に定まっているものではない.

 複雑ネットワークの特徴的構造として知られる代表的なものとして, まずスケールフリー (scale-free) がある. スケールフリーとは, 次数k\, である確率p(k)\, , つまり次数分布べき乗則満たすことp(k) \propto k^{-\gamma}\, , ただし\gamma\, は正の実数)を意味する.

 また, クラスタ係数に関して特徴的性質を持つことが多い. ここで, 次数k\, の点v\, クラスタ係数は, 隣接点間の辺数をk(k-1)/2\, (つまり隣接点間辺数の取りうる最大値) で割ったものとして定義され, すべての点にわたるクラスタ係数平均がそのグラフクラスタ係数と定義される. 現実の複雑ネットワークのクラスタ係数は, 点数関わらず比較大きい値を取ることが知られている.

 スモールワールド (small world) とは, 点数の多さに比較して平均点間距離が小さく, クラスタ係数大きいことを指す. 単に平均点間距離が小さいことをスモールワールドということもある. この特徴を持つ現実の複雑ネットワークも多い.

 現実の複雑ネットワークが, スケールフリーをはじめ上記で挙げたような性質を持つ原因解明するために, 様々なモデル検討されてきた.

 複雑ネットワークの研究興隆以前から知られていた, ErdösとRéyniのランダム・グラフは, 点集合任意の二点間に確率的に辺を張ることでグラフ生成するモデルである. ただ, この次数分布ポアソン分布に従うため, スケールフリーではない. また, クラスタ係数点数n\, 増加にしたがって0\, 収束する. ただし, 平均点間距離はO(\log n)\, であって小さと言える.

 WattsStrogatzは, 大きなクラスタ係数小さ平均点間距離を同時に実現するスモールワールド・ネットワークのモデル提案した. これは, 正方格子の辺集合一部ランダムにつなぎかえるというものである. ただし, このモデル生成されるグラフスケールフリーではない.

 BarabásiAlbertによるBAモデルは, 時間経過とともに点も付け加えられていく「成長」(growth) と, 新しく加わった点は次数の高い既存の点と高い確率で辺で繋がれる「優先的選択」(preferential attachment) という2つの原理基本としており, スケールフリーであるグラフp(k) \propto k^{-3}\, )を生成する. また, 点数n\, の時, 直径O(\log n/\log \log n)\, であり, 平均点間距離は小さい. ただし, クラスタ係数点数増加にしたがって0に収束するため, 現実の複雑ネットワークとは違って小さい.

 「成長」と「優先的選択」に基づいたバリエーションとして, 次数小さい点が選択的非活性化して新しい点からの辺を受け取れなくなる頂点非活性化モデルなどがある. モデルにはランダム性組み込まれていることが多いが, 決定的規則によって点や辺を追加する階層モデルというものもある.

 「成長」と「優先的選択」とは異な原理に基づくモデルとして閾値モデルというものがある. これは, 各点には重み確率的に与えられており, 点i\, j\,の間には, i\,j\,重み和や積 (一般的には二点の重み関数) に基づいて確定的もしくは確率的に辺が張られるというものである. 点の重みが従う確率分布指数分布に従う場合などに, スケールフリーであるグラフ生成することが分かっている. また平均点間距離は小さい. クラスタ係数は, 点数増加しても有限な値に留まるため, 大きと言える. 点間距離の効果考慮した空間閾値モデルへの拡張もある.

 これらのように, 現実の複雑ネットワークの持つ性質再現する様々なモデル提案されているが, 利用する際には, 対象とする分野に応じて適切なモデルを選ぶことが必要である.

 複雑ネットワークの性質解明が進むにしたがって, それらの性質を持つグラフ上で相互作用アルゴリズムに関する研究進みつつある.

 例えば, コンピュータウィルス拡散過程研究がある. 伝染病拡散研究古くら行われており, SISモデルなどの確率過程モデルがあったが, それらはグラフ構造仮定ていない. しかし, コンピュータウィルス拡散グラフ構造強く依存するため, グラフ上のSISモデルであるコンタクト・プロセスをはじめ, 様々なモデル研究されている. これらは基本的に, 各点が健康・病気回復ウィルス潜伏などの状態の一つ取り, 異なる状態の点が隣接すると, それぞれの点の状態が確率的に他の状態に遷移するというものである. BAモデルによって生成されたグラフでは, 感染しやすさを表す感染確率小さくても感染広がりやすいことが知られている.

 Webコミュニティ探索に関する研究進展しつつある. これは, Webハイパーリンク構造によるネットワーク (Webグラフ) 内にコミュニティ見出すことである. コミュニティの定義は様々であるが, 相互に密接にリンクを張っているページ集合, 言い換えればWebグラフ内の密な部分グラフという捉え方や, あるページ集合とそれらへリンクを張る (関心同じくする) ページ集合のなす二部グラフという捉え方一般的である. このようなコミュニティ発見することによって, 検索エンジンカバー率の向上や, ディレクトリ検索検索サイトカテゴリ自動生成などに応用できる.

 Kleinbergによって提案された, オーソリティハブからなる二部グラフコミュニティ考えるものは有名である. これは, 関連するページ多くのリンクを持つページ (ハブ) は情報連結点として重要であり, また多くのハブページからリンクされているページ (オーソリティ) は, そのトピックについて重要な情報を持つといういう考え方ベースとしている. Webグラフ構造から各ページオーソリティとしての価値ハブとしての価値の高いものを選び出すことによってコミュニティ抽出する.

 検索サイトGoogle採用されている, 検索結果重要度測るページランクという概念は, Webグラフ上のランダムウォークと密接に関係している. 点p\, ランクr(p)\, , 次数d(p)\, とした時, \textstyle r(p) = {\sum}_{s \in} \{\ p\, 終点とする有向辺の始点集合S\}\ r(s)/d(s)\, 満たすものとして, 各点のランクが定義される(ただし, すべての点のランクの和が1であるように正規化される). あるページランクは, そこへリンクを張るページが多いほど, そしてリンク元ランクが高いほど高くなる. ただし, リンク元ページから外部へのリンクが多いと, それからの寄与小さくなる. ページランクは, 有向グラフ遷移確率行列に基づくマルコフ過程にしたがうランダムウォークにおいて, 定常状態における各点での滞在確率等しい.

 上記に挙げたものの他にも, うわさやデマ広がり, マーケティングにおける広告戦略, パケット制御カスケード故障などの振る舞い性能は, グラフ構造強く依存しており, 現在も精力的研究が進められている.



参考文献

[1] 増田直紀, 今野紀雄, 『複雑ネットワークの科学』, 産業図書, 2005.

[2] A. -L. バラバシ,『新ネットワーク思考 -世界のしくみを読み解く』, NHK出版, 2002.

[3] D. J. Watts, Small Worlds, Princeton University Press, 1999.

[4] M. E. J. Newman, "The structure and function of complex networks," SIAM Review 45 (2003), 167-256.

[5] R. Albert, A. -L. Barabási, "Statistical mechanics of complex networks," Review of Modern Physics 74 (2002), 47-97.

「OR事典」の他の用語
グラフ・ネットワーク:  配送計画問題  被覆  付値マトロイド  複雑ネットワーク  分枝カット法  平面グラフ  辺分離定理

複雑ネットワーク

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/07/12 04:08 UTC 版)

複雑ネットワーク(ふくざつネットワーク、complex networks)は、現実世界に存在する巨大で複雑なネットワークの性質について研究する学問である。


  1. ^ 右田・今野 2011, p. 14.
  2. ^ 右田・今野 2011, p. 26.
  3. ^ 今野・町田 2008, p. 46.
  4. ^ a b c d 今野・町田 2008, pp. 12-13.
  5. ^ 右田・今野 2011, p. 142.
  6. ^ a b 右田・今野 2011, p. 146.
  7. ^ Watts, D.J., and Strogatz, S.H. (1998)
  8. ^ F Liljeros et al. "The web of human sexual contacts". Nature, 411, pp.907-908(2001) オンライン・ペーパー
  9. ^ A. Schneeberger et al. "Scale-Free Networks and Sexually Transmitted Diseases" Sexually Transmitted Diseases, 31(6), pp.380-387(2004) オンライン・ペーパー
  10. ^ Amaral, L.A.N. et al (2000) によれば、現実世界の全てのネットワークが完全なべき乗則の次数分布となるわけではない。辺が集中することで混雑などのコストが発生する場合は集中は頭打ちとなる。典型例は航空路線のネットワークである。
  11. ^ 「スモールワールド性」という用語の定義に関しては曖昧さがある。単にグラフの平均最短距離が小さい状態を指す場合もあれば、小さな平均最短距離と大きなクラスター係数とを共に満たす状態を指す場合もある。ランダムグラフは、前者の定義に従えばスモールワールドであり、後者に従えばスモールワールドではない。
  12. ^ Albert, R., and Barabási, A.-L. (2002)
  13. ^ a b 右田・今野 2011, p. 162.
  14. ^ 例えば Dorogovtsev, S.N. et al. (2002) や Klemm, K., and Eguíluz, V.M. (2002)
  15. ^ Reuven Cohen , Shlomo Havlin (Jul 2010), RobustComplex Networks: Structure,ness and Function, Cambridge University Press, pp. 120, ISBN 978-0-521-84156-6, http://www.cambridgejapan.org/academicproduct.html?isbn=9780521841566 
  16. ^ Albert, R. et al. (2000)
  17. ^ Solë, R.V., and Montoya, J.M. (2001)
  18. ^ Newman, M.E.J., and Girvan, M. (2004)
  19. ^ Costa, L.F. et al. (2005)






英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「複雑ネットワーク」の関連用語

複雑ネットワークのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

ゴホンツノカブト

RADIDEN

千匹猿透図鐔

ジョグZR

キハ2501

ウイングオーバー

セーラー

馬瀬川上流





複雑ネットワークのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2017 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの複雑ネットワーク (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2017 Weblio RSS