[本]複雑ネットワーク : 基礎から応用まで 1章・2章
書誌情報
増田直紀 &今野紀雄.(2010).複雑ネットワーク : 基礎から応用まで. 東京: 近代科学社.
最近だと、笹原和俊 (監訳)．(2023)．ネットワーク科学入門: Pythonで学ぶデータ分析とモデリング [原書名: A First Course in Network Science]．東京: 丸善出版
もでたとか。先輩は、笹原先生の方が少し優しめなので、並行して読むといいといわれました。
著者情報
増田直紀さんは、専門外の私もよく名前をお聞きするネットワークの先生ですね。
今野紀雄もネットワークの専門家っぽいです。研究実績を見ても私なんかではまだ全然理解できそうにないです。
注意
数学に関しては大学教養数学を独学で学んだレベル。そんな人間が読んだ感想だと思ってください。また、自分のメモ用なので、自分が分かっている部分は飛ばします。
内容
本書で触れないこと
グラフの可視化方法(p.4)、枝が実数値の太さを持つ場合(p.7)があげられてました。
だからといって、決して可視化を軽視しているわけではなく、べき則のプロットを説明する際には、いきなり累積分布・順位プロットを紹介するのではなく、ナイーブなプロット→区間を用いたプロット→累積分布→順位プロットと順に紹介されていくので、そのプロットを選択するモチベーションも学べるので理解しやすかったです。(私個人が、ナラティブな説明が好きとい傾向もあります)
1章
ノードや隣接行列、連結など基本的な用語解説に加え、近似・∝・O(N)になどの数学的な予備知識が説明されていました。
*私は、O(N)はすべて計算量を指す記号だと思っていて恥ずかしかった。
2章
ここから、ネットワークの特徴量に関する記述が始まります。
次数
あるノードが次数kをもつ確率をp(k)と考えることで確率分布や期待値の考え方を導入していた。
べき則
p(k)∝k ** (-γ)
おおくのネットワークの次数分布がこのべき則に従うから大事っぽい。ネットワーク界では、べき則をスケールフリーという。
2<γ<3程度であることが知られている。
なおγ<3で <k**2>が発散することがネットワークにおける多くの驚きをもたらしいているらしい。（詳しくは本書の数式を）
<k**2>を導入したのは、次数の分散を考えるためなのかな？と思った。
またγ<3で<k**2>は発散するので、分散はめっちゃでかくなって、テキトーにつくったネットワークが一般性を担保できないっぽい。今のところ、たくさん作って平均とるしかなさそう
平均距離(L)・クラスター係数(C)
クラスター係数に二つの定義が紹介されていた。
一つはよくある3角形の数を分子にとるもので、もう一つは社会学の推移性という概念に基づくものだった。(この本は結構、社会学の参考文献が多い)
L・Cともに実データではノードの数(N)をいじれないので、評価に際しては、次数を保持したまま、リンクを無作為に繋ぎ変えてLを評価する。
Lが小さくて、Cが大きいネットワークをスモールワールド・ネットワークという
*LはL∝logNならば小さいといっていい
次数相関
隣接する2点の次数が似る度合(知らなかった。)
次数相関が正ならばHomophilyを表象していると考えられる。
次数がkのノードvと、次数がk'である隣接ノードv'の次数分布を考える際、前者はp(k)でいいけど、後者はp(k')じゃダメ。P(k'|k)として考えないと。
そこから<kenn(k)>(隣接ノードの平均次数)まで求めていた。
ピアソンの相関係数で表す方法も紹介されていた。（一変数なので情報量は減るが、正負で判断できるというメリットがあるっぽい）
中心性
次数・近接・媒介・固有ベクトル中心性が紹介されていた。どれがいいとかではなく、全部使うべきなのかな？
コミュニティ構造
同じ集団内では密、集団間では疎なネットワーク。（クラスタリングの手法と似ているような気がするが、本書ではクラスター係数と区別するためにコミュニティというらしい）
①ギルバンとニューマンのコミュニティ検出法
所与のコミュニティ数に分かれるまで、媒介中心性の高いリンクを切断していく。→毎回、媒介中心性を計算するのでOがえぐい。
②ニューマンのコミュニティ検出法
1.N個のコミュニティに分ける.
2.Qが高くなるように２つのコミュニティをつなげていく
3.Qが最大であった分割を採用
Qとは？
→同じ集団内では密、集団間では疎な 程度を測る尺度
(実際に隣接しているか|{0,1})ー(隣接している確率)を比較した罰則項みたいなので評価している？
①はクイックソートのアルゴリズム、②はマージソートのアルゴリズムに似ている？
重なっているコミュニティに関しては参考文献があげられていた。
②の発展verは難しくてよくわからないので割愛（宿題）
モチーフ
あるネットワークに含まれやすい小さいネットワーク(=パターン)
例)三角形はCが高いネットワークのモチーフ
(知らなかった)
あるパターンがモチーフであるかは
あるネットワークにあるパターン数Nm
と
そのネットワークをつなぎ変えたネットワークNm randとを比較
実際には標準化した値を用いる
エコーチェンバーのモデルを作るときに使われるような三角形もモチーフなのかな？