中心性：始まりから最近まで

Tag

preferred

PFI に入社して二ヶ月ちょっとの伊藤です。

ソーシャルネットワークサービスが一般的になるにつれ中心性という概念が注目されてきました。情報科学を専攻されている場合、Google PageRank や HITS アルゴリズムで算出されるグラフの節点に付与される重要度と言うと分かりやすいとのではないか思います。呼び方こそ違いますが、この中心性と重要度は同一の概念、つまりグラフの節点に重み（点数）をつける尺度として知られています。以下、PageRank とHITS が提案された論文です。

Brin, S. and Page, L. The anatomy of a large-scale hypertextual (web) search engine. Computer Network and ISDN Systems.1998.
Kleinberg, J. M. Authoritative sources in a hyperlinked environment. Journal of the ACM. 1999.

今回は中心性を算出するアルゴリズムではなく歴史の方に注目してみます。今でこそ当然のように考えられていますが、中心性は計量書誌学(英語名は Scientmetrics, Bibliometrics)、社会科学と情報科学でおのおの独立して数十年もの間研究されてきました。

中心性に関する初めての論文は Gerfield さんのインパクトファクター(IF)があります。この論文は学術雑誌の重要性を各雑誌に含まれる論文の引用関係か計算する研究です。この論文がすばらしいのは、節点の重要度は接続する孤の数で定義されると提案した点です。つまり、たくさん孤があれば (引用されれば)、その節点 (論文、Webページ) は重要であると提案したのです。

Garfield, E. Citation analysis as a tool in journal evaluation, Science 178. 1972.

社会ネットワーク分析の分野で他にも多く中心性が提案されました。広く知られているものだと、情報中心性、媒介中心性、近接中心性、Bonacich 中心性等があります。これらは社会ネットワーク分析の本を買うと詳細な説明が乗っていますので一度調べてみると面白いと思います。ちなみにBonachich 中心性は固有値を計算する手法で (孤に重みはつけない)、Eigen 中心性とも呼ばれます。Authority と Hub という概念は出てきませんが、式はほぼ Kleignberg さんの HITS と同じです。

社会科学で中心性が進む中、1976 年 Pinsky さんとNarin さんが情報科学分野で記念碑的な論文を発表します。提案手法は PageRank と同様に (節点の out edge の重みの合計が１になるように) 孤に重みをつけ、固有値（ベクトル）を計算する。まさに PageRank アルゴリズムの原型です。違いは Pinsky さんらの手法では一定の割合で均等に移動する部分の項が存在しない点です。

Pinski, G. and Narin, F. Citation inﬂuence for journal aggregates of scientiﬁc publications: theory, with application to the literature of physics. Information Processing & Management. 1976.

これまで紹介してきた論文はそのほとんどがお互いを引用することはありませんでした。出版時期が離れていたのと、分野が異なっていたため、お互いの存在に気がつかなかったのでしょう。

中心性の研究が大きく動くのは 1990 年代の終わりに提案された PageRank と、HITS のアルゴリズムが出現した後です。比較的小規模な引用関係や社会ネットワークでしか研究されなかった研究が、数十億を超えるウェブグラフに適用されることで、その有用性が理解されるようになったのです。

牧歌的な時代は終わり世界中の研究者が中心性の研究を我れ先にと参入し、研究は一気に進みます。この時期、年間数十も手法が提案されました。私もこの頃中心性に関する研究をしていたのですが、あまりにも関連する論文の数が多くてサーベイに手を焼いていたことを覚えています。

PageRank や HITS とは異なるアルゴリズムを提案した論文としては Lampel さんのSALSA が有名です。また、全く異なる手法を提案するまでは行かなくても、改善方法を提案した論文がたくさんあります。特に印象的だったのは Ng さんらが提案した Subspace HITS アルゴリズムです。このアルゴリズムは、複数の固有ベクトルの線形和を使用することで、HITS の持つ不安定なランキングを補正します。

Lempel, R. and Moran, S. The stochastic approach for link-structure analysis.
ACM Transactions on Information Systems. 2001.
Ng, A. Zheng, A. and Jordan, M. Stable algorithms for link analysis, in SIGIR conference 2001.

この時期重要度ベクトルをグラフのサブコミュニティ毎に計算するというトピックもまた盛んに提案されました。特に記憶に残っているのは、Kolda さんらの手法です。提案された手法はトピックを考慮するために、2次元の行列から3次元のテンソルに拡張して HITS を計算するという手法です。コミュニティ内の重要度を計算するためにグラフの中心性を確率モデルで解析した論文もあります。Cohn さんらは自然言語処理分野で有名な文書の確率モデルだった Probabilistic Latent Semantic Indexing (PLSI) をグラフに適用し、各節点の重要度をコミュニティ毎に計算しました。

Kolda, T. G, Bader, B.W, and Kenny, J. P. Higher-Order Web Link Analysis Using Multilinear Algebra. ICDM 2005.
Cohn, D. Chang, H. Learning to Probabilistically identify authoritative documents, International Conference on Machine Learning. 2000.

これとは逆に中心性をWeb グラフ以外に適用に適用する流れが起こりました。Balmn さんが提案した ObjectRank は重要度の概念をデータベースに適用した研究です。自然言語処理学分野でもグラフを利用した方法が存在します。私の知る限り自然言語処理分野でグラフを利用した初めての論文は LexPageRank です。この手法は文書の要約を生成する為に、一文が節点となるグラフを計算し PageRank を計算するという手法です。その後も自然言語処理でグラフのアルゴリズムを利用するという流れは数はそれほど出ていないですが、今でもしっかりと続いています。

Balmin, A. Hristidis, V. Papakonstantinou, Y. ObjectRank: Authority-based keyword search in databases. VLDB 2004.
Erkan G, Radev D R. Lexpagerank: Prestige in multi-document text summarization. In Proc. EMNLP. 2004.

現在ミクシィ、Facebook, Twitter といったソーシャルグラフが注目を集めるに従い、ソーシャルグラフの中の重要な人（インフルエンサー）を抽出する研究が注目されています。現在のところ PageRank の変形アルゴリズムを利用したアルゴリズムが多いようですが、SNS 上の広告戦略にとってコアとなる部分ですので、今後さらに研究が進むと考えられます。

最後に今回の記事を書くまで知らなかったのですが、以下のブログによると 1940 年代、すでに経済学の分野で PageRank と同様の研究がされていたらしいです。