(57)【要約】【課題】ノード検索において、高速かつ正確な検索結果を得る。【解決手段】検索装置１００の部分グラフ構築部１１０は、問い合わせに用いるグラフＧと、更新前のｉ回目の繰り返し計算前の部分グラフＧｉ−１と、選択ノードＳを入力とし、更新後のｉ回目の繰り返し計算後の部分グラフＧｉを出力する。ランダムウォーク確率計算部１２０は、更新後の部分グラフＧｉを入力とし、部分グラフＧｉにおける各ノードのランダムウォークの確率ｐｉを出力する。推定値計算部１３０は、各ノードのランダムウォークの確率ｐｉを入力とし、選択ノードＳの推定値を出力する。候補ノード計算部１４０は、選択ノードＳの推定値と、解ノードの個数ｋを入力とし、候補ノードＬを出力する。決定ノード計算部１５０は、候補ノードＬと、候補ノードＬに対応する選択ノードＳの推定値と、解ノードの個数ｋを入力とし、解ノードＡを出力する。【選択図】図１
2014228975.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークを形成する機器をノードとし、前記機器間の接続をエッジとする前記コンピュータネットワークのグラフを、問い合わせノードおよび前記問い合わせノードに対する解ノードの個数を示すｋ（ｋは前記ノードの数を超えない正整数）の入力を受け付けて検索し、前記問い合わせノードに対応する前記ｋ個の解ノードを出力する検索装置であって、
非負整数であるｉについて、前記グラフが含むノードおよびエッジのうち、前記問い合わせノードからのホップ数が前記ｉホップ以内かつ前記問い合わせノードに到達可能なノードおよび当該ノード間を接続するエッジに基づいて前記グラフの前記ｉ番目の部分グラフを構築する部分グラフ構築部と、
前記部分グラフ構築部が構築した前記部分グラフが含む全てのノードごとに、当該ノードから当該ノードとエッジで接続される隣接ノードへランダムウォークで遷移する確率を計算する確率計算部と、
選択ノードの集合が含む全てのノードについて、前記確率計算部が算出した当該ノードに対応する前記確率に基づいて前記問い合わせノードとのノードの類似度の推定値を計算する推定値計算部と、
前記部分グラフ構築部が構築した前記部分グラフが含むノードのうち、前記問い合わせノードとの類似度が所定値より大となる可能性がある候補ノードの集合を計算する候補ノード計算部と、
前記候補ノード計算部が計算した前記候補ノードの集合の要素数が前記ｋと等しいか否かを判定し、前記候補ノードの集合の要素数が前記ｋと等しい場合には前記候補ノードの要素について前記問い合わせノードとの類似度の降順による順序が決定する要素の集合を決定ノードの集合と計算し、前記候補ノードの集合の要素数が前記ｋと異なる場合に前記決定ノードの集合を空集合と計算する決定ノード計算部と、
前記候補ノード計算部が計算した前記候補ノードの集合と、前記決定ノード計算部が計算した前記決定ノードの集合とから前記ｉ＋１番目の選択ノードの集合を計算する選択ノード計算部と、
前記選択ノード計算部が計算した前記選択ノードの集合の要素数が０と等しいか否かを判定し、前記選択ノードの集合の要素数が０と等しい場合には前記決定ノード計算部が計算した前記決定ノードの集合の前記ｋ個のノードを当該各ノードに対応する前記推定値算出部が算出した前記推定値の降順に並び替えて前記推定値が上位の前記ｋ個である解ノードに設定し、前記選択ノードの集合の要素数が０と異なる場合には前記ｉを＋１インクリメントした非負整数をあらたな前記ｉとして前記部分グラフ構築部に前記グラフのあらたな前記ｉ番目の部分グラフを構築させる解ノード設定部と、
前記解ノード設定部が設定した前記解ノードを出力する出力部と
を有し、
前記選択ノードは、前記ｉが０である場合には前記グラフが含む全てのノードの集合であり、前記ｉが１以上である場合には前記選択ノード計算部が前記ｉについて計算した前記ｉ番目の選択ノードの集合であり、
前記解ノード設定部が前記部分グラフ構築部に前記グラフのあらたな前記ｉ番目の部分グラフを構築させる場合は、あらたな前記ｉについて、前記部分グラフ構築部、前記確率計算部、前記推定値計算部、前記候補ノード計算部、前記決定ノード計算部、前記選択ノード計算部、前記解ノード設定部が各処理を再度、順次実行する
ことを特徴とする検索装置。
【請求項２】
さらに、
前記部分グラフ構築部は、
前記ｉが０と等しい場合に、前記グラフと、前記問い合わせノードとから、前記ｉ＝０に対応する前記部分グラフの初期グラフを構築する初期グラフ構築部と、
前記ｉが１以上の非負整数である場合に、前記ｉ−１に対応する更新前の部分グラフと、前記ｉに対応する前記選択ノードとから構築される前記ｉに対応する更新後の部分グラフの候補を出力する候補グラフ構築部と、
前記ｉに対応する前記選択ノードと、前記候補グラフ構築部が構築した前記ｉに対応する更新後の部分グラフの候補から、前記ｉに対応する更新後の部分グラフを構築する部分グラフ構築部と
を有することを特徴とする請求項１に記載の検索装置。
【請求項３】
コンピュータネットワークを形成する機器をノードとし、前記機器間の接続をエッジとする前記コンピュータネットワークのグラフを、問い合わせノードおよび前記問い合わせノードに対する解ノードの個数を示すｋ（ｋは前記ノードの数を超えない正整数）の入力を受け付けて検索し、前記問い合わせノードに対応する前記ｋ個の解ノードを出力する検索装置で実行される検索方法であって、
非負整数であるｉについて、前記グラフが含むノードおよびエッジのうち、前記問い合わせノードからのホップ数が前記ｉホップ以内かつ前記問い合わせノードに到達可能なノードおよび当該ノード間を接続するエッジに基づいて前記グラフの前記ｉ番目の部分グラフを構築する部分グラフ構築工程と、
前記部分グラフ構築工程が構築した前記部分グラフが含む全てのノードごとに、当該ノードから当該ノードとエッジで接続される隣接ノードへランダムウォークで遷移する確率を計算する確率計算工程と、
選択ノードの集合が含む全てのノードについて、前記確率計算工程が算出した当該ノードに対応する前記確率に基づいて前記問い合わせノードとのノードの類似度の推定値を計算する推定値計算工程と、
前記部分グラフ構築工程が構築した前記部分グラフが含むノードのうち、前記問い合わせノードとの類似度が所定値より大となる可能性がある候補ノードの集合を計算する候補ノード計算工程と、
前記候補ノード計算工程が計算した前記候補ノードの集合の要素数が前記ｋと等しいか否かを判定し、前記候補ノードの集合の要素数が前記ｋと等しい場合には前記候補ノードの要素について前記問い合わせノードとの類似度の降順による順序が決定する要素の集合を決定ノードの集合と計算し、前記候補ノードの集合の要素数が前記ｋと異なる場合に前記決定ノードの集合を空集合と計算する決定ノード計算工程と、
前記候補ノード計算工程が計算した前記候補ノードの集合と、前記決定ノード計算工程が計算した前記決定ノードの集合とから前記ｉ＋１番目の選択ノードの集合を計算する選択ノード計算工程と、
前記選択ノード計算工程が計算した前記選択ノードの集合の要素数が０と等しいか否かを判定し、前記選択ノードの集合の要素数が０と等しい場合には前記決定ノード計算工程が計算した前記決定ノードの集合の前記ｋ個のノードを当該各ノードに対応する前記推定値算出工程が算出した前記推定値の降順に並び替えて前記推定値が上位の前記ｋ個である解ノードに設定し、前記選択ノードの集合の要素数が０と異なる場合には前記ｉを＋１インクリメントした非負整数をあらたな前記ｉとして前記部分グラフ構築工程に前記グラフのあらたな前記ｉ番目の部分グラフを構築させる解ノード設定工程と、
前記解ノード設定工程が設定した前記解ノードを出力する出力工程と
を含み、
前記選択ノードは、前記ｉが０である場合には前記グラフが含む全てのノードの集合であり、前記ｉが１以上である場合には前記選択ノード計算工程が前記ｉについて計算した前記ｉ番目の選択ノードの集合であり、
前記解ノード設定工程が前記部分グラフ構築工程に前記グラフのあらたな前記ｉ番目の部分グラフを構築させる場合は、あらたな前記ｉについて、前記部分グラフ構築工程、前記確率計算工程、前記推定値計算工程、前記候補ノード計算工程、前記決定ノード計算工程、前記選択ノード計算工程、前記解ノード設定工程が各処理を再度、順次実行する
ことを特徴とする検索方法。
【請求項４】
さらに、
前記部分グラフ構築工程は、
前記ｉが０と等しい場合に、前記グラフと、前記問い合わせノードとから、前記ｉ＝０に対応する前記部分グラフの初期グラフを構築する初期グラフ構築工程と、
前記ｉが１以上の非負整数である場合に、前記ｉ−１に対応する更新前の部分グラフと、前記ｉに対応する前記選択ノードとから構築される前記ｉに対応する更新後の部分グラフの候補を出力する候補グラフ構築工程と、
前記ｉに対応する前記選択ノードと、前記候補グラフ構築工程が構築した前記ｉに対応する更新後の部分グラフの候補から、前記ｉに対応する更新後の部分グラフを構築する部分グラフ構築工程と
を含むことを特徴とする請求項３に記載の検索方法。
【請求項５】
コンピュータを、
請求項１または２に記載の検索装置として機能させるための検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法および検索プログラムに関する。
【背景技術】
【０００２】
近年、ソーシャルネットワークに代表されるように、大規模なネットワークの利用が進んでいる。そして、大規模なネットワークに対して、データマイニングや検索をおこなうシステムの重要性が増している。ネットワーク構成は、ネットワークを構築するコンピュータをノードとし、各ノード間の接続を示すリンクをエッジとするグラフデータとして表現できる。このため、ネットワーク構成をグラフデータとして取り扱うグラフデータベースに問い合わせをおこない、グラフのノードの検索、分類、解析などをおこなうことへの関心が高まりつつある。
【０００３】
例えば、ノードとしてのコンピュータがウェブサイトである場合に、ウェブページの重要度を決定するためのアルゴリズムとしてPageRankのアルゴリズムがある。このPageRankのアルゴリズムが発表されて以来、グラフデータにおけるノードのリンク関係に基づいてノードの類似度を用いる処理の重要性が増している。ノードの類似度は、グラフのリンク構造からノードの類似度を取り出す目的で用いられており、ノードの類似度を用いることによりグラフのノードを検索、分類、解析などをおこなうことができる。
【０００４】
従来から、ノードの類似度の計算手法として多くのものが提案されているが、Personalized  Page  Rank（ＰＰＲ）（例えば非特許文献１参照）は、それらの中でも最も用いられるものの一つである。各ノードのＰＰＲのスコアは、ランダムウォークの定常状態における確率として得られる。具体的には、ＰＰＲにおける各処理ステップは、現在のノードに接続されるエッジを一つランダムに選択し、選択したエッジを経由して現在のノードから他のノードへ移動する。そして、ＰＰＲにおける各処理ステップは、一定の確率ｃ（ｃは、０＜ｃ＜１なる実数）で、問い合わせノードの一つにランダムにジャンプする。ここで、確率ｃは、スケーリングパラメータとよばれる。
【０００５】
ここで、アプリケーションを用いるノード検索などは、インタラクティブに処理される。例えば、インタラクティブなノード検索は、グラフやスケーリングパラメータをアドホックに変更する。このようにしてノード検索をおこなうことには、２つの理由がある。１つ目の理由は、ノード検索を実際におこなうまでは検索対象となるグラフが不明であることである。これは、グラフが動的に変化するなどに起因する。２つ目の理由は、スケーリングパラメータが検索結果へ影響を与えることである。これは、アプリケーションごとに求められる検索結果が異なるため、スケーリングパラメータを動的に設定し、適切な値に変更することを要するためである。
【０００６】
なお、ＰＰＲについて上述したが、Random  Walk  with  Restart（ＲＷＲ）（例えば非特許文献２参照）についても、同様である。これは、ＲＷＲが、特殊ケースとしてＰＰＲに含まれるためである。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Glen  Jeh、Jennifer  Widom、“Scaling  Personalized  Web  Search”、WWW2003、May  20−24  2003
【非特許文献２】Yasuhiro  Fujiwara、Makoto  Nakatsuji、Makoto  Onizuka、Masaru  Kitsuregawa、“Fast  and  Exact  Top-k  Search  for  Random  Walk  with  Restart”、The  38th  International  Conference  on  Very  Large  Data  Bases、August  27th-31th  2012
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述の従来技術では、ノード検索のための計算コストが大きく、高速かつ正確な検索結果が得られない。すなわち、上述の従来技術では、総ノード数をＮ、総エッジ数をＭ、ノード検索のための繰り返しの計算回数をＴとすると（Ｎ、Ｍ、Ｔは自然数）、ノード検索のために、Ｏ（（Ｎ＋Ｍ）・Ｔ)という高い計算コストを要するためである。なお、Ｏ（＊）は、ランダウの記号である。
【０００９】
本願が開示する技術は、上記に鑑みてなされたものであって、ノード検索において、高速かつ正確な検索結果を得ることを目的とする。
【課題を解決するための手段】
【００１０】
本願が開示する技術は、一つの実施形態として、コンピュータネットワークを形成する機器をノードとし、機器間の接続をエッジとするコンピュータネットワークのグラフを、問い合わせノードおよび問い合わせノードに対する解ノードの個数を示すｋ（ｋはノードの数を超えない正整数）の入力を受け付けて検索し、問い合わせノードに対応するｋ個の解ノードを出力する検索装置である。さらに、検索装置は、非負整数であるｉについて、グラフが含むノードおよびエッジのうち、問い合わせノードからのホップ数がｉホップ以内かつ問い合わせノードに到達可能なノードおよび当該ノード間を接続するエッジに基づいてグラフのｉ番目の部分グラフを構築する。さらに、検索装置は、部分グラフが含む全てのノードごとに、当該ノードから当該ノードとエッジで接続される隣接ノードへランダムウォークで遷移する確率を計算する。さらに、検索装置は、選択ノードの集合が含む全てのノードについて、当該ノードに対応する確率に基づいて問い合わせノードとのノードの類似度の推定値を計算する。さらに、検索装置は、部分グラフが含むノードのうち、問い合わせノードとの類似度が所定値より大となる可能性がある候補ノードの集合を計算する。さらに、検索装置は、候補ノードの集合の要素数がｋと等しいか否かを判定し、候補ノードの集合の要素数がｋと等しい場合には候補ノードの要素について問い合わせノードとの類似度の降順による順序が決定する要素の集合を決定ノードの集合と計算し、候補ノードの集合の要素数がｋと異なる場合に決定ノードの集合を空集合と計算する。さらに、検索装置は、候補ノードの集合と、決定ノードの集合とからｉ＋１番目の選択ノードの集合を計算する。さらに、検索装置は、選択ノードの集合の要素数が０と等しいか否かを判定し、選択ノードの集合の要素数が０と等しい場合には計算した決定ノードの集合のｋ個のノードを当該各ノードに対応する算出した推定値の降順に並び替えて推定値が上位のｋ個である解ノードに設定し、選択ノードの集合の要素数が０と異なる場合にはｉを＋１インクリメントした非負整数をあらたなｉとしてグラフのあらたなｉ番目の部分グラフを構築する。なお、検索装置において、選択ノードは、ｉが０である場合にはグラフが含む全てのノードの集合であり、ｉが１以上である場合にはｉについて計算したｉ番目の選択ノードの集合であり、グラフのあらたなｉ番目の部分グラフを構築させる場合は、あらたなｉについて、上述の各処理が再度、順次実行される。
【発明の効果】
【００１１】
本願が開示する技術によれば、ノード検索において、高速かつ正確な検索結果を得ることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、検索装置の構成を示すブロック図である。
【図２】図２は、部分グラフ構築部を示すブロック図である。
【図３】図３は、検索処理を示すフローチャートである。
【図４】図４は、部分グラフ計算処理を示すフローチャートである。
【図５】図５は、検索アルゴリズムを示す図である。
【図６】図６は、部分グラフ構築アルゴリズムを示す図である。
【図７】図７は、検索プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本願が開示する技術にかかる検索装置などの実施形態を図面に基づいて説明する。以下の実施形態は、コンピュータネットワークを形成する機器をノードとし、機器間の接続をエッジとするコンピュータネットワークのグラフを、問い合わせノードおよび問い合わせノードに対する解ノードの個数を示すｋ（ｋはノードの数を超えない正整数）の入力を受け付けて検索し、問い合わせノードに対応するｋ個の解ノードを出力する。なお、以下の実施形態は、一例を示すに過ぎず、本願が開示する技術を限定するものではない。また、以下の実施形態は、矛盾しない範囲内で適宜組み合わせることができる。
【００１４】
［記号の定義］
実施形態の説明で用いる記号を下表に示す。なお、実施形態の説明では、行列をボールド体のラテン大文字、ベクトルをボールド体のラテン小文字で表記する。
【００１５】
【表１】
2014228975.tif 000003
【００１６】
（従来技術の概要）
実施形態の説明に先立ち、従来技術について説明する。従来技術では、PageRankと同様に、ランダムサーファモデルに基づき、Jehらによって提案されたＰＰＲをノードの類似度として計算し、グラフ全体におけるノードの類似度をユーザごとに個別化する（非特許文献１参照）。すなわち、ユーザごとにノードを任意に設定し、設定されたノードの優先度に基づいてノードの重要度を計算する。ここで、ユーザごとに設定されたノードを問い合わせノードとすると、各ノードの重要度は、問い合わせノードに対する類似度であると捉えることができる。問い合わせノードは、検索対象のノードである。なお、ＲＷＲは、ＰＰＲにおいて単独のノードのみが問い合わせノードとして設定された場合に該当する。
【００１７】
ＰＰＲにおけるノードの類似度は、定常状態におけるランダムウォークの確率に対応する。ＰＰＲの各処理ステップは、現在のノードに隣接する複数の隣接ノードから１つの隣接ノードを確率ｃで選択する。また、ＰＰＲの各処理ステップは、問い合わせノードの一つへ、問い合わせノードの値にしたがって確率（１−ｃ）で遷移する。以下、ＰＰＲにおけるノードの類似度を、ＰＰＲのスコアもしくはノードのスコアと呼ぶ。
【００１８】
ここで、Ｖをグラフのノード集合、Ｅをグラフのエッジ集合とすると、問い合わせ対象のグラフはＧ＝｛Ｖ，Ｅ｝となる。また、
2014228975.tif 000004
をＮ×１（Ｎ行１列、Ｎは自然数）であるＰＰＲのスコアを示すベクトル（以下、ＰＰＲのスコアベクトルと呼ぶ）とすると、ノードｕ（ｕ∈Ｖ）のスコアｓ［ｕ］は、ＰＰＲのスコアベクトルのｕ番目の要素に該当する。
2014228975.tif 000005
は、列の合計が１になるように正規化されたグラフの隣接行列であり、その要素Ｗ［ｕ，ｖ］（ｕ，ｖ∈Ｖ）は、ノードｖからノードｕへランダムウォークが遷移する確率となる。ＰＰＲのスコアベクトルは、以下の式（１）を再帰的に計算することによって得る。
【００１９】
【数１】
2014228975.tif 000006
【００２０】
なお、式（１）における
2014228975.tif 000007
は、問い合わせノードのベクトルであり、そのｕ番目の値ｑ［ｕ］は、問い合わせノードとしての優先度に対応する。なお、ノードｕが問い合わせノードでなければｑ［ｕ］＝０である。問い合わせノードの優先度に対応するｑ［ｕ］の合計は、１になるように正規化されている。
【００２１】
（従来技術の問題点）
しかし、式（１）により再帰的に計算を行う上述の従来技術の手法は、上位ｋ個のノード検索をおこなうことには適切ではない。それは、従来技術の手法では、式（１）による各繰り返し計算において、全てのノードのスコアを更新することを要するためである。さらに、従来技術の手法では、正確なノードのスコアに基づくランキングで上位ｋ個のノードを検索するために、ノードのスコアが収束するまで、式（１）による繰り返し計算をおこなうことを要する。しかし、アプリケーションにおいては、ランキングが重要であり、ノードのスコアは必ずしも重要ではない。このため、従来技術の手法は、必ずしも重要ではないノードのスコアを含む繰り返し計算のためにＯ（（Ｎ＋Ｍ）・Ｔ)の計算コストを要するため、大規模なグラフに対して高速にノード検索をおこなうことが難しい。なお、Ｏ（＊）は、ランダウの記号である。
【００２２】
［実施形態］
（実施形態の概要）
以下に説明する実施形態は、上述の従来技術の問題点を解決するものである。上述したように、従来技術の手法は、定常状態における確率を計算することを要し、再帰的にグラフ全体を用いてノードのスコアを計算するため、高い計算コストとなる。その一方、実施形態は、上位ｋ個のノードを高速に求めるため、選択されたノードに対してのみ、式（１）により再帰的にＰＰＲのスコアベクトルの推定値を更新する。
【００２３】
また、実施形態は、ノードの類似度の推定値を高速に更新するために、グラフ全体から不要なノードとエッジを除外するように、動的に部分グラフを構築する。また、実施形態は、ノードの推定値を計算するために要するランダムウォークの確率を部分グラフから計算する。また、実施形態は、不要なノードとエッジを特定するために、ノードの類似度の下限値と上限値を推定する。また、実施形態は、繰り返し計算の中で得られる部分グラフから解ノードを検索する。
【００２４】
以下の実施形態では、まず、実施形態にかかる計算処理方法および理論的背景を説明し、次に、実施形態にかかる検索装置の構成および処理を説明する。
【００２５】
＜計算処理方法および理論的背景＞
（ノードの類似度の計算方法）
実施形態は、ノードの類似度の推定値を求めるために、問い合わせノードの１つから開始してノードｕに到達する長さがｉ（ｉ＝０，１，２，・・・、（非負整数））のランダムウォークの確率ｐｉ［ｕ］を用いる。このランダムウォークにおいては、一定確率（１―ｃ）で問い合わせノードに遷移することはない。ここで、Ｎ×１のベクトル 
2014228975.tif 000008
を、ｕ番目の要素がＰｉ［ｕ］に対応するベクトルとする。
2014228975.tif 000009
は、隣接行列のｉ乗から、
2014228975.tif 000010
と計算することができる。ここで、明らかに
2014228975.tif 000011
であるため、長さｉのランダムウォークの確率
2014228975.tif 000012
は、
2014228975.tif 000013
から、以下の式（２）のように逐次的に計算できる。
【００２６】
【数２】
2014228975.tif 000014
【００２７】
ここで、式（２）におけるＣ［ｕ］は、ノードｕと接続するエッジ集合とする。すなわち、Ｃ［ｕ］は、問い合わせ対象のグラフＧにおいて、ノードｕと直接隣接するノードの集合と見なしうる。実施形態では、式（２）のｉ番目の繰り返し計算における選択ノード集合Ｓｉを計算し、選択ノード集合Ｓｉに対して、ノードの類似度の下限値および上限値を推定する。選択ノード集合Ｓｉの初期集合は、グラフＧのノード集合Ｖである。すなわち、Ｓ０＝Ｖである。また、Ｓｉは、つねにＳｉ−１に含まれるように設定される。すなわち、Ｖ＝Ｓ０⊇Ｓ１⊇Ｓ２・・・⊇Ｓｉ−１⊇Ｓｉである。具体的なノードの選択方法は、後述する。
【００２８】
ノードの類似度の上限値を計算するために、ノード集合Ｒｉを用いる。Ｒｉは、選択ノード集合Ｓｉに含まれるいずれか１つのノードへランダムウォークにより到達可能なノード集合である。なお、ノードｕがノードｖへ到達可能とは、問い合わせ対象のグラフＧにおいて、ノードｕからノードｖへのパスがあるということである。
【００２９】
ここで、明らかに、Ｓｉ⊆Ｒｉであり、ｕ∈ＳｉならばＣ［ｕ］⊆Ｒｉである。また、Ｐｉ［Ｒｉ］は、長さがｉのランダムウォークが、問い合わせノードｑ∈Ｑから始まってＲｉのいずれかのノードに到達する確率であり、
2014228975.tif 000015
と計算される。ここで、ノードの類似度の上限値を計算するためにＷｍａｘ［ｕ］を導入する。Ｗｍａｘ［ｕ］は、ノードｕと接続するエッジの最大の重みである。すなわち、Ｗｍａｘ［ｕ］＝ｍａｘ｛Ｗ［ｕ，ｖ］：ｖ∈Ｖ｝である。
【００３０】
（ノードの類似度の下限値）
ノードの類似度の下限値は、各繰り返し計算において以下のようにランダムウォークの確率を用いて計算される。以下のように、ノードｕの下限値
2014228975.tif 000016
を定義する。
【００３１】
【数３】
2014228975.tif 000017
【００３２】
定義１は、ｉ＝０ならば、ノードｕの下限値は、ランダムウォークの確率とスケーリングパラメータから計算できることを示す。また、定義１は、ｉ≠０ならば、ノードｕの下限値は、ランダムウォークの確率とスケーリングパラメータから逐次的に計算されることを示す。また、定義１は、ランダムウォークの確率ｐｉ［ｕ］が計算されていれば、ノードｕの下限値は、Ｏ（１）のオーダで計算できることを示す。式（３）で定義するノードｕの下限値の性質について、以下の補助定理１を示す。
【００３３】
【数４】
2014228975.tif 000018
【００３４】
（ノードの類似度の上限値）
ノードの類似度の上限値を計算するために定義１によるノードの類似度の下限値を利用する。ノードの類似度の上限値は、以下のように、ノードｕの上限値
2014228975.tif 000019
を定義する。
【００３５】
【数５】
2014228975.tif 000020
【００３６】
定義２は、ノードｕの上限値は、スケーリングパラメータｃ、ノードｕと接続するエッジの最大の重みＷｍａｘ［ｕ］、ランダムウォークの確率ｐｉ［ｕ］を用いることにより、Ｏ（１）のオーダで計算できることを示す。ノードｕの上限値の性質について、以下の補助定理２を示す。
【００３７】
【数６】
2014228975.tif 000021
【００３８】
定義１および定義２に示すように、ノードｕの下限値および上限値は、各繰り返し計算において、ランダムウォークの確率から推定される。ノードｕの下限値および上限値の推定値は、繰り返し計算の繰り返し回数が進むごとに推定の精度が上がっていくという性質を有する。ノードｕの下限値および上限値の推定値の精度向上の性質について、以下の補助定理３を示す。
【００３９】
【数７】
2014228975.tif 000022
【００４０】
後述するように、補助定理３により、ノードの類似度の推定値が収束するまで計算せずとも、正確なランキングで上位ｋ個のノードを検索することができる。ノードの類似度の下限値および上限値が、正確な類似度に収束するという性質について、以下の補助定理４を示す。
【００４１】
【数８】
2014228975.tif 000023
【００４２】
（ノードの選択）
実施形態は、問い合わせ対象のグラフＧの部分グラフＧｉを繰り返し計算の中で動的に構築し、ランダムウォークの確率ｐｉ［ｕ］を高速に計算する。そして、実施形態は、選択ノードＳに対するノードの類似度の下限値および上限値を、ランダムウォークの確率ｐｉ［ｕ］を用いて計算する。以下では、部分グラフＧｉを構築する際のノードの選択方法について述べる。
【００４３】
実施形態は、解ノードになる可能性があるノードが、ノードの類似度の推定値を用いても解ノードとしてのランキングが決定できないならば、ノードの類似度の下限値および上限値を計算するために、当該のノードを選択する。その際、ｉ番目の繰り返し計算におけるノードの類似度の下限値のうちｋ番目の大きさのものをθｉとし、ｉ番目の繰り返し計算における解ノードの候補ノード集合Ｌｉを、以下のように定義する。
【００４４】
【数９】
2014228975.tif 000024
【００４５】
定義３は、あるノードの類似度の上限値がｉ以上ならば、当該のノードは、候補ノードとなることを示す。これは、あるノードの類似度の推定値がｉならば、当該のノードの正確な類似度はｉ以上になることがないため、解ノードになり得ないからである。後述するように、候補ノード集合は、繰り返し計算の中で単調減少する性質がある。ｉ番目の繰り返し計算において、解ノードとしてのランキングが決定した決定ノード集合Ｄｉを、以下のように定義する。
【００４６】
【数１０】
2014228975.tif 000025
【００４７】
定義４は、次を示す。すなわち、解ノードの数がｋ個であり、かつ、ノードの類似度の下限値または上限値が、
2014228975.tif 000026
と
2014228975.tif 000027
の間にあるノードｖが存在しないノードｕ（ｕ≠ｖ）は、決定ノードとなる。すなわち、下限値または上限値が、
2014228975.tif 000028
と
2014228975.tif 000029
の間にノードが存在すれば、ノードｕは、決定ノードとならない。
【００４８】
定義４において、|Ｌｉ|＝ｋならば、決定ノード集合Ｄｉを計算するコストはＯ（ｋ・logｋ）である。これは、Ｌｉのノードを並び変えることによってＤｉが得られるからである。また|Ｌｉ|≠ｋならば、式（２１）から、Ｄｉを計算しなくてよい。候補ノード集合ＬｉとＤｉの定義から、選択ノード集合Ｓｉを、以下のように定義する。
【００４９】
【数１１】
2014228975.tif 000030
【００５０】
定義５は、まず全てのノードに対してノードの類似度の推定値を計算し、ランキングが決定している候補ノードでないノードの推定値を更新しないことを示す。すなわち、定義５は、ノードの類似度の推定値を、候補ノードでかつランキングが決定していない場合のみ更新することを示す。
【００５１】
以下、選択ノードの性質を示すために候補ノード集合Ｌｉと、決定ノード集合Ｄｉの性質に関する補助定理を示す。まず、候補ノード集合Ｌｉについて、以下の補助定理５および補助定理６を示す。
【００５２】
【数１２】
2014228975.tif 000031
【００５３】
【数１３】
2014228975.tif 000032
【００５４】
補助定理３から、集合Ｌｉを計算するには全てのノードを要するが、繰り返し計算においてより効率的に集合Ｌｉを計算できる。ｉ≠０かつ|Ｌｉ−１|≠ｋならば、集合Ｌｉは、以下のように計算できる。
【００５５】
【数１４】
2014228975.tif 000033
【００５６】
式（２４）は、式（１９）において、ＶをＬｉ−１で置き換えることによって得られる。すなわち、集合Ｌｉ−１から集合Ｌｉを逐次的に計算できる。これは、あるノードが集合Ｌｉ−１に含まれてなければ、補助定理５から、当該のノードが集合Ｌｉに含まれることはないからである。さらに、ｉ≠０かつ|Ｌｉ−１|＝ｋならば、集合Ｌｉは、以下のように計算できる。
【００５７】
【数１５】
2014228975.tif 000034
【００５８】
そして、決定ノード集合Ｄｉの性質にについて、補助定理５および補助定理６に基づいて、以下の補助定理７および補助定理８を示す。
【００５９】
【数１６】
2014228975.tif 000035
【００６０】
【数１７】
2014228975.tif 000036
【００６１】
補助定理５および補助定理７から、候補ノード集合Ｌｉは単調増加し、決定ノード集合Ｄｉは単調減少することが分かる。そして、補助定理６および８から、候補ノード集合Ｌｉおよび決定ノード集合Ｄｉは、収束後において解ノード集合Ａと等しくなることが分かる。そのため、選択ノードＳｉの性質について、以下の補助定理が成り立つ。
【００６２】
【数１８】
2014228975.tif 000037
【００６３】
定義５のとおり、選択ノードＳｉは、グラフＧの更新前のノード集合に初期化されるため、選択ノードＳｉは、Ｖ＝Ｓ０⊇Ｓ１⊇Ｓ２・・・⊇Ｓｉ−１⊇Ｓｉ・・・⊇Ｓ∞である。さらに、Ｓ∞＝φということは、更新するべきノードがないことを示している。すなわち、実施形態は、有限の繰り返し回数で、ノードの類似度の推定値の計算が終了することを示す。
【００６４】
（部分グラフの構築）
実施形態は、ノードの類似度の推定値の算出に不必要なノードとエッジを除外し、高速に推定値を更新する。まず、部分グラフの定義およびその性質を説明する。そして、各繰り返し計算において逐次的に部分グラフを更新する方法を説明する。定義１および定義２から、ノードの類似度の推定値の下限値および上限値は、式（２）で与えられるランダムウォークの確率を用いて計算できる。このため、実施形態は、ランダムウォークの確率を高速に計算するために、部分グラフを構築する。実施形態は、部分グラフを構築するために、問い合わせノードからのホップ数がｉ以内であるノード集合Ｈｉを用いる。集合Ｈｉは、問い合わせノードからのホップ数がｉより大きくなるノードは含まれない。ｉ番目の繰り返し計算における部分グラフＧｉを、ノード集合Ｈｉを用いて、以下のように定義する。
【００６５】
【数１９】
2014228975.tif 000038
【００６６】
定義６は、ｉ番目の繰り返し計算による更新前の部分グラフＧｉにおいて、問い合わせノードからのホップ数がｉホップ以内であり、問い合わせノードに到達可能であるノードは、部分グラフＧｉに含まれることを示す。また、定義６は、部分グラフＧｉにおいて２つのノードがエッジで接続されており、当該の２つのノードがともに部分グラフＧｉに含まれるならば、当該のエッジは、部分グラフＧｉに含まれることを示す。部分グラフＧｉの性質について、以下の補助定理１０を示す。
【００６７】
【数２０】
2014228975.tif 000039
【００６８】
補助定理１０の証明から、選択ノードＳｉに対して、部分グラフＧｉからランダムウォークの確率ｐｉ［ｕ］と、ノードの類似度の推定値を計算できることがわかる。部分グラフＧｉを用いて、以下のように、ノードの類似度の下限値および上限値を効率的に計算できる。以下のように、部分グラフＧｉによるランダムウォークの確率ｐｉ［ｕ］の計算方法を定義する。
【００６９】
【数２１】
2014228975.tif 000040
【００７０】
式（２９）は、式（２）において、Ｃ［ｕ］をＣｉ［ｕ］へ置き換えることで得ることができる。上位ｋ個のノードを高速に検索するために、式（２９）を用いて、部分グラフＧｉからランダムウォークの確率ｐｉ［ｕ］を計算する。ノードの類似度の推定値の下限値および上限値は、定義１および定義２からそれぞれ計算する。ノードの類似度の推定値の下限値および上限値を単純計算するには、問い合わせ対象のグラフＧ全体を処理することを要するが、部分グラフＧｉを用いることにより、ノードの類似度の推定値を効率的に計算できる。
【００７１】
しかし、定義６をそのまま適用すると、問い合わせ対象のグラフＧの全てのノードを用いて部分グラフＧｉを計算することを要する。このため、効率性の観点から、ノード集合ｈｉとエッジ集合ｅｉを用いて、繰り返し計算において逐次的に部分グラフを構築する。ここでノード集合ｈｉは、問い合わせノードからのホップ数がｉであるノードの集合である。そのため、ｈ０＝Ｈ０＝Ｑであり、
2014228975.tif 000041
である。また、ｅｉは、ノード集合ｈｉとノード集合Ｈｉの各ノード間のエッジの集合である。すなわち、Ｈｉ＝Ｈｉ−１＋ｈｉであるため、ｅｉ＝｛（ｕ，ｖ）∈Ｅ：ｕ∈ｈｉ，ｖ∈Ｈｉ−１  or  ｕ∈Ｈｉ−１，ｖ∈ｈｉ  or  ｕ∈ｈｉ，ｖ∈Ｈｉ｝である。なお、ｈｉとｅｉは、問い合わせ対象のグラフＧ全体に対して問い合わせノードをルートノードとし、１回だけ幅優先探索をおこなえば得ることができる。そのため、ノード集合ｈｉとエッジ集合ｅｉは、Ｏ（Ｎ＋Ｍ）の計算コストで得られる。ノード集合ｈｉとエッジ集合ｅｉの性質について、以下の補助定理１１を示す。
【００７２】
【数２２】
2014228975.tif 000042
【００７３】
補助定理１１から、繰り返し計算において逐次的に部分グラフを構築することができることが分かる。グラフ
2014228975.tif 000043
を、
2014228975.tif 000044
とすると、
2014228975.tif 000045
であり、
2014228975.tif 000046
であるため、グラフ
2014228975.tif 000047
を逐次的に構築することができる。すなわち、グラフ
2014228975.tif 000048
は、グラフＧｉ−１に、問い合わせノードからｉホップだけ離れたノードおよび当該のノードに接続されるエッジを加算することで得られる。
【００７４】
ここで、補助定理１１より、
2014228975.tif 000049
であり、ノード集合Ｈｉとエッジ集合ｅｉは、選択ノード集合Ｓｉへのパスではないノードとエッジを含むため、幅優先探索によりグラフ
2014228975.tif 000050
における選択ノード集合Ｓｉへのパスを幅優先探索で求めることで、部分グラフＧｉを計算できる。
【００７５】
以上から、以下の２つの主張を、定理として示す。
【００７６】
【数２３】
2014228975.tif 000051
【００７７】
【数２４】
2014228975.tif 000052
【００７８】
＜検索装置の構成および処理＞
（検索装置の構成）
図１は、検索装置の構成を示すブロック図である。実施形態にかかる検索装置１００は、ノード検索の問い合わせに用いるグラフＧと、スケーリングパラメータｃと、問い合わせノードＱと、解ノードの個数ｋを入力とし、ノードの類似度の降順でソートされたｋ個の解ノードＡを出力する。問い合わせノードは、検索対象のノードである。図１に示すように、検索装置１００は、部分グラフ構築部１１０、ランダムウォーク確率計算部１２０、推定値計算部１３０、候補ノード計算部１４０、決定ノード計算部１５０、選択ノード計算部１６０を有する。
【００７９】
部分グラフ構築部１１０は、問い合わせに用いるグラフＧと、更新前つまり式（１）によるｉ回目の繰り返し計算前の部分グラフＧｉ−１と、選択ノードＳを入力とし、更新後つまり式（１）によるｉ回目の繰り返し計算後の部分グラフＧｉを出力する。ランダムウォーク確率計算部１２０は、更新後の部分グラフＧｉを入力とし、部分グラフＧｉにおける各ノードのランダムウォークの確率ｐｉを出力する。推定値計算部１３０は、各ノードのランダムウォークの確率ｐｉを入力とし、選択ノードＳの推定値を出力する。
【００８０】
候補ノード計算部１４０は、選択ノードＳの推定値と、解ノードの個数ｋを入力とし、候補ノードＬを出力する。決定ノード計算部１５０は、候補ノードＬと、候補ノードＬに対応する選択ノードＳの推定値と、解ノードの個数ｋを入力とし、解ノードＡを出力する。選択ノード計算部１６０は、候補ノードＬと、候補ノードＬに対応する選択ノードＳの推定値と、解ノードの個数ｋと、決定ノードＤを入力とし、選択ノードＳを出力する。
【００８１】
（部分グラフ構築部の構成）
図２は、部分グラフ構築部を示すブロック図である。実施形態にかかる検索装置１００の部分グラフ構築部１１０は、初期グラフ構築部１１１、候補グラフ構築部１１２、部分グラフ構築部１１３を有する。初期グラフ構築部１１１は、問い合わせに用いるグラフＧと、繰り返し番号ｉ＝０と、問い合わせノードＱを入力とし、部分グラフＧ０を初期値として出力する。候補グラフ構築部１１２は、繰り返し番号ｋと、更新前つまり式（１）によるｉ回目の繰り返し計算前の部分グラフＧｉ−１と、選択ノードＳを入力とし、更新後つまり式（１）によるｉ回目の繰り返し計算後の部分グラフＧｉの候補を出力する。部分グラフ構築部１１３は、選択ノードＳと、部分グラフＧｉの候補を入力とし、更新後の部分グラフＧｉを出力する。
【００８２】
（検索処理）
図３は、検索処理を示すフローチャートである。図３に示す検索処理における繰り返し計算回数を示すｉの初期値は、０である。まず、検索装置１００の部分グラフ構築部１１０は、問い合わせ対象のグラフＧ、スケーリングパラメータｃ、解ノード個数ｋ、問い合わせノードＱの入力を受け付ける（ステップＳ１１）。続いて、検索装置１００の部分グラフ構築部１１０は、定義６の式（２７）、式（２８）に基づき、ｉ回目の繰り返し計算における問い合わせ対象のグラフＧの部分グラフＧｉを計算する処理をおこなう（ステップＳ１２）。ステップＳ１２の処理の詳細は、図４を参照して後述する。
【００８３】
続いて、検索装置１００のランダムウォーク確率計算部１２０は、定義７の式（２９）に基づき、ステップＳ１２で計算された部分グラフＧｉの全てのノードに対して、ランダムウォーク確率を計算する（ステップＳ１３）。続いて、検索装置１００の推定値計算部１３０は、定義５の式（２２）に基づき計算される全ての選択ノードＳｉに対して、補助定理１の式（５）に基づき、ノードの類似度の推定値を計算する（ステップＳ１４）。なお、ステップＳ１４が第１回目に実行される場合は、ｉ番目の繰り返し計算回数を示すｉが０であるので、ステップＳ１４でのノードの類似度の推定値の算出対象の選択ノードは、定義５の式（２２）に基づきＳ０＝Ｖとなる。また、ステップＳ１４が第２回目以降に実行される場合は、ステップＳ１４でのノードの類似度の推定値の算出対象の選択ノードは、後述のステップＳ１９により定義５の式（２２）に基づき計算されたｉ＋１番目の繰り返し計算回数についての選択ノードＳｉ＋１となる。
【００８４】
続いて、検索装置１００の候補ノード計算部１４０は、定義３の式（１９）に基づき、ｉ番目の繰り返し計算において正確な類似度がθｉより大きくなりうる候補ノード集合Ｌｉを計算する（ステップＳ１５）。続いて、検索装置１００の決定ノード計算部１５０は、ステップＳ１５で計算した候補ノード集合Ｌｉの要素数|Ｌｉ|が、ステップＳ１１で入力された解ノード個数ｋと等しいか否かを判定する（ステップＳ１６）。検索装置１００の決定ノード計算部１５０は、要素数|Ｌｉ|＝ｋと判定した場合は（ステップＳ１６Ｙｅｓ）、ステップＳ１７へ処理を移す。一方、検索装置１００の決定ノード計算部１５０は、要素数|Ｌｉ|≠ｋと判定した場合は（ステップＳ１６Ｎｏ）、ステップＳ１８へ処理を移す。
【００８５】
ステップＳ１７では、決定ノード計算部１５０は、定義４の式（２０）および式（２１）に基づき、ｉ番目の繰り返し計算において解ノードとして正確なランキングが決定している決定ノード集合Ｄｉを計算する。決定ノード計算部１５０は、ステップＳ１７の処理が終了すると、ステップＳ１９へ処理を移す。一方、ステップＳ１８では、決定ノード計算部１５０は、決定ノード集合Ｄｉを空集合に設定する。決定ノード計算部１５０は、ステップＳ１８の処理が終了すると、ステップＳ１９へ処理を移す。
【００８６】
ステップＳ１９では、検索装置１００の選択ノード計算部１６０は、繰り返し計算回数を示すｉを＋１インクリメントしたｉ＋１について、定義５の式（２２）に基づき、選択ノードＳｉ＋１を計算する。続いて、検索装置１００の選択ノード計算部１６０は、ステップＳ１９で計算した選択ノードＳｉ＋１の要素数|Ｓｉ＋１|が、０であるか否かを判定する（ステップＳ２０）。
【００８７】
検索装置１００の選択ノード計算部１６０は、要素数|Ｓｉ＋１|＝０であると判定した場合は（ステップＳ２０Ｙｅｓ）、|Ｓｉ＋１|＝０であることを検索装置１００の決定ノード計算部１５０へ通知するとともに、ステップＳ２１へ処理を移す。一方、検索装置１００の選択ノード計算部１６０は、要素数|Ｓｉ＋１|≠０と判定した場合は（ステップＳ２０Ｎｏ）、ステップＳ１９で計算した選択ノードＳｉ＋１を検索装置１００の部分グラフ構築部１１０へ通知するとともに、ステップＳ１２へ処理を移す。
【００８８】
ステップＳ２１では、検索装置１００の決定ノード計算部１５０は、ステップＳ１７で決定された決定ノード集合Ｄｉのｋ個の要素を、ステップＳ１４で計算された当該の要素ごとのノードの類似度の推定値の降順で並び替える。続いて、検索装置１００の決定ノード計算部１５０は、ステップＳ２１でノードの類似度の推定値の降順でｋ個の要素を並び替えた決定ノード集合Ｄｉを、解ノードＡに設定する（ステップＳ２２）。続いて、検索装置１００の決定ノード計算部１５０は、ステップＳ２２で設定された解ノードＡを出力する（ステップＳ２３）。検索装置１００は、ステップＳ２３が終了すると、検索処理を終了する。
【００８９】
（部分グラフ計算処理）
図４は、部分グラフ計算処理を示すフローチャートである。部分グラフ計算処理は、図３に示すステップＳ１２の詳細処理を示す。部分グラフ計算処理は、補助定理１１に基づき実行される。まず、部分グラフ構築部１１０の初期グラフ構築部１１１および候補グラフ構築部１１２は、繰り返し番号ｉ、変更前の部分グラフＧｉ−１、ノード集合ｈｉ、エッジ集合ｅｉ、選択ノードＳｉの入力を受け付ける（ステップＳ１２ａ）。すなわち、ステップＳ１２ａで繰り返し番号ｉ＝０である場合は、部分グラフ構築部１１０の初期グラフ構築部１１１は、繰り返し番号ｉ＝０、ノード集合ｈ０としての問い合わせノード集合Ｑの入力を受け付ける。一方、ステップＳ１２ａで繰り返し番号ｉ≠０である場合は、部分グラフ構築部１１０の初期グラフ構築部１１１は、繰り返し番号ｉ、変更前の部分グラフＧｉ−１、ノード集合ｈｉ、エッジ集合ｅｉ、選択ノードＳｉの入力を受け付ける。
【００９０】
続いて、部分グラフ構築部１１０の初期グラフ構築部１１１および候補グラフ構築部１１２は、繰り返し番号ｉ＝０であるか否かを判定する（ステップＳ１２ｂ）。部分グラフ構築部１１０の初期グラフ構築部１１１は、繰り返し番号ｉ＝０である場合は（ステップＳ１２ｂＹｅｓ）、ステップＳ１２ｃへ処理を移す。一方、部分グラフ構築部１１０の候補グラフ構築部１１２は、繰り返し番号ｉ≠０である場合は（ステップＳ１２ｂＮｏ）、ステップＳ１２ｄへ処理を移す。
【００９１】
ステップＳ１２ｃでは、部分グラフ構築部１１０の初期グラフ構築部１１１は、問い合わせノードＱから、初期グラフＧ０のノードおよびエッジを計算する。部分グラフ構築部１１０の初期グラフ構築部１１１は、ステップＳ１２ｃが終了すると、ステップＳ１２ｆへ処理を移し、ステップＳ１２ｃで計算した初期グラフＧ０のノードおよびエッジから初期グラフＧ０を計算する。続いて、部分グラフ構築部１１０の初期グラフ構築部１１１は、ステップＳ１２ｆで計算した初期グラフＧ０を出力する（ステップＳ１２ｇ）。
【００９２】
一方、ステップＳ１２ｄでは、部分グラフ構築部１１０の候補グラフ構築部１１２は、ステップＳ１２ａで受け付けた繰り返し番号ｉ、変更前の部分グラフＧｉ−１、ノード集合ｈｉ、エッジ集合ｅｉ、選択ノードＳｉから、候補グラフを計算する。続いて、部分グラフ構築部１１０の部分グラフ構築部１１３は、幅優先探索により、ステップＳ１２ｄで計算した候補グラフから部分グラフＧｉのノードおよびエッジを計算する（ステップＳ１２ｅ）。続いて、部分グラフ構築部１１０の部分グラフ構築部１１３は、ステップＳ１２ｅで計算したノードおよびエッジから部分グラフＧｉを計算する（ステップＳ１２ｆ）。続いて、部分グラフ構築部１１０の部分グラフ構築部１１３は、ステップＳ１２ｆで計算した部分グラフＧｉを出力する（ステップＳ１２ｇ）。部分グラフ構築部１１０は、ステップＳ１２ｇの処理が終了すると、部分グラフ計算処理を終了し、図３に示す検索処理へ処理を復帰する。
【００９３】
以上の検索処理および部分グラフ計算処理によれば、繰り返し計算の中で再帰的にノードの類似度の下限値と上限値を推定し、動的に解ノードになり得ないノードを除外することで、問い合わせ対象のグラフＧ、スケーリングパラメータｃ、解ノードの個数ｋ、問い合わせノードＱを入力とし、ノードの類似度の降順に正確に並び変えられたｋ個の解ノードを高速に得ることができる。
【００９４】
（検索アルゴリズム）
図５は、検索アルゴリズムを示す図である。図５に示す検索アルゴリズムは、図３に示す検索処理を示すフローチャートに対応する。図５は、部分グラフを用いた検索アルゴリズムを示す。まず、選択ノード集合を初期化し（図５の第２行目）、部分グラフを計算する（図５の第７〜第８行目）。そして、部分グラフに含まれるノードに対してランダムウォークの確率を計算する（図５の第９〜第１１行目）。これは、補助定理１０のとおり、ランダムウォークの確率が、ノードの類似度の推定値の計算に必要だからである。
【００９５】
そして、選択ノード集合に対してノードの類似度の推定値を計算する（図５の第１２〜第１５行目）。ｉ＝０ならば、定義３から、候補ノード集合Ｌｉを計算する（図５の第１６〜第１７行目）。ｉ≠０ならば、候補ノード集合Ｌｉ−１を用いて候補ノード集合Ｌｉを逐次的に計算する（図５の第１８〜第２４行目）。式（４）から、|Ｌｉ|≠ｋならば、Ｄｉ＝φであるので、|Ｌｉ|＝ｋの場合のみＤｉを計算する（図５の第２５〜第２６行目）。そして、選択ノード集合を更新する（図５の第３０行目）。
【００９６】
そして、選択ノード集合が空集合ならば、繰返し計算を打ち切る（図５の第３１行目）。そして、ノードのランキングを集合Ｄｉに含まれるノードを下限値または上限値で並び変えて計算する（図５の第３２行目）。最後に、集合Ｄｉを解ノードＡとして出力する（図５の第３３〜第３４行目）。
【００９７】
図５に示すアルゴリズムのとおり、実施形態は、検索における事前計算を必要としない。すなわち、実施形態は、アドホックにノード検索を行うことができる。また、実施形態は、ユーザは内部パラメータの設定を要しない。そのため、ユーザは簡易に、ＰＰＲによるノード検索をおこなうことができる。
【００９８】
（部分グラフ構築アルゴリズム）
図６は、部分グラフ構築アルゴリズムを示す図である。図６に示す部分グラフ構築アルゴリズムは、図４に示す部分グラフ計算処理を示すフローチャートに対応する。ｉ＝０ならば、部分グラフ構築アルゴリズムは、ノードとエッジ集合をそれぞれＶ０＝Ｑ  and  Ｅ０＝｛（ｕ，ｖ）∈  Ｅ：ｕ∈Ｑ，ｖ∈Ｑ｝に初期化する（図６の第２〜第３行目）。これは、式（２２）および式（２７）から、Ｖ０＝Ｈ０∩Ｒ０＝Ｑ∩Ｖ＝Ｑだからである。もし、Ｖ０＝Ｈ０∩Ｒ０＝Ｑ∩Ｖ＝Ｑでなければ、更新前のグラフＧからグラフ
2014228975.tif 000053
を逐次的に計算する（図６の第５〜第７行目）。そして、集合ＶｉとＥｉをグラフ
2014228975.tif 000054
から幅優先探索を用いて計算する（図６の第８〜第９行目）。部分グラフ構築アルゴリズムに見られるように、部分グラフＧｉは、問い合わせ対象のグラフＧ全体を用いることなく計算できる。
【００９９】
（実施形態による効果）
以上の実施形態によれば、上位ｋ個のノードを高速に求めるため、選択されたノードに対してのみ、式（１）により再帰的にＰＰＲのスコアベクトルの推定値を更新する。すなわち、実施形態は、上位ｋ個のノード検索において、全てのノードについての式（１）による繰り返し計算を回避し、ノードの類似度の推定値を高速に更新するため、高速なノード検索処理が可能になる。
【０１００】
また、実施形態は、ノードの類似度の推定値を高速に更新するために、グラフ全体から不要なノードとエッジを除外するように、動的に部分グラフを構築する。実施形態は、ノードの推定値を計算するために要するランダムウォークの確率が部分グラフから計算できるため、高速に推定値を更新することができる。また、実施形態は、不要なノードとエッジを特定するために、ノードの類似度の下限値と上限値を推定する。また、実施形態は、繰り返し計算の中で得られる部分グラフはグラフ全体より小さいため、高速に解ノードを検索することができる。
【０１０１】
すなわち、実施形態は、部分グラフを用いるので、従来技術の手法と比較して、繰り返し計算回数を減少させることができるという利点がある。従来技術の手法は、ノードの類似度を正確に計算するために、ノードの類似度が収束するまで繰り返し計算をおこなうことを要する。その一方、実施形態は、ノードの類似度の下限値と上限値からノードのランキングを決定することができ、ランキングが決定されたノードに対しては類似度算出のための繰り返し計算を行わない。そのため、実施形態は、ノードの類似度の下限値と上限値から全てのノードのランキングが決定された場合に、ノードの類似度算出のための繰り返し計算を打ち切る。つまり、実施形態は、ノードの類似度の収束を待つことなく計算を打ち切り、従来技術の手法より繰り返し計算回数を少なくすることができる。
【０１０２】
さらに、実施形態は、ノードの類似度の下限値と上限値の推定値をおこなうことから、部分グラフの構造と繰り返し計算回数を、事前計算を要さず、自動的に決定できる。このため、実施形態は、任意のグラフ、スケーリングパラメータ、解ノードに対して、アドホックに、高速に検索をおこなうことができる。また、実施形態は、内部パラメータを要さないため、ユーザはＰＰＲに基づくノード検索を簡易におこなうことができる。
【０１０３】
（実施形態のシステム構成について）
図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【０１０４】
また、検索装置１００においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、検索装置１００においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【０１０５】
また、実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【０１０６】
（プログラムについて）
また、実施形態において説明した検索装置１００のＣＰＵなどの制御装置が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、制御装置が実行する処理をコンピュータが実行可能な言語で記述した検索プログラムを作成することもできる。この場合、コンピュータが検索プログラムを実行することにより、実施形態と同様の効果を得ることができる。さらに、検索プログラムをコンピュータ読み取り可能な記録媒体に記録して、記録媒体に記録された検索プログラムをコンピュータに読み込ませて実行することにより実施形態と同様の処理を実現できる。以下に、図１および図２に示した検索装置１００と同様の機能を実現するプログラムを実行するコンピュータの一例を説明する。
【０１０７】
図７は、検索プログラムを実行するコンピュータ１０００を示す図である。コンピュータ１０００は、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらは、バス１０８０によって接続される。
【０１０８】
図７に示すように、メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。また、ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。また、ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、磁気ディスクや光ディスクなどの着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０は、例えばマウス１０５１、キーボード１０５２に接続される。また、ビデオアダプタ１０６０は、例えばディスプレイ１０６１に接続される。
【０１０９】
ここで、図７に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、検索プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。
【０１１０】
また、実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出す。そして、ＣＰＵ１０２０が、検索プログラムの各手順を実行する。
【０１１１】
なお、検索プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られない。すなわち、プログラムモジュール１０９３およびプログラムデータ１０９４は、着脱可能な記憶媒体に記憶され、ディスクドライブなどを介してＣＰＵ１０２０によって読み出されてもよい。検索プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）など）を介して接続された他のコンピュータに記憶されていてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出され、実行されてもよい。
【符号の説明】
【０１１２】
１００  検索装置
１１０  部分グラフ構築部
１１１  初期グラフ構築部
１１２  候補グラフ構築部
１１３  部分グラフ構築部
１２０  ランダムウォーク確率計算部
１３０  推定値計算部
１４０  候補ノード計算部
１５０  決定ノード計算部
１６０  選択ノード計算部
【図１】
2014228975.tif 000055
【図２】
2014228975.tif 000056
【図３】
2014228975.tif 000057
【図４】
2014228975.tif 000058
【図５】
2014228975.tif 000059
【図６】
2014228975.tif 000060
【図７】
2014228975.tif 000061