でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

次数中心性からPageRankからまた次数中心性

ノードの中心性はネットワーク分析をする上でとても重要です。

例えば、TwitterFacebookでは中心性の大きい人は他の人に対して大きな影響を与えると考えられますし、Webで中心性の大きいページは重要な情報を含むページであると考えることができます。

今読んでるNetworksという本で結構ページを割いて説明されていたので簡単にまとめたいと思います。

Networks: An Introduction

Networks: An Introduction

次数中心性(Degree centrality)

一番単純な中心性は次数中心性です。これはホントに単純で、あるノードの次数中心性=そのノードの次数です。

単純すぎてあんまり良くないんじゃないととおもいますが、実はソーシャルネットワークの分析とかでよく使われてたりします。

固有ベクトル中心性(Eigenvector centrality)

固有ベクトル中心性では、自分に対してエッジを張っているノードがどれだけの中心性を持っているかということを考慮します。

つまり、あるノードiには、iに対してエッジを張っているノードの中心性が”遷移して”きて、その合計値がiの中心性となります。

ノードiの固有ベクトル中心性の値をxiとすると、xiはiに対してエッジを張っているノードjの中心性の値xjを全て足しあわせた値となります。

数式で表すとこんなかんじです。

Aijは隣接行列の要素で、jからiに対してのエッジがあれば1、そうでなければ0です。

この”遷移”を何度も何度も繰り返すと、いつか値が収束する時が来ます*1

収束したとき、全てのxiの値をベクトルとして表現すると、最終的に次の式を満たします。

λ1は隣接行列Aの最大固有値を表しています。つまり、固有ベクトル中心性は隣接行列Aの最大固有値に対する固有ベクトルで与えられるわけですね。

カッツの中心性(Katz centrality)

固有ベクトル中心性にはけっこうやっかいな問題があります。

ネットワークの中にひとつもエッジを張られていないノードがあったとします。

そのノードに対してはどこからも中心性が遷移してこないので、当然中心性は0となりますね。

ここまではいいんですが、この後が問題です。

上のようなノードが複数あったとして、そのようなノードからしかエッジを張られていないノードiがあったとします。

そうすると、iはいくつかのノードからエッジを張られているのにもかかわらず、遷移してくる中心性の値が全て0なので、iの中心性も0となってしまいます。

これは直感に反すると思います*2

そこでカッツの中心性です。

カッツの中心性はこの問題を解決するために、全てのノードの中心性に対して小さな値を与えます。

もちろんひとつもエッジを張られていないノードに対しても。つまり中心性が0となるノードがなくなるわけですね。

全てのノードに与える小さな値をβとすると、こんなかんじの数式で表せます。

固有ベクトル中心性のときと変わっているのはβを足しているところだけです。αはβによって与えられる小さな値と、他のノードから遷移してくる中心性の値の大きさを制御する定数です。

簡単のため、βを1として*3、中心性の値が収束するまで遷移を続けると

となります*4。太字の1は全ての要素が1であるベクトルです。

PageRank

カッツの中心性にも直感的でない部分があります。

例えば、Webグラフを想像してください。

多分Yahoo!はいろんなページからリンクを張られていて、中心性はものすごく大きいと思います。

それと同時に、Yahoo!はいろんなページにリンクを張っていますね。

こういう場合、Yahoo!が持っている大きな中心性の値がそのまま、Yahoo!がリンクを張っている全てのページに遷移してしまうことになります。

Yahoo!からリンクを張られたといっても、そのページは何万ものページのうちの一つに過ぎません。

なので、一つ一つのページにYahoo!の中心性を”そのまま”遷移させるのは直感的ではありません。

そこで、有名なPageRankです。

PageRankは、ノードが持っている中心性をそのノードが張っているエッジの本数(出次数)で割ってからそれぞれに遷移させます。

ノードiの出次数をkiとすると、こんなかんじの数式でかけます。

カッツの中心性と違うのは、xjをkjで割っているところだけです。

ここでまた中心性の値が収束するまで遷移を続けると、

となります。行列Dはkiを対角要素とする対角行列です。

また次数中心性

PageRankの式からβをとったらどうなるでしょう。

つまり、知っている人はわかると思いますが、ランダムジャンプをさせない場合です。

有向グラフの場合はすこし複雑になってしまうので、ここでは無向グラフに限ります。

そのときの式はこうなります。

これは、天下り的ですが、xj = kjとすると成り立ちます。

つまり、このときのノードの中心性は単に次数で表せるわけですね。





これって面白い結果ですよね。PageRankでランダムジャンプをさせない場合は単に次数になってしまうわけです。ちなみにNetworksの本には他にも近接中心性(Closeness centrality)とか、媒介中心性(Betweenness centrality)とかも書いてありましたがはしょります。この数式のここを少しいじってやるとこうなってこうなって、・・・、実はこれと等価だった!とか、最高に楽しいですよね。

*1:これをエルゴード性と言います。

*2:エッジを張られていないノードと張られているノードの中心性が同じって変ですよね。

*3:実際、必要なのは中心性の絶対値ではなくその順位なので、βの値はなんでもいいです。

*4:αを0とすると全てのノードの中心性が同じになります。ただし、αを大きくし過ぎると発散してしまうので、任意に大きくすることはできません。