局所的にクラスタ化されたネットワークのボナチッチの中心性

ボナチッチの中心性指標とは、グラフでいうところの隣接行列の最大固有値の固有ベクトルのことである。隣接行列の代わりに相関係数行列を考えたときの第一主成分といえば統計の人にはわかりやすいかな？

社会科学では、これをネットワークの「中心性」の指標として使おうとしているけど、ノードがいくつかのグループに分かれてしまうような場合（局所的にいくつかのクラスタができてしまうような場合。ひとつ前の日記で書いたような状況）、中心性指標はある特定のグループ(クラスタ)に集中してしまうことがある。今日の画像は、ひとつ前の日記でふれたようなクラスタ化されたネットワークの中心性指標を計算して、それを頂点の半径に使った可視化画像。

2番目に大きな固有値に属する固有ベクトルは、また別のクラスタに集中し、3番目、4番目に大きな固有値も同様の性質を持つ。こういう現象が起こるのは、固有値の間の差が小さいとき。最大固有値が2番目の固有値をうんと突き放して大きいときは、こういうことは起こらない。

多変量解析の主成分分析でも同じような問題が起こっているはずだから、その修正する手法をまねて使わないと、ボナチッチの中心性指標はあまりよい指標とは言えないな。少なくとも元データの小さな揺らぎに対して robust であるとは言えない。

Pagerank も基本的に同じような原理で計算されているので同じ問題を抱えている。もちろんサーチエンジンで使われているのは、もっと複雑だと思うけど、基本的には推移確率行列の最大固有値の固有ベクトルだから、同じようにある特定のクラスタに属する頂点にだけ高い値が与えられてしまう可能性がないわけではない。

おまけ

中心性指標とPagerankを計算して、頂点の半径として可視化するようにシミュレータを更新してみました。
スケールフリーシミュレータ
よろしければお使いください。隣接行列の固有値の分布も出ます。モデルもいくつか追加しています。