ページランクアルゴリズムの概要と実装

サマリー

アルゴリズムは、入力を取り込み、それを何らかの手順で処理し、最終的に出力を返すプロセスを表すもので、コンピューターサイエンスや数学、物理学、経済学、心理学など、多くの分野で利用されているものとなる。またアルゴリズムは、ある問題を解決する手順や方法を明確に定めた手続きということもできる。

アルゴリズムは数学と密接に関連している。数学は、抽象的な問題を形式化し、具体的な問題に変換することができるが、この数学を用いることで、問題を形式化してアルゴリズムに落とし込むことが可能となる。これは具体的には、離散数学での集合論や論理学を用いた、探索アルゴリズムの設計などになる。

このような数学的アプローチは、アルゴリズムの開発だけでなく、アルゴリズムの評価にも用いられる。アルゴリズムの評価は、正しさ、効率性、汎用性などの観点から行われ、正しいアルゴリズムは、すべての入力に対して正しい出力を返す必要があり、効率的なアルゴリズムは、処理時間や必要なリソースの量が少なく、速く処理でき、汎用的なアルゴリズムは、異なる入力に対しても同じ手順で処理できるように設計されている。これらの評価はすべて数学的表現を持って行われている。

アルゴリズムは、コンピュータープログラミングにおいて特に重要であり、多くのプログラムは、特定の問題を解決するために設計されたアルゴリズムを実行することで動作する。プログラミングにおいて、アルゴリズムを設計することは、コンピュータープログラムの設計の中で最も基本的で重要なステップの一つとなる。

ここではジョン マコーミックによる「世界で最も強力な9のアルゴリズム」をベースに様々なアルゴリズムの原理について述べる。

ページランクアルゴリズムの概要

ページランクアルゴリズムは、Googleの共同創業者であるラリー・ページ（Larry Page）によって考案されたアルゴリズムで、ウェブページの重要度を計算するために使用されるアルゴリズムとなる。グーグルを現在の位置に押し上げたのは、このページランクアルゴリズムを用いた検索技術の革新によるものとなる。ページランク技術は、検索エンジンの要素技術のうちの検索結果のランク付け技術にあたる。

このページランク技術の前提技術としてハイパーリンク技術を用いる。これはクリックすると別のWebページにジャンプできるような機能で、このブログの中にもあるアンダーラインがついた部分となる。このページランクのアイデアは1945年にアメリカのエンジニアのヴァネヴァー・ブッシュジによって書かれた「As We May Think」の中でも「文書を保存して自動的に索引を作ったり」、「連想的なインデクシング、つまり、任意の項目が、ただちに、そして自動的にほかの項目を意のままに選択する機構」等を持つmemexというマシンとしてすでに記述されている。

このハイパーリンク技術を使って、なるべくたくさんのリンクが貼られてあるページのほうがランクが高くなると言うのがページランクのベースのコンセプトになる。

このハイパーリンクを使った手法は課題として、ポジティブな推薦のリンクではなく「あのページはよくない」と言ったネガティブなリンクの存在に対して対応できないことや、また本来であれば信頼されているオーソリティから言及(リンク)されているページのランクをあげる方が良いのだがそのようなリンク元のコンピューターによるの信頼度判定は困難である等がある。

この信頼度をコンピューターで計算する手法として、あるページの信頼度(オーソリティスコア)はそのページをリンクしているページがそれぞれ持っている信頼度(オーソリティスコア)を足し合わせたものとし、それらのがカスケードに足し合わせられたものが最終的な自分のスコアとなると定義するとそのページを評価する事ができる。

ただし、上記の方法ではハイパーリンク内にに閉じたループ(循環ループ)が存在すると、無限大にオーソリティスコアが増加してしまうという課題が存在しそのままでは実用化が困難となる。この課題に対する対策としてランダムサーファートリックが生み出された。

ランダムサーファートリックとは、ランダムにインターネットをサーフインする人を想定し、スタート地点をランダムに選んで、そこからのハイパーリンクもランダムに選んでとカスケードに進んでいくことを言う。ここで、新しいリンクの連鎖を始める為の工夫として、あるページに遷移した時に特定の確率(例えば15%)でハイパーリンクを辿らずに新しいページにジャンプするようにしている。

これらを多数回繰り返す事で、多く訪れたページのスコアが上がり、ほぼオーソリティスコアと同等のスコアが循環ループが存在しても得られることとなる。この手法はシミュレーションの手法であり、確率的なモデルからの機械学習においても同様なアプローチを行うこととなる。

ページランクアルゴリズムは、このような考え方を基に、各ウェブページのランキングを計算する。以下に、ページランクアルゴリズムの基本的な手順を述べる。

1. ウェブページをノードとするグラフを作成する。
2. 各ページの初期ランキングを設定する。通常は、すべてのページに対して同じ初期ランキングを設定する。
3. 各ページからのリンクをたどって、リンク先のページのランキングを計算する。その際、リンク元のページのランキングを、リンク先のページの数で割って得られる平均値を使用する。
4. 3を繰り返し行い、各ページのランキングを更新する。
5. ランキングの変化が小さくなるまで、4を繰り返す。
6. 各ページの最終ランキングを求める。

ページランクアルゴリズムは、ウェブページの重要度を数値化することで、検索エンジンの検索結果の順位付けに使用される。ただし、現在ではページランクアルゴリズムだけではなく、様々な要因が考慮された複雑なアルゴリズムが使用されている。

