(57)【特許請求の範囲】
【請求項１】
グラフの構造的な特徴に基づいて類似度を計算するRandom  walk  with  restart(RWR)を用いて類似度を計算する類似度計算手段を有し、類似度が高い順にK個のノードを検索する類似ノード検索装置であって、
外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算手段と、
外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索手段と、
K個の検索結果を出力する出力手段と、
を有し、
前記検索手段は、
前記問い合わせノードと前記検索個数及び前記逆行列から、RWRによりノードの類似度を計算する類似度計算手段と、
前記類似度計算手段から取得した類似度と検索結果保存手段から取得した検索対象ノードについて、前記問い合わせノードを始点とする幅優先木を構築し、該問い合わせノードからのホップ数が小さいほどに大きくなる類似度を用いて、幅優先探索の順番に類似度の推定値を計算し、該類似度の推定値がＫ個の解候補ノードの最も小さい類似度より小さい場合には類似度の計算を打ち切る類似度推定手段と、
前記類似度計算手段で求められた類似度及び前記類似度推定手段で計算された前記類似度の推定値を前記検索結果保存手段に格納し、検索対象ノードを決定し、該類似度計算手段及び該類似度推定手段に出力し、検索結果を前記出力手段に出力する検索結果保存手段と、
を有することを特徴とする類似ノード検索装置。
【請求項２】
前記事前計算手段は、
前記外部から入力されたグラフデータからノードを並び替えて出力するノード並び替え手段と、
並び替えられたグラフから前記上三角行列と前記下三角行列の逆行列を生成する逆行列計算手段と、
を含む請求項１記載の類似ノード検索装置。
【請求項３】
グラフの構造的な特徴に基づいて類似度を計算するRandom  walk  with  restart(RWR)を用いて類似度を計算し、類似度が高い順にK個のノードを検索する類似ノード検索方法であって、
事前計算手段が、外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算ステップ
検索手段が、外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索ステップ、
出力手段が、K個の検索結果を出力する出力ステップと、
を行い、
前記検索ステップにおいて、
前記問い合わせノードと前記検索個数K及び前記逆行列から、RWRによりノードの類似度を計算する類似度計算ステップと、
前記類似度計算ステップで計算された類似度と検索結果保存手段から取得した検索対象ノードについて、前記問い合わせノードを始点とする幅優先木を構築し、該問い合わせノードからのホップ数が小さいほどに大きくなる類似度を用いて、幅優先探索の順番に類似度の推定値を計算し、該類似度の推定値がＫ個の解候補ノードの最も小さい類似度より小さい場合には類似度の計算を打ち切る類似度推定ステップと、
前記類似度計算ステップで求められた類似度及び前記類似度推定ステップで計算された前記類似度の推定値を前記検索結果保存手段に格納し、検索対象ノードを決定し、該類似度計算ステップ及び該類似度推定ステップの入力とし、検索結果を前記出力手段に出力する検索結果保存ステップと、
を行うことを特徴とする類似ノード検索方法。
【請求項４】
前記事前計算ステップにおいて、
前記外部から入力されたグラフデータからノードを並び替え、
並び替えられたグラフから前記上三角行列と前記下三角行列の逆行列を生成する
請求項３記載の類似ノード検索方法。
【請求項５】
請求項１または２に記載の類似ノード検索装置を構成する各手段としてコンピュータを機能させるための類似ノード検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似ノード検索装置及び方法及びプログラムに係り、特に、"Random walk with restart"に基づいて類似度を計算し、ノードの検索を行うための類似ノード検索装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
グラフはデータをノードとエッジで表現するデータ構造であり、様々な分野で用いられている。グラフ理論において２つのノード間野類似度は重要な性質の一つである。ノードの類似度として今まで様々な手法が提案されてきた。
【０００３】
その中でも、“Random  walk  with  restart（RWR）”はノードの類似度として最も注目を集めているものの一つである。RWRは今までグラフ理論でよく用いられてきたノード間の最短距離などと異なり、グラフの構造的な特徴に基づいて類似度が計算できるからである（例えば、非特許文献1参照）。
【０００４】
RWRは、概念的に以下のように説明できる。問い合わせノードｑからランダムウォークを開始し、隣接するノードにエッジの重みに比例した確率でランダムに移動する。さらにノードに到達する度に一定の基準で問い合わせノードｑに戻る。この操作を再帰的に繰り返した結果として各ノードにおける定常状態確率が得られるが、RWRはこの得られた定常状態確率を類似度とする方法である。すなわち、ノードｕのノードｑに対する類似度は、ノードｑからランダムウォークをして得られたノードｕの定常状態確率として計算される。
【０００５】
RWRは様々な分野のアプリケーションに応用されている類似度であるが、計算量が高いという問題がある。そのため今まで様々な高速化手法が提案されている（例えば、非特許文献２，３参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Hanghang Tong and Christos Faloutsos，  Center-piece subgraphs: problem definition and fast solutions, KDD, 2006.
【非特許文献２】Hanghang Tong and Christos Faloutsos and Jia-Yu Pan, Fast Random Walk with restart and Its Applications, ICDM, 2006.
【非特許文献３】Jimeng Sun and Huiming Qu and Deepayan Chakrabarti and Christos Faloutsos, Neighborhood Formation and Anomaly Detection in Bipartite Graphs, ICDM, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上記の非特許文献２、３の手法は精度を犠牲にするものであり、アプリケーションに対する応用を考えた場合、精度が犠牲になるのは好ましくない。また、実際のアプリケーションにおいては問い合わせノードｑから他の全てのノードの類似度を計算するのではなく、類似度の高いノードのみを行う処理が行われている（例えば、非特許文献３参照）。そのため、本明細書では、問い合わせノードｑと検索個数Ｋが与えられたとき、類似度の高いＫ個のノードを高速かつ正確に検索する問題を対象とする。
【０００８】
本発明は、上記の点に鑑みなされたもので、高速かつ正確に類似ノードを検索することが可能な類似ノード検索装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明は、グラフの構造的な特徴に基づいて類似度を計算するRWRを用いて類似度を計算する類似度計算手段を有し、類似度が高い順にK個のノードを検索する類似ノード検索装置であって、
外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算手段と、
外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索手段と、
K個の検索結果を出力する出力手段と、
を有し、
前記検索手段は、
前記問い合わせノードと前記検索個数及び前記逆行列から、RWRによりノードの類似度を計算する類似度計算手段と、
前記類似度計算手段から取得した類似度と検索結果保存手段から取得した検索対象ノードについて、前記問い合わせノードを始点とする幅優先木を構築し、該問い合わせノードからのホップ数が小さいほどに大きくなる類似度を用いて、幅優先探索の順番に類似度の推定値を計算し、該類似度の推定値がＫ個の解候補ノードの最も小さい類似度より小さい場合には類似度の計算を打ち切る類似度推定手段と、
前記類似度計算手段で求められた類似度及び前記類似度推定手段で計算された前記類似度の推定値を前記検索結果保存手段に格納し、検索対象ノードを決定し、該記類似度計算手段及び該類似度推定手段に出力し、検索結果を前記出力手段に出力する検索結果保存手段と、を有する。
【発明の効果】
【００１０】
上記のように、本発明によれば、特定のノードの類似度を、疎行列を用いて計算し、また、不必要な類似度計算を探索において省略することにより、従来手法より大幅に高速に類似ノードを検索できると共に、その検索結果が正確であることが保証できる。さらに、ユーザはパラメータを調整する必要がなく、容易に本発明を利用することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】本発明の一実施の形態における類似ノード検索装置の構成図である。
【図２】本発明の一実施の形態におけるノード並び替え部の次数による並び替えのフローチャートである。
【図３】本発明の一実施の形態におけるノード並び替え部のクラスタリングによる並び替えのフローチャートである。
【図４】本発明の一実施の形態におけるノード並び替え部の併用による並び替えのフローチャートである。
【図５】本発明の一実施の形態における図２〜図４の方法により並び替えが行われたグラフの隣接行列の例である。
【図６】本発明の一実施の形態における推定値の計算のフローチャートである。
【図７】本発明の一実施の形態における類似検索のアルゴリズムである。
【図８】本発明の一実施の形態における検索処理のフローチャートである。
【発明を実施するための形態】
【００１２】
以下図面と共に、本発明の実施の形態を説明する。
【００１３】
本実施の形態では、以下の問題を対象とする。
【００１４】
・問題：類似ノードの検索
・Given：問い合わせノードｑ、類似ノードの数Ｋ
・Find：問い合わせノードｑに対して類似度の高いノードＫ個
図１は、本発明の一実施の形態における類似ノード検索装置の構成を示す。
【００１５】
同図に示す類似ノード検索装置は、事前計算部１０、検索部２０、出力部３０から構成される。事前計算部１０はグラフデータを外部入力とし、上三角行列と下三角行列の逆行列を出力する。検索部２０は、問い合わせノードと検索個数を外部入力とし、上三角行列と下三角行列の逆行列を事前計算部１０からの入力とし類似ノードを出力する。
【００１６】
まず、事前計算部１０について説明する。
【００１７】
事前計算部１０は、ノード並び替え部１１、逆行列計算部１２を有する。ノード並び替え部１１は、グラフデータを外部入力とし、ノードを並び替え出力する。逆行列計算部１２は、ノードが並び替えたグラフを入力とし、上三角行列と下三角行列の逆行列を出力する。
【００１８】
検索部２０は、類似度計算部２１、類似度推定部２２、検索結果保存部２３から構成され、類似度推定部２２は、問い合わせノードと検索個数Ｋを外部入力とし、類似度計算部２１で計算された類似度、検索対象のノードを検索結果保存部２３からの入力とし、ノードの類似度を推定し、その推定値を検索結果保存部２３に出力する。類似度計算部２１は、上三角行列と下三角行列の逆行列を事前計算部１０からの入力とし、検索対象のノードを検索結果保存部２３からの入力としてRWRによりノードの類似度を計算し、検索結果保存部２３に出力する。検索結果保存部２３は、類似度推定部２２から入力された推定値、類似度計算部２1で計算された類似度を格納すると共に、検索対象のノードを決定し、類似度推定部２２と類似度計算部２１に出力する。出力部３０は、Ｋ個の検索結果を検索結果保存部２３から読み出して出力する。
【００１９】
具体的な処理の説明の前に、本明細書で用いる記号を定義し、必要となる背景知識を説明する。
【００２０】
RWRは、グラフのノードの類似度を計算する一つの方法である。RWRでは問い合わせノードを始点とするランダムウォークを行う。そしてランダムウォークでノードに到達するたびに一定の確率ｃで問い合わせノードに戻る。グラフのノード数をｎとする。ｐをｎ×１行列とし、ｐu要素をノードｕにランダムウォークする確率を表すとする。また、ｑをｎ×１行列とし、ｑq要素を１、その他の要素を０とする。またＡを列が正規化されたグラフの隣接行列とする（すなわち、Ａu,v要素はノードｖからノードｕへランダムウォークする確率を表す）。定常状態における各ノードにおける存在確率は以下の式を再帰的に収束するまで繰り返すことで計算することができる。
【００２１】
ｐ＝（１−ｃ）Ａp＋ｃq                        （１）
定常状態における確率は問い合わせノードを中心に高くなるが、RWRはこの確率を類似度とする方法である。すなわち、ｐ行列のｐu要素はノードｕのノードｑに対する類似度となる。
【００２２】
上記の定義から繰り返し回数をｔとしたとき、RWRの計算コストはＯ（mt）となる。そのためグラフが大規模である場合RWRの値を計算するのは非常に時間がかかる。
【００２３】
本発明は以下の２つの方法で構成される。
【００２４】
＜疎行列＞
当該疎行列は、事前計算部１０で生成され、検索部２０の類似度計算部２１で用いられる。問い合わせノードに対する類似度は繰り返し計算によって定常状態における確率を計算することで求めることができる。この方法はグラフの全てのノードの類似度を再帰的に計算するための計算コストが高い。そこで、本発明では、全てのノードの類似度を計算せずに、選んだノードの類似度のみを計算し高速な検索を可能にする。
【００２５】
選んだノードの類似度は式（１）から直接求められる逆行列を用いることで計算できる。そのためこの逆行列を事前に計算しておけば類似度を高速に計算できる。しかし、逆行列を保持するには、一般的にＯ（n2）のメモリが必要になるのが問題になる。
【００２６】
そこで、本発明では、この逆行列を疎行列として保持するために、ノード並び替え部１１において、まずノードを並び替えてからLU分解を計算し、上三角行列、下三角行列を生成し、逆行列計算部１２において、上三角行列、下三角行列から逆行列を計算する。この上三角行列、下三角行列の逆行列は疎行列なため、検索部２０の類似度計算部２１では、隣接リスト表現（文献1：Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 2001）を用いることにより選んだノードの類似度を疎行列から計算できる。
【００２７】
＜木構造による推定＞
前述の疎行列計算の手法により選んだノードの類似度を高速に計算することができる。本発明では、検索においてどのノードの類似度を計算し、どのノードの類似度の計算を枝刈りするかを決めるためにノードの類似度を推定する。
【００２８】
ノードの類似度を推定するために、検索部２０の類似度推定部２２では、RWRの値が問い合わせノードからのホップ数が増えるほど小さくなり、また、ノードの類似度は計算済みの類似度から推定できることを用いる。類似度推定部２２では、まず問い合わせノードを始点として幅優先探索を行い、ホップ数の小さい順にノードの類似度の推定値を計算する。そしてそのノードが解になり得る場合、類似度計算部２１において、逆行列計算部１２から出力された疎行列から類似度を計算する。類似度の推定値は既に計算を行った類似度から計算するが、検索結果保存部２３に格納されているホップ数の小さい順にノードを調べることにより、より高い精度で推定を行うことができる。ノードの推定値はO（１）で計算することができるため、少ない計算コストで類似度計算部２１による類似度の計算を省略することができる。
【００２９】
一般的な疎行列を用いて選択したノードの類似度を計算する方法として、まず、選択したノードの類似度は逆行列から計算し、その逆行列を疎行列から計算する方法がある。この方法は、式（１）から以下のように類似度を計算する。
【００３０】
ｐ＝ｃ｛Ｉ−(１−ｃ)Ａ｝−１q=ｃW−１ｑ              （２）
ここでＩは、単位行列であり、Ｗ＝Ｉ−（１−ｃ）Ａである。この式から選んだノードの類似度の類似度は逆行列Ｗ−１の対応する要素を用いることで計算できることがわかる。しかし、一般的に行列Ｗが疎であってもその逆は密になるため、直接逆行列を用いる手法は多くはメモリ量が必要になる。
【００３１】
ここで、本発明では、事前計算部１０の逆行列計算部１２は、ノード並び替え部１１で並び替えられた上三角行列と下三角行列の逆行列を疎な行列として保持し、逆行列を計算する。定式的には、ノード並び替え部１１で行列ＷをLU分解し、Ｗ＝LUとすることで、類似度計算部２１では問い合わせノードの類似度を以下のように計算する。
【００３２】
ｐ＝ｃＵ−１Ｌ−１ｑ                （３）
ここで、Ｌ−１とＵ−１はそれぞれ下三角行列と上三角行列になる。
【００３３】
ノード並び替え部１１の具体的な並び替えの方法を述べる前に、行列Ｌ−１とＵ−１の要素は行列ＬとＵの要素を用いて計算できることを示す。前進後退代入を用いることにより行列Ｌ−１とＵ−１の要素は以下のように計算できる（文献２：William H. Press and Saul A. Teukolsky and William T Vetterling and Brian P. Flannery, Numerical Recipes 3rd Edition, Cambridge University Press, 2007）。
【００３４】
【数１】
0005506711.tif 000002
また、クラウト法を用いることにより行列ＬとＵの要素は、行列Ｗを用いて以下のように計算できる（文献２）。
【００３５】
【数２】
0005506711.tif 000003
上記の式（４）、（５）、（６）、（７）は、行列Ｌ−１，Ｕ−１，Ｌ，Ｕの要素がそれぞれ列を左から右の要素の順に、また同じ列は上から下の要素の順に計算できることがわかる。例えば、行列element
【００３６】
【数３】
0005506711.tif 000004
の要素は、行列ＬとＬ−１の対応する上と左の要素から計算でき、行列Ｌijの要素は行列Ｗ，Ｌ，Ｕの対応する上と左の要素から計算できる。
【００３７】
本発明では、以下の上三角行列と下三角行列の逆行列についての考察に基づいている。
【００３８】
（１）行列
【００３９】
【数４】
0005506711.tif 000005
と、
【００４０】
【数５】
0005506711.tif 000006
は対応する行列ＬとＵの上または左の要素が０になるほど疎になる。
【００４１】
（２）行列ＬとＵの上または左の要素は行列Ｗの上または左の要素が０であれば０になる。
【００４２】
（３）Ｗの上または左の要素は行列Ａの上または左の要素が０であれば０になる。
【００４３】
すなわち、行列Ａの上または左の要素が０になるようにすれば行列
【００４４】
【数６】
0005506711.tif 000007
と、行列
【００４５】
【数７】
0005506711.tif 000008
を疎にすることができる。
【００４６】
この考察に基づき、ノード並び替え部１１における上三角行列と下三角行列を疎にするための並び替えの手法について、次数による並び替え、クラスタリングによる並び替え、併用による並び替えを提案する。
【００４７】
＜次数による並び替え＞
この方法では、グラフのノードをその次数が小さい順に並び替える。次数が小さいノードは少ないエッジで他のノードと繋がっているため、この並び替えに対応する行列Ａと左と上の要素は０となる。この方法を図２に示す。
【００４８】
＜クラスタリングによる並び替え＞
この方法では、Newman clustering（文献３：Aaron Clauset and M. E. J. Newman and Cristopher Moore, Finding community structure in very large networks, Physical Review E, 2004）によってグラフをκ個のクラスタに分割し、その結果からノードを並び替える。クラスタの数はNewman clusteringにより自動的に決定される。クラスタに分割してから空のκ＋１番目のクラスタを新たに作り、１番目からκ番目のクラスタにおいてクラスタを跨るエッジをノードが持つ場合、そのノードをκ＋１番目のクラスタに移動する。その結果行列Ａにおいて、１番目からκ番目のクラスタのノードは全てクラスタ内にしかエッジを張ってなく、κ＋１番目のクラスタのノードのみ複数のクラスタにエッジを張っている形になる。この方法を図３に示す。
【００４９】
＜併用による並び替え＞
この方法では、次数による並び替えとクラスタリングによる並び替えを併用する。すなわち、まず、クラスタリングによる並び替えによって、ノードを並び替えてから、それぞれのクラスタ内において次数の小さい順にノードを並び替える。
【００５０】
図５に、上記の３つの方法で得られる行列Ａを示す。同図において、値が０の用は白、そうでない要素は灰色で表現している。
【００５１】
事前計算部１０では、上記の手法により、上三角行列と下三角行列の逆用列は疎になり、その結果少ないメモリ量で逆行列を計算できる。
【００５２】
次に、検索部２０において、検索途中で類似度を計算していないノードの類似度を高速かつ効果的に推定する処理について説明する。
【００５３】
類似度推定部２２は、幅優先木の構造を利用して類似度の上限値を計算する。そのため、検索途中の暫定的な解のノードの類似度より推定値が小さい場合、類似度計算部２１による類似度の計算を省略するものである。
【００５４】
まず、推定に用いる記号について説明してから、推定式の定義を述べる。そして最後に推定式は検索途中において逐次的に更新できることを述べる。
【００５５】
検索部２０では、まず、類似度推定部２２において、問い合わせノードを始点にする幅優先探索木を構築する。その結果、幅優先木の第０層は問い合わせノードとなり、第１層は問い合わせノードに直接繋がっているノードとなり、第ｉ層は問い合わせノードからのホップ数がｉとなるノードとなる。
【００５６】
グラフにおけるノードの集合をVとし、類似度計算部２１で類似度を計算したノード(検索結果保存部２３に格納)をVｓとする。ノードｕの層番号をｌuとする。さらに層番号がｌuであるノードの集合をV（ｌu）とする。すなわち、V（ｌu）＝｛ｖ：（ｖ∈Vｓ）∩（ｌｖ＝ｌu）｝である。隣接行列Ａにおいて最も値の大きいエッジの重みをＡmax、すなわち、Ａmax=max{Ａij：ｉ，ｊ∈Ｖ}とする。またノードｕから出ている最も値の大きいエッジの重みをＡmax (u)、すなわち、Ａmax（ｕ）＝max{Ａiu:i∈Ｖ}とする。なお、ＡmaxとＡmax（ｕ）は検索を行う前に計算できる。ここでは、ノードの類似度の推定値の定義と、推定値が類似度より小さくなることが無いことを示す。ノードｕの推定値
【００５７】
【数８】
0005506711.tif 000009
は、幅優先木の構造を用いて定義する（定義１）。
【００５８】
［定義１］（類似度の推定）
問い合わせノードでないノードｕの推定値
【００５９】
【数９】
0005506711.tif 000010
は以下の式から計算する。
【００６０】
【数１０】
0005506711.tif 000011
ここで、ｃ'＝（１−ｃ）／（１−Ａu,u+ｃＡuu）である。また、ノードｕが問い合わせノードであるとき
【００６１】
【数１１】
0005506711.tif 000012
とする。
【００６２】
上記の定義１を用いて推定値を計算するには、Ｏ（n）の計算コストが必要である。これは集合Ｖ(lu−１)とＶ（ｌu）とＶｓの大きさがＯ（ｎ）だからである。この推定値をＯ（１）の計算コストで計算するためのアプローチは後述する。
【００６３】
この推定値の性質を示すため、以下の補助定理を導入する。
【００６４】
［補助定理１］（類似度の推定）
ノードｕに対して
【００６５】
【数１２】
0005506711.tif 000013
が成り立つ。
【００６６】
証明：もし、ノードｕが問い合わせノードでなければ、式（１）から以下が成り立つ。
【００６７】
【数１３】
0005506711.tif 000014
幅優先木において２つ以上の層番号が異なるノードは直接繋がっていることはないので、もしノードｕに直接繋がっているノードの集合をＮｕとすると類似度は以下のように現すことができる。
【００６８】
【数１４】
0005506711.tif 000015
ここで、pｖは確率であるため、
【００６９】
【数１５】
0005506711.tif 000016
となる。そのため、
【００７０】
【数１６】
0005506711.tif 000017
となる。もし、ノードｕが問い合わせノードであれば明らかに、
【００７１】
【数１７】
0005506711.tif 000018
となる。よって成り立つ。
【００７２】
検索においては、問い合わせノードを始点とする幅優先木を構築するが、これは問い合わせノードからホップ数が小さいほど類似度の値は大きくなり、また、推定は計算した類似度から行うため、より効果的に推定を行えるからである。
【００７３】
検索部２０では、類似度推定部２２において、幅優先探索の順番にノードの推定値を計算し、それが解候補のノードの最も小さい類似度より小さい場合、検索を打ち切る。その他の類似度を計算せずに検索を打ち切っても正しい検索結果になることを示すために、この推定についての以下の性質を示す。
【００７４】
［補助定理２］（木構造の探索）
幅優先の探索の順番にノードを探索していれば、ｌu≦ｌｖとなるため、ノードｕとｖに対して、
【００７５】
【数１８】
0005506711.tif 000019
が成り立つ。
【００７６】
証明：もし、ｌu＝ｌｖであれば明らかに、
【００７７】
【数１９】
0005506711.tif 000020
となる。また、ｌu＝ｌｖ−１であればＶ（ｌu）＝０(空集合)であるため、
【００７８】
【数２０】
0005506711.tif 000021
となる。また、ｌu≧ｌv−２であれば、Ｖ（ｌｖ）＝０（空集合）であり、 Ｖ(ｌｖ−１)＝０（空集合）であるため、
【００７９】
【数２１】
0005506711.tif 000022
となる。よって成り立つ。
【００８０】
上記の補助定理２からあるノードにおける推定値はそのノードと同じかまたは下の層にあるノードの推定値より小さくならないことがわかる。そのため類似度を計算していないノードの推定値が解候補のノードの最も小さい類似度より小さい場合、類似度計算部２１の類似度計算（検索）を打ち切っても検索結果に影響はでない。
【００８１】
定義１を用いてそれぞれのノードの推定値を計算するには、Ｏ（ｎ）の計算コストが必要である。ノードの推定値を高速に計算する手法について述べる。ここでノードｕはノードｕ'の直後に類似度を計算されるとする。すなわち類似度計算部２１では、ノードｕ'、ノードｕの順番で類似度を計算するとする。また、
【００８２】
【数２２】
0005506711.tif 000023
と、
【００８３】
【数２３】
0005506711.tif 000024
と
【００８４】
【数２４】
0005506711.tif 000025
はそれぞれ定義式(８)における第一項、第二項、第三項とする。すなわち、
【００８５】
【数２５】
0005506711.tif 000026
となる。
【００８６】
類似度推定部２２においてノードｕの推定値を以下のように計算する。
【００８７】
［定義２］（逐次的計算）
もし、ノードｕが問い合わせノードでないとき、推定式の第一項、第ニ項、第三項をそれぞれ以下のように計算する。
【００８８】
【数２６】
0005506711.tif 000027
もし、ノードｕが問い合わせノードであるとき、
【００８９】
【数２７】
0005506711.tif 000028
とする。
【００９０】
上記の計算式について以下の補助定理を示す。
【００９１】
［補助定理３］（逐次的計算）
定義２を用いれば、ノードｕの推定値を正確にＯ（１）の計算コストで計算できる。
【００９２】
証明：まず、ノードｕが問い合わせノードであるとき、
【００９３】
【数２８】
0005506711.tif 000029
と、
【００９４】
【数２９】
0005506711.tif 000030
と
【００９５】
【数３０】
0005506711.tif 000031
を用いてノードｕの推定値を正確に計算できることを示す。この場合、Ｖ（ｌu−１）＝ｑ，Ｖ（ｌu）＝０（空集合）、Ｖｓ＝ｑであるため、明らかに定義２より
【００９６】
【数３１】
0005506711.tif 000032
となる。
【００９７】
次に、ノードｕが問い合わせノードでないとき、ノードｕの推定値を正確に計算できることを示す。もし、ｌｕ＝ｌｕ'であれば、Ｖ（ｌu−１）＝Ｖ（ｌu'−１）であり、Ｖ（ｌu）＝Ｖ（ｌｕ'）＋ｕ'である。そのため、
【００９８】
【数３２】
0005506711.tif 000033
であり、
【００９９】
【数３３】
0005506711.tif 000034
である。
【０１００】
もし、ｌu＝ｌu'＋１であれば、V(ｌｕ−1)＝V(ｌu')+u'でありV(ｌu)=０（空集合）である。そのため、
【０１０１】
【数３４】
0005506711.tif 000035
であり、
【０１０２】
【数３５】
0005506711.tif 000036
である。
【０１０３】
また、ノードｕはノードｕ'の直後に類似度を計算させるため、
【０１０４】
【数３６】
0005506711.tif 000037
となる。
【０１０５】
よって、
【０１０６】
【数３７】
0005506711.tif 000038
と、
【０１０７】
【数３８】
0005506711.tif 000039
と
【０１０８】
【数３９】
0005506711.tif 000040
は、
【０１０９】
【数４０】
0005506711.tif 000041
と
【０１１０】
【数４１】
0005506711.tif 000042
と
【０１１１】
【数４２】
0005506711.tif 000043
を用いて正確に計算できる。
【０１１２】
そして、最後に、
【０１１３】
【数４３】
0005506711.tif 000044
と、
【０１１４】
【数４４】
0005506711.tif 000045
と
【０１１５】
【数４５】
0005506711.tif 000046
はＯ（１）の計算コストで計算できることを示す。もし、ノードｕが問い合わせノードであるとき、
【０１１６】
【数４６】
0005506711.tif 000047
と、
【０１１７】
【数４７】
0005506711.tif 000048
と
【０１１８】
【数４８】
0005506711.tif 000049
は定義２から計算できる。先に述べたとおり、ＡmaxとＡmax（u）は事前に計算できる。もし、ノードｕが問い合わせノードでないとき、
【０１１９】
【数４９】
0005506711.tif 000050
を計算する前に、
【０１２０】
【数５０】
0005506711.tif 000051
と、
【０１２１】
【数５１】
0005506711.tif 000052
と
【０１２２】
【数５２】
0005506711.tif 000053
とｐu'は既に計算されている。よって成り立つ。
【０１２３】
上記の推定値の計算の処理のフローチャートを図６に示す。
【０１２４】
次に、類似度推定部２２において、類似度の推定値が元の類似度の上限値になることを利用して、検索漏れのない検索処理について説明する。
【０１２５】
図７に類似検索のアルゴリズムを示し、図８に、検索処理のフローチャートを示す。
【０１２６】
類似度推定部２２は、図７に示すアルゴリズムを用いて、問い合わせノードに対してＫ個の類似度の高いノードを検索する。ここで、θを解候補のノードの最小の類似度とし、Ｖａを解候補のノードとする。
【０１２７】
検索では、まず、ダミーのノードの類似度は全て０とし、Vs=０（空集合）、Va＝０(空集合)とする（図７：１〜３行目(図８：ステップ１０２)）。Ｋ個のダミーのノードを解候補のノードとする（図７：４行目(図８：ステップ１０３)）。そして幅優先木を構築する（図７：５行目(図８：ステップ１０４)）。層番号の順にノードを選択し（図７：７行目（図８：ステップ１０５））、選ばれたノードの推定値を計算する(図７：８行目（ステップ１０６）。もし推定値がθより小さい場合（ステップ１０７、Ｙｅｓ）、そのノードは解になり得ず（補助定理１）、またその他の選択されなかったノードの推定値もθよりも小さくなる(補助定理２)。そのため、検索を終了する(図７：９，１０行目)（ステップ１０８)）。もしそうでなければ（ステップ１０７、No）、選択されたノードが解になり得る。そのため、そのノードの類似度を計算する（図７：１２行目（図８：ステップ１０９））。もし、計算した類似度がθよりも大きい場合(図８：ステップ１１０、Ｙｅｓ)、Ｖａとθを更新する（図７：１３〜１８行目)(図８：ステップ１１１，１１２)）。
【０１２８】
上記のように、事前計算部１０のノード並び替え部１１では、入力されたグラフデータからＬＵ分解し、上三角行列と下三角行列とし、逆行列計算部１２では、上三角行列と下三角行列の逆行列を求め、疎行列にする。なお、ノードの並び替えには外部入力パラメータは用いない。
【０１２９】
次に、検索部２０の類似度推定部２２は、検索の途中で類似度を計算していないノードの類似度を推定し、不必要な類似度計算を省略する。省略されない場合は、類似度計算部２１において、逆行列計算部１２から出力された上三角行列と下三角行列の逆行列と、検索結果保存部２３から検索対象ノードを取得して、ノードの類似度を計算し、検索結果保存部２３に保存する。
【０１３０】
類似度推定部２２におけるノードの類似度の推定は、検索途中において、計算コストＯ（１）で計算できるため、高速処理が可能である。また、類似度の推定値は元の類似度の上限値となるため、検索漏れは発生しない。また、類似度の推定においても、外部入力パラメータは不要である。
【０１３１】
なお、図１に示す類似ノード検索装置の構成要素の動作をプログラムとして構築し、類似ノード検索装置として利用されるコンピュータにインストールし、実行させる、または、ネットワークを介して流通させることが可能である。
【０１３２】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１３３】
１０  事前計算部
１１  ノード並び替え部
１２  逆行列計算部
２０  検索部
２１  類似度計算部
２２  類似度推定部
２３  検索結果保存部
３０  出力部
【図１】
0005506711.tif 000054
【図２】
0005506711.tif 000055
【図３】
0005506711.tif 000056
【図４】
0005506711.tif 000057
【図６】
0005506711.tif 000058
【図７】
0005506711.tif 000059
【図８】
0005506711.tif 000060
【図５】
0005506711.tif 000061