無向ネットワークのリンクの結合度

ネットワークサイエンスについて勉強している。

ノード間のリンクの結合の強さを表す尺度を思いついた。既に発見されているかもしれないが記録しておく。*1

仮説１： リンクに重みが予め付加されていない場合でも、ネットワークの構造からリンクの結合度を表すことができる。

重み付きネットワークであれば、どのリンクが重要かという問について悩む必要はない。大きい重みが付けられているリンクが重要なリンクであろう。もちろん何をもって重要とするかによって、どのリンクが重要かは変わってくるだろうが、（変な言葉だが）重みによってウェイトがつけられるのは間違いないだろう。

一方、リンクに重みが明に付加されていないネットワークであっても、すべてのリンクが等しく重要であるということはないだろう。重要なリンクもあればそうでないリンクもある。非重み付きネットワークであっても、リンクの重要度、言い換えると結合の強さというのが存在するはずだ。そして、それはネットワークの構造から計算できるに違いない。

ネットワークサイエンスを学んでいると、クラスタリング係数 (Transivity) というものが登場します。実在するネットワークは一般に、一部のノードが密にリンクを張っていて、クラスタを作っています。家族だとか、サークルだとか、互いに見知り合った集団のことです。コミュニティともモジュールとも呼び方はいろいろあるかと思います。クラスタリング係数はクラスタリングが起こっている度合いを示す指標です。

仮説２： クラスタ内のリンクは結合度が高い。

結合度、結びつきの強さを考えます。厳密な定義はまだできないですが、リンクの重みと同じイメージです。結合が強いリンクがあるところにクラスタができるのか、クラスタがあったらリンクが強くなるのかはわかりませんが、感覚的にクラスタ内の結合は強いと思われます。

クラスタを作るようなリンクは結合度が高いとすると、次の仮説が得られます。

仮説３： 共通のノードに接続している２つのノード間のリンクは結合度が高い。

共通の知り合いが多い二人組は強い関係にあるということです。例えば夫婦とかです。

図の上と下のノードは４つの共通のノードにリンクしています。点線のリンクは強いリンクであると考えられます。

このような考え方で、リンクの結合度を表す値が定義できるのではないだろうか。そうすると、重みなしネットワークから、重みつきネットワークを生成できる。何かしら新しいものが見えてきそうだ。

だが、上のコンセプトの元でも、結合度の定義は幾通りも考えれる。単に共通のノードの数としてもいいし、次数を用いて [0, 1] の区間の値を持つように規格化してもいい。どのような定義が適切かはデータを元に決めるしかない。

仮説4: よいノードの結合度の定義は２つのノードが結合している確率と強い相関をもつ

結合度の強いリンクというのは生じやすくて、切れづらいと考えれる。任意の２つのノード間にリンクが貼られている確率が高い条件というものがあったとき、その条件下で結合している２つのノードは結合度が強いと言えるのではないだろうか。

例えば、上の図でいうと、２つのノードが共通にリンクを張っているノードの数と、その２つのノード間にリンクがある確率に強い相関があるとすれば、２つのノードが共通にリンクしているノードの数が２つのノード間の結合度を示していると言えるでしょう。

ただ、この考えでいくと、結合度はリンクがないノード間にも定義できなければならなくなる。統計値を得やすいという利点はあるが、そのように定義された結合度が適切なのかはよくわからない。

副作用として、確率的にそこにリンクがあって然るべきなのに、リンクがないという状況があれば、リコメンデーションに利用できるだろう。Facebook のもしかして友達？という通知はそういう戦略なのかもしられない。

以上、ただの思いつきです。気が向けば上記の方針で適切な結合度を探すことをしてみる。クラスの依存関係のグラフは有向グラフだからちょっと取り扱いにくい……。無向グラフで、ベンチマークがしやすいような適当なサンプルデータはないのだろうか？

---

追記 2016-12-03

Ahn, Bagrow, Hehmann の link-clustering algorithm のアイデアに似ている。こちらは２つのリンクの類似度というのを求めている。

Link communities reveal multiscale complexity in networks : Nature : Nature Research

*1:もし既存の研究を見つけたら後から追記します。似ているが、異なるものはありました。