Localization and centrality in networks

読んだ論文の内容について書いています。

論文のタイトルは Localization and centrality in networks で

http://journals.aps.org/pre/abstract/10.1103/PhysRevE.90.052808

にあります。

Physical Reviewという物理学の中で最も権威ある学術雑誌の2014年の論文です。

内容をかいつまんで要約すると

　グラフの各頂点の重要度(centrality)として、そのグラフの隣接行列の第一固有値に対応する固有ベクトルを用いる手法がある。しかしこの指標には局所性(localization transition)という問題点があり、例えばハブとなるような頂点があるとその頂点の重要度が集中しすぎてしまい、他の頂点をまともに評価できないという問題点がある。現実にあるいわゆるソーシャルネットワークのような、次数がべき乗則に従うようなネットワークにもこの問題が発生してしまうため、隣接行列の固有ベクトルを用いた評価は適当ではない。

　この問題点を解決するために、グラフの nonbacktracking matrix の第一固有ベクトルを用いた手法を提案し、これが上手くいくことについて考察した。

というものです。

固有値による重要度の評価

　グラフの各頂点の重要度(centrality)をどのようにして決めるかという問題は例えばページランクとかそういうものに応用が利くので考えたくなる題材です。頂点数を n とし、頂点 i  の重要度を



とおき、特に頂点の重要度を成分として持つn次元ベクトルを単に  と表記することにします。

　最も簡単な評価はその頂点の次数を重要度として採用するというものです。これは「沢山の友達とつながっている人の方が影響力が大きい」という観察に基づいたものです。

　この評価では「どの友達も同じくらいの影響力を持っている」という仮定があります。しかし実際は「友達の中に偉い人がいるような人の方が影響力が高い」と見なせるというのが自然だと思います。「東大生と友達だよ」よりも「オバマと友達だよ」って言われた方がインパクトがあるってものです。 この観察を考慮すると、重要度の定義を



とするのが適当と思われます。ここで A は隣接行列、λは適当な定数を意味します。 つまり友人の重要度の和をスカラー倍を自分の重要度とするわけです。この式をベクトルの形で書くと




となりまさに v は固有ベクトルとなるわけです。ペロン・フロベニウスの定理より、隣接行列Aは全ての成分が非負なので第一固有値は非負となり、対応する固有ベクトルで全要素が非負であるものが存在するためこの固有ベクトルをもって v とする、ということです。

問題点

　隣接行列の固有ベクトルを用いた評価は、次数が極端に大きい頂点が少しだけあるようなグラフに対しては、次数が大きい頂点ら(局所的な部分)に重要度が集中してしまいます。その結果、その他の頂点の評価がおざなりになってしまい、比較しにくくなってしまうという欠点があります。

　この現象を感覚的に説明します。

　この図では次数5の頂点が一つだけ存在します。この頂点の重要度は大きくなります。周りにある頂点は真ん中の頂点の重要度を足されるので、重要度が大きくなります。また、真ん中の頂点は近傍の重要度を足すので重要度はかなり大きくなることが予想されます。つまり真ん中の頂点は自分の重要度が近傍に影響した後、その影響が反射してまた自分の重要度が大きくなるわけです。これを繰り返した結果、真ん中の頂点の重要度は他の頂点に比べて極端に大きくなることになります。

　論文ではランダムグラフにハブを追加したようなモデルと次数がべき乗則に従うようなランダムグラフを考え、そのグラフの隣接行列の第一固有値と第二固有値に対応する固有ベクトルを解析し、隣接行列の固有ベクトルによる手法が上手くいかないことを説明しています。

　この問題は、重要度が行って戻ってくる(backtrack)することに起因します。従ってそうならない(nonbacktrack)ような関係式を考察すればよいのでは？ということになります。

nonbacktracking matrix

 グラフから抽出される行列は隣接行列やグラフラプラシアンのほかにも色々あり、その中の一つに nonbacktracking matrix というものがあります。無向グラフG=(V, E)に対してEの各辺を、行きと帰りの二つの向きをつけます。 このように向きつけられた辺はGに対しては全部で 2|E| 本ありますが、この 2|E| 本の向き付き辺が nonbacktracking matrix のインデックスになっています。 従って, Gのnonbacktracking matrix は 2|E| × 2|E| の行列となります。 式で書くと



となります。この行列の最大固有値に対応する固有ベクトルを計算し、各頂点に対してそれに入ってくる(incoming)な辺に対応する固有ベクトルの成分の和を重要度とする、というのが提案手法です。

　この固有値と固有ベクトルの計算は一見すると大変そうに見えるのですが、



という行列の第一固有値に対応する固有ベクトルを計算し、先頭のn個の成分をとってくれば、所望の重要度になっていることが知られています。この行列の疎性は元の行列の疎性と対して代わらないためにそれほど計算時間は問題にならないということが分かります。