こんにちは。kzです。

前回の記事でNetworkXを紹介しました。そこで中心性について触れましたがその中の固有ベクトル中心性をより理解するために今回は簡単なネットワークを用いてその振る舞いを確認しようと思います。また、固有ベクトル中心性とPageRankについてまとめようと思います。

有向グラフと無向グラフ

グラフには２種類あります。エッジに向きがあるものとないものです。これがなぜ重要かというと、前回紹介した中心性を計算する際に計算できなかったり、行列の転置の処理で意味が大きく変わるからです。

固有ベクトル中心性

前回、固有ベクトル中心性は飽和、と言いました。僕もよく分かっていなかったので例があげられなかったのですが、今回、いい結果が得られたのでまとめます。
これは有向グラフです。AとBそれぞれのDegreeとEigen-Numpyに注目してください。FからBへのリプライがあることでBの固有ベクトル中心性が大きく反応しています。一方でAはリプライはなく、一方的なエッジのみを持っているせいか固有ベクトル中心性はゼロです。この結果から、固有ベクトル中心性は周囲への影響力（リプライを生み出す力的なもの）の指標として使えることがわかりました。

Code of Eigen Vector Centrality

PageRank

これは有向グラフだと固有ベクトル中心性が計算できない！！、厳密にゆうと複素数が登場してきて扱いにくすぎる！！という問題を解決するためのアルゴリズムで改良版的なものです。GoogleのLarry Page and Sergei Brinらによって発明されました。

PageRankという名前の通り、webpageをノードとしたネットワーク分析に使われていたようです。
どう捉えれば正解かは分からないのですが僕は以下のように理解しました。

  • Eigenのように0で潰れないのでデータ的に扱いやすい
  • 有向エッジがしっかり効いている
というのはCDとEFの組に注目すると前者はAから生えているノードで後者はBから生えているノードです。ここで、BはFからのリプライがありAにはないという点でBのPageRankが周囲にうまく影響を与えていると思ったからです。

色々実験してみたCode

色々実験して思ったことは以下の２点です。

  • NetworkXの固有ベクトル中心性の実装はeigenvector_centrality_numpy、eigenvector_centralityの２つあるが、エッジの重みをちゃんと考慮できているのか？という不安
  • アルゴリズムが単純ではない
しかしまあ、今回は久しぶりに収穫が多かったと個人的に思います。でわ

Reference