ネットワーク科学を読んで
サムネはお絵描きばりぐっとくん
スラムの課題図書
用語
スラムの友だちネットワークで例える
ノード
スラム民のこと
ノードの総数はNで表される
リンク
友だち関係のこと
例えば、「ノードAとノードBが友だちなら、AB間にリンクがある」という
次数
各ノードのリンク（友だち）の数
記号はk
平均次数
平均的な友だちの数
記号は<k>
ハブ
次数がとても高いノード、つまり友だちがめっちゃ多い人のこと
ネットワークと連結成分の違い
ネットワークはノードとリンクの全体のこと
連結成分はリンクでつながっている塊のこと
ネットワークは全スラム民およびそのつながりであり、連結成分は友だち関係でつながっている塊（以降は「群れ」と呼ぶことにする）と考えることができる。
つまり、「スラム内で友だち関係がない人は、スラム民だが、群れの一員ではない」ということになる。
ざっくり全体の説明
この本は、（カレーをスパイスから作るように）現実のネットワークを0から作ろうとしている。まず、モデル（ネットワークの設計図）を作り、シミュレーション（コンピュータを使って設計図どおりにネットワークを作成）し、手作りネットワークと現実のネットワークの特徴（友達の人数の分布など）を比較することで、モデルのできを評価する。んで、欠点があったら、それを補う仕組みをモデルに組み込んで、シミュレーションして、現実のネットワークと比較して...の繰り返し。
第3章
ランダムネットワーク・・・まずノード（人）があって、ランダムにリンクを張る（人と人がお友だちになる）。
欠点 現実のネットワークにはハブ（友達がめっちゃいる人）がいるけど、ランダムネットワークにはハブが存在しない。
第4章
ハブのないランダムネットワークから、ハブのあるスケールフリーネットワークに変更して、モデルを改善しよう！
第5章
現実のネットワークにあって、ランダムネットワークにないもの。それは、「成長」と「優先的選択」だ。
成長・・・ネットワークには新たに人が増えていく。
優先的選択・・・新しいノードは、次数が高いノード（友だちが多い人）と結びつこうとする。
バラバシ・アルバート・モデル・・・「成長」と「優先的選択」を組み込んだモデル
なんと「成長」と「優先的選択」をモデルに組み込むと、スケールフリー（次数がべき分布）になることが判明❗️
どちらか片方がモデルに入っていないと、スケールフリーネットワークにならないこともシミュレーションで検証済み。
欠点 バラバシ・アルバート・モデルだと、次数最大のノードを追い越して、新たなノードが最大次数になることはない。しかし現実は諸行無常。時代によってトップは変わる。
第6章
ビアンコーニ・バラバシ・モデル・・・各ノードに適応度（他との結びつきやすさ）を組み込んだモデル
適応度を導入することで、新人が次数で古参を追いこすことが可能に。「生まれつきの人気者」の概念を取り入れる。
バラバシ・アルバート・モデル（BAモデル）の欠点
1. BAモデルの次数分布は傾きが固定であるが、実際のネットワークでは傾きに幅がある。
2. BAモデルの次数分布はべき分布（以下の図の赤線のように直線）であるが、実際のネットワークは、「低次数の飽和（赤線より低くなる）」と「高次数のカットオフ（次数の高さに制限がある）」がある。
3. 現実のネットワークでは、リンクが付け加えられたり、ノードが除去されたりするが、BAモデルではそのような基本的な過程が無視されている。
画像非公開
『ネットワーク科学』第4章 図4.23 次数分布のスケーリング
初期誘引度・・・BAモデルの優先的選択に定数を加えて、次数0のノードにもリンクが張られるようにする。
BAモデルの優先的選択の場合、次数0のノードにリンクが張られる確率はゼロである。
→ 低次数にリンクが張られる確率が高まるため、ノードの次数が押し上げられ、低次数の飽和が起こる。
内部リンク・・・新規ノードだけではなく、元々存在するノード間にもリンクを張る。
ノード除去・・・その名のとおり。
加速成長・・・リンクを追加するスピードが、ノードを追加するスピードよりも速くなる。
加齢・・・新しいリンクを獲得する比率が次第に減っていく。
画像非公開
『ネットワーク科学』第6章 図6.15 ネットワークのトポロジーに影響を与える基本過程
以上のようなさまざまな素過程がネットワークの特徴に影響を与える。γは次数分布の傾き。素過程を加えることによって、傾きは変化する。
第7章
同じ次数分布でも異なる次数相関をもつネットワーク
次数親和的なネットワーク・・・ハブはハブ同士、低次数のノードは低次数のノード同士でつながりやすい。
次数排他的なネットワーク・・・ハブは低次数のノードとつながりやすい。
ニュートラルなネットワーク・・・ランダムにつながる。
優先的選択ではリンク数の期待値がノードの次数に比例するため、ハブ間のリンク数の期待値が1以上になる場合がある。しかしBAモデルでは、ノード間にはリンクが1つしかつかない。この矛盾が高次数のカットオフを引き起こす（次数分布の傾きがBAモデルよりも緩やかである場合にのみ起こる）。
次数親和的なネットワークでは、ハブ除去によるダメージはより小さくなる。なぜならハブ自体がコアなグループを形成しており、冗長性があるためである。逆に次数排他的なネットワークではハブ除去によるダメージは大きくなる。なぜなら、ハブは数多くの小さな次数のノードとつながっており、ハブが一つ取り除かれるだけでネットワークがばらばらになりうる。
第8章
ネットワークの頑健性
頑健性とは、ある一つのノードを選択して、そのノードとそのノードから出ているリンクをネットワークから取り除いたときの、ネットワークのバラバラになりにくさのことを意味してる。ランダムな故障やハブを狙った攻撃（最大次数のノードから順に破壊）に対して、どれくらい強いかという実用的な話。例えば、スケールフリーネットワークだと、ランダムな故障に対しては強く、ハブを狙った攻撃には弱い。
スケールフリーにはせずにノードの繋げ方を工夫してやると、ランダムな故障にも、ハブを狙った攻撃にも強いネットワークを作ることができる。
ランダムな故障とハブを狙った攻撃の両方への頑健性を最大化するネットワークの次数分布は二峰性分布（山が2つある分布）である。もっというと、最大次数のノードが1つだけ、その他のノードは全て最小次数である。
このハブ・アンド・スポーク型のトポロジーは明らかに無作為な故障には強いということであった。すなわち、中央のハブが故障する確率は1/Nであり、Nが大きい場合は無視できるほど小さい。
一方で、この得られたネットワークは攻撃に対して脆弱であるように見える。しかし、必ずしもそうとはいえない。実際、ネットワークの最大連結成分は中央にあるハブと『低次数のノード』を、『低次数のノード』が補うように形成されている。それゆえ、『最大次数であるハブ』の除去は確かに一時的に大きい損失となりうるが、それら低次数ノードは続く選択的な攻撃に対して頑健である（図8.24c）。
※『』は表現を変更
画像非公開
『ネットワーク科学』第8章 図8.24 攻撃と故障への耐久性の最適化
横軸はリンクの除去率。縦軸はノードをランダムに選択したときに最大連結成分内のノードである確率。
二峰性分布の場合、平均次数2のときは攻撃に対して弱いけど、3以上だとどちらに対しても強いね
第3章 ランダム・ネットワーク
手始めに単純なモデルを考える。
ランダムネットワークとは
スラム民N人に対して、確率的にリンクを張る（友だちになる）ネットワーク
ランダムネットワークの特徴
よこ軸は平均次数<k>、つまり平均的な友だちの数
たて軸は最大の群れの割合
（最大の群れの人数）÷（スラム民の総数）
リンクがないはじめは0
1つの群れに全員がつながると1になる
画像非公開
『ネットワーク科学』第3章 図3.7 ランダム・ネットワークの成長
<k>が0以上1未満: 赤領域。とても小さな群れが少しだけある
<k>が1: 巨大な群れができる境目
<k>が1以上4.5未満: 黄領域。1つの巨大な群れができ、小さな群れが巨大な群れに繋がっていく
<k>が4.5以上: 青領域。1つの巨大な群れができ、小さな群れが巨大な群れに繋がっていく
スラム内の友だちの数の平均が1人を超えると、急激に巨大な群れが形成される（赤領域と黄領域では増加の仕方が全く変わることがポイント）
黄領域と青領域の境目はスラム民の総数Nによって違う
<k> = ln(N)
ランダムネットワークを作ってみた
N = 500
外側にドーナツ状にいるのが、ぼっち。
真ん中のひとびとがムレムレしてます。
ランダムネットワークによって正確に記述されるような現実のネットワークは知られていない
この結論に対して次のような疑問が投げかけられるべきであろう。もし現実のネットワークがランダムでないのであれば、なぜ私たちは丸々1章もランダム・ネットワークモデルに費やしたのか、と。その答えは単純である。このモデルが現実のネットワークの性質をこれから探求する上で重要な比較・参照すべきものであるからである。ネットワークの性質を観察するたびに、もし仮にこれが偶然生み出されたものだとしたら、と問わなければならないだろう。このためいつもガイドとしてのランダム・ネットワークに立ち返る。もしある性質がランダム・ネットワークに存在していないとすれば、何か別の秩序を表すのであって、より深く掘り下げて説明することが求められる。したがってランダム・ネットワークモデルは多くの現実のシステムにおいては誤ったモデルかもしれないが、ネットワーク科学においては重要であり続けるのである。
第4章 スケールフリーの性質
多くのネットワークにはスケールフリー性（友だちの数の分布がべき分布になる）が見られることがわかった。
ランダムネットワークではハブは説明できない
著者の昔話
実際のWWWのネットワークの次数分布を取得した。『そのデータを見たとき、我々は本当に驚いた。そこで見たものは、ランダムネットワーク理論の予測するポアソン分布ではなかった。そのかわりに、私たちを出迎えてくれたのは、べき則であったのである。』『べき則の次数分布をもつネットワークのことなど文献には何の記述もなかったのである。実際のところ、この時点まで、次数分布に注目するものなど誰もいなかった。ランダム・グラフの文献と社会ネットワークの文献の双方とも、ポアソン分布を当然のものとしていた。我々が見ているべき則は、WWW上には膨大なリンク数をもつノード、すなわち、ハブが存在することを示していた。ハブのようなはずれ者はランダムな世界では存在が許されない。ハブを説明できるモデルは存在しなかったのである。』
※『』内が本文の引用
スケールフリー性をもつネットワーク
インターネット（通信するための物理的装置のネットワーク）
WWW（URLのネットワーク）
携帯電話の発信
電子メール
共同研究
俳優の共演
論文引用
大腸菌の代謝
たんぱく質の相互作用
スケールフリーでないネットワーク
電力網
材料の原子間結合
Cエレガンス（線虫）の神経ネットワーク
第5章 バラバシ・アルバート・モデル
成長と優先的選択
ランダムネットワークが現実のネットワークと異なるのはなぜか？
それは以下の現実のネットワークの2つの特徴を満たしていないからである。
成長
時間が経つごとにノード（人の数）が増えていく。優先的選択
新しいノードは多くのリンクをもつノード（友だちの多い人）に繋がろうとする。
成長と優先的選択を組み込んだモデル（バラバシ・アルバート・モデル）がスケールフリー性を生み出すことが発見された
成長と優先的選択のどちらか片方が欠けているとスケールフリー性は生まれない
第8章 ネットワークの頑健性
電力網の頑健性
平均次数（ノードが持つ平均のリンク数）が低い電力網の方が、安定した電力供給を行なっている
頑健性とは、ある一つのノードを選択して、そのノードとそのノードから出ているリンクをネットワークから取り除いたときの、ネットワークのバラバラになりにくさのことを意味してる。ランダムな故障やハブを狙った攻撃（最大次数のノードから順に破壊）に対して、どれくらい強いかという実用的な話。例えば、スケールフリーネットワークだと、ランダムな故障に対しては強く、ハブを狙った攻撃には弱い。
スケールフリーにはせずにノードの繋げ方を工夫してやると、ランダムな故障にも、ハブを狙った攻撃にも強いネットワークを作ることができる。
画像非公開
『ネットワーク科学』第8章 図8.26 電力網
ヨーロッパの電力網ネットワークの頑健性
画像 図8.26(f)
横軸: 平均次数
縦軸: ネットワークの寸断に必要なノードの割合（以降、fと表記する）
※fはハブを狙った攻撃が起きたと想定したときの推定値
点は、実際の33ヶ所の電力網
曲線は、次数分布が実際の電力網ネットワークと同じな一般的なネットワーク（その他の実際のネットワークの特徴は同じにしていない。）
グループ1は、実際のネットワーク（点）と一般的なネットワーク（曲線）のfは大体同じ。
グループ2は、実際のネットワークの方が一般的なネットワークより、ネットワークの寸断に必要なノードの割合（f）が大きい。つまり頑健性が高くなっている。
停電についての情報を比較してみると、グループ1は、頑健性が高くなっっているグループ2に比べて、電力損失が2倍以上、電力未供給が4倍以上、平均中断時間が5倍以上になっている。
つまり、平均次数の低い（けど、頑健性が一般のネットワークより高い）電力網の方が、安定した電力供給を行なっている。
文献
この記事が気に入ったらサポートをしてみませんか？