はじめに

ネットワーク分析に興味をもち過去にこちらの書籍を読み、

ネットワーク分析第2版 (Rで学ぶデータサイエンス)

作者:努, 鈴木
発売日: 2017/05/24
メディア: 単行本

以下のような記事を書いていました。

qiita.com

複雑ネットワークについてだけ勉強していなかったので、書籍の続きを読みまとめます。

コードの詳細等は書籍を確認してください。

複雑ネットワークとは

複雑ネットワークとは、現実世界に存在する巨大で複雑なネットワークの性質について研究する学問です。

例えば、WEBサイトのリンク構造やSNSでのフォロー関係などのネットワーク構造について着目するような取り組みが挙げられます。

複雑ネットワークでは各頂点の指標について議論することは少なく、ネットワーク全体の構造を捉えるための指標はよく用いられると考えています。

ここでは代表的な指標をあげます。

指標

複雑ではないランダムグラフを例に考える。

ランダムグラフとは、グラフに含まれる２つの頂点の間に一定の確率で辺を張ると考えたグラフである。

Rでランダムグラフの生成をこなうにはsample_gnp()を用いる。

nで頂点の数、pで頂点間に辺を張る確率を指定する。

random_graph <- sample_gnp(n = 50, p = 0.1)

random_graph %>%  
  ggraph(layout = "circle") +
  geom_edge_link(alpha=0.8, colour = "lightgray") + 
  scale_edge_width(range = c(0.4,1)) +
  geom_node_point(aes( size = 2)) + 
  theme(legend.position = 'none')

f:id:saltcooky:20210418013356p:plain

次数分布

ランダムグラフのある頂点間に辺を張る確率はpで一定とする。

ある頂点が他の(n-1)個のうちk個の頂点とへんで結ばれ残り(n-1-k)個との間には辺がない確率は $p^k(1-p)^{n-k-1}$ である。

ランダムグラフの実数の確率分布は二項分布の形をとり、平均次数 $(k)=(n-1)p$ となる。

頂点を500個, 辺を張る確率をp=0.1として生成したランダムグラフの次数分布は次のようになった。

f:id:saltcooky:20210425163811p:plain

このグラフの平均次数は理論値では $(k)=(n-1)p=(500-1)×0.01=4.99$ になるはずであるが、実測値は次のように大体理論値と同じ値が得られた。

my_degree <- function(g){
  mean(degree(g))
}

my_degree(random_graph)
# [1] 4.92

平均距離

ある頂点から頂点の間の最短経路の辺の数が距離であり、全ての頂点同士の距離の平均が平均距離となる。

ランダムグラフにおける頂点同士の平均距離は $log n / log(k)$ で近似できる。

上記のランダムグラフの平均距離は次のようになった。

my_mean_distance <- function(g){
  g %>% 
    as_tbl_graph %>% 
    mean_distance()  
}

my_mean_distance(random_graph)
# [1] 2.566531

ランダムグラフにおける頂点や平均次数の関係を確認するために、次にようなグラフを作成した。

右がランダムグラフにおける頂点すうと頂点間距離の分布、左がランダムグラフにおける平均次数と頂点間距離の分布である。

f:id:saltcooky:20210425165028p:plain

左のグラフを見ると頂点数が十倍になると頂点間距離は一定幅で増加することから、平均距離はlog nに比例することがわかる。

右のグラフを見ると平均次数が大きくなるほど、頂点間距離は小さくなることがわかる。

クラスター係数

自分の友達同士は友達であるかのように、ある頂点に隣接した頂点同士の繋がりの度合いを示しているのがクラスター係数。

ある頂点 $i$ のクラスター係数 $C_i$ は、その頂点を含む三角形の数の理論的な最大値との比で求めることができる。

$\displaystyle{ C_i= \frac{頂点iを含む三角形の数}{k_i(k_i-1)/2} }$

そして、全体のクラスター係数は平均値をとることで計算することができる。

my_clust_coeff <- function(g){
  mean(transitivity(g, type="local"), na.rm = T)
}

my_clust_coeff(random_graph)
#[1] 0.1060253

クラスター係数と辺の発生pや頂点数Nの関係を確認するために以下のグラフをした。

