Localization and centrality in networks (Phys. Rev. E. '14)

Localization and centrality in networks (Phys. Rev. E. '14)

　T. Martin, Z. Xiao, M.E. J. Newman

概要

Eigenvector centralityは頂点の重要度を表す有名な指標であるが,高い次数の頂点とその隣接頂点のみ値が大きくなってしまい（localization）それ以外の頂点の相対的な優先度がわからなくなってしまうという問題点が知られていた.本論文ではまず,その問題点を数学的に解析し,べき乗則にしたがうネットワークでも同様の現象が起こることをしめす.次に,その解決策としてeigenvector centralityの亜種を新たに提案し,その指標ではlocalizationが発生しないということを理論・実験の両方によって示している.

詳しい説明は次のページで https://www.quora.com/What-is-an-intuitive-explanation-of-the-Hashimoto-non-backtracking-matrix-and-its-utility-in-network-analysis

感想

論文中にあったEigenvector centralityにおけるlocalizationと提案手法によってそれが解消された図はかなりimpressiveであった. ランダムウォークで直前の辺を通らないというアイデアはだいぶ前からあったようだし,提案された指標の新規性がどうなのかは正直わからない.数学的な解析が主な貢献ということでいいんだろうか？もうひとつ気になったのはeigenvector centralityの計算方法で今知られている高速なものはなんなんだろうかということ.これはこの論文では触れられていなかった.