複雑ネットワークの科学2章
複雑ネットワークの科学を読んで考えたことの覚え書きです。
グラフとネットワーク
空間的に離れた人々が、直接的な接触、交通手段、コミュニケーションを通じて交流する状況を把握するための数学的な手段には微分方程式とグラフ理論がある。微分方程式は各地点がその近傍の状況に応じて変化する現象の解明に優れている。一方、グラフ理論は、微分方程式での定式化が困難な複雑ネットワークの解析の道具である。伝統的なグラフ理論は小規模で、比較的整ったグラフを研究対象としてきた。それに対して、実ネットワークの扱いは社会学のネットワーク分析に長い伝統があり、さまざまな分析手法(ソシオメトリー)が提案されてきた。社会学が対象としたネットワークは、社会学者が主に人手によって収集してきたデータをもとにしたが、コンピュータ技術の発展とともに、人間に活動がさまざまな主にログとしてデジタルデータの形で入手することができるようになってきた。これにより、大規模なネットワーク解析に注目が集っている。
グラフ理論への入口
- グラフGは頂点の集合Vと枝(紐帯、弦ともいう)の集合Eからなる。*1
- 頂点の次数と総枝数の関係: 次数の合計は枝の数の合計のちょうど倍
- 次数分布の確率密度: p(k) = グラフ内の頂点のうち(次数=k)となるものの割合
グラフのさまざまな特徴量
- 平均頂点間距離
- クラスター係数*2: 内輪のつながりの濃密さを表す。各頂点について、二つの隣接頂点間に枝がある確率を求め、それをグラフ全体の頂点について平均したものがクラスター係数。直感的に言えば、友達の友達が友達である割合。あるいは、グラフの規模に対して、グラフ内の枝が構成する三角形の個数の割合とも言えるかもしれない。
※1) クラスターという言葉はネットワーク解析においては、この意味で用いられる*3が、データマイニングなどでは別の意味をもって使われる。ぼくらのようにネットワークのクラスター化に関する研究をしている場合には特に注意を要する。
※2) クラスター係数は、ここでは隣接頂点たちが三角形を構成するか否かという視点から与えられたが、これをより一般化できる。たとえば、頂点v0の隣接頂点v1とv3がともにv0以外の共通の隣接頂点v2を持つときに、四角形のクラスターv0-v1-v2-v3を構成することができる。このようにして構成される四角形の割合を計算することでクラスター係数の概念をより一般化することができる。しかし、より複雑なクラスターを対象とすることで、計算量は爆発的に増加するだろう。
- 平均次数: 各頂点の次数の平均。例：友人の数の平均。
