グラフとネットワークモデル

ふと思い立ったのでグラフについてまとめてメモしておきます.

グラフとは

複数の要素の関係性を表現するためのデータ構造をグラフと呼ぶ.
グラフはエッジとノードの集合で記述される.

エッジには方向を持つものや重みを持つものも存在し,例えばノード間の距離等の移動コストなどが重みとして付加される.

f:id:Takuya-Shuto-Engineer:20190801133209p:plain
無向グラフ
f:id:Takuya-Shuto-Engineer:20190801133244p:plain
有向グラフ
f:id:Takuya-Shuto-Engineer:20190801133321p:plain
重み付き有向グラフ

ケーニッヒスベルクの橋

グラフ理論の起源となる問題「7つの橋をそれぞれ一回だけ渡って全ての橋を渡ることができるかどうか(一筆書き)」
グラフ理論の祖(ポケモンで言うとアルセウス,モンハンで言うとミラルーツレオンハルト・オイラーは不可能であると結論付ける.

f:id:Takuya-Shuto-Engineer:20190801133501p:plain
ケーニッヒスベルクの橋

グラフモデル

現代の社会に転がっているようなデータ(ソーシャルデータ)の多くは,グラフで記述することが可能である.実世界をグラフでモデル化し,構造を把握しようという目的から多くのグラフモデルが提案されている.

ソーシャルデータの例

  • Webページ
  • 道路交通ネットワーク
  • 購買履歴

など

ERモデル

ランダムなネットワークモデル

特徴

  • 最もシンプルなモデル
  • 全ノード間に一定確率pでエッジを張る
  • ランダム性を持つグラフ
  • エッジ生成確率を1.00にすると完全グラフ(全ノード間にエッジ)になる

f:id:Takuya-Shuto-Engineer:20190801134532p:plain
ERモデル
完全グラフ

必要なパラメータ:

  • ノード数n, エッジ生成確率p

アルゴリズム:

  1. ノードをn個作る
  2. ノードペア \binom {n} {2} (n個から2個を抽出する組み合わせ)の中から一つ選択し,確率pでエッジを張る
  3. 2の処理を全てのノードペアに対して行う

ランダム性を持たせて生成するという最も単純な考えの元作られたモデル.でも,現実にあるデータってこんなランダム性はもっていないので実用性が低い.

ソーシャルネットワークが持つ性質

ERモデルでは,ソーシャルネットワークのモデル化が困難である理由は,ソーシャルネットワークが持つ以下の三つの理由からくる.

  • スケールフリー性: 次数の分布が極端に異なる
  • クラスタ: 三部クリークを含む比率が高い
  • スモールワールド性: 平均最短経路長が短い

グラフモデルを評価・検討する上で,ランダムなERモデルと比較して上記の三つの性質が現れるかどうかを評価する必要がある.

BAモデル

スケールフリー性を持つようなグラフモデル.
特徴:

  • 次数分布が冪乗則に従う
  • 中心にいる人気者は少数派であり,多くは狭い友好関係の中で生きている(悲しい)

f:id:Takuya-Shuto-Engineer:20190801140658p:plain
BAモデル
f:id:Takuya-Shuto-Engineer:20190801140611p:plain
次数分布

必要なパラメータ:

  • ノード数𝒏,初期ノード数 n_0,平均次数𝒌(𝒌≤n_0≪𝒏)

アルゴリズム:

  1. 𝒏_𝟎個のノードからなる完全グラフを作る
  2. 新しいノード𝒗を1つ追加する
  3. 既に存在しているノードから,優先選択確率𝒑(𝒖)に従ってkノードを選択し,ノード𝒗からエッジを張る
  4. 2 ~ 3をノード数がnになるまで繰り返す.

ここでは,優先選択確率というものを導入している.

 𝒑(𝒖) = \frac {d_u} {\sum_{u \in V} d_u}

この式は,「既に友達がたくさんいる人には友達がさらに増える友達がいない人には今後も友達が出来ない」というマタイ効果のようなものを再現している.

f:id:Takuya-Shuto-Engineer:20190801151053p:plain
BAモデル生成過程

生成したモデルを見ても,中心となるようなノードが3つほど出てきたのがわかる.

スケールフリー性に関しては,日本人のTwitterの特異性に触れた面白い論文がある.
S. A. Myers et al., ”Information Network or Social Network? The Structure of the Twitter Follow Graph,” In Proc. WWW 2014.

この論文では,Twitterは日本人ユーザのせいでソーシャルネットワークの要件を満たせない可能性があることを示唆している.
日本には相互フォロワー1000人くらいの人たちの集団,いわゆるクラスタがたくさんあるせいで,Twitter全体の分布に影響を与えてしまっているらしく,分布の冪乗則を脅かしているらしい.集団で集まるのが大好きな国民性があるのかも.

f:id:Takuya-Shuto-Engineer:20190801143616p:plain
相互フォロワー分布

HKモデル

クラスタ性を持つグラフモデル.

特徴:

  • 三部クリーク(三角形)を多く含む
  • 友達の友達が自分の友達である割合が高い
  • BAモデルの改良版

f:id:Takuya-Shuto-Engineer:20190801144245p:plain
友達の友達が自分の友達(三部クリーク)

f:id:Takuya-Shuto-Engineer:20190801144337p:plain
HKモデル(三角っぽく)
f:id:Takuya-Shuto-Engineer:20190801144405p:plain
HKモデル(円状)

HKモデルはBAモデルの改良版であるため,スケールフリー性も確保している.アルゴリズムを見ればより理解しやすい.

必要なパラメータ:

  • ノード数𝒏,初期ノード数 𝒏_𝟎,平均次数𝒌,確率𝜷

アルゴリズム:

  1.  𝒏_𝟎個のノードからなる完全グラフを作る
  2. 新しいノード𝒗を一つ追加する
  3. 以下の処理に従いノード𝒗から𝒌本のエッジを張る
    • 優先選択確率𝒑(𝒖)に従いノード𝒗^′を選択しエッジを張る
    • 残りの𝒌−𝟏本は以下に従いエッジを張る
      • 確率𝜷で,ノード𝒗^′の𝒗を除く隣接ノードからランダムにノードを選択しエッジを張る(クラスタ
      • 確率𝟏−𝜷で,優先選択確率𝒑(𝒖)に従ってノード𝒗^′以外のノードを選択しエッジを張る(スケールフリー性
  4. 2 ~ 3をノード数がnになるまで繰り返す

f:id:Takuya-Shuto-Engineer:20190801151353p:plain
HKモデルの生成過程

確率βはクラスタ性を確保するのか,スケールフリー性を確保するのかを選択させる確率.

WSモデル

スモールワールド性を持つグラフモデル

特徴:

  • 平均最短経路長が短い
  • 任意のノードペア間の距離が短い
  • わあ!世界は狭いね!という感じ

生成アルゴリズムは簡単で,一次元格子を作成してランダムにエッジを張り替えるだけ.

f:id:Takuya-Shuto-Engineer:20190801152107p:plain
WSモデルの生成

スモールワールド性に関して,ミルグラムの実験(1967)が有名.
カンザス州の住人に手紙を預け,2200km先のマサチューセッツ州に住む特定の人物に手紙を届けるように指示.
ルールは以下の通り:

  • 手紙の伝達手段は個人的な知り合いへの手渡しのみ

f:id:Takuya-Shuto-Engineer:20190801152243p:plain
カンザス - マサチューセッツ

結果は,平均仲介人数が6人.これを6次の隔たりといい,6人辿ればだいたいの人間にアクセスできることを示唆した.

つまり,スモールワールド性とは情報の伝達速度が早いことを示すとも言える.

最近の調査だと,

などがある.

まとめ

ソーシャルデータをモデル化するグラフモデルをメモした.

  • ERモデル: ランダム性のあるモデル, ソーシャルデータには適さないことから比較に用いられる
  • BAモデル: スケールフリー性を持つモデル
  • HKモデル: BAモデルを改良,クラスタ性を持つモデル
  • WSモデル: スモールワールド性を持つモデル

参考文献

  • 増田直紀、今野紀雄, “複雑ネット ワーク 基礎から応用まで”近代科学社.
  • Erdős, P.; Rényi, A. "On Random Graphs Ⅰ". Publicationes Mathematicae. 1959, p.290-297.
  • Albert, Réka; Barabási, Albert-László (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. , p.47–97.
  • S. A. Myers et al., ”Information Network or Social Network? The Structure of the Twitter Follow Graph,” In Proc. WWW 2014.
  • Holme,P.; Kim,B.J. "Growing Scale-Free Networks with Tunable Clustering". Phys. Rev. E 65, 026107 . Phys. Rev. E, 2001, p.440-442.
  • Watts,D.; Strogatz,S.H. "Collective dynamics of ‘small-world’ networks". Publicationes Mathematicae. . Nature(332), 1998, p.440-442.
  • Stanley Milgram, "The Small World Problem", Psychology Today, May 1967. pp 60 - 67.