"グラフの構造的な特徴に基づいて類似度を計算するRandomwalkwithrestartを用いて類似度を計算する類似度計算手段を有し、類似度が高い順にK個のノードを検索する類似ノード検索装置であって、外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算手段と、外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索手段と、K個の検索結果を出力する出力手段と、を有することを特徴とする類似ノード検索装置。前記事前計算手段は、前記外部から入力されたグラフデータからノードを並び替えて出力するノード並び替え手段と、並び替えられたグラフから前記上三角行列と前記下三角行列の逆行列を生成する逆行列計算手段と、を含む請求項1記載の類似ノード検索装置。前記検索手段は、前記問い合わせノードと前記検索個数及び前記逆行列から類似度を計算する前記類似度計算手段、類似度推定手段、前記類似度計算手段で求められた類似度及び前記類似度推定手段で計算された推定された類似度を格納し、検索対象ノードを決定し、前記類似度計算手段及び前記類似度推定手段に出力し、検索結果を前記出力手段に出力する検索結果保存手段と、を有し、前記類似度推定手段は、前記類似度計算手段から取得した類似度と前記検索結果保存手段から取得した検索対象ノードについて、前記問い合わせノードを始点とする幅優先木を構築し、幅優先探索の順番に推定された類似度を計算し、前記検索結果保存手段に格納し、該推定された類似度が解候補ノードの最も小さい類似度より小さい場合には類似度の計算を打ち切る手段を含む請求項1記載の類似ノード検索装置。グラフの構造的な特徴に基づいて類似度を計算するRandomwalkwithrestartを用いて類似度を計算し、類似度が高い順にK個のノードを検索する類似ノード検索方法であって、事前計算手段が、外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算ステップ検索手段が、外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索ステップ、出力手段が、K個の検索結果を出力する出力ステップと、を行うことを特徴とする類似ノード検索方法。前記事前計算ステップにおいて、前記外部から入力されたグラフデータからノードを並び替えて出力するノード並び替え、並び替えられたグラフから前記上三角行列と前記下三角行列の逆行列を生成する請求項4記載の類似ノード検索方法。前記検索ステップにおいて、類似度計算手段が、前記問い合わせノードと前記検索個数及び前記逆行列から前記RWRを用いて類似度を計算し、記憶手段に格納する類似度計算ステップと、類似度推定手段が、前記類似度計算ステップで計算された前記類似度と前記記憶手段から検索対象ノードを取得し、該検索対象ノードについて、前記問い合わせノードを始点とする幅優先木を構築し、幅優先探索の順番に推定された類似度を計算し、前記記憶手段に格納し、該推定値が解候補ノードの最も小さい類似度より小さい場合には類似度の計算を打ち切る請求項4記載の類似ノード検索方法。請求項1乃至3のいずれか1項に記載の類似ノード検索装置を構成する各手段としてコンピュータを機能させるための類似ノード検索プログラム。しかし、上記の非特許文献2、3の手法は精度を犠牲にするものであり、アプリケーションに対する応用を考えた場合、精度が犠牲になるのは好ましくない。また、実際のアプリケーションにおいては問い合わせノードqから他の全てのノードの類似度を計算するのではなく、類似度の高いノードのみを行う処理が行われている例えば、非特許文献3参照。そのため、本明細書では、問い合わせノードqと検索個数Kが与えられたとき、類似度の高いK個のノードを高速かつ正確に検索する問題を対象とする。本発明は、上記の点に鑑みなされたもので、高速かつ正確に類似ノードを検索することが可能な類似ノード検索装置及び方法及びプログラムを提供することを目的とする。上記の課題を解決するため、本発明は、グラフの構造的な特徴に基づいて類似度を計算するRWRを用いて類似度を計算する類似度計算手段を有し、類似度が高い順にK個のノードを検索する類似ノード検索装置であって、外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算手段と、外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索手段と、K個の検索結果を出力する出力手段と、を有する。上記のように、本発明によれば、特定のノードの類似度を、疎行列を用いて計算し、また、不必要な類似度計算を探索において省略することにより、従来手法より大幅に高速に類似ノードを検索できると共に、その検索結果が正確であることが保証できる。さらに、ユーザはパラメータを調整する必要がなく、容易に本発明を利用することが可能となる。以下図面と共に、本発明の実施の形態を説明する。本実施の形態では、以下の問題を対象とする。問題:類似ノードの検索Given:問い合わせノードq、類似ノードの数KFind:問い合わせノードqに対して類似度の高いノードK個図1は、本発明の一実施の形態における類似ノード検索装置の構成を示す。同図に示す類似ノード検索装置は、事前計算部10、検索部20、出力部30から構成される。事前計算部10はグラフデータを外部入力とし、上三角行列と下三角行列の逆行列を出力する。検索部20は、問い合わせノードと検索個数を外部入力とし、上三角行列と下三角行列の逆行列を事前計算部10からの入力とし類似ノードを出力する。まず、事前計算部10について説明する。事前計算部10は、ノード並び替え部11、逆行列計算部12を有する。ノード並び替え部11は、グラフデータを外部入力とし、ノードを並び替え出力する。逆行列計算部12は、ノードが並び替えたグラフを入力とし、上三角行列と下三角行列の逆行列を出力する。検索部20は、類似度計算部21、類似度推定部22、検索結果保存部23から構成され、類似度推定部22は、問い合わせノードと検索個数Kを外部入力とし、類似度計算部21で計算された類似度、検索対象のノードを検索結果保存部23からの入力とし、ノードの類似度を推定し、その推定値を検索結果保存部23に出力する。類似度計算部21は、上三角行列と下三角行列の逆行列を事前計算部10からの入力とし、検索対象のノードを検索結果保存部23からの入力としてRWRによりノードの類似度を計算し、検索結果保存部23に出力する。検索結果保存部23は、類似度推定部22から入力された推定値、類似度計算部21で計算された類似度を格納すると共に、検索対象のノードを決定し、類似度推定部22と類似度計算部21に出力する。出力部30は、K個の検索結果を検索結果保存部23から読み出して出力する。具体的な処理の説明の前に、本明細書で用いる記号を定義し、必要となる背景知識を説明する。RWRは、グラフのノードの類似度を計算する一つの方法である。RWRでは問い合わせノードを始点とするランダムウォークを行う。そしてランダムウォークでノードに到達するたびに一定の確率cで問い合わせノードに戻る。グラフのノード数をnとする。pをn×1行列とし、pu要素をノードuにランダムウォークする確率を表すとする。また、qをn×1行列とし、qq要素を1、その他の要素を0とする。またAを列が正規化されたグラフの隣接行列とするすなわち、Auv要素はノードvからノードuへランダムウォークする確率を表す。定常状態における各ノードにおける存在確率は以下の式を再帰的に収束するまで繰り返すことで計算することができる。p=1-cApcq1定常状態における確率は問い合わせノードを中心に高くなるが、RWRはこの確率を類似度とする方法である。すなわち、p行列のpu要素はノードuのノードqに対する類似度となる。上記の定義から繰り返し回数をtとしたとき、RWRの計算コストはOmtとなる。そのためグラフが大規模である場合RWRの値を計算するのは非常に時間がかかる。本発明は以下の2つの方法で構成される。<疎行列>当該疎行列は、事前計算部10で生成され、検索部20の類似度計算部21で用いられる。問い合わせノードに対する類似度は繰り返し計算によって定常状態における確率を計算することで求めることができる。この方法はグラフの全てのノードの類似度を再帰的に計算するための計算コストが高い。そこで、本発明では、全てのノードの類似度を計算せずに、選んだノードの類似度のみを計算し高速な検索を可能にする。選んだノードの類似度は式1から直接求められる逆行列を用いることで計算できる。そのためこの逆行列を事前に計算しておけば類似度を高速に計算できる。しかし、逆行列を保持するには、一般的にOn2のメモリが必要になるのが問題になる。そこで、本発明では、この逆行列を疎行列として保持するために、ノード並び替え部11において、まずノードを並び替えてからLU分解を計算し、上三角行列、下三角行列を生成し、逆行列計算部12において、上三角行列、下三角行列から逆行列を計算する。この上三角行列、下三角行列の逆行列は疎行列なため、検索部20の類似度計算部21では、隣接リスト表現文献1:ThomasHCormenandCharlesELeisersonandRonaldLRivestandCliffordSteinIntroductiontoAlgorithmsTheMITPress2001を用いることにより選んだノードの類似度を疎行列から計算できる。<木構造による推定>前述の疎行列計算の手法により選んだノードの類似度を高速に計算することができる。本発明では、検索においてどのノードの類似度を計算し、どのノードの類似度の計算を枝刈りするかを決めるためにノードの類似度を推定する。ノードの類似度を推定するために、検索部20の類似度推定部22では、RWRの値が問い合わせノードからのホップ数が増えるほど小さくなり、また、ノードの類似度は計算済みの類似度から推定できることを用いる。類似度推定部22では、まず問い合わせノードを始点として幅優先探索を行い、ホップ数の小さい順にノードの類似度の推定値を計算する。そしてそのノードが解になり得る場合、類似度計算部21において、逆行列計算部12から出力された疎行列から類似度を計算する。類似度の推定値は既に計算を行った類似度から計算するが、検索結果保存部23に格納されているホップ数の小さい順にノードを調べることにより、より高い精度で推定を行うことができる。ノードの推定値はO1で計算することができるため、少ない計算コストで類似度計算部21による類似度の計算を省略することができる。一般的な疎行列を用いて選択したノードの類似度を計算する方法として、まず、選択したノードの類似度は逆行列から計算し、その逆行列を疎行列から計算する方法がある。この方法は、式1から以下のように類似度を計算する。p=c{I-A}-1qcW-1q2ここでIは、単位行列であり、W=I-1-cAである。この式から選んだノードの類似度の類似度は逆行列W-1の対応する要素を用いることで計算できることがわかる。しかし、一般的に行列Wが疎であってもその逆は密になるため、直接逆行列を用いる手法は多くはメモリ量が必要になる。ここで、本発明では、事前計算部10の逆行列計算部12は、ノード並び替え部11で並び替えられた上三角行列と下三角行列の逆行列を疎な行列として保持し、逆行列を計算する。定式的には、ノード並び替え部11で行列WをLU分解し、W=LUとすることで、類似度計算部21では問い合わせノードの類似度を以下のように計算する。p=cU-1L-1q3ここで、L-1とU-1はそれぞれ下三角行列と上三角行列になる。ノード並び替え部11の具体的な並び替えの方法を述べる前に、行列L-1とU-1の要素は行列LとUの要素を用いて計算できることを示す。前進後退代入を用いることにより行列L-1とU-1の要素は以下のように計算できる文献2:WilliamHPressandSaulATeukolskyandWilliamTVetterlingandBrianPFlanneryNumericalRecipes3rdEditionCambridgeUniversityPress2007。また、クラウト法を用いることにより行列LとUの要素は、行列Wを用いて以下のように計算できる文献2。上記の式4、5、6、7は、行列L-1,U-1,L,Uの要素がそれぞれ列を左から右の要素の順に、また同じ列は上から下の要素の順に計算できることがわかる。例えば、行列elementの要素は、行列LとL-1の対応する上と左の要素から計算でき、行列Lijの要素は行列W,L,Uの対応する上と左の要素から計算できる。本発明では、以下の上三角行列と下三角行列の逆行列についての考察に基づいている。1行列と、は対応する行列LとUの上または左の要素が0になるほど疎になる。2行列LとUの上または左の要素は行列Wの上または左の要素が0であれば0になる。3Wの上または左の要素は行列Aの上または左の要素が0であれば0になる。すなわち、行列Aの上または左の要素が0になるようにすれば行列と、行列を疎にすることができる。この考察に基づき、ノード並び替え部11における上三角行列と下三角行列を疎にするための並び替えの手法について、次数による並び替え、クラスタリングによる並び替え、併用による並び替えを提案する。<次数による並び替え>この方法では、グラフのノードをその次数が小さい順に並び替える。次数が小さいノードは少ないエッジで他のノードと繋がっているため、この並び替えに対応する行列Aと左と上の要素は0となる。この方法を図2に示す。<クラスタリングによる並び替え>この方法では、Newmanclustering文献3:AaronClausetandMEJNewmanandCristopherMooreFindingcommunitystructureinverylargenetworksPhysicalReviewE2004によってグラフをκ個のクラスタに分割し、その結果からノードを並び替える。クラスタの数はNewmanclusteringにより自動的に決定される。クラスタに分割してから空のκ1番目のクラスタを新たに作り、1番目からκ番目のクラスタにおいてクラスタを跨るエッジをノードが持つ場合、そのノードをκ1番目のクラスタに移動する。その結果行列Aにおいて、1番目からκ番目のクラスタのノードは全てクラスタ内にしかエッジを張ってなく、κ1番目のクラスタのノードのみ複数のクラスタにエッジを張っている形になる。この方法を図3に示す。<併用による並び替え>この方法では、次数による並び替えとクラスタリングによる並び替えを併用する。すなわち、まず、クラスタリングによる並び替えによって、ノードを並び替えてから、それぞれのクラスタ内において次数の小さい順にノードを並び替える。図5に、上記の3つの方法で得られる行列Aを示す。同図において、値が0の用は白、そうでない要素は灰色で表現している。事前計算部10では、上記の手法により、上三角行列と下三角行列の逆用列は疎になり、その結果少ないメモリ量で逆行列を計算できる。次に、検索部20において、検索途中で類似度を計算していないノードの類似度を高速かつ効果的に推定する処理について説明する。類似度推定部22は、幅優先木の構造を利用して類似度の上限値を計算する。そのため、検索途中の暫定的な解のノードの類似度より推定値が小さい場合、類似度計算部21による類似度の計算を省略するものである。まず、推定に用いる記号について説明してから、推定式の定義を述べる。そして最後に推定式は検索途中において逐次的に更新できることを述べる。検索部20では、まず、類似度推定部22において、問い合わせノードを始点にする幅優先探索木を構築する。その結果、幅優先木の第0層は問い合わせノードとなり、第1層は問い合わせノードに直接繋がっているノードとなり、第i層は問い合わせノードからのホップ数がiとなるノードとなる。グラフにおけるノードの集合をVとし、類似度計算部21で類似度を計算したノードをVsとする。ノードuの層番号をluとする。さらに層番号がluであるノードの集合をVluとする。すなわち、Vlu={v:v∈Vs∩lv=lu}である。隣接行列Aにおいて最も値の大きいエッジの重みをAmax、すなわち、AmaxmaxAij:i,j∈Vとする。またノードuから出ている最も値の大きいエッジの重みをAmax、すなわち、Amaxu=maxAiui∈Vとする。なお、AmaxとAmaxuは検索を行う前に計算できる。ここでは、ノードの類似度の推定値の定義と、推定値が類似度より小さくなることが無いことを示す。ノードuの推定値は、幅優先木の構造を用いて定義する定義1。[定義1]類似度の推定問い合わせノードでないノードuの推定値は以下の式から計算する。ここで、c=1-c/1-AuucAuuである。また、ノードuが問い合わせノードであるときとする。上記の定義1を用いて推定値を計算するには、Onの計算コストが必要である。これは集合VとVluとVsの大きさがOnだからである。この推定値をO1の計算コストで計算するためのアプローチは後述する。この推定値の性質を示すため、以下の補助定理を導入する。[補助定理1]類似度の推定ノードuに対してが成り立つ。証明:もし、ノードuが問い合わせノードでなければ、式1から以下が成り立つ。幅優先木において2つ以上の層番号が異なるノードは直接繋がっていることはないので、もしノードuに直接繋がっているノードの集合をNuとすると類似度は以下のように現すことができる。ここで、pvは確率であるため、となる。そのため、となる。もし、ノードuが問い合わせノードであれば明らかに、となる。よって成り立つ。検索においては、問い合わせノードを始点とする幅優先木を構築するが、これは問い合わせノードからホップ数が小さいほど類似度の値は大きくなり、また、推定は計算した類似度から行うため、より効果的に推定を行えるからである。検索部20では、類似度推定部22において、幅優先探索の順番にノードの推定値を計算し、それが解候補のノードの最も小さい類似度より小さい場合、検索を打ち切る。その他の類似度を計算せずに検索を打ち切っても正しい検索結果になることを示すために、この推定についての以下の性質を示す。[補助定理2]木構造の探索幅優先の探索の順番にノードを探索していれば、lu≦lvとなるため、ノードuとvに対して、が成り立つ。証明:もし、lu=lvであれば明らかに、となる。また、lu=lv-1であればVlu=0であるため、となる。また、lu≧lv-2であれば、Vlv=0空集合であり、V=0空集合であるため、となる。よって成り立つ。上記の補助定理2からあるノードにおける推定値はそのノードと同じかまたは下の層にあるノードの推定値より小さくならないことがわかる。そのため類似度を計算していないノードの推定値が解候補のノードの最も小さい類似度より小さい場合、類似度計算部21の類似度計算検索を打ち切っても検索結果に影響はでない。定義1を用いてそれぞれのノードの推定値を計算するには、Onの計算コストが必要である。ノードの推定値を高速に計算する手法について述べる。ここでノードuはノードuの直後に類似度を計算されるとする。すなわち類似度計算部21では、ノードu、ノードuの順番で類似度を計算するとする。また、と、とはそれぞれ定義式における第一項、第二項、第三項とする。すなわち、となる。類似度推定部22においてノードuの推定値を以下のように計算する。[定義2]逐次的計算もし、ノードuが問い合わせノードでないとき、推定式の第一項、第ニ項、第三項をそれぞれ以下のように計算する。もし、ノードuが問い合わせノードであるとき、とする。上記の計算式について以下の補助定理を示す。[補助定理3]逐次的計算定義2を用いれば、ノードuの推定値を正確にO1の計算コストで計算できる。証明:まず、ノードuが問い合わせノードであるとき、と、とを用いてノードuの推定値を正確に計算できることを示す。この場合、Vlu-1=q,Vlu=0空集合、Vs=qであるため、明らかに定義2よりとなる。次に、ノードuが問い合わせノードでないとき、ノードuの推定値を正確に計算できることを示す。もし、lu=luであれば、Vlu-1=Vlu-1であり、Vlu=Vluuである。そのため、であり、である。もし、lu=lu1であれば、V=VuでありV0空集合である。そのため、であり、である。また、ノードuはノードuの直後に類似度を計算させるため、となる。よって、と、とは、ととを用いて正確に計算できる。そして、最後に、と、とはO1の計算コストで計算できることを示す。もし、ノードuが問い合わせノードであるとき、と、とは定義2から計算できる。先に述べたとおり、AmaxとAmaxuは事前に計算できる。もし、ノードuが問い合わせノードでないとき、を計算する前に、と、ととpuは既に計算されている。よって成り立つ。上記の推定値の計算の処理のフローチャートを図6に示す。次に、類似度推定部22において、類似度の推定値が元の類似度の上限値になることを利用して、検索漏れのない検索処理について説明する。図7に類似検索のアルゴリズムを示し、図8に、検索処理のフローチャートを示す。類似度推定部22は、図7に示すアルゴリズムを用いて、問い合わせノードに対してK個の類似度の高いノードを検索する。ここで、θを解候補のノードの最小の類似度とし、Vaを解候補のノードとする。検索では、まず、ダミーのノードの類似度は全て0とし、Vs0空集合、Va=0とする図7:1~3行目。K個のダミーのノードを解候補のノードとする図7:4行目。そして幅優先木を構築する図7:5行目。層番号の順にノードを選択し図7:7行目図8:ステップ105、選ばれたノードの推定値を計算する。そのため、検索を終了するステップ108。もしそうでなければステップ107、No、選択されたノードが解になり得る。そのため、そのノードの類似度を計算する図7:12行目図8:ステップ109。もし、計算した類似度がθよりも大きい場合、Vaとθを更新する図7:13~18行目。上記のように、事前計算部10のノード並び替え部11では、入力されたグラフデータからLU分解し、上三角行列と下三角行列とし、逆行列計算部12では、上三角行列と下三角行列の逆行列を求め、疎行列にする。なお、ノードの並び替えには外部入力パラメータは用いない。次に、検索部20の類似度推定部22は、検索の途中で類似度を計算していないノードの類似度を推定し、不必要な類似度計算を省略する。省略されない場合は、類似度計算部21において、逆行列計算部12から出力された上三角行列と下三角行列の逆行列と、検索結果保存部23から検索対象ノードを取得して、ノードの類似度を計算し、検索結果保存部23に保存する。類似度推定部22におけるノードの類似度の推定は、検索途中において、計算コストO1で計算できるため、高速処理が可能である。また、類似度の推定値は元の類似度の上限値となるため、検索漏れは発生しない。また、類似度の推定においても、外部入力パラメータは不要である。なお、図1に示す類似ノード検索装置の構成要素の動作をプログラムとして構築し、類似ノード検索装置として利用されるコンピュータにインストールし、実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"