複雑ネットワークとは何か 複雑な関係性を読み解く新しいアプローチ 読書メモ

複雑ネットワークとは何か 複雑な関係性を読み解く新しいアプローチ

複雑ネットワークとは、多数の要素が相互につながり合った、非常に複雑な構造を持つネットワークのこととなる。そのようなネットワークは、単純な規則性だけでは説明できない非線形な相互作用によって構成されており、スケールフリー性、スモールワールド性、階層性などの特徴を持っている。スケールフリー性は、一部のノードが非常に多くのリンクを持ち、他の多くのノードがわずかなリンクしか持たないことを示し、スモールワールド性は、短い距離で多くのノードに到達できることを示す。

複雑ネットワークの研究は、多数の要素が相互に影響しあっている現象を理解するために役立ち、複雑ネットワークの解析には、グラフ理論、統計力学、情報理論、ネットワーク科学などの手法が使われ、社会ネットワーク、物理学、生物学、情報科学などの分野に適用されている。

今回はそのような複雑ネットワーク技術の入門書である「複雑ネットワークとは何か 複雑な関係性を読み解く新しいアプローチ」 から読書メモを示す。

まえがき
第１章　ネットワークのはじまり──グラフ理論の誕生

1.1 橋の街のケーニヒスベルク

大数学者オイラー
グラフ理論の始まり
グラフ理論のその後
1.2 グラフ理論の父、ハラリー
近代グラフの萌芽
グラフ理論の強さと弱さ
1.3 ネットワークは複雑
小さなネットワークの理解
ネットワーク科学の考え方

第２章　ネットワークの格子模様──碁盤目とその仲間

2.1 木グラフ

ケーリー・ツリー
ベーテ格子
「木」
2-2 碁盤目な格子たち
正方格子

結晶格子

格子いろいろ

六角格子

三角格子

カゴメ格子
2-3 ゲームと格子
ボードゲームと格子
ダイヤモンドゲーム

コンピューターゲームと格子
2-4 現実と格子

正方格子は近道が存在しない

第３章　ネットワークの距離──ベーコン数とエルデシュ数

3-1 ベーコンとエルディッシュ
ベーコン数
共演者で行き着く
エルディシュ数
論文の共著の和
3-2 ベースボールの神託
ベースボールのネットワーク
ネットワークの距離

ネットワークの平均頂点距離
全頂点での頂点と頂点を結ぶ最小の距離
全ての頂点対の距離の平均
頂点が7個あり、頂点対は21
1 x 10/20 + 2 x 9/21 + 3 x 2/21 =34/21
正方格子では平均距離が大きすぎて現実的ではない
現実的な例では平均距離は小さくなる
木は十分小さい平均距離を持つ
3-3 ランダム・グラフ

木の課題
ある頂点からある頂点へいく道が一つしかない
ランダムネットワーク
乱雑さを持つ
各2点間(n(n-1)/2)で確率pで枝をおき、確率1-pで置かない
Pが小さいとネットワークは分断するが、pがある程度だと全点がつながる
平均距離は小さい
現実から遠い

ネットワークの比較

第４章　世界はせまい!?──スモールワールド

4-1 スモールワールド実験
イッツアスモールワールド
人と人との距離
ミルグラムのスモールワールド実験
手紙で実験
ミルグラムの実験の難点
実際に到達した手紙が少なかった
ワッツのスモールワールド実験
ウェブで実験(電子メール)
スモールワールド実験のメッセージ
人と人とを結ぶ近道が存在している
動機として人の好奇心がある
4-2 内輪付き合い
ワッツとストロガノフ
クラスター性に注目
共通の友達

クラスター性
比較的人数が少なくて密な関係

クラスター性を測る
クラスターの素単位は三角形
クラスター性の大きさ(クラスター係数)
枝の使いすぎもいけない

完全グラフ

クラスター係数1
次数が大きすぎる
4-3 スモールワールド性
スモールワールド再考
正方格子も変形するとクラスター性として見れる

ネットワークの比較
4-4 スモールワールド・ネットワーク

ワッツとストロガッツのアイデア

近道の導入
近道を少し加えるとネットワークの平均距離が劇的に小さくなる
クラスター性は変わらない
小さい平均距離+高いクラスター性=スモールワールド
一次元格子
一次元格子からスタートしてワッツ・ストロガッツモデルを生成
スモールワールド・ネットワークの作り方
枝を切ったり、加えたりする操作(枝のつなぎ変え)をランダムに行う
4-5 宴会ゲーム
山手線ゲーム
ショートカットのない一次元格子
平均距離が大きい
驚きが少ない
ドビンチャゴンハゲチャビンゲーム

ネットワーク表現
ショートカットが刺激をもたらす
せんだみつおゲーム

ショートカットだらけ
4-6 すごろくと人生

昔のすごろく

抽象化
ランダムグラフのようなすごろく
すごろくは有向グラフ
平均距離を小さく作る(例4)
一次元格子のようなすごろく
伝統的なボードゲーム

第５章　世界は不平等!?──スケールフリー

5.1 ベキ則
バラバシ
ネットワークの不規則さ、乱雑さに注目
頂点の次数のバラツキ
次数分布はベキ則に従っている

