📢 Webサイト閉鎖と移転のお知らせ
このWebサイトは2026年9月に閉鎖いたします。
新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）
ページの作成:「== 概要 == * グラフ理論の周辺分野の概要について理解する。 * グラフの種類の概要について理解する。 * グラフ理論上の問題…」 |
|||
| 165行目: | 165行目: | ||
*: 安定的マッチングとは、離婚する可能性の低いペアの集まりのことである。 | *: 安定的マッチングとは、離婚する可能性の低いペアの集まりのことである。 | ||
*: 現実的な応用が多数存在する問題で、医師臨床研修マッチング制度などがある。 | *: 現実的な応用が多数存在する問題で、医師臨床研修マッチング制度などがある。 | ||
<br> | |||
===== インターネット関連グラフ問題 ===== | |||
コンピュータを点とし、コンピュータ間の回線を辺で表すとインターネットのグラフができる。<br> | |||
このグラフの構造を調べることでインターネット上の様々な事象を解明しようとする研究がある。<br> | |||
<br> | |||
例<br> | |||
* WWWにおけるハイパーリンクで繋がれたドキュメント全体の構造 | |||
* インターネットの接続構造 | |||
* SNSのコミュニティ構造 | |||
<br> | |||
===== 複雑ネットワーク問題 ===== | |||
複雑ネットワークとは、現実世界に存在する巨大で複雑なネットワーク、<br> | |||
あるいはそれらネットワークの性質について考察する問題および分野のことである。<br> | |||
<br> | |||
複雑ネットワークは、現実世界の様々な現象を説明するためのパラダイムの1つである。<br> | |||
<br> | |||
例<br> | |||
* WWW | |||
* 食物連鎖ネットワーク | |||
* 論文の被引用関係ネットワーク | |||
* 映画俳優の共演グラフ | |||
* 線虫の神経回路網グラフ | |||
* 送電網グラフ | |||
<br> | |||
複雑ネットワークの性質<br> | |||
* スモールワールド性(一見赤の他人に見えても、実際は中間に少数の人を介するだけで繋がっているという性質) | |||
* スケールフリー性(一部の人は非常に多くの知人を持っているが、大多数の人々は知人の数は少ないという性質) | |||
* クラスター性(多くの人が互いに知り合いであるようなグループが存在するという性質) | |||
<br> | |||
複雑ネットワークのグラフモデル<br> | |||
* スモールワールドモデル(スモールワールド性を持つグラフのモデル) | |||
* バラバシ=アルバートモデル(スケールフリー性を持つグラフのモデル) | |||
<br> | |||
スモールワード現象<br> | |||
スモールワールド現象とは、世界中の人の中から任意に2人を選んだとき、その2人は驚くほど少ない知人を介して繋がっているという現象。<br> | |||
<br> | |||
例<br> | |||
ベーコン数とは、アメリカの俳優ケヴィン・ベーコンと映画で共演したことのある俳優のベーコン数を1、<br> | |||
ベーコン数nの俳優と共演関係にある俳優のベーコン数をn + 1とする。<br> | |||
世界中の俳優のベーコン数を調べると大多数がベーコン数3から4の範囲に収まる。<br> | |||
<br> | |||
スモールワールドネットワーク<br> | |||
スモールワールド現象に関連する具体的なグラフはスモールワールドネットワークと呼ばれる。<br> | |||
<br> | |||
特徴<br> | |||
* 頂点の数に対して辺の数が少ない。 | |||
* 2頂点間の距離の平均は意外と小さい。 | |||
* 小さなクラスターがたくさんある。 | |||
<br> | |||
病気の感染や噂の伝達が驚くほど速いのは、人々がスモールワールドネットワークで繋がっているからだと考えられている。<br> | |||
<br><br> | |||
== 様々な事象をグラフで表すことのメリット == | |||
* グラフに表すことで、複雑な事象の全体が視覚的にとらえられ、理解しやすくなる。 | |||
* 全体の構造を把握しやすくなる。 | |||
* 各点の特徴がとらえやすくなる。 | |||
<br> | |||
以上のメリットにより、社会の複雑な現象の解明に役立つ。<br> | |||
<br><br> | <br><br> | ||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||