pythonでの実装

Pythonを用いたページランクアルゴリズムの実装には、いくつかのライブラリが存在するが、ここでは簡単な実装例を紹介する。以下のコードは、グラフを辞書型で表現し、ページランクアルゴリズムを実行するものとなる。

def pagerank(graph, damping_factor=0.85, max_iterations=100, epsilon=1.0e-6):
    # グラフのノード数を取得
    n = len(graph)

    # グラフの各ノードに対して、初期ランキングを設定
    initial_rank = 1.0 / n
    ranks = {node: initial_rank for node in graph}

    # 収束するまでランキングの計算を繰り返す
    for i in range(max_iterations):
        new_ranks = {}
        # すべてのノードに対して、新しいランキングを計算する
        for node in graph:
            # すべてのリンク元のランキングの合計を計算
            rank_sum = 0.0
            for referring_page in graph:
                if node in graph[referring_page]:
                    rank_sum += ranks[referring_page] / len(graph[referring_page])
            # 新しいランキングを計算
            new_rank = (1 - damping_factor) / n + damping_factor * rank_sum
            new_ranks[node] = new_rank

        # 収束判定を行い、収束していたら計算を終了
        converged = True
        for node in graph:
            if abs(ranks[node] - new_ranks[node]) > epsilon:
                converged = False
                break
        if converged:
            break

        # 新しいランキングを反映
        ranks = new_ranks

    return ranks

このコードでは、グラフを辞書型で表現し、各ノードの初期ランキングを等しく設定している。ランキングの計算には、指定された反復回数（max_iterations）または収束判定条件（epsilon）に達するまで繰り返し計算を行い、最終的なランキングを返す。

この実装例では、ダンピングファクターとして0.85を使用しているが、必要に応じて他の値に変更することができる。また、グラフを辞書型で表現する方法は一例であり、他の方法を使用することも可能となる。

Rを用いたアルゴリズム

次にRを用いたページランクアルゴリズムを実装する。ここではigraphパッケージを使用した実装例について述べる。

まずは、igraphパッケージをインストールし、読み込む。

install.packages("igraph")
library(igraph)

次に、グラフを作成する。ここでは、4つのノードからなる単純な有向グラフを作成する。

# グラフの定義
edges <- data.frame(from=c(1,1,2,3), to=c(2,3,3,4))
g <- graph_from_data_frame(edges, directed=TRUE)

# プロット
plot(g)

次に、igraphパッケージに含まれるpage.rank関数を使用して、ページランクを計算する。

# ページランクの計算
page_rank <- page.rank(g, damping=0.85)$vector
page_rank

このように、page.rank関数はグラフとダンピングファクターを引数に取り、ページランクを計算する。結果は、各ノードのページランクの値を含むベクトルとして返さる。なお、igraphパッケージには、ページランク以外にも様々なグラフ解析のための関数が含まれている。

Clojureによる実装

Clojureを使ったページランクアルゴリズムの実装例について述べる。

まずは、leinプロジェクトを作成し、clojure.java.ioライブラリをインポートする。

(ns page-rank.core
  (:require [clojure.java.io :as io]))

次に、グラフを表す隣接リストを読み込む。ここでは、グラフをgraph.txtというファイルに保存し、隣接リストを読み込んでいる。グラフは以下のように表される。graph.txtのファイルフォーマットは、1行目にノード数nとエッジ数mが、2行目以降に各エッジの始点と終点が空白区切りで並んでいるものとする。

4 4
1 2
1 3
2 3
3 4

(defn load-graph [filename]
  (let [lines (-> filename
                  io/resource
                  io/reader
                  line-seq)
        [n m] (-> lines
                  first
                  (clojure.string/split #" ")
                  (map read-string))]
        edges (->> lines
                  rest
                  (map #(-> %
                             (clojure.string/split #" ")
                             (map read-string)
                             vec)))
        graph (vec (map #(atom #{}) (range n)))]
    (doseq [[from to] edges]
      (swap! (nth graph from) conj to))
    graph))

次に、ページランクを計算する関数pagerankを定義する。ページランクの計算には、反復回数、ダンピングファクター、および収束条件を指定する必要がある。ここでは、デフォルト値として反復回数を1000回、ダンピングファクターを0.85、収束条件を0.001としている。

(defn pagerank
  [graph & {:keys [max-iter damping-factor epsilon]
            :or {max-iter 1000
                 damping-factor 0.85
                 epsilon 0.001}}]
  (let [n (count graph)
        ranks (vec (repeat n (/ 1.0 n)))]
    (loop [iter 0 ranks ranks]
      (let [new-ranks (vec (map #(+
                                  (* (1.0 - damping-factor) (/ 1.0 n))
                                  (* damping-factor
                                     (reduce + (map #(/
                                                       (get ranks %)
                                                       (count (get graph %))))
                                                    (get graph %)))))
                            (range n)))
            converged? (every? #(<= epsilon (Math/abs (- (get ranks %)
                                                          (get new-ranks %))))
                               (range n))]
        (if (or (= iter max-iter) converged?)
          new-ranks
          (recur (inc iter) new-ranks))))))

最後に、main関数を定義して、ページランクを計算し、結果を出力する。

(def -main