pとクラスター係数は線形関係にあり、頂点の数によらないことがわかる。

f:id:saltcooky:20210424151232p:plain

複雑ネットワークにおける代表的なモデルと特徴

複雑ネットワークにおける2つの性質と代表的なモデルを2つ扱い、複雑ネットワークで表現するものを理解する。

フリースケール性

ウェブサイトのリンクのように、大規模なサイトは大量のリンクがあり多くのサイトとつながっているか、多くのサイトは少ないリンクしかない。

このようにリンクの分布がべき乗則に従っており、次のように表される。

$\displaystyle{ p(k) \propto \frac{1}{k^\gamma} }$

$\gamma$ はネットワークの特徴を表現する定数となる。

フリースケール性のあるネットワークでは、ランダムグラフのような次数分布にはならず、平均的な次数や平均との差の分布といった尺度は存在しない。

そのため、フリースケールネットワークと呼ばれている。

フリースケールネットワークの代表的なモデルはBarabasi-Albertモデル(以下 BAモデル)と呼ばれている。

BAモデルは(1)元となるネットワークに頂点と辺を順次追加していくことで生成すること、(2)ある頂点の次すうが大きいほど新しく加わる頂点から辺を張る相手として選ばれやすいという特性がある。

フリースケールネットワークはigraphパッケージにおいてsample_pa関数を用いることで生成することができる。

$m$ は新しく加わる頂点がいくつの辺を張るかを指定する。

$power$ は辺が張られる確率は入次数に対して何乗になるかを意味する。

以下に２パターンのスケールフリーモデルを生成した。

sf_graph <- sample_pa(n = 60, m = 1)
plot_graph(sf_graph, lo="kk") 

sf_graph <- sample_pa(n = 60, m = 2, power = 1.5)
plot_graph(sf_graph, lo="kk")

f:id:saltcooky:20210418214143p:plain

左図ではハブとなる次数の高い頂点が存在するが、ハブに接していない頂点も多く存在する。

右図ではハブとなる頂点にほとんどの頂点が接続している。

次にスケールフリーモデルにおける次数分布を確認する。

そのまま分布を可視化すると1が大多数をしめるため、両側対数グラフで表示する。

sf_graph <- sample_pa(n = 10^6, m = 1)
sf_graph_deg <- degree_distribution(sf_graph, mode = "in")
loglog_plot(sf_graph_deg)

この場合、理論的には $\gamma=3$ であり傾きが３の直線に近似できる。

実際にグラフを見てみると、傾きが３の直線に近い分布をしている。

f:id:saltcooky:20210418220903p:plain

ランダムグラフとの特徴の違いを確認するために次のような図を作成した。

f:id:saltcooky:20210424152434p:plain

BAモデルではハブとなる頂点への辺の集中が起きる。

そのため、任意の2頂点間に注目するとハブとなる頂点を経由してつながっていることが多くなり、ネットワーク全体の平均距離が短くなる傾向になる。

また、頂点の増加に伴う平均距離の増加がランダムグラフより小さいことも確認することができる。

これは上の左図で確認することができる。

次に、ハブとなる頂点経由で2頂点間は距離は近いが、互いにつながっていることは少ないため、クラスター係数は大きくならない。

これは上の右図で確認することができる。

スモールワールド性

友人の友人は友人であるように密度が高い集団に属していることが多いか、時に繋がりがない人と共通の友人がいるような場合も多い。

このようにネットワークにおける各頂点は高密度なサブグループに属しているにもかかわらず、異なるサブグループに属する2点間の距離は意外に小さいことをスモールワールド性と呼ぶ。

ランダムグラフは、頂点間距離が短いことを満たしているがクラスター度が低い状態にあり、スモールワールド性を満たすには不十分である。

スモールワールド性をうまく表現したモデルはWattsにより提案されたWatts-Strogatzモデルがあげられる。

Watts-Strogatzモデルは、はじめにクラスター度が高く平均距離が大きいネットワークとしてレギュラーグラフを作る。

以下の3つのグラフの左のグラフのようなネットワークである。

