(57)【要約】【課題】PageRankに基づくノード検索において、高速に検索結果を得る。【解決手段】検索装置１０の部分グラフ構築部１１は、グラフＧと、解ノードの個数を示すｋを入力とし、繰り返し計算回数を示すｉについての部分グラフＧｉを計算する。ランダムウォーク確率計算部１２は、部分グラフＧｉに対応するランダムウォークの確率ｒｉ［ｕ］を計算する。推定値計算部１３は、ランダムウォークの確率ｒｉ［ｕ］および候補ノードＣｉから、候補ノードＣｉの全てのノードに対してPageRankのスコアの下限値および上限値の推定値を計算する。候補ノード計算部１４は、候補ノードＣｉから、（ｉ＋１）回目の繰り返し計算における候補ノードの集合Ｃｉ＋１を計算し、候補ノードの集合Ｃｉ＋１の要素数|Ｃｉ＋１|がｋに等しい場合には、候補ノードの集合Ｃｉ＋１を解ノードとして出力する。【選択図】図１
2014229110.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークを形成する機器をノードとし、前記機器間の接続をエッジとする前記コンピュータネットワークのグラフを、解ノードの個数を示すｋ（ｋは前記ノードの数を超えない正整数）の入力を受け付けて検索し、前記ｋ個の解ノードを出力する検索装置であって、
０を初期値とし、＋１ずつインクリメントされるｉについて、ｉ＝０の場合には前記グラフを部分グラフとし、ｉ＞０の場合にはｉ回目の繰り返し計算における候補ノードに基づく（ｉ−１）回目の繰り返し計算における前記グラフの部分グラフへ到達可能なノードの集合からｉ回目の繰り返し計算における前記グラフの部分グラフを構築する部分グラフ構築処理を実行する部分グラフ構築部と、
前記部分グラフ構築部が構築した部分グラフに対応するランダムウォークの確率を計算するランダムウォーク確率計算部と、
前記ランダムウォーク確率計算部が計算したランダムウォークの確率およびｉ回目の繰り返し計算における前記候補ノードの全てのノードに対するPageRankのスコアの下限値の推定値および上限値の推定値を計算する推定値計算部と、
ｉ回目の繰り返し計算における前記候補ノードから（ｉ＋１）回目の繰り返し計算における前記候補ノードを計算し、当該（ｉ＋１）回目の繰り返し計算における前記候補ノードの集合の要素数が前記ｋに等しい場合には当該（ｉ＋１）回目の繰り返し計算における前記候補ノードの集合を解ノードとして出力し、当該（ｉ＋１）回目の繰り返し計算における前記候補ノードの集合の要素数が前記ｋと異なる場合には、前記部分グラフ構築部に当該（ｉ＋１）をさらに＋１インクリメントさせたあらたなｉについて前記部分グラフ構築処理を実行させる候補ノード計算部と
を有し、
前記候補ノード計算部が前記部分グラフ構築部に前記あらたなｉについて前記部分グラフ構築処理を実行させる場合は、当該あらたなｉについて、前記部分グラフ構築部、前記ランダムウォーク確率計算部、前記推定値計算部、前記候補ノード計算部が各処理を再度、順次実行する
ことを特徴とする検索装置。
【請求項２】
コンピュータネットワークを形成する機器をノードとし、前記機器間の接続をエッジとする前記コンピュータネットワークのグラフを、解ノードの個数を示すｋ（ｋは前記ノードの数を超えない正整数）の入力を受け付けて検索し、前記ｋ個の解ノードを出力する検索装置で実行される検索方法であって、
０を初期値とし、＋１ずつインクリメントされるｉについて、ｉ＝０の場合には前記グラフを部分グラフとし、ｉ＞０の場合にはｉ回目の繰り返し計算における候補ノードに基づく（ｉ−１）回目の繰り返し計算における前記グラフの部分グラフへ到達可能なノードの集合からｉ回目の繰り返し計算における前記グラフの部分グラフを構築する部分グラフ構築処理を実行する部分グラフ構築工程と、
前記部分グラフ構築工程が構築した部分グラフに対応するランダムウォークの確率を計算するランダムウォーク確率計算工程と、
前記ランダムウォーク確率計算工程が計算したランダムウォークの確率およびｉ回目の繰り返し計算における前記候補ノードの全てのノードに対するPageRankのスコアの下限値の推定値および上限値の推定値を計算する推定値計算工程と、
ｉ回目の繰り返し計算における前記候補ノードから（ｉ＋１）回目の繰り返し計算における前記候補ノードを計算し、当該（ｉ＋１）回目の繰り返し計算における前記候補ノードの集合の要素数が前記ｋに等しい場合には当該（ｉ＋１）回目の繰り返し計算における前記候補ノードの集合を解ノードとして出力し、当該（ｉ＋１）回目の繰り返し計算における前記候補ノードの集合の要素数が前記ｋと異なる場合には、前記部分グラフ構築工程に当該（ｉ＋１）をさらに＋１インクリメントさせたあらたなｉについて前記部分グラフ構築処理を実行させる候補ノード計算工程と
を含み、
前記候補ノード計算工程が前記部分グラフ構築工程に前記あらたなｉについて前記部分グラフ構築処理を実行させる場合は、当該あらたなｉについて、前記部分グラフ構築工程、前記ランダムウォーク確率計算工程、前記推定値計算工程、前記候補ノード計算工程が各処理を再度、順次実行する
ことを特徴とする検索方法。
【請求項３】
コンピュータを、
請求項１に記載の検索装置として機能させるための検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法および検索プログラムに関する。
【背景技術】
【０００２】
近年、ソーシャルネットワークに代表されるように、大規模なネットワークの利用が進んでいる。そして、大規模なネットワークに対して、データマイニングや検索をおこなうシステムの重要性が増している。ネットワーク構成は、ネットワークを構築するコンピュータをノードとし、各ノード間の接続を示すリンクをエッジとするグラフデータとして表現できる。このため、ネットワーク構成をグラフデータとして取り扱うグラフデータベースに問い合わせをおこない、グラフのノードの検索、分類、解析などをおこなうことへの関心が高まりつつある。
【０００３】
例えば、ノードとしてのコンピュータがウェブサイトである場合に、ウェブページの重要度を決定するためのアルゴリズムとしてPageRankのアルゴリズムがある。このPageRankのアルゴリズムは、ランダムサーファーモデルに基づきノードの重要度を計算する。ランダムサーファーモデルは、ユーザが複数回ウェブページのリンクをクリックした後にランダムなページにジャンプするという行動をモデル化したものである。
【０００４】
PageRankによるノードの重要度は、ランダムウォークの定常状態における確率に対応する。PageRankの各処理ステップでは、現在のノードからリンク先のノードを選択して移動し、また一定の確率でランダムなページへジャンプする。その有効性から、PageRankは、様々なアプリケーションに応用されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Lawrence  Page、Sergey  Brin、Rajeev  Motwani、Terry  Winograd、“The PageRank  Citation  Ranking：Bringing  Order  to  the  Web”、1999
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の従来技術では、PageRankの計算コストが高いという問題がある。すなわち、従来技術によるPageRankの計算では、グラフ全体を用いて全てのノードのスコアが収束するまで繰り返し計算を行わなければならないため、大規模なグラフに対しては高速に重要度の高いノードの検索ができない。
【０００７】
本願が開示する実施形態は、上記に鑑みてなされたものであって、PageRankに基づくノード検索において、高速に検索結果を得ることを目的とする。
【課題を解決するための手段】
【０００８】
本願が開示する実施形態の一例は、コンピュータネットワークを形成する機器をノードとし、機器間の接続をエッジとするコンピュータネットワークのグラフを、解ノードの個数を示すｋ（ｋは前記ノードの数を超えない正整数）の入力を受け付けて検索し、ｋ個の解ノードを出力する検索装置である。検索装置は、０を初期値とし、＋１ずつインクリメントされるｉについて、ｉ＝０の場合にはグラフを部分グラフとし、ｉ＞０の場合にはｉ回目の繰り返し計算における候補ノードに基づく（ｉ−１）回目の繰り返し計算におけるグラフの部分グラフへ到達可能なノードの集合からｉ回目の繰り返し計算におけるグラフの部分グラフを構築する部分グラフ構築処理を実行する。また、検索装置は、部分グラフに対応するランダムウォークの確率を計算する。また、検索装置は、ランダムウォークの確率およびｉ回目の繰り返し計算における候補ノードの全てのノードに対するPageRankのスコアの下限値の推定値および上限値の推定値を計算する。また、検索装置は、ｉ回目の繰り返し計算における候補ノードから（ｉ＋１）回目の繰り返し計算における候補ノードを計算し、当該（ｉ＋１）回目の繰り返し計算における候補ノードの集合の要素数がｋに等しい場合には当該（ｉ＋１）回目の繰り返し計算における候補ノードの集合を解ノードとして出力し、当該（ｉ＋１）回目の繰り返し計算における候補ノードの集合の要素数がｋと異なる場合には、当該（ｉ＋１）をさらに＋１インクリメントさせたあらたなｉについて部分グラフ構築処理を実行させる。そして、検索装置は、あらたなｉについて部分グラフ構築処理を実行させる場合は、当該あらたなｉについて、上述の各処理を再度、順次実行する。
【発明の効果】
【０００９】
本願が開示する実施形態によれば、例えば、PageRankに基づくノード検索において、高速に検索結果を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、検索装置の構成を示すブロック図である。
【図２】図２は、検索処理を示すフローチャートである。
【図３】図３は、検索アルゴリズムを示す図である。
【図４】図４は、検索プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願が開示する検索装置などの実施形態を図面に基づいて説明する。以下の実施形態は、コンピュータネットワークを形成する機器をノードとし、機器間の接続をエッジとするコンピュータネットワークのグラフを、解ノードの個数を示すｋ（ｋはノードの数を超えない正整数）の入力を受け付けて検索する際に、PageRankのスコアが上位ｋである候補ノードを、解ノードとして出力する。なお、以下の実施形態は、一例を示すに過ぎず、本願が開示する技術を限定するものではない。
【００１２】
［記号の定義］
実施形態の説明で用いる記号を下表に示す。なお、実施形態の説明では、ベクトルをボールド体のラテン小文字、行列をボールド体のラテン大文字で表記する。
【００１３】
【表１】
2014229110.tif 000003
【００１４】
（従来技術の概要および問題点）
実施形態の説明に先立ち、従来技術の概要および問題点について説明する。従来技術では、PageRankは、ランダムなノードからランダムウォークを開始し、各処理ステップにおいて再帰的にランダムウォークを確率ｓ（０＜ｓ＜１）で繰り返す。また、従来技術では、各処理ステップにおいて、一定の確率（１−ｓ）でランダムなノードへジャンプする。
【００１５】
集合Ｖをグラフ全体のノードとし、集合Ｅをエッジの集合とすると、問い合わせ対象のグラフＧは、Ｇ＝｛Ｖ，Ｅ｝と表現できる。ここで、
2014229110.tif 000004
をｕ番目の要素ｐ［ｕ］がノードｕのPageRankのスコアに対応する列ベクトルとする。また、Ｎをグラフのノード数とする場合に、
2014229110.tif 000005
を全ての要素の値が１／Ｎである列ベクトルとする。また、Ｗ［ｕ，ｖ］をノードｖからノードｕへ移動する確率とする場合に、
2014229110.tif 000006
を列要素が正規化されたグラフの隣接行列とする。各ノードのPageRankのスコアは、以下の式（１）を再帰的に収束するまで繰り返し計算を行うことで得られる。
【００１６】
【数１】
2014229110.tif 000007
【００１７】
ここで、ｉ＝０であれば、
2014229110.tif 000008
は
2014229110.tif 000009
に設定される。この繰り返し計算を行う従来技術の手法は、各ノードにおけるPageRankのスコアが収束するまでおこなわれる。Ｍをグラフのエッジ数とし、Ｔを収束するまでの繰り返し計算の計算回数とすると、この繰り返し計算は、Ｏ（（Ｎ＋Ｍ）・Ｔ）の計算コストを要する。そのため、従来技術の手法は、大規模なグラフに対して高速に検索が行えないという問題がある。なお、Ｏ（＊）は、ランダウの記号である。
【００１８】
［実施形態］
（実施形態の概要）
以下に説明する実施形態は、上述の従来技術の問題点を解決するものである。実施形態では、計算コストを低減するために、PageRankのスコアの下限値の推定値および上限値の推定値を計算する。すなわち、実施形態は、従来技術の手法のように検索対象のグラフ全体を用いるのではなく、PageRankのスコアの下限値および上限値の推定値により、不要なノードとエッジを検索対象のグラフから除外した部分グラフに対してPageRankのスコアの繰り返し計算をおこなうことにより、ノード検索をおこなう。
【００１９】
以下の実施形態では、まず、実施形態にかかる計算処理方法および理論的背景を説明し、次に、実施形態にかかる検索装置の構成および処理を説明する。
【００２０】
＜計算処理方法および理論的背景＞
（PageRankのスコアの下限値および上限値の推定方法）
実施形態では、PageRankのスコアのｉ（ｉ＝０，１，２，・・・、（非負整数））番目の繰り返し計算において、候補ノードの集合に含まれるノードのPageRankのスコアの下限値および上限値の推定値を計算する。以下では、PageRankのスコアの下限値を「下限値」、PageRankのスコアの上限値を「上限値」、PageRankのスコアの下限値の推定値を「下限値の推定値」、PageRankのスコアの上限値の推定値を「上限値の推定値」、PageRankのスコアの下限値の推定値および上限値の推定値を「推定値」と適宜表記する。なお、候補ノードの集合を求める方法については、後述する。
【００２１】
上限値を計算するために、候補ノードの集合Ｃｉに到達可能なノードの集合Ｒｉを用いる。ここで、ノードｕがノードｖへ到達可能であるとは、グラフ上にノードｕからノードｖへのパスが存在するということである。またｕ番目の要素がエッジの最大の重みから、
2014229110.tif 000010
となるＮ×１の列ベクトルを
2014229110.tif 000011
とする。
【００２２】
また、長さがｉのランダムウォークの確率をＮ×１の列ベクトル
2014229110.tif 000012
とする。なお、
2014229110.tif 000013
のｕ列目の成分をｒｉ［ｕ］とする。ここで、グラフの隣接行列
2014229110.tif 000014
のｉ乗を用いて、
2014229110.tif 000015
は
2014229110.tif 000016
と計算できる。なお、ｉ＝０ならば、
2014229110.tif 000017
とする。ｉ番目の繰り返し計算における下限値
2014229110.tif 000018
と、ｉ番目の繰り返し計算における上限値
2014229110.tif 000019
を以下のように定義する。
【００２３】
【数２】
2014229110.tif 000020
【００２４】
【数３】
2014229110.tif 000021
【００２５】
これらの推定値の性質を、以下の補助定理１、補助定理２、補助定理３で示す。なお、補助定理３は、実施形態では、推定値が収束することを示す。
【００２６】
【数４】
2014229110.tif 000022
【００２７】
【数５】
2014229110.tif 000023
【００２８】
【数６】
2014229110.tif 000024
【００２９】
実施形態は、再帰的に上位ｋ個のノードを検索するために候補ノードを計算し、候補ノードの数がｋ個になれば繰り返し計算を終了する。推定値を計算するために、候補ノードの集合に含まれるノードに対して部分グラフを計算する。そして、候補ノードは、繰り返し計算の中で動的に更新される。
【００３０】
（候補ノードについて）
以下に、候補ノードおよび部分グラフの定義、ならびに、候補ノードおよび部分グラフの性質を示す。閾値εｉ−１を（ｉ−１）番目の繰り返し計算におけるｋ番目に高い下限値とし、ｉ番目の繰り返し計算における候補ノードの集合Ｃｉを以下のように定義する。
【００３１】
【数７】
2014229110.tif 000025
【００３２】
集合Ｃｉの性質は、以下のとおりである。
【００３３】
【数８】
2014229110.tif 000026
【００３４】
補助定理４から、Ａ⊆Ｃｉであるため、各繰り返し計算において、候補ノードの集合Ｃｉ−１から候補ノードの集合Ｃｉを、以下のように逐次的に計算できる。
【００３５】
【数９】
2014229110.tif 000027
【００３６】
また、候補ノードの集合Ｃｉ（ｉ＝０，１，２，・・・）は、以下のとおり、ｉについて単調減少する。
【００３７】
【数１０】
2014229110.tif 000028
【００３８】
（部分グラフについて）
また、実施形態は、部分グラフを用いて、候補ノードに対する推定値を計算する。ここで、ｉ番目の繰り返し計算における部分グラフＧｉを、以下のように定義する。
【００３９】
【数１１】
2014229110.tif 000029
【００４０】
部分グラフの集合Ｇｉ（ｉ＝０，１，２，・・・）について、次が成り立つ。
【００４１】
【数１２】
2014229110.tif 000030
【００４２】
また、部分グラフの集合Ｇｉ（ｉ＝０，１，２，・・・）は、以下のとおり、ｉについて単調減少する。
【００４３】
【数１３】
2014229110.tif 000031
【００４４】
（推定値の計算について）
また、ｉ番目の繰り返し計算における下限値および上限値は、部分グラフの集合Ｇｉを用いて、逐次的に、以下のように計算する。なお、補助定理７に基づき部分グラフの集合Ｇｉを構築する方法は、後述する。
【００４５】
【数１４】
2014229110.tif 000032
【００４６】
そして、定義６によるｉ番目の繰り返し計算における下限値および上限値の計算の計算コストは、以下のとおりである。
【００４７】
【数１５】
2014229110.tif 000033
【００４８】
以上から、以下の２つの主張を、定理として示す。
【００４９】
【数１６】
2014229110.tif 000034
【００５０】
【数１７】
2014229110.tif 000035
【００５１】
＜検索装置の構成および処理＞
（検索装置の構成）
図１は、検索装置の構成を示すブロック図である。実施形態にかかる検索装置１０は、ノード検索の問い合わせに用いるグラフＧと、解ノードの個数ｋを入力とし、候補ノードの要素数がｋに等しい場合に、PageRankのスコアが上位ｋである候補ノードを解ノードとして出力する。図１に示すように、検索装置１０は、部分グラフ構築部１１、ランダムウォーク確率計算部１２、推定値計算部１３、候補ノード計算部１４を有する。
【００５２】
部分グラフ構築部１１は、問い合わせに用いるグラフＧと、解ノードの個数を示すｋ（ｋはノードの数を超えない正整数）を入力とし、繰り返し計算回数を示すｉ（ｉは非負整数）について、部分グラフＧｉを計算して出力する。
【００５３】
具体的には、部分グラフ構築部１１は、ｉ＝０の場合には、候補ノードＣｉの初期集合であるＣ０に関してＣ０＝Ｖ、部分グラフＧｉの初期集合であるＧ０に関してＧ０＝Ｇをセットする。そして、部分グラフ構築部１１は、ランダムウォーク確率計算部１２へ、部分グラフＧ０を出力する。
【００５４】
一方、部分グラフ構築部１１は、ｉ≠０の場合には、ｉを＋１インクリメントする。この＋１インクリメントにより、部分グラフ構築部１１が計算した部分グラフＧｉは、部分グラフＧｉ−１となる。そして、部分グラフ構築部１１は、定義３の式（５）および定義４の式（６）に基づいて候補ノードＣｉを計算する。そして、部分グラフ構築部１１は、補助定理７に基づいて、幅優先探索により、候補ノードＣｉから部分グラフＧｉ−１に到達可能なノードの集合Ｒｉを計算する。そして、部分グラフ構築部１１は、定義５に基づいて、ノードの集合Ｒｉから部分グラフＧｉを計算し、ランダムウォーク確率計算部１２へ出力する。
【００５５】
ランダムウォーク確率計算部１２は、部分グラフ構築部１１が出力した部分グラフＧｉを入力とし、補助定理６および定義６に基づいて、部分グラフＧｉに対応するランダムウォークの確率ｒｉ［ｕ］を計算し、推定値計算部１３へ出力する。
【００５６】
推定値計算部１３は、ランダムウォーク確率計算部１２が出力したランダムウォークの確率ｒｉ［ｕ］および部分グラフ構築部１１が計算した候補ノードＣｉから、定義６に基づいて、候補ノードＣｉの全てのノードに対してPageRankのスコアの下限値の推定値および上限値の推定値を計算する。そして、推定値計算部１３は、計算した推定値を、候補ノード計算部１４へ出力する。
【００５７】
候補ノード計算部１４は、部分グラフ構築部１１が計算した候補ノードＣｉから、ｉ番目の繰り返し計算におけるｋ番目に高い下限値である閾値εｉを計算する。そして、候補ノード計算部１４は、定義３および定義４、ならびに、計算した閾値εｉに基づいて、（ｉ＋１）回目の繰り返し計算における候補ノードの集合Ｃｉ＋１を計算する。そして、候補ノード計算部１４は、候補ノードの集合Ｃｉ＋１の要素数|Ｃｉ＋１|がｋに等しいか否かを判定する。そして、候補ノード計算部１４は、要素数|Ｃｉ＋１|がｋに等しい場合には、候補ノードの集合Ｃｉ＋１を解ノードとして出力する。一方、候補ノード計算部１４は、要素数|Ｃｉ＋１|がｋと異なる場合には、部分グラフ構築部１１に対して、ｉの＋１インクリメント処理以降の処理をおこなわせる。
【００５８】
（検索処理）
図２は、検索処理を示すフローチャートである。まず、検索装置１０の部分グラフ構築部１１は、問い合わせに用いるグラフＧと、解ノードの個数を示すｋ（ｋはノードの数を超えない正整数）の入力を受け付ける（ステップＳ１０）。続いて、検索装置１０の部分グラフ構築部１１は、繰り返し計算回数を示すｉに０をセットし、候補ノードの集合Ｖの初期集合にＣ０をセットし、グラフＧの部分グラフの初期集合にＧ０をセットする初期化をおこなう（ステップＳ１２）。
【００５９】
続いて、検索装置１０の部分グラフ構築部１１は、ｉ≠０であるか否かを判定する（ステップＳ１３）。検索装置１０の部分グラフ構築部１１は、ｉ≠０である場合に（ステップＳ１３Ｙｅｓ）、ステップＳ１４へ処理を移す。一方、検索装置１０の部分グラフ構築部１１は、ｉ＝０である場合に（ステップＳ１３Ｎｏ）、ステップＳ１７へ処理を移す。
【００６０】
ステップＳ１４では、検索装置１０の部分グラフ構築部１１は、ｉを＋１インクリメントする。続いて、検索装置１０の部分グラフ構築部１１は、定義３の式（５）および定義４の式（６）に基づいて候補ノードＣｉを計算し、補助定理７に基づいて、幅優先探索により、候補ノードＣｉから部分グラフＧｉ−１に到達可能なノードの集合Ｒｉを計算する（ステップＳ１５）。続いて、検索装置１０の部分グラフ構築部１１は、定義５に基づいて、ノードの集合Ｒｉから部分グラフＧｉを計算する（ステップＳ１６）。
【００６１】
続いて、検索装置１０のランダムウォーク確率計算部１２は、補助定理６および定義６に基づいて、部分グラフＧｉに対応するランダムウォークの確率ｒｉ［ｕ］を計算する（ステップＳ１７）。
【００６２】
続いて、検索装置１０の推定値計算部１３は、ランダムウォークの確率ｒｉ［ｕ］および候補ノードＣｉから、定義６に基づいて、候補ノードＣｉの全てのノードに対してPageRankのスコアの下限値の推定値および上限値の推定値を計算する（ステップＳ１８）。
【００６３】
続いて、検索装置１０の候補ノード計算部１４は、候補ノードＣｉから閾値εｉを計算し、定義３および定義４、ならびに、閾値εｉに基づいて、（ｉ＋１）回目の繰り返し計算における候補ノードの集合Ｃｉ＋１を計算する（ステップＳ１９）。続いて、検索装置１０の候補ノード計算部１４は、候補ノードの集合Ｃｉ＋１の要素数|Ｃｉ＋１|がｋに等しいか否かを判定する（ステップＳ２０）。検索装置１０の候補ノード計算部１４は、要素数|Ｃｉ＋１|がｋに等しい場合には（ステップＳ２０Ｙｅｓ）、ステップＳ２１へ処理を移す。一方、検索装置１０の候補ノード計算部１４は、要素数|Ｃｉ＋１|がｋと異なる場合には（ステップＳ２０Ｎｏ）、ステップＳ１４へ処理を移す。ステップＳ２１では、検索装置１０の候補ノード計算部１４は、候補ノードＣｉ＋１を、解ノードとして出力する。ステップＳ２１が終了すると、検索装置１０は、検索処理を終了する。
【００６４】
以上の検索処理によれば、検索における事前計算を要さず、アドホックに検索をおこなうことができる。また、以上の検索処理によれば、内部パラメータの設定を要さないため、ユーザは、簡易にPageRankによる検索を行うことができる。
【００６５】
（検索アルゴリズム）
図３は、検索アルゴリズムを示す図である。図３に示す検索アルゴリズムは、図２の検索処理のフローチャートが示す処理に対応する。図３に示すように、検索アルゴリズムは、ｉ＝０ならば、定義３および定義５から、集合Ｃ０、グラフＧ０をそれぞれＣ０＝Ｖ、Ｇ０＝Ｇとして初期化する（図３の第２行目〜第３行目）。検索アルゴリズムは、ｉ≠０ならば、グラフＧｉ−１に幅優先探索を用いて集合Ｃｉから集合Ｒｉを計算する（図３の第７行目）。これは、補助定理７から、部分グラフＧｉに対してＧｉ⊆Ｇｉ−１という性質があるからである。そして、検索アルゴリズムは、定義５から、集合Ｒｉを用いて部分グラフＧｉを計算する（図３の第８行目）。
【００６６】
そして、検索アルゴリズムは、部分グラフＧｉにおける各ノードに対してランダムウォークの確率を計算する（図３の第１０行目〜第１２行目）。これは、補助定理６から、推定値を計算するためにランダムウォークの確率が必要だからである。そして、検索アルゴリズムは、候補ノードＣｉに対して推定値を計算し（図３の第１３行目〜第１５行目）、候補ノードＣｉから閾値εｉを計算する（図３の第１６行目）。
【００６７】
また、検索アルゴリズムは、候補ノードを更新し、Ｃｉ＋１を計算する（図３の第１７行目）。検索アルゴリズムは、集合Ｃｉ＋１の要素数|Ｃｉ＋１|がｋと等しい、すなわち|Ｃｉ＋１|＝ｋであれば、補助定理４から、候補ノードの集合Ｃｉ＋１に含まれるノードは全て解ノードである。よって、繰り返し計算を打ち切り（図３の第１８行目）、候補ノードの集合Ｃｉ＋１を解ノードとして出力する（図３の第１９行目）。
【００６８】
（実施形態による効果）
以上の実施形態によれば、従来技術の手法と比較して、PageRankのスコアをグラフ全体ではなく部分グラフから計算することにより、高速に検索が可能である。また、以上の実施形態によれば、入力パラメータｋ（ｋはノード数を超えない自然数）に対し、PageRankのスコアの正確な上位ｋ個のノードを検索できる。また、以上の実施形態によれば、検索に事前計算を要さず、任意のグラフに対してアドホックに検索をおこなうことができる。また、以上の実施形態によれば、内部パラメータの設定を要さないため、ユーザは、PageRankによる検索を簡易におこなうことができる。
【００６９】
（実施形態のシステム構成について）
図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００７０】
また、検索装置１０においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、検索装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００７１】
また、実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００７２】
（プログラムについて）
また、実施形態において説明した検索装置１０のＣＰＵなどの制御装置が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、制御装置が実行する処理をコンピュータが実行可能な言語で記述した検索プログラムを作成することもできる。この場合、コンピュータが検索プログラムを実行することにより、実施形態と同様の効果を得ることができる。さらに、検索プログラムをコンピュータ読み取り可能な記録媒体に記録して、記録媒体に記録された検索プログラムをコンピュータに読み込ませて実行することにより実施形態と同様の処理を実現できる。以下に、図１に示した検索装置１０と同様の機能を実現するプログラムを実行するコンピュータの一例を説明する。
【００７３】
図４は、検索プログラムを実行するコンピュータ１０００の一例を示す図である。コンピュータ１０００は、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらは、バス１０８０によって接続される。
【００７４】
図４に示すように、メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。また、ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。また、ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、磁気ディスクや光ディスクなどの着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０は、例えばマウス１０５１、キーボード１０５２に接続される。また、ビデオアダプタ１０６０は、例えばディスプレイ１０６１に接続される。
【００７５】
ここで、図４に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、検索プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。
【００７６】
また、実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出す。そして、ＣＰＵ１０２０が、検索プログラムの各手順を実行する。
【００７７】
なお、検索プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られない。すなわち、プログラムモジュール１０９３およびプログラムデータ１０９４は、着脱可能な記憶媒体に記憶され、ディスクドライブなどを介してＣＰＵ１０２０によって読み出されてもよい。検索プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）など）を介して接続された他のコンピュータに記憶されていてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出され、実行されてもよい。
【符号の説明】
【００７８】
１０  検索装置
１１  部分グラフ構築部
１２  ランダムウォーク確率計算部
１３  推定値計算部
１４  候補ノード計算部
【図１】
2014229110.tif 000036
【図２】
2014229110.tif 000037
【図３】
2014229110.tif 000038
【図４】
2014229110.tif 000039