(57)【特許請求の範囲】
【請求項１】
複数のノードを有するグラフにおけるノード間の接続状態を示す情報に基づいて、前記複数のノードの中から、それぞれ複数のノードを有する複数のグループを選択する選択部と、
前記選択部により選択された複数のグループのそれぞれについて、グループ内のノード間の平均距離を算出する第一の算出部と、
前記第一の算出部によりグループごとに算出されたグループ内のノード間の平均距離、および、前記ノード間の接続状態を示す情報に基づいて、前記グループのそれぞれと、前記複数のノードのそれぞれとの距離を算出する第二の算出部と、
前記第二の算出部により算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する第三の算出部と、
を有することを特徴とする算出装置。
【請求項２】
前記第三の算出部は、前記第二の算出部により算出された前記２つのノードのそれぞれと前記グループとの距離の和をグループごとに算出し、算出した距離の和のうち、最小の和を前記２つのノード間の距離として算出する
請求項１に記載の算出装置。
【請求項３】
前記選択部は、前記ノード間の接続状態を示す情報に基づいて、複数のノードの中から第一の条件を満たすノードを複数選択し、選択した複数のノードのそれぞれについて、第二の条件を満たすグループを選択する
ことを特徴とする請求項１または２に記載の算出装置。
【請求項４】
前記選択部は、前記ノード間の接続状態を示す行列から複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、算出した複数の固有値および複数の固有ベクトルに基づいて、前記複数のグループを選択することを特徴とする請求項１または２に記載の算出装置。
【請求項５】
複数のノードを有するグラフにおけるノード間の接続状態を示す行列から複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、算出した複数の固有値および複数の固有ベクトルに基づいて、それぞれ複数のノードを有する複数のグループを選択する選択部と、
前記固有値および前記固有ベクトルに基づいて、前記複数のグループのそれぞれと、前記複数のノードのそれぞれとの距離を算出する第一の算出部と、
前記第一の算出部により算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する第二の算出部と、
を有することを特徴とする算出装置。
【請求項６】
前記選択部は、前記複数の固有値および複数の固有ベクトルに基づいて、固有値ごとに、該固有値の絶対値の平方の逆数よりも、固有ベクトルの成分の絶対値が大きいノードを一つのグループとして選択する
ことを特徴とする請求項４または５に記載の算出装置。
【請求項７】
複数のノードを有するグラフにおけるノード間の接続状態を示す行列から複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出する第一の算出部と、
前記複数の固有ベクトルごとに、距離の算出対象の２つのノードのそれぞれに対応する該固有ベクトルの２つの成分の積と該固有ベクトルに対応する固有値のｋ乗の値との積を算出し、前記複数の固有ベクトルごとに算出した前記積の和を算出し、算出した該和が、前記行列においてノード間が接続していることを示す値から所定値を減算した値を超える最小の前記ｋの値を、前記２つのノード間の距離として算出する第二の算出部と、
を有することを特徴とする算出装置。
【請求項８】
コンピュータに、
記憶部に記憶される、複数のノードを有するグラフにおけるノード間の接続状態を示す情報に基づいて、前記複数のノードの中から、それぞれ複数のノードを有する複数のグループを選択し、
選択された前記複数のグループのそれぞれについて、グループ内のノード間の平均距離を算出し、
グループごとに算出された前記グループ内のノード間の平均距離、および、前記ノード間の接続状態を示す情報に基づいて、前記グループのそれぞれと、前記複数のノードのそれぞれとの距離を算出し、
算出された前記距離に基づいて、距離の算出対象の２つのノード間の距離を算出する、
各処理を実行させるための算出プログラム。
【請求項９】
コンピュータに、
記憶部に記憶される、複数のノードを有するグラフにおけるノード間の接続状態を示す行列から、複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、算出した複数の固有値および複数の固有ベクトルに基づいて、それぞれ複数のノードを有する複数のグループを選択し、
前記固有値および前記固有ベクトルに基づいて、前記複数のグループのそれぞれと、前記複数のノードのそれぞれとの距離を算出し、
算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する、
各処理を実行させるための算出プログラム。
【請求項１０】
コンピュータに、
記憶部に記憶される、複数のノードを有するグラフにおけるノード間の接続状態を示す行列から、複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、
前記複数の固有ベクトルごとに、距離の算出対象の２つのノードのそれぞれに対応する該固有ベクトルの２つの成分の積と該固有ベクトルに対応する固有値のｋ乗の値との積を算出し、前記複数の固有ベクトルごとに算出した前記積の和を算出し、算出した該和が、前記行列においてノード間が接続していることを示す値から所定値を減算した値を超える最小の前記ｋの値を、前記２つのノード間の距離として算出する、
各処理を実行させるための算出プログラム。
【請求項１１】
コンピュータが実行する算出方法であって、
記憶部に記憶される、複数のノードを有するグラフにおけるノード間の接続状態を示す情報に基づいて、前記複数のノードの中から、それぞれ複数のノードを有する複数のグループを選択し、
選択された前記複数のグループのそれぞれについて、グループ内のノード間の平均距離を算出し、
グループごとに算出された前記グループ内のノード間の平均距離、および、前記ノード間の接続状態を示す情報に基づいて、前記グループのそれぞれと、前記複数のノードのそれぞれとの距離を算出し、
算出された前記距離に基づいて、距離の算出対象の２つのノード間の距離を算出する、
各処理を実行することを特徴とする算出方法。
【請求項１２】
コンピュータが実行する算出方法であって、
記憶部に記憶される、複数のノードを有するグラフにおけるノード間の接続状態を示す行列から、複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、算出した複数の固有値および複数の固有ベクトルに基づいて、それぞれ複数のノードを有する複数のグループを選択し、
前記固有値および前記固有ベクトルに基づいて、前記複数のグループのそれぞれと、前記複数のノードのそれぞれとの距離を算出し、
算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する、
各処理を実行することを特徴とする算出方法。
【請求項１３】
コンピュータが実行する算出方法であって、
記憶部に記憶される、複数のノードを有するグラフにおけるノード間の接続状態を示す行列から、複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、
前記複数の固有ベクトルごとに、距離の算出対象の２つのノードのそれぞれに対応する該固有ベクトルの２つの成分の積と該固有ベクトルに対応する固有値のｋ乗の値との積を算出し、前記複数の固有ベクトルごとに算出した前記積の和を算出し、算出した該和が、前記行列においてノード間が接続していることを示す値から所定値を減算した値を超える最小の前記ｋの値を、前記２つのノード間の距離として算出する、
各処理を実行することを特徴とする算出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算出装置、算出プログラムおよび算出方法に関する。
【背景技術】
【０００２】
従来、多数のノードのそれぞれを示す情報と、ノード間を結ぶエッジを示す情報とを含むグラフデータにおいて、ノード間の距離を算出する装置がある。なお、グラフデータにおけるノードは、例えば、Ｆａｃｅｂｏｏｋ（登録商標）における「人物」に対応する。この場合には、ノード間の距離の値が小さいほど、２つのノードが示す「人物」同士は、友人関係において密接な関係にあるといえる。また、グラフデータの一例としては、隣接行列のデータが挙げられる。隣接行列とは、エッジを介して直接接続されているノード間に対応する成分（要素）の値が、２つのノードが接続されていることを示す値であり、接続されていないノード間に対応する成分の値が、２つのノードが接続されていないことを示す値である行列を指す。「２つのノードが接続されていることを示す値」の一例としては、「１」が挙げられる。また、「２つのノードが接続されていないことを示す値」の一例としては、「０」が挙げられる。また、ここでいうノード間の距離とは、２つのノードを結ぶ経路、すなわち、２つのノードを結ぶエッジとノードのパターンが複数存在する場合には、エッジの数が最短となるパターンにおけるエッジの数を示す。
【０００３】
ここで、単純に、距離を計算する対象の２つのノード間で取り得る全ての経路を導出し、導出した全ての経路から、エッジの数が最短となる場合の経路を特定することで、ノード間の距離を算出する方法が考えられる。しかしながら、この方法では、グラフデータにおける経路の数が増加するにつれて、計算量が多くなってしまう。
【０００４】
そこで、全てのノード間の距離を予め算出し、算出した距離を記憶装置に記憶しておき、距離を計算する対象の２つのノードが指定された場合に、２つのノード間に対応する距離を記憶装置から取得することで、ノード間の距離を算出する方法も考えられる。この方法では、予め全てのノード間の距離を記憶装置に記憶しておくので、計算量を抑制することができる。しかしながら、この方法では、予め全てのノード間の距離を算出する処理に多くの時間がかかり、記憶しておくノードの組み合わせの数も膨大なものとなるため、実現が困難である。
【０００５】
そこで、上記の従来の装置は、例えば、多数のノードのうち、他のノードと比べて、より多くのエッジに接続された所定のノードを「ランドマークノード」として選択し、全てのノード間の距離ではなく、ランドマークノードと他のノードとの距離を予め算出する。そして、上記の従来の装置は、算出したランドマークノードと他のノードとの距離を記憶装置に記憶する。続いて、上記の従来の装置は、距離を計算する対象の２つのノードが指定された場合に、記憶装置から２つのノードのそれぞれとランドマークとの距離の和をランドマークごとに算出する。そして、上記の従来の装置は、ランドマークごとに算出した距離の和のうち、最小の和の値を、指定された２つのノード間の距離として算出する。
【０００６】
図２０Ａ〜２０ｃは、従来の装置による距離の算出方法の一例を示す図である。図２０Ａには、グラフデータ８０が示すノードと、各ノードを接続するエッジとが示されている。図２０Ａの例では、ランドマークノードとしてノード８３，８４が選択された場合が示されている。なお、図２０Ａの例では図示されていないが、ここでは、ノード８３，８４以外のノードについてもランドマークノードとして選択されたものとする。また、図２０Ａの例では、ノード８３との距離が「２」であり、ノード８４との距離が「２」であるノード８１、および、ノード８３との距離が「２」であり、ノード８４との距離が「３」であるノード８２が示されている。図２０Ｂは、選択された各ランドマークノードと、各ノードとの距離を示す図である。図２０Ｂの例は、ランドマークノード８３とノード８１との距離が「２」であることを示す。また、図２０Ｂの例は、ランドマークノード８３とノード８２との距離が「２」であることを示す。また、図２０Ｂの例は、ランドマークノード８４とノード８１との距離が「２」であることを示す。また、図２０Ｂの例は、ランドマークノード８４とノード８２との距離が「３」であることを示す。
【０００７】
図２０Ｃは、各ランドマークと、距離を計算する対象として指定された２つのノードのそれぞれとの距離の和の一例を示す。ここでは、距離を計算する対象の２つのノードとして、ノード８１，８２が指定された場合について説明する。図２０Ｃの例では、ノード８１とランドマークノード８３との距離と、ノード８２とランドマークノード８３との距離との和が「４」である場合が示されている。また、図２０Ｃの例では、ノード８１とランドマークノード８４との距離と、ノード８２とランドマークノード８４との距離との和が「５」である場合が示されている。従来の装置は、図２０Ｃの例の場合では、ノード８１とノード８２との距離として、「４」を算出する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M.  Potamias  et  al.、「Fast  Shortest  Path  Distance  Estimation  in  Large  Networks」、CIKM’09、２００９年
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記の従来の装置では、距離の算出結果の精度が低くなる場合があるという問題がある。
【００１０】
例を挙げて説明する。図２１Ａ〜２１Ｃ、図２２Ａ〜２２Ｃ、図２３は、従来の装置の問題点の一例を説明するための図である。図２１Ａの例は、グラフデータ８５において、ランドマークノードとして選択されたノード８６に、ノード８７およびノード８８がエッジを介して接続された場合を示す。また、図２１Ａの例では、ノード８７とノード８８とが直接エッジを介して接続されていない。また、図２１Ａの例では、ノード８７に、エッジを介してノード８９が接続されている。
【００１１】
図２１Ｂは、図２１Ａの場合における各ノード間の実際の距離を示す図である。図２１Ｂの例は、ノード８７とノード８８との距離が、「２」である場合を示す。また、図２１Ｂの例は、ノード８７とノード８６との距離が、「１」である場合を示す。また、図２１Ｂの例は、ノード８７とノード８９との距離が、「１」である場合を示す。また、図２１Ｂの例は、ノード８８とノード８６との距離が、「１」である場合を示す。また、図２１Ｂの例は、ノード８８とノード８９との距離が、「３」である場合を示す。また、図２１Ｂの例は、ノード８６とノード８９との距離が、「２」である場合を示す。
【００１２】
図２１Ｃは、図２１Ａの場合において、従来の装置によって算出された各ノード間の距離を示す図である。図２１Ｃの例に示すように、従来の装置は、ノード８７とノード８８との距離「２」を算出する。また、図２１Ｃの例に示すように、従来の装置は、ノード８７とノード８６との距離「１」を算出する。また、図２１Ｃの例に示すように、従来の装置は、ノード８７とノード８９との距離「３」を算出する。また、図２１Ｃの例に示すように、従来の装置は、ノード８８とノード８６との距離「１」を算出する。また、図２１Ｃの例に示すように、従来の装置は、ノード８８とノード８９との距離「３」を算出する。また、図２１Ｃの例に示すように、従来の装置は、ノード８６とノード８９との距離「２」を算出する。
【００１３】
すなわち、図２１Ａの例では、ノード８７，８９間の距離についての算出結果は、実際の距離と異なり、ノード８７，８９間以外のノード間の距離の算出結果は、実際の距離と同一となる。このように、ほとんどのノード間について、算出結果が、実施の距離と同一となる理由は、ランドマークノード８６に接続されたノード８７，８８同士が直接エッジを介して接続されていないからである。なお、ノード８７，８９間の距離の算出結果が、実際の距離と異なる理由としては、次のような理由が挙げられる。すなわち、ノード８７，８９同士が直接エッジを介して接続されているにも関わらず、従来の装置では、ランドマーク８６と、ノード８７，８９のそれぞれとの距離の和がノード８７，８９間の距離として算出されてしまうという理由が挙げられる。
【００１４】
図２２Ａの例は、グラフデータ９０において、ランドマークノードとして選択されたノード９１に、ノード９２およびノード９３がエッジを介して接続された場合を示す。また、図２２Ａの例では、ノード９２とノード９３とが直接エッジを介して接続されている。また、図２２Ａの例では、ノード９２に、エッジを介してノード９４が接続されている。
【００１５】
図２２Ｂは、図２２Ａの場合における各ノード間の実際の距離を示す図である。図２２Ｂの例は、ノード９２とノード９３との距離が、「１」である場合を示す。また、図２２Ｂの例は、ノード９２とノード９１との距離が、「１」である場合を示す。また、図２２Ｂの例は、ノード９２とノード９４との距離が、「１」である場合を示す。また、図２２Ｂの例は、ノード９３とノード９１との距離が、「１」である場合を示す。また、図２２Ｂの例は、ノード９３とノード９４との距離が、「２」である場合を示す。また、図２２Ｂの例は、ノード９１とノード９４との距離が、「２」である場合を示す。
【００１６】
図２２Ｃは、図２２Ａの場合において、従来の装置によって算出された各ノード間の距離を示す図である。図２２Ｃの例に示すように、従来の装置は、ノード９２とノード９３との距離「２」を算出する。また、図２２Ｃの例に示すように、従来の装置は、ノード９２とノード９１との距離「１」を算出する。また、図２２Ｃの例に示すように、従来の装置は、ノード９２とノード９４との距離「３」を算出する。また、図２２Ｃの例に示すように、従来の装置は、ノード９３とノード９１との距離「１」を算出する。また、図２２Ｃの例に示すように、従来の装置は、ノード９３とノード９４との距離「３」を算出する。また、図２２Ｃの例に示すように、従来の装置は、ノード９１とノード９４との距離「２」を算出する。
【００１７】
すなわち、図２２Ａの例では、ノード９２，９３間、ノード９２，９４間、ノード９３，９４間の距離の算出結果が、実際の距離と異なる。このように、図２１Ａの例の場合に比べて図２２Ａの例の場合のほうが、従来の装置によって算出された距離が、実際の距離と異なる可能性が高くなる。この理由の一つについて説明する。図２２Ａの例では、ランドマークノード９１に接続されたノード９２，９３同士は、直接エッジを介して接続されている。そのため、ノード９２，９３間、ノード９２，９４間、ノード９３，９４間の実際の距離は、ランドマークノード９１を経由しない経路が示す距離となる。しかしながら、図２２Ａの例において、従来の装置は、ランドマークノード９１と、各ノードとの距離の和、すなわち、ランドマークノード９１を経由する経路が示す距離を各ノード間の距離として算出してしまう。このように、従来の装置では、ランドマークノードに接続されたノード同士が直接エッジを介して接続される場合には、算出される距離が、実際の距離と異なる可能性が高くなる。
【００１８】
例えば、図２３に示すように、ランドマークノードに接続されたノード同士が接続され、グラフ直径が小さい場合には、従来の装置により算出される距離が実際の距離と異なる可能性が高い。図２３の例では、従来の装置により算出される距離の正答率（正解数／ノードの全てのペアの数）は、約０．５１（６３０／１２２５）であり、半分程度にしかならない。なお、グラフ直径とは、グラフデータが示すグラフにおける全てのノード間の距離のうち、最大の距離を指す。また、図２３の例では、ノードが、「Ｎ」と表記され、ランドマークノードが「ＬＭ」と表記されている。
【００１９】
開示の技術は、上記に鑑みてなされたものであって、距離の算出結果の精度の低下を抑制することができる算出装置、算出プログラムおよび算出方法を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本願の開示する算出装置は、選択部と、第一の算出部と、第二の算出部と、第三の算出部とを有する。選択部は、複数のノードを有するグラフにおけるノード間の接続状態を示す情報に基づいて、複数のノードの中から、それぞれ複数のノードを有する複数のグループを選択する。第一の算出部は、選択部により選択された複数のグループのそれぞれについて、グループ内のノード間の平均距離を算出する。第二の算出部は、第一の算出部によりグループごとに算出されたグループ内のノード間の平均距離、および、ノード間の接続状態を示す情報に基づいて、グループのそれぞれと、複数のノードのそれぞれとの距離を算出する。第三の算出部は、第二の算出部により算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する。
【００２１】
また、本願の開示する算出装置は、選択部と、第一の算出部と、第二の算出部とを有する。選択部は、複数のノードを有するグラフにおけるノード間の接続状態を示す行列から複数の固有値、および、該複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出する。そして、選択部は、算出した複数の固有値および複数の固有ベクトルに基づいて、それぞれ複数のノードを有する複数のグループを選択する。第一の算出部は、固有値および固有ベクトルに基づいて、複数のグループのそれぞれと、複数のノードのそれぞれとの距離を算出する。第二の算出部は、第一の算出部により算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する。
【００２２】
また、本願の開示する算出装置は、第一の算出部と、第二の算出部とを有する。第一の算出部は、複数のノードを有するグラフにおけるノード間の接続状態を示す行列から複数の固有値、および、複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出する。第二の算出部は、複数の固有ベクトルごとに、距離の算出対象の２つのノードのそれぞれに対応する固有ベクトルの２つの成分の積と固有ベクトルに対応する固有値のｋ乗の値との積を算出する。そして、第二の算出部は、複数の固有ベクトルごとに算出した積の和を算出する。続いて、第二の算出部は、算出した和が、行列においてノード間が接続していることを示す値から所定値を減算した値を超える最小の前記ｋの値を、前記２つのノード間の距離として算出する。
【発明の効果】
【００２３】
本願の開示する算出装置の一つの態様によれば、距離の算出結果の精度の低下を抑制することができる。
【図面の簡単な説明】
【００２４】
【図１】図１は、実施例１に係る算出装置の機能構成の一例を示す図である。
【図２】図２は、隣接行列データのデータ構成の一例を示す図である。
【図３】図３は、距離情報のデータ構成の一例を示す図である。
【図４】図４は、実施例１に係る算出装置が実行する処理の一例を説明するための図である。
【図５】図５は、実施例１に係る算出装置が実行する処理の一例を説明するための図である。
【図６】図６は、実施例１に係る算出装置が実行する処理の一例を説明するための図である。
【図７】図７は、実施例１に係る距離情報算出処理の手順を示すフローチャートである。
【図８】図８は、実施例１に係る算出処理の手順を示すフローチャートである。
【図９】図９は、実施例２に係る算出装置の機能構成の一例を示す図である。
【図１０】図１０は、隣接行列の一例を示す図である。
【図１１Ａ】図１１Ａは、固有値および固有ベクトルの一例を示す図である。
【図１１Ｂ】図１１Ｂは、固有値の絶対値の平方根の逆数の一例を示す図である。
【図１２】図１２は、距離の算出方法の一例を説明するための図である。
【図１３】図１３は、実施例２に係る距離情報算出処理の手順を示すフローチャートである。
【図１４】図１４は、実施例３に係る算出装置の機能構成の一例を示す図である。
【図１５】図１５は、実施例３にかかる算出装置が実行する処理の一例を説明するための図である。
【図１６】図１６は、実施例３にかかる算出装置が実行する処理の一例を説明するための図である。
【図１７】図１７は、実施例３に係る行列情報算出処理の手順を示すフローチャートである。
【図１８】図１８は、実施例３に係る算出処理の手順を示すフローチャートである。
【図１９】図１９は、算出プログラムを実行するコンピュータを示す図である。
【図２０Ａ】図２０Ａは、従来の装置による距離の算出方法の一例を示す図である。
【図２０Ｂ】図２０Ｂは、従来の装置による距離の算出方法の一例を示す図である。
【図２０Ｃ】図２０Ｃは、従来の装置による距離の算出方法の一例を示す図である。
【図２１Ａ】図２１Ａは、従来の装置の問題点の一例を説明するための図である。
【図２１Ｂ】図２１Ｂは、従来の装置の問題点の一例を説明するための図である。
【図２１Ｃ】図２１Ｃは、従来の装置の問題点の一例を説明するための図である。
【図２２Ａ】図２２Ａは、従来の装置の問題点の一例を説明するための図である。
【図２２Ｂ】図２２Ｂは、従来の装置の問題点の一例を説明するための図である。
【図２２Ｃ】図２２Ｃは、従来の装置の問題点の一例を説明するための図である。
【図２３】図２３は、従来の装置の問題点の一例を説明するための図である。
【発明を実施するための形態】
【００２５】
以下に、本願の開示する算出装置、算出プログラムおよび算出方法の各実施例を図面に基づいて詳細に説明する。なお、実施例は開示の技術を限定するものではない。また、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００２６】
実施例１に係る算出装置について説明する。図１は、実施例１に係る算出装置の機能構成の一例を示す図である。
【００２７】
［算出装置の機能構成］
図１に示すように、算出装置１０は、入力部１１と、出力部１２と、通信部１３と、記憶部１４と、制御部１５とを有する。
【００２８】
入力部１１は、各種情報を制御部１５に入力する。例えば、入力部１１は、ユーザから、後述の算出処理を実行するための指示を受け付けて、受け付けた指示を制御部１５に入力する。なお、かかる指示には、距離の計算対象の２つのノード（ノードのペア）のＩＤ（ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）が含まれる。また、入力部１１は、ユーザから、後述の距離情報算出処理を実行するための指示を受け付けて、受け付けた指示を制御部１５に入力する。また、入力部１１は、ユーザから各種の指示を受け付けて、受け付けた指示を制御部１５へ入力する。また、入力部１１は、ユーザから、後述の隣接行列データ１４ｂを受け付けて、受け付けた隣接行列データ１４ｂを制御部１５に入力する。また、入力部１１は、ユーザから、隣接行列データ１４ｂを外部のサーバから取得する指示を受け付けて、受け付けた指示を制御部１５に入力する。入力部１１のデバイスの一例としては、マウスやキーボードなどのユーザの操作を受け付けるデバイスなどが挙げられる。
【００２９】
出力部１２は、各種の情報を出力する。例えば、出力部１２は、後述の出力制御部１５ｆの制御により、２つのノード間の距離を表示する。出力部１２のデバイスの一例としては、液晶ディスプレイなどが挙げられる。
【００３０】
通信部１３は、各装置間の通信を行うためのインターフェースである。例えば、通信部１３は、図示しないサーバに接続される。かかるサーバの一例としては、後述の隣接行列データ１４ｂを算出装置１０に送信する指示を受信した場合に、隣接行列データ１４ｂを算出装置１０に送信するサーバが挙げられる。また、通信部１３は、サーバから隣接行列データ１４ｂを受信した場合には、受信した隣接行列データ１４ｂを制御部１５へ送信する。
【００３１】
記憶部１４は、各種情報を記憶する。例えば、記憶部１４は、隣接行列データ１４ｂ、距離情報１４ｂを記憶する。
【００３２】
隣接行列データ１４ｂは、複数のノードを有するグラフにおけるノード間の接続状態を示すグラフデータの一例である。隣接行列データ１４ｂが示す隣接行列は、エッジを介して直接接続されている２つのノード間に対応する成分の値として、２つのノードが接続されていることを示す値を有する行列である。また、隣接行列は、接続されていないノード間に対応する成分の値として、２つのノードが接続されていないことを示す値を有する行列である。図２は、隣接行列データのデータ構成の一例を示す図である。以下の説明では、ノードを、「Ｎ」と表記する場合がある。図２中左側に示すように、Ｎ１に、Ｎ２、Ｎ３、Ｎ４が接続され、Ｎ２に、Ｎ１、Ｎ４が接続され、Ｎ３に、Ｎ１が接続され、Ｎ４に、Ｎ１、Ｎ２が接続されるようなグラフの場合における隣接行列データ１４ｂについて説明する。かかるグラフの場合には、図２中右側に示す隣接行列データ１４ｂが示す隣接行列は、Ｎ１とＮ２、Ｎ１とＮ３およびＮ１とＮ４の各ノード間の成分の値として、２つのノードが接続されていることを示す値、例えば、「１」を有する。また、図２中右側に示す隣接行列データ１４ｂが示す隣接行列は、Ｎ２とＮ４のノード間の成分の値として、２つのノードが接続されていることを示す値、例えば、「１」を有する。なお、図２中右側には、隣接行列データ１４ｂが示す隣接行列が、同一のノード間（Ｎ１とＮ１、Ｎ２とＮ２、Ｎ３とＮ３、Ｎ４とＮ４）の成分の値として、「１」を有する場合が示されている。
【００３３】
距離情報１４ｂは、後述の各ランドマークノードグループと各ノードとの距離を示す情報である。距離情報１４ｂは、後述の第二の算出部１５ｄにより算出される。図３は、距離情報のデータ構成の一例を示す図である。以下の説明では、後述のランドマークノードグループを、「ＬＭＧ」と表記する場合がある。図３の例では、距離情報１４ｂが、Ｎ１とＬＭＧ１との距離が「０．７」であることを示す場合が示されている。また、図３の例では、距離情報１４ｂが、Ｎ１とＬＭＧ２との距離が「１．７」であることを示す場合が示されている。
【００３４】
記憶部１４は、例えば、フラッシュメモリなどの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部１４は、上記の種類の記憶装置に限定されるものではなく、ＲＡＭ（Random  Access  Memory)、ＲＯＭ（Read  Only  Memory)であってもよい。
【００３５】
制御部１５は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。図１に示すように、制御部１５は、取得部１５ａと、選択部１５ｂと、第一の算出部１５ｃと、第二の算出部１５ｄと、第三の算出部１５ｅと、出力制御部１５ｆとを有する。
【００３６】
取得部１５ａは、隣接行列データ１４ｂを取得する。例えば、取得部１５ａは、入力部１１から隣接行列データ１４ｂが入力された場合には、入力された隣接行列データ１４ｂを取得し、取得した隣接行列データ１４ｂを記憶部１４に格納する。また、取得部１５ａは、入力部１１から、隣接行列データ１４ｂを外部のサーバから取得する指示が入力された場合には、隣接行列データ１４ｂを算出装置１０に送信する指示を通信部１３へ送信する。また、取得部１５ａは、通信部１３から隣接行列データ１４ｂを受信した場合には、受信した隣接行列データ１４ｂを取得し、取得した隣接行列データ１４ｂを記憶部１４に格納する。
【００３７】
選択部１５ｂは、各種情報を選択する。例えば、選択部１５ｂは、複数のノードを有するグラフにおけるノード間の接続状態を示す隣接行列データ１４ｂに基づいて、複数のノードの中から、それぞれ複数のノードを有する複数のランドマークノードグループを選択する。
【００３８】
具体例を挙げて説明すると、選択部１５ｂは、まず、記憶部１４から、隣接行列データ１４ｂを取得する。そして、選択部１５ｂは、「Fast  Shortest  Path  Distance  Estimation  in  Large  Networks」などに記載されているような公知の技術を用いて、所定個のランドマークノードを選択する。例えば、選択部１５ｂは、隣接行列データ１４ｂが示すグラフにおけるノード間の隣接状態から、各ノードに接続されているノード数を計数し、接続されているノード数が多い順に、次のような処理を行う。すなわち、選択部１５ｂは、接続されているノード数が最も多いノードから所定個のノードをランドマークノードとして選択する。図４は、実施例１に係る算出装置が実行する処理の一例を説明するための図である。図４が示すグラフの例では、選択部１５ｂは、接続されているノード数の多さが上位５個のノード、すなわち、接続されているノード数が「９」であるＮ８、Ｎ１８、Ｎ２８、Ｎ３８、Ｎ４８の５つのノードをランドマークノードとして選択する。
【００３９】
次に、選択部１５ｂは、ランドマークノードから所定の距離に位置するノードおよび当該ランドマークノードのグループを、ランドマークノードグループとして選択する。図４のグラフが示す例では、選択部１５ｂは、Ｎ８から距離が「１」のＮ１〜Ｎ７、Ｎ９、Ｎ１０の各ノードを特定し、特定したＮ１〜Ｎ７、Ｎ９、Ｎ１０と、ランドマークノードであるＮ８のグループを、ＬＭＧ１として決定することにより、ランドマークノードグループを選択する。同様に、図４のグラフが示す例では、選択部１５ｂは、ＬＭＧ２〜ＬＭＧ５を選択する。すなわち、図４のグラフが示す例では、選択部１５ｂは、５つのランドマークノードグループを選択する。
【００４０】
第一の算出部１５ｃは、選択部１５ｂにより選択された複数のランドマークノードグループのそれぞれについて、ランドマークノードグループ内のノード間の平均距離を算出する。具体例について説明すると、第一の算出部１５ｃは、選択部１５ｂにより選択された複数のランドマークノードグループのうち、第一の算出部１５ｃによって選択されていないランドマークノードグループ（未選択のランドマークノードグループ）を１つ選択する。そして、第一の算出部１５ｃは、選択したランドマークノードグループ内の全てのノード間について、距離を算出する。そして、第一の算出部１５ｃは、算出した全てのノード間の距離の和を算出し、算出した和を、選択したランドマークノードグループ内の全てのノード間の組み合わせの個数で除することにより、ランドマークノードグループ内のノード間の距離の平均値を算出する。なお、この距離の平均値が、平均距離である。このようにして、第一の算出部１５ｃは、ノード間の平均距離を全てのランドマークノードグループについて算出する。例えば、図４のグラフが示す例では、第一の算出部１５ｃは、ＬＭＧ１について、ノード間の平均距離「１．４」を算出する。
【００４１】
第二の算出部１５ｄは、第一の算出部１５ｃによりランドマークノードグループごとに算出されたランドマークノードグループ内のノード間の平均距離、および、隣接行列データ１４ｂに基づいて、次のような処理を行う。すなわち、第二の算出部１５ｄは、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を算出する。
【００４２】
具体例を挙げて説明する。第二の算出部１５ｄは、ランドマークノードグループと、当該ランドマークノードグループ内のノードとの距離を、当該ランドマークノードグループについて、第一の算出部１５ｃにより算出されたノード間の平均距離を所定値で割った値とする。図５は、実施例１に係る算出装置が実行する処理の一例を説明するための図である。図５の例は、図４のグラフが示す例におけるＬＭＧ１、および、ＬＭＧ１内のＮ１に接続されたＮ１１を示す。図５のグラフが示す例では、第二の算出部１５ｄは、ＬＭＧ１と、ＬＭＧ１内のＮ１〜Ｎ１０のそれぞれとの距離を次のように算出する。すなわち、第二の算出部１５ｄは、ＬＭＧ１について第一の算出部１５ｃにより算出されたノード間の平均距離「１．４」を「２」で割った値「０．７」を、ＬＭＧ１と、ＬＭＧ１内のＮ１〜Ｎ１０のそれぞれとの距離として算出する。
【００４３】
また、第二の算出部１５ｄは、ランドマークノードグループと、当該ランドマークノードグループに属さないノードとの距離を、次のように算出する。すなわち、第二の算出部１５ｄは、まず、当該ランドマークノードグループ内のノードであって、当該ランドマークノードグループに属さないノードに最も近いノードを特定する。そして、第二の算出部１５ｄは、当該ランドマークノードグループについて第一の算出部１５ｃにより算出されたノード間の平均距離を所定値で割った値に、当該ランドマークに属さない上記のノードと特定したノードとの距離を加算した値を算出する。このようにして、第二の算出部１５ｄは、ランドマークノードグループと、当該ランドマークノードグループに属さないノードとの距離を算出する。図５のグラフが示す例では、第二の算出部１５ｄは、ＬＭＧ１と、ＬＭＧ１に属さないＮ１１との距離を次のように算出する。すなわち、第二の算出部１５ｄは、まず、ＬＭＧ１内のノードであって、ＬＭＧ１に属さないＮ１１に最も近いＮ１を特定する。そして、第二の算出部１５ｄは、ＬＭＧ１について第一の算出部１５ｃにより算出されたノード間の平均距離「１．４」を「２」で割った値「０．７」に、ＬＭＧ１に属さないＮ１１と特定したノードＮ１との距離「１」を加算した値「１．７」を算出する。このようにして、第二の算出部１５ｄは、ＬＭＧ１と、ＬＭＧ１に属さないＮ１１との距離を算出する。
【００４４】
また、第二の算出部１５ｄは、上述した方法と同様の方法で、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を算出する。そして、第二の算出部１５ｄは、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を示す情報である距離情報１４ｂを記憶部１４に格納する。
【００４５】
第三の算出部１５ｅは、第二の算出部１５ｄにより算出された距離に基づいて、距離の算出対象の２つのノード間の距離を算出する。具体例について説明する。入力部１１から、算出処理を実行するための指示が入力されると、第三の算出部１５ｅは、まず、指示に含まれる、距離の計算対象の２つのノード（ノードのペア）のＩＤから、２つのノードを特定する。以下、特定された２つのノードが、ＮＡ，ＮＢである場合について説明する。そして、第三の算出部１５ｅは、記憶部１４から距離情報１４ｂを取得する。
【００４６】
次に、第三の算出部１５ｅは、未選択のランドマークノードグループを１つ選択する。そして、第三の算出部１５ｅは、取得した距離情報１４ｂを参照し、ノードＮＡと選択したランドマークノードグループとの距離「ＤＡ」を特定する。また、第三の算出部１５ｅは、取得した距離情報１４ｂを参照し、ノードＮＢと選択したランドマークノードグループとの距離「ＤＢ」を特定する。その後、第三の算出部１５ｅは、距離「ＤＡ」と距離「ＤＢ」との和「ＤＡ＋ＤＢ」を距離の候補として算出する。第三の算出部１５ｅは、全てのランドマークノードグループについて順番に１つずつ選択し、同様の処理を行って、全てのランドマークノードグループについて、距離の候補を算出する。
【００４７】
図６は、実施例１に係る算出装置が実行する処理の一例を説明するための図である。図６を参照して、入力された指示に含まれる２つのノードのＩＤから、Ｎ２およびＮ１２が特定され、図３の例に示す距離情報１４ｂを用いて、Ｎ２とＮ１２との距離を算出する場合について説明する。図６の例に示すように、第三の算出部１５ｅは、ＬＭＧ１とＮ２との距離「０．７」と、ＬＭＧ１とＮ１２との距離「２．７」との和「３．４」を、Ｎ２とＮ１２との距離の候補として算出する。また、図６の例に示すように、第三の算出部１５ｅは、ＬＭＧ２とＮ２との距離「２．７」と、ＬＭＧ２とＮ１２との距離「０．７」との和「３．４」を、Ｎ２とＮ１２との距離の候補として算出する。また、図６の例に示すように、第三の算出部１５ｅは、ＬＭＧ３とＮ２との距離「１．７」と、ＬＭＧ３とＮ１２との距離「１．７」との和「３．４」を、Ｎ２とＮ１２との距離の候補として算出する。また、図６の例に示すように、第三の算出部１５ｅは、ＬＭＧ４とＮ２との距離「２．７」と、ＬＭＧ４とＮ１２との距離「２．７」との和「５．４」を、Ｎ２とＮ１２との距離の候補として算出する。また、図６の例に示すように、第三の算出部１５ｅは、ＬＭＧ５とＮ２との距離「２．７」と、ＬＭＧ５とＮ１２との距離「２．７」との和「５．４」を、Ｎ２とＮ１２との距離の候補として算出する。
【００４８】
その後、第三の算出部１５ｅは、算出した距離の候補のうち、最も距離が短い候補を選択する。例えば、図６の例では、最も距離が短い候補として、距離の候補「３．４」を選択する。続いて、第三の算出部１５ｅは、選択した候補を、小数第一位で四捨五入した値を、距離の計算対象の２つのノード間の距離として算出する。例えば、図６の例では、第三の算出部１５ｅは、選択した距離の候補「３．４」を、小数第一位で四捨五入した値「３」を、Ｎ２、Ｎ１２間の距離として算出する。なお、第三の算出部１５ｅは、選択した距離の候補を、そのまま、距離の計算対象の２つのノード間の距離として算出することもできる。
【００４９】
出力制御部１５ｆは、第三の算出部１５ｅにより算出された２つのノード間の距離を表示するように、出力部１２による表示を制御する。
【００５０】
上述してきたように、制御部１５は、各ランドマークノードグループについてノード間の平均距離を算出し、算出したノード間の平均距離を用いて、各ランドマークノードグループと、全ノードとの距離を算出し、算出した距離を含む距離情報１４ｂを記憶させる。そして、制御部１５ｂは、距離情報１４ｂを参照して、２つのノード間の距離を算出する。このように、ノード間の距離を算出する際に用いられる距離情報１４ｂが、ノード間の平均距離によって算出されるので、従来のランドマークノードと、全ノードとの距離を用いてノード間の距離を算出する場合と比較して、距離の算出結果の精度が良好となる。したがって、制御部１５によれば、距離の算出結果の精度の低下を抑制することができる。
【００５１】
制御部１５は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路である。
【００５２】
［処理の流れ］
次に、本実施例に係る算出装置１０の処理の流れについて説明する。図７は、実施例１に係る距離情報算出処理の手順を示すフローチャートである。距離情報算出処理は、例えば、入力部１１から、距離情報算出処理を実行するための指示を制御部１５が受け付けたタイミングで、実行される。
【００５３】
図７に示すように、選択部１５ｂは、記憶部１４から、隣接行列データ１４ｂを取得する（Ｓ１０１）。そして、選択部１５ｂは、所定数のランドマークノードを選択し、選択した所定数のランドマークノードのそれぞれについて、次のような処理を行う。すなわち、選択部１５ｂは、当該ランドマークノードから所定の距離に位置するノードおよび当該ランドマークノードのグループを、ランドマークノードグループとして選択する（Ｓ１０２）。
【００５４】
続いて、第一の算出部１５ｃは、選択部１５ｂにより選択された複数のランドマークノードグループのうち、後述のＳ１０４で未選択のランドマークノードグループがあるか否かを判定する（Ｓ１０３）。未選択のランドマークノードグループがある場合（Ｓ１０３肯定）には、第一の算出部１５ｃは、未選択のランドマークノードグループを１つ選択する（Ｓ１０４）。そして、第一の算出部１５ｃは、選択したランドマークノードグループ内の全てのノード間について、距離を算出し、算出した全てのノード間の距離の和を算出し、その後、次のような処理を行う。すなわち、第一の算出部１５ｃは、算出した和を、選択したランドマークノードグループ内の全てのノード間の組み合わせの個数で除することにより、ランドマークノードグループ内のノード間の距離の平均値（平均距離）を算出する（Ｓ１０５）。
【００５５】
そして、第二の算出部１５ｄは、第一の算出部１５ｃによりランドマークノードグループごとに算出されたランドマークノードグループ内のノード間の平均距離、および、隣接行列データ１４ｂに基づいて、次のような処理を行う。すなわち、第二の算出部１５ｄは、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を算出し（Ｓ１０６）、Ｓ１０３へ戻る。
【００５６】
一方、未選択のランドマークノードグループがない場合（Ｓ１０３否定）には、第二の算出部１５ｄは、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を示す情報である距離情報１４ｂを記憶部１４に格納し（Ｓ１０７）、処理を終了する。
【００５７】
図８は、実施例１に係る算出処理の手順を示すフローチャートである。算出処理は、例えば、入力部１１から、算出処理を実行するための指示を制御部１５が受け付けたタイミングで、実行される。
【００５８】
図８に示すように、第三の算出部１５ｅは、算出処理を実行するための指示に含まれる、距離の計算対象の２つのノードのＩＤから、２つのノードＮＡ，ＮＢを特定する（Ｓ２０１）。そして、第三の算出部１５ｅは、記憶部１４から距離情報１４ｂを取得する（Ｓ２０２）。
【００５９】
次に、第三の算出部１５ｅは、後述のＳ２０４で未選択のランドマークノードグループがあるか否かを判定する（Ｓ２０３）。未選択のランドマークノードグループを１つ選択する（Ｓ２０４）。そして、第三の算出部１５ｅは、取得した距離情報１４ｂを参照し、ノードＮＡと選択したランドマークノードグループとの距離「ＤＡ」を特定する（Ｓ２０５）。続いて、第三の算出部１５ｅは、取得した距離情報１４ｂを参照し、ノードＮＢと選択したランドマークノードグループとの距離「ＤＢ」を特定する（Ｓ２０６）。その後、第三の算出部１５ｅは、距離「ＤＡ」と距離「ＤＢ」との和「ＤＡ＋ＤＢ」を距離の候補として算出し（Ｓ２０７）、Ｓ２０３へ戻る。
【００６０】
その後、第三の算出部１５ｅは、算出した距離の候補のうち、最も距離が短い候補を選択する（Ｓ２０８）。続いて、第三の算出部１５ｅは、選択した候補を、小数第一位で四捨五入した値を、距離の計算対象の２つのノード間の距離として算出する（Ｓ２０９）。
【００６１】
そして、出力制御部１５ｆは、第三の算出部１５ｅにより算出された２つのノード間の距離を表示するように、出力部１２による表示を制御し（Ｓ２１０）、処理を終了する。
【００６２】
上述してきたように、本実施例に係る算出装置１０は、複数のノードを有するグラフにおけるノード間の接続状態を示す隣接行列データ１４ｂに基づいて、複数のノードの中から、それぞれ複数のノードを有する複数のランドマークノードグループを選択する。そして、算出装置１０は、選択された複数のランドマークノードグループのそれぞれについて、ランドマークノードグループ内のノード間の平均距離を算出する。続いて、算出装置１０は、ランドマークノードグループ内のノード間の平均距離、および、隣接行列データ１４ｂに基づいて、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を示す距離情報１４ｂ算出する。その後、算出装置１０は、算出された距離情報１４ｂに基づいて、距離の算出対象の２つのノード間の距離を算出する。このように、ノード間の距離を算出する際に用いられる距離情報１４ｂが、ノード間の平均距離によって算出されるので、従来のランドマークノードと、全ノードとの距離を用いてノード間の距離を算出する場合と比較して、距離の算出結果の精度が良好となる。したがって、算出装置１０によれば、距離の算出結果の精度の低下を抑制することができる。
【実施例２】
【００６３】
実施例２では、隣接行列の固有値および固有ベクトルを算出し、算出した固有値および固有ベクトルに基づいて、２つのノード間の距離を算出する場合について説明する。
【００６４】
［算出装置２０の構成］
図９は、実施例２に係る算出装置の機能構成の一例を示す図である。図９に示すように、算出装置２０は、記憶部２４および制御部２５を有する。記憶部２４は、図１に示す実施例１に係る記憶部１４の記憶内容に加えて、固有値データ２４ａおよび固有ベクトルデータ２４ｂを記憶する点が実施例１に係る記憶部１４と異なる。固有値データ２４ａおよび固有ベクトルデータ２４ｂについては、後述する。また、制御部２５は、図１に示す実施例１に係る制御部１５と比較して、選択部２５ａ、第一の算出部２５ｂ、第二の算出部２５ｃ、出力制御部２５ｄを有する点が異なる。なお、以下では、上記の実施例１と同様の機能を果たす各部や機器については図１と同様の符号を付し、その説明は省略することとする。
【００６５】
選択部２５ａは、隣接行列データ１４ｂが示す隣接行列から複数の固有値、および、複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出し、算出した複数の固有値および複数の固有ベクトルに基づいて、ランドマークノードグループを選択する。
【００６６】
具体例について説明すると、選択部２５ａは、まず、記憶部１４から、隣接行列データ１４ｂを取得する。そして、選択部２５ａは、隣接行列データ１４ｂが示す隣接行列の固有値を算出する。図１０は、隣接行列の一例を示す図である。図１０には、Ｎ１〜Ｎ５０の５０個のノード間の接続状態を示す隣接行列が示されている。例えば、選択部２５ａは、図１０の例の隣接行列を示す隣接行列データ１４ｂを取得した場合に、隣接行列の固有ベクトルが重複しないときには、５０個の固有値を算出する。そして、選択部２５ａは、算出した固有値の中から、絶対値が大きい順に、最も大きい固有値から所定数個までの固有値を特定し、特定した固有値のデータを固有値データ２４ａとして記憶部２４に格納する。例えば、選択部２５ａは、上位５個の固有値を特定する。図１１Ａは、固有値および固有ベクトルの一例を示す図である。図１１Ａの例は、選択部２５ａが、算出した固有値の中から、絶対値が大きい上位５個の固有値を特定した場合を示す。なお、下記の説明では、選択部２５ａが、絶対値が大きい上位５個の固有値を特定する場合について説明する。また、図１１Ａの例は、上位５個の固有値の値が全て「１０」である場合を示す。
【００６７】
そして、選択部２５ａは、固有値を特定すると、次のような処理を行う。すなわち、選択部２５ａは、まず、変数ｎの値を０に設定する。そして、選択部２５ａは、上位５個の固有値のうち、未選択の固有値があるか否かを判定する。未選択の固有値がある場合には、選択部２５ａは、変数ｎの値を１つインクリメントする。その後、選択部２５ａは、未選択の１つの固有値を固有値Ｅｎとして選択する。図１１Ａの例では、選択部２５ａが、まず、未選択の１つの固有値「１０」を固有値Ｅ１として選択した場合が示されている。
【００６８】
続いて、選択部２５ａは、選択した固有値Ｅｎに対応する固有ベクトルＶｎを算出し、算出した固有ベクトルのデータを固有ベクトルデータ２４ｂとして記憶部２４に格納する。図１１Ａの例では、選択部２５ａが、選択した固有値Ｅ１に対応する固有ベクトルＶｎを算出した場合が示されている。続いて、選択部２５ａは、絶対値が、固有値Ｅｎの絶対値の平方根の逆数（１／（Ｅｎ）１／２）より大きい固有ベクトルＶｎの成分を特定する。図１１Ｂは、固有値の絶対値の平方根の逆数の一例を示す図である。図１１Ｂの例は、固有値Ｅ１〜Ｅ５の各値が「１０」である場合に、各固有値の絶対値の平方根の逆数が、ほぼ「０．３」であることを示す。すなわち、図１１Ａの例において、選択部２５ａは、絶対値が、固有値Ｅ１の絶対値の平方根の逆数「０．３」より大きい固有ベクトルＶ１の成分として、Ｎ１に対応する「０．３４」を特定する。また、選択部２５ａは、絶対値が、固有値Ｅ１の絶対値の平方根の逆数「０．３」より大きい固有ベクトルＶ１の成分として、Ｎ２に対応する「０．３４」を特定する。また、選択部２５ａは、絶対値が、固有値Ｅ１の絶対値の平方根の逆数「０．３」より大きい固有ベクトルＶ１の成分として、Ｎ３に対応する「０．３５」を特定する。また、選択部２５ａは、絶対値が、固有値Ｅ１の絶対値の平方根の逆数「０．３」より大きい固有ベクトルＶ１の成分として、Ｎ４に対応する「０．３４」を特定する。
【００６９】
そして、選択部２５ａは、特定した成分に対応するノードの集合を、ランドマークノードグループＧｎとして選択する。例えば、図１１Ａの例では、選択部２５ａは、Ｎ１〜Ｎ４のノードの集合を、ランドマークノードグループＧ１として選択する。これにより、いわゆる「密」になっているノード同士をランドマークノードグループとして選択することできる。なお、ここでいう「密になっているノード同士」とは、互いに、接続されているエッジ数が多いノード群を指す。
【００７０】
第一の算出部２５ｂは、固有値および固有ベクトルに基づいて、複数のランドマークノードグループのそれぞれと、複数のノードのそれぞれとの距離を算出する。具体例について説明する。第一の算出部２５ｂは、選択部２５ａにより選択されたランドマークノードグループＧｎと、全てのノードのそれぞれとの距離を次のようにして算出する。すなわち、第一の算出部２５ｂは、固有ベクトルＶ１のノードの成分の絶対値についてＥｎの絶対値を底とする対数をとった値に、マイナス「−」を掛けた値を、ランドマークノードグループＧｎとノードとの距離として算出する。図１２は、距離の算出方法の一例を説明するための図である。図１２の例では、第一の算出部２５ｂが、固有ベクトルＶ２のＮ１の成分の絶対値についてＥ２の絶対値「１０」を底とする対数をとった値に、マイナス「−」を掛けた値を、ランドマークノードグループＧ２とＮ１との距離として算出する。このようにして、第一の算出部２５ｂは、選択部２５ａにより選択されたランドマークノードグループＧｎと、全てのノードのそれぞれとの距離を算出する。そして、第一の算出部２５ｂは、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を示す情報である距離情報１４ｂを記憶部２４に格納する。なお、実施例２において、第一の算出部２５ｂに代えて、実施例１に係る第一の算出部１５ｃおよび第二の算出部１５ｄを採用して、実施例１と同様に、選択されたランドマークノードグループＧｎと、全てのノードのそれぞれとの距離を算出することもできる。
【００７１】
第二の算出部２５ｃ、出力制御部２５ｄについては、それぞれ、実施例１に係る第三の算出部１５ｅ、出力制御部１５ｆと同様であるため、説明を省略する。
【００７２】
制御部２５は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路である。
【００７３】
［処理の流れ］
次に、本実施例に係る算出装置２０の処理の流れについて説明する。図１３は、実施例２に係る距離情報算出処理の手順を示すフローチャートである。距離情報算出処理は、例えば、入力部１１から、距離情報算出処理を実行するための指示を制御部２５が受け付けたタイミングで、実行される。
【００７４】
図１３に示すように、選択部２５ａは、記憶部１４から、隣接行列データ１４ｂを取得する（Ｓ３０１）。そして、選択部２５ａは、隣接行列データ１４ｂが示す隣接行列の固有値を算出する（Ｓ３０２）。そして、選択部２５ａは、算出した固有値の中から、絶対値が大きい上位５個の固有値を特定し、特定した固有値のデータを固有値データ２４ａとして記憶部２４に格納する（Ｓ３０３）。そして、選択部２５ａは、変数ｎの値を０に設定する（Ｓ３０４）。
【００７５】
そして、選択部２５ａは、上位５個の固有値のうち、未選択の固有値があるか否かを判定する（Ｓ３０５）。未選択の固有値がある場合（Ｓ３０５肯定）には、選択部２５ａは、変数ｎの値を１つインクリメントする（Ｓ３０６）。その後、選択部２５ａは、未選択の１つの固有値を固有値Ｅｎとして選択する（Ｓ３０７）。
【００７６】
続いて、選択部２５ａは、選択した固有値Ｅｎに対応する固有ベクトルＶｎを算出し、算出した固有ベクトルのデータを固有ベクトルデータ２４ｂとして記憶部２４に格納する（Ｓ３０８）。続いて、選択部２５ａは、絶対値が、固有値Ｅｎの絶対値の平方根の逆数（１／（Ｅｎ）１／２）より大きい固有ベクトルＶｎの成分を特定する（Ｓ３０９）。
【００７７】
そして、選択部２５ａは、特定した成分に対応するノードの集合を、ランドマークノードグループＧｎとして選択する（Ｓ３１０）。続いて、第一の算出部２５ｂは、固有ベクトルＶ１のノードの成分の絶対値についてＥｎの絶対値を底とする対数をとった値に、マイナス「−」を掛けた値を、ランドマークノードグループＧｎとノードとの距離として算出する処理を、全ノードに対して行う（Ｓ３１１）。そして、Ｓ３０５に戻る。
【００７８】
ここで、未選択の固有値がない場合（Ｓ３０５否定）には、第一の算出部２５ｂは、ランドマークノードグループのそれぞれと、全ノードのそれぞれとの距離を示す情報である距離情報１４ｂを記憶部２４に格納し（Ｓ３１２）、処理を終了する。
【００７９】
なお、算出処理については、実施例１と同様であるため、説明を省略する。
【００８０】
上述してきたように、本実施例に係る算出装置２０は、隣接行列データ１４ｂが示す隣接行列から複数の固有値、および、複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出する。そして、算出装置２０は、算出した複数の固有値および複数の固有ベクトルに基づいて、ランドマークノードグループを選択する。そして、算出装置２０は、固有値および固有ベクトルに基づいて、複数のランドマークノードグループのそれぞれと、複数のノードのそれぞれとの距離を示す距離情報１４ｂを算出する。その後、算出装置２０は、算出された距離情報１４ｂに基づいて、距離の算出対象の２つのノード間の距離を算出する。このように、ノード間の距離を算出する際に用いられる距離情報１４ｂが、「密」になったノード同士を有するランドマークノードグループごとに算出されるので、距離の算出結果の精度がさらに良好となる。したがって、算出装置２０によれば、距離の算出結果の精度の低下を抑制することができる。
【実施例３】
【００８１】
実施例２では、ランドマークノードグループを選択したが、実施例３では、ランドマークノードグループを選択せずに、２つのノード間の距離を算出する場合について説明する。
【００８２】
［算出装置３０の構成］
図１４は、実施例３に係る算出装置の機能構成の一例を示す図である。図１４に示すように、算出装置３０は、記憶部３４および制御部３５を有する。記憶部３４は、図９に示す実施例２に係る記憶部２４の記憶内容のうち、隣接行列データ１４ｂ、固有値データ２４ａおよび固有ベクトルデータ２４ｂを記憶する点が実施例２に係る記憶部２４と異なる。また、制御部３５は、図９に示す実施例２に係る制御部２５と比較して、第一の算出部３５ａ、第二の算出部３５ｂ、出力制御部３５ｃを有する点が異なる。なお、以下では、上記の実施例１、２と同様の機能を果たす各部や機器については図１、図９と同様の符号を付し、その説明は省略することとする。
【００８３】
第一の算出部３５ａは、隣接行列データ１４ｂが示す隣接行列から複数の固有値、および、複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出する。
【００８４】
具体例について説明すると、第一の算出部３５ａは、まず、記憶部３４から、隣接行列データ１４ｂを取得する。そして、第一の算出部３５ａは、隣接行列データ１４ｂが示す隣接行列の固有値を算出する。そして、第一の算出部３５ａは、算出した固有値の中から、絶対値が大きい順に、最も大きい固有値から所定数個までの固有値を特定する。例えば、第一の算出部３５ａは、上位５個の固有値を特定する。なお、下記の説明では、第一の算出部３５ａが、絶対値が大きい上位５個の固有値を特定する場合について説明する。
【００８５】
そして、第一の算出部３５ａは、固有値を特定すると、次のような処理を行う。すなわち、第一の算出部３５ａは、まず、変数ｎの値を０に設定する。そして、第一の算出部３５ａは、上位５個の固有値のうち、未選択の固有値があるか否かを判定する。未選択の固有値がある場合には、第一の算出部３５ａは、変数ｎの値を１つインクリメントする。その後、第一の算出部３５ａは、未選択の１つの固有値を固有値Ｅｎとして選択する。
【００８６】
続いて、第一の算出部３５ａは、選択した固有値Ｅｎに対応する固有ベクトルＶｎを算出する。そして、第一の算出部３５ａは、再び、上位５個の固有値のうち、未選択の固有値があるか否かを判定する。第一の算出部３５ａは、未選択の固有値がないと判定するまで、変数ｎの値を１つインクリメントし、未選択の固有値Ｅｎを選択し、選択した固有値Ｅｎに対応する固有ベクトルＶｎを算出する処理を繰り返し行う。
【００８７】
そして、未選択の固有値がないと判定した場合には、第一の算出部３５ａは、次のような処理を行う。すなわち、第一の算出部３５ａは、固有ベクトルＶｎ（ｎ＝１、２、・・・５）のデータを固有ベクトルデータ２４ｂとして記憶部３４に格納し、固有値Ｅｎ（ｎ＝１、２、・・・５）のデータを固有値データ２４ａとして記憶部３４に格納する。
【００８８】
第二の算出部３５ｂは、複数の固有ベクトルＶｎ（ｎ＝１、２、・・・５）ごとに、距離の算出対象の２つのノードのそれぞれに対応する固有ベクトルＶｎの２つの成分の積と、固有ベクトルＶｎに対応する固有値Ｅｎのｋ乗の値との積を算出する。そして、第二の算出部３５ｂは、複数の固有ベクトルＶｎごとに算出した積の値の総和を算出する。続いて、第二の算出部３５ｂは、算出した総和が、隣接行列においてノード間が接続していることを示す値「１」から所定値「α」を減算した値「１−α」を超える最小のｋの値を、２つのノード間の距離として算出する。
【００８９】
具体例について説明する。入力部１１から、算出処理を実行するための指示が入力されると、第二の算出部３５ｂは、まず、指示に含まれる、距離の計算対象の２つのノード（ノードのペア）のＩＤから、２つのノードを特定する。以下、特定された２つのノードが、ＮＡ，ＮＢである場合について説明する。そして、第二の算出部３５ｂは、記憶部３４から固有ベクトルデータ２４ｂ、固有値データ２４ａを取得する。次に、第二の算出部３５ｂは、変数ｋの値を０に設定する。
【００９０】
その後、第二の算出部３５ｂは、変数ｋの値を１つインクリメントする。そして、第二の算出部３５ｂは、次の式によって、「Ｊ」の値を算出する。
【数１】
0005831274.tif 000002
【００９１】
ここで、隣接行列を「Ａ」、隣接行列Ａの固有ベクトルを列方向に並べた行列を「Ｐ」、行列Ｐの逆行列を「Ｐ−１」、Ｐ−１ＡＰ＝Ｗとすると、行列Ｗは、対角成分に固有値を有し、他の成分が「０」となる行列である。また、Ａ＝ＰＷＰ−１であることから、Ａｋ＝ＰＷｋＰ−１である。さらに、Ａｋが示す行列において、２つのノード間の接続状態を示す成分が、「１」以上となるときのｋの値が、２つのノード間の距離を示すため、上記の式は、Ａｋの近似式である。
【００９２】
図１５および図１６は、実施例３にかかる算出装置が実行する処理の一例を説明するための図である。図１５の例は、第二の算出部３５ｂが、算出処理を実行するための指示に含まれる、距離の計算対象の２つのノードのＩＤから、Ｎ１、Ｎ２５を特定した場合を示す。また、図１５の例は、第二の算出部３５ｂが取得した固有ベクトルデータ２４ｂが示す固有ベクトルの成分のうち、固有ベクトルＶ１〜Ｖ５のそれぞれにおける、Ｎ１、Ｎ２５の成分を示す。また、図１５の例は、第二の算出部３５ｂが取得した固有値データ２４ａが示す固有値Ｅ１〜Ｅ５のそれぞれが、「１０」である場合を示す。図１５の例において、ｋ＝１の場合、第二の算出部３５ｂは、図１６中、一番上の式が示す計算を行う。このとき、Ｊの値は、０．０１である。
【００９３】
そして、第二の算出部３５ｂは、Ｊの値が、「１−α」以上であるか否かを判定する。ここで、「１」は、隣接行列においてノード間が接続していることを示す値である。また、「１」ではなく、「１−α」とＪとを比較している理由は、上記の式がＡｋの近似式であり、行列Ｗの対角成分には、第一の算出部３５ａにより特定された所定個（本実施例では５個）の固有値以外の固有値も含まれているからである。
【００９４】
Ｊの値が、「１−α」以上でない場合には、第二の算出部３５ｂは、ｋの値を１つインクリメントして、再び、上記の式を用いて、Ｊの値を算出し、算出したＪの値が、「１−α」以上であるか否かを判定する。このように、第二の算出部３５ｂは、算出したＪの値が、「１−α」以上となるまで、ｋの値を１つインクリメントし、上記の式によってＪを算出する処理を繰り返す。
【００９５】
例えば、図１６の例では、ｋ＝１の場合、Ｊの値は、０．０１であり、Ｊの値が、「１−α」以上でないため、第二の算出部３５ｂは、ｋ＝２に設定し、再び、Ｊの値を計算する。ここで、図１５の例において、ｋ＝２の場合、第二の算出部３５ｂは、図１６中、中央の式が示す計算を行う。このとき、Ｊの値は、０．１２であり、Ｊの値が、「１−α」以上でないため、第二の算出部３５ｂは、ｋ＝３に設定し、再び、Ｊの値を計算する。図１６の例では、ｋ＝３の場合、Ｊの値は、１．２２であり、Ｊの値が、「１−α」以上となる。
【００９６】
Ｊの値が、「１−α」以上である場合には、第二の算出部３５ｂは、ｋの値を、ＮＡ〜ＮＢ間の距離として算出する。
【００９７】
このように、制御部３５は、上記の式を用いて、Ｊの値が「１−α」以上となる場合のｋの値を「１」から１つずつ増加させて調べている。そのため、本実施例によれば、精度良くノード間の距離を算出することができる。
【００９８】
出力制御部３５ｃは、第二の算出部３５ｂにより算出された２つのノード間の距離を表示するように、出力部１２による表示を制御する。
【００９９】
制御部３５は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路である。
【０１００】
［処理の流れ］
次に、本実施例に係る算出装置３０の処理の流れについて説明する。図１７は、実施例３に係る行列情報算出処理の手順を示すフローチャートである。行列情報算出処理は、例えば、入力部１１から、行列情報算出処理を実行するための指示を制御部３５が受け付けたタイミングで、実行される。
【０１０１】
図１７に示すように、第一の算出部３５ａは、記憶部３４から、隣接行列データ１４ｂを取得する（Ｓ４０１）。そして、第一の算出部３５ａは、隣接行列データ１４ｂが示す隣接行列の固有値を算出する（Ｓ４０２）。そして、第一の算出部３５ａは、値の大きい上位５個の固有値を特定する（Ｓ４０３）。
【０１０２】
そして、第一の算出部３５ａは、変数ｎの値を０に設定する（Ｓ４０４）。そして、第一の算出部３５ａは、上位５個の固有値のうち、未選択の固有値があるか否かを判定する（Ｓ４０５）。未選択の固有値がある場合（Ｓ４０５肯定）には、第一の算出部３５ａは、変数ｎの値を１つインクリメントする（Ｓ４０６）。その後、第一の算出部３５ａは、未選択の１つの固有値を固有値Ｅｎとして選択する（Ｓ４０７）。
【０１０３】
続いて、第一の算出部３５ａは、選択した固有値Ｅｎに対応する固有ベクトルＶｎを算出し（Ｓ４０８）、Ｓ４０５へ戻る。
【０１０４】
また、未選択の固有値がない場合（Ｓ４０５否定）には、第一の算出部３５ａは、次のような処理を行う。すなわち、第一の算出部３５ａは、固有ベクトルＶｎ（ｎ＝１、２、・・・５）のデータを固有ベクトルデータ２４ｂとして記憶部３４に格納し、固有値Ｅｎ（ｎ＝１、２、・・・５）のデータを固有値データ２４ａとして記憶部３４に格納し（Ｓ４０９）、処理を終了する。
【０１０５】
図１８は、実施例３に係る算出処理の手順を示すフローチャートである。算出処理は、例えば、入力部１１から、算出処理を実行するための指示を制御部３５が受け付けたタイミングで、実行される。
【０１０６】
図１８に示すように、第二の算出部３５ｂは、算出処理を実行するための指示に含まれる、距離の計算対象の２つのノードのＩＤから、２つのノード（ＮＡ，ＮＢ）を特定する（Ｓ５０１）。そして、第二の算出部３５ｂは、記憶部３４から固有ベクトルデータ２４ｂ、固有値データ２４ａを取得する（Ｓ５０２）。次に、第二の算出部３５ｂは、変数ｋの値を０に設定する（Ｓ５０３）。
【０１０７】
その後、第二の算出部３５ｂは、変数ｋの値を１つインクリメントする（Ｓ５０４）。そして、第二の算出部３５ｂは、上記の式によって、「Ｊ」の値を算出する（Ｓ５０５）。
【０１０８】
そして、第二の算出部３５ｂは、Ｊの値が、「１−α」以上であるか否かを判定する（Ｓ５０６）。Ｊの値が、「１−α」以上でない場合（Ｓ５０６否定）には、Ｓ５０４に戻る。
【０１０９】
ここで、Ｊの値が、「１−α」以上である場合（Ｓ５０６肯定）には、第二の算出部３５ｂは、ｋの値を、ＮＡ〜ＮＢ間の距離として算出する（Ｓ５０７）。そして、出力制御部３５ｃは、Ｓ５０７で算出された２つのノード間の距離を表示するように、出力部１２による表示を制御し（Ｓ５０８）、処理を終了する。
【０１１０】
上述してきたように、本実施例に係る算出装置３０は、隣接行列データ１４ｂが示す隣接行列から複数の固有値、および、複数の固有値のそれぞれに対応する複数の固有ベクトルのそれぞれを算出する。そして、算出装置３０は、複数の固有ベクトルＶｎ（ｎ＝１、２、・・・５）ごとに、距離の算出対象の２つのノードのそれぞれに対応する固有ベクトルＶｎの２つの成分の積と、固有ベクトルＶｎに対応する固有値Ｅｎのｋ乗の値との積を算出する。そして、算出装置３０は、複数の固有ベクトルＶｎごとに算出した積の値の総和Ｊを算出する。続いて、算出装置３０は、算出した総和Ｊが、隣接行列においてノード間が接続していることを示す値「１」から所定値「α」を減算した値「１−α」を超える最小のｋの値を、２つのノード間の距離として算出する。このように、本実施例に係る算出装置３０は、総和Ｊの値が「１−α」以上となる場合のｋの値を「１」から１つずつ増加させて調べている。そのため、本実施例に係る算出装置３０によれば、精度良くノード間の距離を算出することができる。
【０１１１】
また、Ｊの値として、次の値を用いることもできる。まず、算出装置３０は、複数の固有ベクトルＶｎ（ｎ＝１、２、・・・５）ごとに、距離の算出対象の２つのノードのそれぞれに対応する固有ベクトルＶｎの２つの成分の積と、固有ベクトルＶｎに対応する固有値Ｅｎのｋ乗の値との積を算出する。そして、算出装置３０は、複数の固有ベクトルＶｎごとに算出した積の値の総和の平均値、すなわち、Ｖｎ（ｎ＝１）を用いて算出した積と、Ｖｎ（ｎ＝１、２）を用いて算出した積の総和と、Ｖｎ（ｎ＝１、２、３）を用いて算出した積の総和と、Ｖｎ（ｎ＝１、２、３、４）を用いて算出した積の総和と、Ｖｎ（ｎ＝１、２、３、４、５）を用いて算出した積の総和の、平均値をＪとして用いることもできる。このようにすることにより、より精度良くノード間の距離を算出することができる。精度が向上する理由は、用いる固有値の個数を順次増やしていくと、上記の数式で示したＪの値は、隣接行列Ａの冪乗Ａｋにおいて２つのノード間の接続状態を示す成分より、大きい値と小さい値の間を行き来するため、その平均値をとることで、より正確にＡｋの成分に近くなるためである。
【０１１２】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【０１１３】
例えば、実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。また、実施例において説明した各処理のうち、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。
【０１１４】
また、各種の負荷や使用状況などに応じて、各実施例において説明した各処理の各ステップでの処理を任意に細かくわけたり、あるいはまとめたりすることができる。また、ステップを省略することもできる。
【０１１５】
また、各種の負荷や使用状況などに応じて、各実施例において説明した各処理の各ステップでの処理の順番を変更できる。
【０１１６】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１１７】
［算出プログラム］
また、上記の実施例で説明した算出装置１０、２０または３０の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図１９を用いて、上記の実施例で説明した算出装置１０、２０または３０と同様の機能を有する算出プログラムを実行するコンピュータの一例を説明する。図１９は、算出プログラムを実行するコンピュータを示す図である。
【０１１８】
図１９に示すように、コンピュータ３００は、ＣＰＵ（Central  Processing  Unit）３１０、ＲＯＭ（Read  Only  Memory）３２０、ＨＤＤ（Hard  Disk  Drive）３３０、ＲＡＭ（Random  Access  Memory）３４０を有する。ＣＰＵ３１０、ＲＯＭ３２０、ＨＤＤ３３０、ＲＡＭ３４０は、互いに、バス３５０を介して接続されている。
【０１１９】
ＲＯＭ３２０には、ＯＳなどの基本プログラムが記憶されている。また、ＨＤＤ３３０には、上記の実施例で示す取得部、選択部、第一の算出部、第二の算出部、第三の算出部および出力制御部などと同様の機能を発揮する算出プログラム３３０ａが予め記憶される。なお、算出プログラム３３０ａについては、適宜分離しても良い。また、ＨＤＤ３３０には、距離情報、隣接行列データ、固有値データ、固有ベクトルデータなどが設けられる。これらの距離情報、隣接行列データ、固有値データ、固有ベクトルデータは、上述した距離情報１４ａ、隣接行列データ１４ｂ、固有値データ２４ａ、固有ベクトルデータ２４ｂに対応する。
【０１２０】
そして、ＣＰＵ３１０が、算出プログラム３３０ａをＨＤＤ３３０から読み出して実行する。
【０１２１】
そして、ＣＰＵ３１０は、距離情報、隣接行列データ、固有値データ、固有ベクトルデータなどを読み出してＲＡＭ３４０に格納する。さらに、ＣＰＵ３１０は、ＲＡＭ３４０に格納された距離情報、隣接行列データ、固有値データ、固有ベクトルデータなどを用いて、算出プログラム３３０ａを実行する。なお、ＲＡＭ３４０に格納される各データは、常に全てのデータがＲＡＭ３４０に格納されなくともよい。処理に用いられるデータがＲＡＭ３４０に格納されれば良い。
【０１２２】
なお、上記した算出プログラム３３０ａについては、必ずしも最初からＨＤＤ３３０に記憶させておく必要はない。
【０１２３】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。  
【０１２４】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１２５】
１０      算出装置
１１      入力部
１２      出力部
１４      記憶部
１４ａ    隣接行列データ
１４ｂ    距離情報
１５      制御部
１５ｂ    選択部
１５ｃ    第一の算出部
１５ｄ    第二の算出部
１５ｅ    第三の算出部
【図１】
0005831274.tif 000003
【図２】
0005831274.tif 000004
【図３】
0005831274.tif 000005
【図４】
0005831274.tif 000006
【図５】
0005831274.tif 000007
【図６】
0005831274.tif 000008
【図７】
0005831274.tif 000009
【図８】
0005831274.tif 000010
【図９】
0005831274.tif 000011
【図１０】
0005831274.tif 000012
【図１１Ａ】
0005831274.tif 000013
【図１１Ｂ】
0005831274.tif 000014
【図１２】
0005831274.tif 000015
【図１３】
0005831274.tif 000016
【図１４】
0005831274.tif 000017
【図１５】
0005831274.tif 000018
【図１６】
0005831274.tif 000019
【図１７】
0005831274.tif 000020
【図１８】
0005831274.tif 000021
【図１９】
0005831274.tif 000022
【図２０Ａ】
0005831274.tif 000023
【図２０Ｂ】
0005831274.tif 000024
【図２０Ｃ】
0005831274.tif 000025
【図２１Ａ】
0005831274.tif 000026
【図２１Ｂ】
0005831274.tif 000027
【図２１Ｃ】
0005831274.tif 000028
【図２２Ａ】
0005831274.tif 000029
【図２２Ｂ】
0005831274.tif 000030
【図２２Ｃ】
0005831274.tif 000031
【図２３】
0005831274.tif 000032