次にレギュラーグラフのの確変の一方の辺を一定の確率 $p$ で、他の頂点にランダムに架け替えることで得られるネットワークがWatts-Strogatzモデルとなる。

以下の真ん中のグラフは $p=0.2$ 、右のグラフは $p=0.9$ で辺を架け替えて得られたWatts-Strogatzモデルである。

f:id:saltcooky:20210415021101p:plain

$p=1.0$ とすると完全にランダムグラフになる。

pを変化させていくと頂点間距離が小さくクラスター度が大きいスモールワールド性を満たしたネットワークが得られることになる。

これを確認すると次のようになる。

平均距離はpが小さいうちは急激に変化する一方で、クラスター係数はpが大きくなるまで変化は緩やかであり、スモールワールド性が満たされたネットワークになっている。

f:id:saltcooky:20210418155254p:plain

また、Watts-Strogatzモデルのpを１に近づけていくと様々な頂点との架け替えが起こるようになるため次数分布はばらつきが大きくなっていき、ランダムグラフの指数分布に近くなっていく。

f:id:saltcooky:20210415021210p:plain

次数相関

科学論文の共著のネットワークのように、次数が高い頂点同士がつながりやすく、次数が小さい頂点同士はつながりにくいような状態になることがある。

このように次数の大きさが同じようなもの同士が結びつきやすいことを表現する指標として次数相関がある。

ランダムに一つの辺を選んだ時、両端にある頂点に接続している残りの次数を $j$ 本と $k$ 本の頂点につながっている場合を考えていくと、次数相関 $r$ は次のように定義される。

$\displaystyle{ r =\frac{\frac{1}{m} \sum_i j_i k_i -(\frac{1}{2m} \sum_i(j_i+k_i))^2} {\frac{1}{2m} \sum_i (k_i^2+j_i^2) -(\frac{1}{2m} \sum_i(j_i+k_i))^2} }$

次数相関はigraphパッケージにおいてassortativity関数を用いることで算出することができる。

sf_graph <- sample_pa(n = 10^6, m = 1, directed = FALSE)

assortativity_degree(sf_graph)
# [1] -0.007020434

ネットワークの形状と次数相関の関係を見るために、平均次数を変化させた場合のBAモデルとランダムグラフにおける次数相関を算出してみた。

f:id:saltcooky:20210424161740p:plain

ランダムグラフにおいてどの頂点も同じような次数を持つため、次数相関は一定となっている。

一方で、BAモデルでは次数が0に近い場合では負の相関を持つが、次数が大きくなるにつれて正の相関を持つようになる。

BAモデルでは次数の大きい頂点ほど新たに加わる頂点から辺が張られやすいため、平均次数が小さいときは次数の小さい頂点は次数の大きい頂点につながりやすくなり、負の相関が発生しやすくなる。

そして、平均次数が大きくなるとハブ以外の頂点同士もつながりやすくなるため、0に近い相関や正の相関をとるようになる。

最後に

次のようなことが気になりました。

複雑ネットワークを少し勉強すると、実際に使うには結局その統計量がどういう分布をしているのかが重要になってくるので、ネットワークのブートストラップ法を理解する必要が出てくる気がする
そこ手を出しちゃう〜？
— Tact (@saltcooky) 2021年4月11日

すると以下のような回答をいただきました。

難しそうですね。そうなるとちょっと活用する方法は考えないと行けなさそうです。

基本的に未解決なのであまり手を出さなくていいような気がします、、、
— kur0cky (@kur0cky_y) 2021年4月11日

ランダムグラフを仮定した平均次数の推定では例えば次があります。https://t.co/CLITvTCpGj

これはhorvitz-thompson推定量を利用して偏りを修正するようなものですが、他の統計量に利用しようと思うと同じアプローチでは限界があると思います。
— kur0cky (@kur0cky_y) 2021年4月11日

『理論的に完璧ではないけど筋のいい分布の推定はできるぐらいのレベルにも達していないんですかね？』
直感的なに思いつくノード単位のリサンプリングは昔から提案されているのですが、実際にはこれは厳しいと思います。（数値実験でも理論的な値からかなり遠くなる）https://t.co/jom0peC3MD
— kur0cky (@kur0cky_y) 2021年4月11日