(57)【特許請求の範囲】
【請求項１】
問い合わせノードに対するSimRankの近似値を計算し、該近似値が高い順にK個のノードを検索する類似ノード検索装置であって、
グラフデータとグラフのノード数Nと特異値の数nを外部入力とし、記憶手段に格納し、該グラフのノード数Nと該特異値の数nを読み出して、N×nの行列とn×Nの行列とそれらの統計量を算出し、出力する事前計算手段と、
問い合わせノードと検索個数を外部入力とし、記憶手段に格納し、前記N×nの行列と前記n×Nの行列と前記統計量を前記事前計算手段から取得し、K個の類似ノードを出力する検索手段と、
を有し、
前記事前計算手段は、
入力された前記グラフデータのグラフの固有値分解を行う固有値分解手段と、
前記固有値分解の結果を入力とし、特異値分解を計算する特異値分解手段と、
前記固有値分解の結果と前記特異値分解の結果と前記特異値の数nを入力として、前記N×nの行列と前記n×Nの行列と該行列の統計量を求める行列計算手段と、
を含み、
前記検索手段は、
前記行列の統計量を入力とし、該統計量に基づいて近似値の上限値を計算する上限値計算手段と、
前記N×nの行列と前記n×Nの行列を入力とし、前記上限値に基づいてノードを枝刈りし、枝刈りされなかったノードに対してのみ類似度の近似計算を行う近似値計算手段と、
を含むことを特徴とする類似ノード検索装置。
【請求項２】
前記近似値計算手段は、
前記N×nの行列と前記n×Nの行列のノードの推定値を求め、該推定値が前記上限値より小さければ枝刈りし、大きければ該ノードの類似度を求め、解候補ノードとして解候補記憶手段に格納し、該ノード推定値を上限値として更新する手段を含む
請求項１記載の類似ノード検索装置。
【請求項３】
問い合わせノードに対するSimRankの近似値を計算し、該近似値が高い順にK個のノードを検索する類似ノード検索装置における類似ノード検索方法であって、
前記類似ノード検索装置が、
グラフデータとグラフのノード数Nと特異値の数nを外部入力とし、記憶手段に格納し、該グラフのノード数Nと該特異値の数nを読み出して、N×nの行列とn×Nの行列とそれらの統計量を算出し、出力する事前計算ステップと、
問い合わせノードと検索個数を外部入力とし、記憶手段に格納し、前記事前計算ステップで求められた前記N×nの行列と前記n×Nの行列と前記統計量を取得し、K個の類似ノードを出力する検索ステップと、を行い
前記事前計算ステップにおいて、
入力された前記グラフデータのグラフの固有値分解を行う固有値分解ステップと、
前記固有値分解の結果を入力とし、特異値分解を計算する特異値分解ステップと、
前記固有値分解の結果と前記特異値分解の結果と前記特異値の数nを入力として、前記N×nの行列と前記n×Nの行列と該行列の統計量を求める行列計算ステップと、
を行い、
前記検索ステップにおいて、
前記行列の統計量を入力とし、該統計量に基づいて近似値の上限値を計算する上限値計算ステップと、
前記N×nの行列と前記n×Nの行列を入力とし、前記上限値に基づいてノードを枝刈りし、枝刈りされなかったノードに対してのみ類似度の近似計算を行う近似値計算ステップと、を行う
ことを特徴とする類似ノード検索方法。
【請求項４】
前記近似値計算ステップにおいて、
前記N×nの行列と前記n×Nの行列のノードの推定値を求め、該推定値が前記上限値より小さければ枝刈りし、大きければ該ノードの類似度を求め、解候補ノードとして解候補記憶手段に格納し、該ノード推定値を上限値として更新する
請求項３記載の類似ノード検索方法。
【請求項５】
コンピュータを、
請求項１または２に記載の類似ノード検索装置の各手段として機能させるための類似ノード検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似ノード検索装置及び方法及びプログラムに係り、特に、SimRankに基づき類似度を計算し、検索を行う類似ノード検索装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフはデータをノードとエッジで表現するデータ構造であり、様々な分野で用いられている。グラフ理論において2つのノード間の類似度は重要な性質の一つであり、ノードの類似度として今まで様々な手法が提案されてきた。
【０００３】
その中でもSimRankはノードの類似度として最も注目を集めているものの一つである（例えば、非特許文献1参照）。SimRankは今までグラフ理論でよく用いられてきたノード間の最短距離などと異なり、グラフの構造的な特徴に基づいて類似度が計算できるからである。
【０００４】
SimRankは、「複数のノードからあるノードペアそれぞれに対してエッジがあれば、そのノードペアの類似度は高い」という考えに基づいたノードの類似度である。SimRankにおける類似度は、ノードペアから出発した２つのランダムウォークがあるノードで出会う確率を再帰的に繰り返し計算することで得ることができる。この計算により全てのノードペアの類似度が得られるが、この処理が計算量が高いという問題がある。また、実際のアプリケーションにおいては全てのノードペアの類似度が必要なのではなく、問い合わせノードから類似度の高いノードを探す処理が行われている（例えば、非特許文献2，3，4参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Glen Jeh and Jennifer Widom, SimRank: a measure of structural-context similarity, KDD, 2002.
【非特許文献２】Alexandros Ntoulas and Marc Najork and Mark Manasse and Dennis Fetterly, Detecting spam web pages through content analysis, WWW, 2006.
【非特許文献３】Kaikou Xu and Yu Chen and Yexi Jiang and Rong Tang and Yintian Liu and Jie Gong, A Comparative Study of Correlation Measurements for Searching Similar Tags, ADMA, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のSimRankの計算は、再帰的に計算を繰り返す必要があり、計算量が多くなるという問題がある。
【０００７】
本発明は、上記の点に鑑みなされたもので、繰り返し計算を行うことなく、高速に計算可能な類似ノード検索装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明は、問い合わせノードに対するSimRankの近似値を計算し、該近似値が高い順にK個のノードを検索する類似ノード検索装置であって、
グラフデータとグラフのノード数Nと特異値の数nを外部入力とし、記憶手段に格納し、該グラフのノード数Nと該特異値の数nを読み出して、N×nの行列とn×Nの行列とそれらの統計量を算出し、出力する事前計算手段と、
問い合わせノードと検索個数を外部入力とし、記憶手段に格納し、前記N×nの行列と前記n×Nの行列と前記統計量を前記事前計算手段から取得し、K個の類似ノードを出力する検索手段と、
を有し、
前記事前計算手段は、
入力された前記グラフデータのグラフの固有値分解を行う固有値分解手段と、
前記固有値分解の結果を入力とし、特異値分解を計算する特異値分解手段と、
前記固有値分解の結果と前記特異値分解の結果と前記特異値の数nを入力として、前記N×nの行列と前記n×Nの行列と該行列の統計量を求める行列計算手段と、
を含み、
前記検索手段は、
前記行列の統計量を入力とし、該統計量に基づいて近似値の上限値を計算する上限値計算手段と、
前記N×nの行列と前記n×Nの行列を入力とし、前記上限値に基づいてノードを枝刈りし、枝刈りされなかったノードに対してのみ類似度の近似計算を行う近似値計算手段と、
を含む。
【０００９】
また、本発明は、前記近似値計算手段において、
前記N×nの行列と前記n×Nの行列のノードの推定値を求め、該推定値が前記上限値より小さければ枝刈りし、大きければ該ノードの類似度を求め、解候補ノードとして解候補記憶手段に格納し、該ノード推定値を上限値として更新する手段を含む。
【発明の効果】
【００１０】
上述のように本発明では、特定のノードの類似度を、行列を用いて繰り返し計算を行うことなく求め、行列の統計量を用いて不必要な類似度計算の枝刈りを行うことで、従来手法よりも大幅に高速に類似ノードを検索でき、同時にメモリ資源も節約することが可能である。さらに、近似的に解ノードを高い精度で求めることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の一実施の形態における類似ノード検索装置の構成図である。
【図２】本発明の一実施の形態における事前計算部のアルゴリズムである。
【図３】本発明の一実施の形態における事前計算部のフローチャートである。
【図４】本発明の一実施の形態における検索部のアルゴリズムである。
【図５】本発明の一実施の形態における検索部のフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面と共に本発明の実施の形態を説明する。
【００１３】
図１は、本発明の一実施の形態における類似ノード検索装置の構成を示す。
【００１４】
類似ノード検索装置１００は、問い合わせノードに対するSimRankの近似値を計算し、近似値が高い順にＫ個の類似ノードを検索するものである。
【００１５】
同図に示す類似ノード検索装置１００は、事前計算部１１０と検索部１２０から構成される。
【００１６】
事前計算部１１０は、固有値分解部１１１、特異値分解部１１２、行列計算部１１３から構成され、グラフデータとグラフのノード数Ｎと特異値の数ｎを外部入力とし、N×nの行列とn×Nの行列とそれらの統計量を検索部１２０に出力する。
【００１７】
事前計算部１１０の固有値分解部１１１は、外部からのグラフデータを入力とし、グラフの固有値分解を行い、特異値分解部１１２に出力する。
【００１８】
特異値分解部１１２は、固有値分解部１１１の固有値分解の結果と特異値の数nを入力とし、特異値分解を計算し、行列計算部１１３に出力する。
【００１９】
行列計算部１１３は、固有値分解の結果と特異値分解の結果と特異値の数ｎを入力とし、N×nの行列とn×Nの行列とそれらの統計量を出力する。
【００２０】
検索部１２０は、上限値計算部１２１と近似値計算部１２２を有し、問い合わせノードと検索個数（K個）を外部入力とし、N×nの行列とn×Nの行列とそれらの統計量を事前計算部１１０からの入力とし、Ｋ個の類似ノードを出力する。
【００２１】
上限値計算部１２１は、事前計算部１１０で求められた行列の統計量を入力とし、類似度の近似値の上限値を計算し、近似値計算部１２２に出力する。
【００２２】
近似値計算部１２２は、N×nの行列とN×nの行列を入力とし、類似度の近似計算を行う。
【００２３】
なお、上記の事前計算部１１０、検索部１２０は図示しないが、入力データ、途中の計算結果を格納するためのメモリを有する。
【００２４】
まず、本明細書で用いる記号を定義し、必要となる背景知識を説明する。
【００２５】
q：問い合わせノード
K：解ノードの個数
N：グラフにおけるノードの個数
T：繰り返し計算の計算回数
n：特異値分解における特異値の数
d：ノードの次数の平均値
c：decay factor
s(u,v)：ノードuとｖの類似度
S：類似度行列
W：グラフの隣接行列
D：固有値行列
P：固有ベクトル行列
【００２６】
【数１】
0005647166.tif 000002
SimRankはグラフのノードの類似度を計算する一つの方法である。SimRankにおいてノードuとノードvの類似度s(u，v)は、ノードuとノードvから始まる２つのランダムウォークが同じノードにたどり着くまでのホップ数の期待値として計算される。具体的に、SimRankの類似度は以下の式を再帰的に収束するまで繰り返し計算する。
【００２７】
【数２】
0005647166.tif 000003
ここで、cはdecay factorと呼ばれる０から１の定数であり、A(u)はノードuに向かってエッジを張っているノードの集合であり、｜A(u)|は集合A(u)におけるノードの数であり、集合におけるノードはAi(u)として表現される。また、s(u,v)はu≠vであれば０に初期化され、そうでなければ１に初期化される。式(1)において０で割ることを防ぐために、もしA(u)またはA(v)が空集合である場合は、s(u,v)は０と定義される。
【００２８】
グラフにおけるノード数をN、ノードの次数をd、収束するまでの繰り返し計算回数をTとしたときに、SimRankの計算には、O(N2d2T)の計算コストを要する。そのためグラフが密になる最悪の場合、SimRankの計算にはO(N4T)の計算コストが必要になる。また、上記のSimRankの計算式は一つのノードペアに対して定義される。すなわち、ノード数がNであるグラフにはN2個の式が定義されるため、SimRankの計算にはO(N2)のメモリ量を要する。そのため、グラフの規模が大きい場合、SimRankの計算には莫大な計算コストとメモリコストが必要になるという問題がある。
【００２９】
本発明は、以下の２つの手法で構成される。
【００３０】
［手法１］行列による類似度の計算：
当該手法１は、事前計算部１１０で用いられる手法である。
【００３１】
SimRankにおいては、全てのノードペアの類似度を繰り返し計算によって求めるが、莫大な計算コストとメモリコストが必要になるという問題がある。本発明では、全てのノードペアの類似度を求めずに、上位K個のノードを求めるのに必要なノードペアに対してのみ類似度を計算する。
【００３２】
後述するように、SimRankの類似度は定義式を変換したシルベスタ方程式（文献１『Peter Benner, Factorized Solution of Sylvester Equations with Applications in Control, NTNS, 2004』）から計算することができる。シルベスタ方程式は、Bartels-Stewart法（文献２『Richard H.  Bartels and G. W. Stewart, Solution of the Matrix Equation AX+XB=C[F4] (Algorithm 432), Commun. ACM, 1972.』）を用いれば解けるが、Bartels-Stewart法による手法は必要なノードペアに対してのみ類似度を計算することができないという問題がある。そのため、本発明では、事前計算部１１０の固有値分解部１１１において、固有値分解を用いて必要なノードペアの類似度を計算する。この手法によりノードの類似度をO(N3)で計算できるようになるが、更に本発明では、特異値分解を用いて類似度を近似的にO(Nn)で高速に計算する。
【００３３】
詳細については後述する。
【００３４】
［手法２］統計量による推定：
当該手法２は、検索部１２０で用いられる手法である。
【００３５】
上記の手法１により選んだノードの類似度の近似値を高速に計算することができる。さらに、本手法２では、検索においてどのノードの類似度を計算し、どのノードの類似度の計算を枝刈りするかを決めるために、検索部１２０の上限値計算部１２１においてノードの類似度の上限値を推定する。
【００３６】
検索部１２０の上限値計算部１２１では、行列の統計量を用いることによりO(1)でノードの類似度の上限値を計算することができる。そのため、上限値を計算することで、近似値計算部１２２において、類似度を計算するべきノードを高速に特定し、結果として解ノードを高速に計算することができる。
【００３７】
詳細は後述する。
【００３８】
［手法１の詳細］
上記（手法１）は、事前計算部１１０において、行列を用いて選択したノードの類似度を計算するものである。SをN×Nの類似度行列とし、Wを列ベクトルが１に正規化されたグラフの隣接行列とする。
【００３９】
まず、はじめに類似度は繰り返し計算せずに求められることを示す。
【００４０】
上記の式(1)は以下のように書き換えることができる。
【００４１】
【数３】
0005647166.tif 000004
ここで、Wtは行列Wの転置行列であり、Iは単位行列である。式(2)は以下のように書き換えることができる。
【００４２】
【数４】
0005647166.tif 000005
式(3)の形式はシルベスタ方程式（文献１）であり、Bartels-Stewart法(文献２)を用いれば解ける。しかし選択されたノードペアの類似度のみを計算することができないという問題がる。そのため本手法では、固有値分解部１１１において、式(3)を更に固有値分解を用いて書き換える。λi(i=1,2,…,N)を隣接行列Wの固有値とし、pi(ここでpiのノルムは１とする。すなわち‖pi‖＝１である)を固有値λi(i=1,2,…,N)に対応する固有ベクトルとし、Dを固有値による対角行列とし、P(=[p1p2…pN])を固有ベクトルからなる行列とする。式（3）は左からPtをかけ右からPをかけると以下のようになる。
【００４３】
【数５】
0005647166.tif 000006
式(8)から類似度を計算するのは行列Xの要素が必要であることがわかる。Xの(i,j)の要素は式(7)から計算できる。行列DとD−1は共に対角行列であるため、式(7)における左側の（i,j）要素は以下のようになる。
【００４４】
【数６】
0005647166.tif 000007
さらに式(7)の右側の行列の要素は固有値行列と固有値ベクトル行列から計算できる。そのため類似式を式(8)から繰り返し計算なしに求めることができる。
【００４５】
次に、本発明で用いる類似度の計算方法について述べる。式(8)に見られるように、類似度は行列(Pt)−1とXとP−1を用いれば計算できるが、式(8)を直接計算するとO(N3)のコストがかかる。これは、これらの行列のサイズがN×Nだからである。
【００４６】
本発明では、類似度の計算コストを下げるため、事前計算部１１０の特異値分解部１１２において特異値分解を用いて行列の近似を行う。
【００４７】
【数７】
0005647166.tif 000008
を行列P-1の近似とすると理論的に類似度は
【００４８】
【数８】
0005647166.tif 000009
として計算できる。
【００４９】
【数９】
0005647166.tif 000010
は行列UとΣとVをランクnの行列としたときに、
【００５０】
【数１０】
0005647166.tif 000011
と計算できる。一般的に近似により、
【００５１】
【数１１】
0005647166.tif 000012
は極めて小さくなることが知られている。
【００５２】
本発明では、ノードuとqの類似度を以下のように計算する。
【００５３】
[定義１]
【００５４】
【数１２】
0005647166.tif 000013
であり、L=(P t)−1XUΣであり、ベクトルviをVにおけるi番目の列ベクトルであり、ベクトルｌiをi番目の行ベクトルとすると、ノードuとqの類似度s(q,u)は以下のように計算する。
【００５５】
【数１３】
0005647166.tif 000014
すなわち、u≠qであれば類似度s(q,u)をベクトルｌqとｖuの内積として計算する。
【００５６】
定義１について以下の補助定理が成り立つ。
【００５７】
[補助定理１]
もし、
【００５８】
【数１４】
0005647166.tif 000015
であり、u≠qであれば式(10)は式(8)と同じ計算結果になる。
【００５９】
証明）本発明では、類似度を理論的に
【００６０】
【数１５】
0005647166.tif 000016
と計算するが、もし、
【００６１】
【数１６】
0005647166.tif 000017
であれば、式(8)から
【００６２】
【数１７】
0005647166.tif 000018
となる。そのため行列Sの（q,u）要素と同じになる。そのためもしu≠qであれば、明らかにs(q,u)はベクトルlqとvuの内積と等しくなる。
【００６３】
本発明における類似度の計算方法の計算量を示すために以下の補助定理を示す。
【００６４】
[補助定理２]
もし、u≠qであれば、ノードの類似度s(q,u)の計算にはO(n)の計算コストを要する。
【００６５】
証明）もし、u≠qであれば式(10)において、s(q,u)=lq・vuとなる。ここで行列LとVのサイズはそれぞれN×nとn×Nであるため、ベクトルlqとvuの長さはnとなる。そのため、s(q,u)はO(n)のコストで計算できる。
【００６６】
もし、u=qであれば式(10)より類似度は明らかにO(1)で計算できる。
【００６７】
本手法では、行列計算部１１３において、
【００６８】
【数１８】
0005647166.tif 000019
を用いて類似度の近似値を計算するが、類似ノードの検索において近似精度を上げるための手法について述べる。この手法では、固有値行列と固有ベクトル行列における以下の特性を利用する。
【００６９】
・固有値と固有ベクトルの順番は任意に設定することができる。
【００７０】
・固有ベクトルのノルムの大きさは任意に設定することができる。
【００７１】
本発明は、理論的には類似度を
【００７２】
【数１９】
0005647166.tif 000020
として計算する。つまり、類似度s(q,u)は行列
【００７３】
【数２０】
0005647166.tif 000021
のq番目の行ベクトルと行列
【００７４】
【数２１】
0005647166.tif 000022
のu番目の列ベクトルの内積として計算される。そのため、s(q,u)の近似誤差を小さくするためには、行列
【００７５】
【数２２】
0005647166.tif 000023
のu番目の列ベクトルの近似誤差を小さくすることが必要である。本発明では、近似に特異値分解を用いるが、特異値分解は２乗誤差を小さくする特性がある。すなわち、もし絶対値が大きい値は特異値分解により高精度で近似され、絶対値が小さな値は高精度で近似できない特性がある。そのため、本発明では、検索の解になりそうなノードに対応する列別ベクトルのノルムを大きくする。
【００７６】
検索の解になりそうなノードの指標としては、ノードの次数を用いる。これは、SimRankが「複数のノードからあるノードペアそれぞれに対してエッジがあれば、そのノードペアの類似度は高い」という考えに基づいていて、さらに次数が高いほど他のノードから短いホップ数で辿り着けると期待できるからである。そのため、本発明では、行列WとPとDにおいて高い次数に対応する要素のノルムを大きくし、行列W'とP'とD'に変換する。
【００７７】
図２に当該手法１のアルゴリズムを示す。
【００７８】
図２において、まず、次数の小さい順にノードを並び替え、メモリに格納する（４行目）。その結果、行列Wは行列W'に変換される。行列W'においてはノード番号が大きくなるにしたがって検索の解ノードになることが期待される。重み付きノルムを各固有ベクトルに対して計算する（５〜７行目）。i番目の固有ベクトルの重み付きノルムwiは行列Pから以下のように計算される。
【００７９】
【数２３】
0005647166.tif 000024
固有ベクトルの順番は任意に設定できるため、行列P'とD'における固有ベクトルと固有値を重み付きノルムの小さい順に並べる（８行目）。その結果、行列Dは行列D'に変換される。固有ベクトルのノルムは任意に設定可能なため、行列P'における各列ベクトルにそれらの列番号をかける（９〜１１行目）。結果行列Pから行列P'が得られる。行列P'における各行ベクトルのノルムは、行番号が大きくなるほど小さくなる。図２におけるアルゴリズムを事前計算部１１０の特異値分解部１１２に適用した場合のフローチャートを図３に示す。
【００８０】
ステップ１０１）固有値分解部１１１から特異値分解部１１２にグラフの隣接行列W、固有値行列D、固有ベクトル行列Pが入力されると、メモリ（図示せず）に格納する。
【００８１】
ステップ１０２）特異値分解部１１２は、W'=W、D'=D、P'=Pとする。
【００８２】
ステップ１０３）  特異値分解部１１２は、メモリ（図示せず）中のW'のノードを次数の小さい順に並び替える。
【００８３】
ステップ１０４）  特異値分解部１１２は、メモリからノードを一つ選択し、固有ベクトル行列P'の中の列ベクトルに対して重み付きノルムを計算する処理を、全ノードに対して行う。
【００８４】
ステップ１０５）  特異値分解部１１２は、行列D'とP'の列ベクトルを重み付きノルムの小さい順に並び替え、メモリ（図示せず）に格納する。
【００８５】
ステップ１０６）  特異値分解部１１２は、P'の中の列ベクトルに対して列番号をかける。
【００８６】
ステップ１０７）  特異値分解部１１２は、固有値ベクトル行列P'に対して特異値分解を行う。
【００８７】
事前計算部１１０において、行列P'から行列(P')−1を計算する。行列P'のi番目の行ベクトルと行列(P')−1のi番目の列ベクトルの内積は逆行列の定義から１になる。そのため、行列(P')−1の列ベクトルのノルムは列番号が大きくなる程に大きくなる。そのため特異値分解を用いることにより行列(P')−1の要素は列番号が大きくなる程よく近似できるようになる。ノードは、次数の小さい順に並び替えてあるため、検索の解になりそうなノードほどよく近似できるようになる。
【００８８】
［手法２の詳細］
手法２は、検索部１２０において、検索の途中において類似度を計算していないノードの類似度を高速にかつ効果的に推定するためのものである。当該手法は、検索部１２０の上限値計算部１２１において、事前計算部１１０から入力された行列の統計量を利用して類似度の上限値を計算するものである。
【００８９】
まず、当該手法２において用いる統計量について説明する。
【００９０】
【数２４】
0005647166.tif 000025
はそれぞれベクトルliとviの平均値である。また、
【００９１】
【数２５】
0005647166.tif 000026
はそれぞれベクトルliとviの標準偏差である。
【００９２】
これらの統計量を用いて以下のように類似度を推定する。
【００９３】
[定義２]
ノードuとqの類似度の推定値（上限値）
【００９４】
【数２６】
0005647166.tif 000027
は以下のように計算する。
【００９５】
【数２７】
0005647166.tif 000028
この推定値は以下の性質を有する。
【００９６】
[補助定理３]
ノードqとuのペアに対して
【００９７】
【数２８】
0005647166.tif 000029
となる。
【００９８】
証明）もし、u=qであれば定義１と２より明らかに
【００９９】
【数２９】
0005647166.tif 000030
となる。そうでなければ定義１より以下の式が成り立つ。
【０１００】
【数３０】
0005647166.tif 000031
ここで、Δlqiはlqiの
【０１０１】
【数３１】
0005647166.tif 000032
からの差とし、Δviuはviuの
【０１０２】
【数３２】
0005647166.tif 000033
からの差とする。
【０１０３】
【数３３】
0005647166.tif 000034
であるため、
【０１０４】
【数３４】
0005647166.tif 000035
となる。ここで、シュワルツの不等式（文献３：J. Michael Steele, The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities, Cambridge University Press, 2004.）より以下が成り立つ。
【０１０５】
【数３５】
0005647166.tif 000036
そのため、
【０１０６】
【数３６】
0005647166.tif 000037
となる。
【０１０７】
この補助定理を用いることにより、効果的に不必要な類似度計算を枝刈りで切る。さらにこの手法における計算コストを示すために以下の補助定理を示す。
【０１０８】
[補助定理４]
類似度の上限値はO(1)のコストで計算できる。
【０１０９】
証明）もし、u=qであれば
【０１１０】
【数３７】
0005647166.tif 000038
であるため、明らかにO(1)のコストで計算できる。そうでなければ定義２より
【０１１１】
【数３８】
0005647166.tif 000039
となるが、ここで統計量は事前に計算可能であり、またnは定数であるためO(1)のコストで計算できる。
【０１１２】
手法２の検索アルゴリズムを図４に示す。同図に示すアルゴリズムにおいて、θは解候補のノードにおける最も小さな類似度の値であり、vcは解候補のノードの集合とする。
【０１１３】
まず、アルゴリズムではθを０とし、vcにK個のダミーノードを加える（１〜３行目）。ここで、ダミーノードの類似度は全て０とする。ノードを一つ選択し、それらのノードの推定値を計算する（５行目）。もし、推定値がθより小さければそのノードは解になりえないので、枝刈りする。そうでなければ、そのノードは解になりうるので、そのノードの類似度を計算する（７行目）。もし類似度がθ以下でなかったら、vcとθを更新する（８〜１３行目）。そして最後にvcを解ノードとして出力する（１６行目）。
【０１１４】
図４におけるアルゴリズムを検索部１２０に適用した場合のフローチャートを図５に示す。
【０１１５】
ステップ２０１）  検索部１２０に、外部から問い合わせノードq、検索個数K、及び、事前計算部１１０から行列L、行列V、特異値の数n、行列Lの統計量、行列Vの統計量が入力されると、メモリ（図示せず）に格納する。
【０１１６】
ステップ２０２）  メモリ（図示せず）上に、解候補のノードにおける最も小さな類似度θ＝０、解候補のノード集合Vcを設定する。
【０１１７】
ステップ２０３）  K個のダミーノードをVcに加える。
【０１１８】
ステップ２０４）  上限値計算部１２１は、入力されたノードを１つメモリ（図示せず）から読み出し、統計量l、vを用いてノードの推定値（上限値）を前述の式(12)により計算する。
【０１１９】
ステップ２０５）  ステップ２０４で求められた推定値がθ以上であればステップ２０６に移行し、θより小さければ次のノードを選択する（ステップ２０４に戻る）。
【０１２０】
ステップ２０６）  近似値計算部１２２は、ノードの類似度を前述の式(10)により求める。
【０１２１】
ステップ２０７）  求められたノードの類似度がθ以上であればステップ２０８に移行し、θより小さければ次のノードを選択する（ステップ２０４に戻る）。
【０１２２】
ステップ２０８）  当該ノードを解候補のノード集合Vcに追加し、ノード集合Vcから類似度が尤も小さいノードを削除する。そしてθをｋ番目の類似度に設定する。
【０１２３】
ステップ２０９）  最後に解候補のノード集合Vcを出力する。
【０１２４】
なお、上記の図２、図４に示すアルゴリズムをプログラムとして構築し、類似ノード検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１２５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１２６】
１００  類似ノード検索装置
１１０  事前計算部
１１１  固有値分解部
１１２  特異値分解部
１１３  行列計算部
１２０  検索部
１２１  上限値計算部
１２２  近似値計算部
【図１】
0005647166.tif 000040
【図２】
0005647166.tif 000041
【図３】
0005647166.tif 000042
【図４】
0005647166.tif 000043
【図５】
0005647166.tif 000044