ベキ則とは
1/kのγ乗
ベキ則と指数則

Kが大きくなると値がともに減るが指数則は減り方が圧倒的に大きい

パレートの法則
分布がベキ作になる例
5-2 スケールフリー・ネットワーク

ネットワークのベキ則
次数分布がベキ則になる
スケールフリー性
次数のベキ則
特徴的なスケール(縮尺)がない(フリー)
特徴的なスケール
釣鐘型分布の時の平均値や分散
実世界の例
ランダムネットワークやスモールワールドネットワークでは次数が釣鐘型や指数則に従う
ネットワークの動き
インターネットのネットワーク

成長するネットワーク
枝のみが変わるネットワーク
変化しない(静的な)ネットワーク

BA(Barabashi-Albert)モデル
成長するネットワーク
遊覧的選択
成長と優先滝選択
新しい頂点が生成される
頂点は枝を持って入る
枝の接続先は「優先的選択」でランダムに付けられる
優先的選択
先に存在している頂点の中で、次数の大きいものが優先的に新しい枝を受け取りやすくする
成長の振る舞い

一般化ランダムグラフ
木に似たスケールフリー・ネットワーク

一般化ランダムグラフの作り方
頂点配置ルール

コンピューターのディレクトリ構造
別名:ゴルドン・ワトソン木

コンフィギュレーションモデル
前もって(次数分布を)設定した置いたモデル
仕組まれたフリースケール性
5-3 ハブ
ハブとは
次数が非常に大きい頂点
スケールフリー・ネットワークにはハブがあり、釣鐘型や指数型の次数を持つネットワークにはハブがない
スモールワールドネットワークにはハブがない

スケールフリーが全てではない

小さい平均距離と高いクラスター性の組み合わせ(スモールワールド)は、 ほとんどの実世界のネットワークが持っている
フリースケールは普遍的ではない
ネットワークの比較
5-4 次数相関

次数のバラツキ
正の相関
ハブとハブが結びつきやすい
例
友人関係
ビジネスの協働関係
負の相関
ハブとハブが結びつきにくい
例
インターネット
WWW
電気回路
タンパク質の化学反応
脳内ネットワーク
生態系の捕食・被食
次数相関が0
BAモデル
スモールワールドネットワーク
ランダムグラフ
5-5 コミュニティ
人間社会のコミュニティ

コミュニティネットワークから決める

ネットワークのコミュニティ

ネットワークのコミュニティの解析例

第６章　伝染病から身を守る──感染経路と予防接種

6-1 人間の伝染病との戦い
感染症とは
6-2 感染症の従来のモデル

ネットワークを無視したSIRモデル
健康なSグループ
病人のIグループ
病気だったが回復して免疫を持ったRグループ
正方格子のSIRモデル

ボンド・パーコレーション

SIRよりも単純なネットワーク型感染症モデル
ボンド(枝)
ある確率pで枝が通るかどうかが決まる

サイト・パーコレーション
各頂点に確率pで患者候補がいる
Pがある程度以上だと大規模な観戦になる

SISモデル
RがなくてSとIを往復するモデル
6-3 感染症のネットワークモデル

現在はスモールワールド
スモールネットワーク上の感染

モデルによる感染の違い

スケールフリーネットワークと感染
ハブとスーパースプレッダー
ハブが感染を罰初させる
ネットワークの近代化と感染症の近代化
6-4 公衆衛生とネットワーク倫理
ワクチンと予防接種の政策
ハブ優先策
ハブ優先の技術面

第７章　通信ネットワーク──インターネットと携帯電話

7.1 コンピューターウィルス

インターネット上の感染
インターネットは典型的なフリースケール・ネットワーク
スモールワールド性も兼ねている
臨界確率は小さく、ウィルスの蔓延が起きやすい

偶然の故障とパーコレーション
壊れたコンピューターと昨日しているコンピューターが混在している様子は、 サイト・パーコレーションの問題に置き換えれる
中央集権型は故障に弱い
分散型は故障に強いが平均距離が長くなる
スケールフリーネットワークは平均距離が小さく、 ハブへの集中も極端ではない
フリースケール・ネットワークの頑強性
意図的な攻撃とパーコレーション
意図的な攻撃に対してはフリースケール・ネットワークは弱い
7.2 無線と携帯

携帯電話の進歩
携帯電話のネットワーク
携帯電話=中継局
7.3 ミクシィ
ソーシャルネットワーキングサービス
ミクシィ
ミクシィはスモールワールド
ミクシィはスケールフリー
ネットワーク科学の汎用性

第８章　生命を支える──ニューロンとタンパク質

8.1. ニュラルネットワーク
ニューロン
ニューロン上の計算
化学シナプスという繋がり方

ギャップ・ジャンクションという繋がり方

化学シナプスは、軸索は鞘に覆われた細い糸のようなものなので、 他の細胞を通り越して遠くのものと連絡することができる

化学シナプスはネットワークのショートカットになる
ギャップジャンクションによる相互作用では、 片方から他方へと自由に信号を送ることはできない
隣り合う2つのニューロンの内部状態の差を縮めるように働く

第９章　ビジネスを生き抜く──黒幕とエリートの社会

付録：ネットワークを描いてみる
参考文献