(57)【特許請求の範囲】
【請求項１】
グラフ内の複数のノードをそれぞれ含む複数のクラスタを設定し、
全てのクラスタ対のうち、最も結合力の大きいクラスタ対を併合して併合クラスタとし、
前記併合クラスタと、他の各クラスタとの結合力を再計算し、
併合後のクラスタ数が所定値より大きい場合、併合後のクラスタからクラスタ対を抽出する、
処理をコンピュータに実行させ、
前記再計算では、前記併合クラスタとそれに繋がる各クラスタとの結合力のみを再計算するとともに、クラスタ対の結合力が
（１）該クラスタ対を構成する各クラスタ内のノードの数の少なさに応じて、
（２）該クラスタ対を構成する各クラスタの次数の少なさに応じて、かつ
（３）該クラスタ対を構成する一のクラスタ内のノードと、該クラスタ対を構成する他のクラスタ内のノードとを連結するリンクの数の多さに応じて
高くなるように、前記結合力を再計算することを特徴とするクラスタリングプログラム。
【請求項２】
複数のノードが複数のクラスタに分割されたグラフにおいて、クラスタ間のリンクは検索の対象から除き、
問合せグラフと一致する部分グラフを包含している可能性のあるクラスタを、前記問合せグラフにより表現される条件の一部を用いて絞り込み、
絞り込まれたクラスタの中から、前記問合せグラフと一致する部分グラフを包含するクラスタを、前記条件のすべてを用いて検索し、
検索の結果を出力する、
処理をコンピュータに実行させる検索プログラム。
【請求項３】
コンピュータが、
グラフ内の複数のノードをそれぞれ含む複数のクラスタを設定する工程と、
全てのクラスタ対のうち、最も結合力の大きいクラスタ対を併合して併合クラスタとする工程と、
前記併合クラスタと、他の各クラスタとの結合力を再計算する工程と、
併合後のクラスタ数が所定値より大きい場合、併合後のクラスタからクラスタ対を抽出する工程と、
を実行し、
前記再計算では、前記併合クラスタとそれに繋がる各クラスタとの結合力のみを再計算するとともに、クラスタ対の結合力が
（１）該クラスタ対を構成する各クラスタ内のノードの数の少なさに応じて、
（２）該クラスタ対を構成する各クラスタの次数の少なさに応じて、かつ
（３）該クラスタ対を構成する一のクラスタ内のノードと、該クラスタ対を構成する他の
クラスタ内のノードとを連結するリンクの数の多さに応じて
高くなるように、前記結合力を再計算することを特徴とするクラスタリング方法。
【請求項４】
コンピュータが、
複数のノードが複数のクラスタに分割されたグラフにおいて、クラスタ間のリンクは検索の対象から除き、
問合せグラフと一致する部分グラフを包含している可能性のあるクラスタを、前記問合せグラフにより表現される条件の一部を用いて絞り込む工程と、
絞り込まれたクラスタの中から、前記問合せグラフと一致する部分グラフを包含するクラスタを、前記条件のすべてを用いて検索する工程と、
検索の結果を出力する工程と、
を実行することを特徴とする検索方法。
【請求項５】
グラフ内の複数のノードをそれぞれ含む複数のクラスタを設定する手段と、
全てのクラスタ対のうち、最も結合力の大きいクラスタ対を併合して併合クラスタとする手段と、
前記併合クラスタと、他の各クラスタとの結合力を再計算する手段と、
併合後のクラスタ数が所定値より大きい場合、併合後のクラスタからクラスタ対を抽出する手段と、
を備え、
前記再計算では、前記併合クラスタとそれに繋がる各クラスタとの結合力のみを再計算するとともに、クラスタ対の結合力が
（１）該クラスタ対を構成する各クラスタ内のノードの数の少なさに応じて、
（２）該クラスタ対を構成する各クラスタの次数の少なさに応じて、かつ
（３）該クラスタ対を構成する一のクラスタ内のノードと、該クラスタ対を構成する他のクラスタ内のノードとを連結するリンクの数の多さに応じて
高くなるように、前記結合力を再計算することを特徴とするクラスタリング装置。
【請求項６】
複数のノードが複数のクラスタに分割されたグラフにおいて、クラスタ間のリンクは検索の対象から除き、
問合せグラフと一致する部分グラフを包含している可能性のあるクラスタを、前記問合せグラフにより表現される条件の一部を用いて絞り込む手段と、
絞り込まれたクラスタの中から、前記問合せグラフと一致する部分グラフを包含するクラスタを、前記条件のすべてを用いて検索する手段と、
検索の結果を出力する手段と、
を備えることを特徴とする検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ノードとノード間を連結するリンクからなる検索対象グラフの中から問合せグラフと一致するグラフを検索する情報検索プログラム、情報検索装置、および情報検索方法に関する。
【背景技術】
【０００２】
従来、サーチエンジンはＷｅｂ上で情報を検索するために、日常生活でもなくてはならないものになっている。しかし、その検索結果が我々の期待するものと異なる不要な結果が含まれることがしばしばである。これは、サーチエンジンが文字列のマッチングにより検索を行い、意味まで考慮して検索しているわけではないためである。この不要な結果が増加する傾向はＷｅｂのデータの爆発的増加に伴い、さらに強まりつつある。
【０００３】
この問題を解決することを１つの目的に、Ｓｅｍａｎｔｉｃ  Ｗｅｂの研究が行われている。Ｓｅｍａｎｔｉｃ  Ｗｅｂでは、Ｗｅｂページから主要な情報をメタデータと呼ばれる構造的なデータとして抽出する。このメタデータは、計算機が意味内容を理解しやすいように、構造化されている。その意味でＲＤＢ（関係データベース）のようなデータベースと同様である。したがって、サーチエンジンによる情報検索とは異なり、意味内容も考慮して検索できるため、検索精度を高めることが可能である。
【０００４】
メタデータはＲＤＦ（Ｒｅｓｏｕｒｃｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｆｒａｍｅｗｏｒｋ）と呼ばれるグラフ（ネットワーク）構造をもつデータであり、階層構造をもつＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）により記述されている。ＲＤＦの検索は、すでに商用のデータベースシステムで実用化されている。
【０００５】
ＲＤＦ検索に関しては、Ｊｅｎａ（下記非特許文献１を参照。）、ＲＤＦＳｔｏｒｅ（下記非特許文献２を参照。）など、いくつかの試作システムが発表されている。これらの試作システムでは、グラフを三つ組の集まりとして捉え、三つ組をＲＤＢに格納する方法が一般に取られている。
【０００６】
【非特許文献１】Ｊｅｎａ  Ｓｅｍａｎｔｉｃ  Ｗｅｂ  Ｆｒａｍｅｗｏｒｋ［Ｏｎｌｉｎｅ］  ［２００８年１月２８日検索］、インターネット＜ｈｔｔｐ：／／ｊｅｎａ．ｓｏｕｒｃｅｆｏｒｇｅ．ｎｅｔ／＞
【非特許文献２】ＲＤＦＳｔｏｒｅ  Ｐｅｒｌ／Ｃ  ＲＤＦ  Ｓｔｏｒａｇｅ  ＡＮＤ  ＡＰＩ［Ｏｎｌｉｎｅ］  ［２００８年１月２８日検索］、インターネット＜ｈｔｔｐ：／／ｒｄｆｓｔｏｒｅ．ｓｏｕｒｃｅｆｏｒｇｅ．ｎｅｔ／＞
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した非特許文献１および非特許文献２で示されている三つ組による方式では、問合せグラフがマッチングする部分グラフを探すために、ジョインという処理が頻繁に用いられている。ジョインはＲＤＢにおける主要で頻繁に用いられる演算であるが、ソートと合わせ、処理負荷が重い処理でもある。したがって、検索速度が遅くなり、検索に時間がかかるという問題がある。今後のデータの爆発的増加を考えると、計算時間がかかるという問題は解消されない。また、すべてのクラスタを検索する場合、問合せグラフにマッチしないクラスタも検索することとなるため、検索速度が遅くなり、検索に時間がかかるという問題がある。
【０００８】
この発明は、上述した従来技術による問題点を解消するため、問合せグラフにマッチする可能性のあるクラスタを絞り込むことにより、検索速度の向上を図ることができる情報検索プログラム、情報検索装置、および情報検索方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、この情報検索プログラム、情報検索装置、および情報検索方法は、ノードとノード間を連結するリンクからなる検索対象グラフの中から問合せグラフと一致するグラフを検索する場合に、前記検索対象グラフ内の互いに異なるノードを包含するクラスタの集合の中から、一のクラスタと当該一のクラスタ内のノードと前記リンクにより連結されるノードを包含する他のクラスタとからなるクラスタ対を抽出し、抽出されたクラスタ対の結びつきの強さをあらわす結合力を前記クラスタ対ごとに算出し、算出されたクラスタ対ごとの結合力に基づいて、前記クラスタ対の集合の中から、併合対象を決定し、併合対象に決定されたクラスタ対を併合し、併合後のクラスタの集合の中から、前記問合せグラフと一致するグラフを検索し、検索結果を出力することを要件とする。
【００１０】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、検索対象グラフから分割されたクラスタを縮退させることができる。
【００１１】
また、前記クラスタ対を構成する各クラスタ内のノードの数の少なさに応じて高くなるように、前記結合力を算出することとしてもよい。
【００１２】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、包含するノード数が多いクラスタについては結合力が低くなる。したがって、そのようなクラスタの膨張（包含するノード数の増加）を抑制することで、適度な範囲で問合せグラフがマッチする解を得ることができる。
【００１３】
また、前記クラスタ対を構成する各クラスタ内のノードから他のクラスタ内のノードに連結するリンクの数の少なさに応じて高くなるように、前記結合力を算出することとしてもよい。
【００１４】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、検索対象グラフ内のハブとなるクラスタについては結合力が低くなる。したがって、ハブを回避することで、ハブ以外のクラスタ対から優先的に縮退させることができる。
【００１５】
また、前記一のクラスタ内のノードと前記他のクラスタ内のノードとが連結するリンクの数の多さに応じて高くなるように、前記結合力を算出することとしてもよい。
【００１６】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、つながりの強いクラスタ対から優先的に縮退させることができる。
【００１７】
また、前記クラスタ対の集合の中から、前記結合力が最大となるクラスタ対を前記併合対象に決定することとしてもよい。
【００１８】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、結びつきの強いクラスタ対から優先的に縮退させることができる。
【００１９】
また、併合後のクラスタの数が所定数に到達したか否かを判断し、前記所定数に到達していないと判断された場合、併合後のクラスタの集合の中から、前記クラスタ対を抽出することとしてもよい。
【００２０】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、クラスタ数を適切な数に抑制することができ、個々のクラスタの過剰な膨張を抑制することで、検索速度の向上を保ちつつ、検索精度の低下を抑制することができる。
【００２１】
また、前記問合せグラフが有する条件に基づいて、前記併合手段による併合後のクラスタの集合を絞り込み、絞り込まれたクラスタの集合の中から、前記問合せグラフと一致するグラフを検索することとしてもよい。
【００２２】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、問合せグラフとマッチする可能性のあるクラスタを特定することで、問合せグラフとマッチしないクラスタについての無駄な検索を抑制することができる。
【発明の効果】
【００２３】
この情報検索プログラム、情報検索装置、および情報検索方法によれば、問合せグラフにマッチする可能性のあるクラスタを絞り込むことにより、検索速度の向上を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００２４】
以下に添付図面を参照して、この情報検索プログラム、情報検索装置、および情報検索方法の好適な実施の形態を詳細に説明する。
【００２５】
（クラスタリングを用いた検索の概要）
本実施の形態では、検索対象グラフの中から問合せグラフと一致するグラフを検索する。検索対象グラフとは、ノードとノード間を連結するリンクからなるネットワークである。グラフ検索の対象分野としては、Ｗｅｂのほか、輸送網、通信網、分子構造、人間関係などネットワークで表されるものが該当する。検索対象グラフはリンクに向きが有る有向グラフでも無向グラフでもよい。
【００２６】
図１は、クラスタリングを用いた検索の概要を示す説明図である。（Ａ）は、検索対象グラフ１００を示している。検索対象グラフ１００中、小丸図形はノードをあらわしており、そのうち二重丸図形はコンピュータ企業を、塗りつぶされた小丸図形はバイオ企業をあらわしている。また、ノード間の矢印は、リンクをあらわしている。この検索対象グラフ１００では、矢印の始点となるノードから終点となるノードに資金を出資していることをあらわしている。
【００２７】
（Ａ）において、クラスタリングをおこなった結果を（Ｂ）に示す。（Ｂ）において、ノードやリンクを包含する円がクラスタをあらわしている。クラスタとは、検索対象グラフ１００の中の少なくともノードを包含する連結した部分グラフである。ノードを複数包含している場合には、リンクも包含する。また、クラスタリングとは、グラフを互いに共有部分がなく、かつ任意のノードが何れかのクラスタに含まれるように、クラスタに分割する操作である。したがって、同一のノードが複数のクラスタにまたがって包含されることはない。
【００２８】
（Ｂ）において、問合せグラフ１１０を与える。問合せグラフ１１０とは、グラフ検索におけるユーザの問合せをあらわすグラフであり、検索条件となる。（Ｂ）では、コンピュータ企業からバイオ企業への出資をあらわしている。この問合せグラフ１１０にマッチする部分グラフを包含している可能性のあるクラスタは、太線で示した円のクラスタである。細線で示したクラスタは、コンピュータ企業または、バイオ企業の一方しか含まないため、マッチする可能性はない。
【００２９】
したがって、細線で示した円のクラスタは、検索対象外となるため、検索速度の高速化を図ることができる。このように、クラスタリングをおこなうと、検索範囲を絞り込むことができるが、どのようにしてクラスタリングするかが問題となる。
【００３０】
上述したように、クラスタリングとは、以下の定義（１−１）〜（１−４）に示すように検索対象グラフ１００全体を複数のクラスタ（部分グラフ）に分割することである。
【００３１】
（１−１）ノードはいずれかのクラスタの１つ（のみ）に含まれる。
（１−２）クラスタは連結したグラフである。
【００３２】
また、クラスタの絞込みの性能を考慮すると、次の２つのことが重要である。
（１−３）クラスタ間に跨るリンクの数をなるべく少なくする。
（１−４）全体をバランスよく分割する。すなわち、クラスタが包含するノードの数ができる限り均等になるように分割する。
【００３３】
図２および図３は、クラスタリング例を示す説明図である。図２および図３において、点がノードをあらわしており、ノード間を結ぶ線がリンクをあらわしている。なお、リンクのうち点線で示したリンクは、クラスタ間に跨るリンクを示している。
【００３４】
図２に示した例は、上記（１−３）、（１−４）の観点から好ましいクラスタリングである。一方、図３は逆に好ましくない例である。図３中、ａ）はクラスタ間のリンクが４個と多く、上記（１−３）の観点から好ましくない。ｂ）はクラスタ間のリンク数は１と好ましいが、上記（１−４）の観点から好ましくない。本実施の形態では、上述した原理により、クラスタリングをおこなう。
【００３５】
（検索対象グラフおよび問合せグラフの一例）
図４は、検索対象グラフおよび問合せグラフの一例を示す説明図である。図４において、この検索対象グラフ１００は、企業間の出資関係をあらわしている。各ノードＮａ〜Ｎｌが企業をあらわしている。ノード間のリンクは、矢印と数値からなり、矢印によりどの企業からどの企業へ出資されているかをあらわしており、数値（単位は百万円）によりいくら出資されているかをあらわしている。たとえば、企業Ｎａは企業Ｎｂに３０００万円出資していることとなる。
【００３６】
また、問合せグラフ１１０は、グラフ検索におけるユーザの問合せをあらわすグラフであり、検索条件となる。この問合せグラフ１１０は、コンピュータ企業からバイオ企業に１億（１００百万）円以上出資しているケースを検索条件としている。グラフ検索は検索対象グラフ１００の中から問合せグラフ１１０にマッチする部分グラフを検索する処理である。
【００３７】
（情報検索装置のハードウェア構成）
図５は、この発明の実施の形態にかかる情報検索装置のハードウェア構成を示すブロック図である。情報検索装置は、ＣＰＵ５０１と、ＲＯＭ５０２と、ＲＡＭ５０３と、ＨＤＤ（ハードディスクドライブ）５０４と、ＨＤ（ハードディスク）５０５と、ＦＤＤ（フレキシブルディスクドライブ）５０６と、着脱可能な記録媒体の一例としてのＦＤ（フレキシブルディスク）５０７と、ディスプレイ５０８と、Ｉ／Ｆ（インターフェース）５０９と、キーボード５１０と、マウス５１１と、スキャナ５１２と、プリンタ５１３と、を備えている。また、各構成部はバス５００によってそれぞれ接続されている。
【００３８】
ここで、ＣＰＵ５０１は、情報検索装置の全体の制御を司る。ＲＯＭ５０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ５０３は、ＣＰＵ５０１のワークエリアとして使用される。ＨＤＤ５０４は、ＣＰＵ５０１の制御にしたがってＨＤ５０５に対するデータのリード／ライトを制御する。ＨＤ５０５は、ＨＤＤ５０４の制御で書き込まれたデータを記憶する。
【００３９】
ＦＤＤ５０６は、ＣＰＵ５０１の制御にしたがってＦＤ５０７に対するデータのリード／ライトを制御する。ＦＤ５０７は、ＦＤＤ５０６の制御で書き込まれたデータを記憶したり、ＦＤ５０７に記憶されたデータを情報検索装置に読み取らせたりする。
【００４０】
また、着脱可能な記録媒体として、ＦＤ５０７のほか、ＣＤ−ＲＯＭ（ＣＤ−Ｒ、ＣＤ−ＲＷ）、ＭＯ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、メモリーカードなどであってもよい。ディスプレイ５０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ５０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００４１】
Ｉ／Ｆ５０９は、通信回線を通じてインターネットなどのネットワーク５１４に接続され、このネットワーク５１４を介して他の装置に接続される。そして、Ｉ／Ｆ５０９は、ネットワーク５１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ５０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００４２】
キーボード５１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス５１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００４３】
スキャナ５１２は、画像を光学的に読み取り、情報検索装置内に画像データを取り込む。なお、スキャナ５１２は、ＯＣＲ機能を持たせてもよい。また、プリンタ５１３は、画像データや文書データを印刷する。プリンタ５１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００４４】
（情報検索装置の機能的構成）
図６は、情報検索装置の機能的構成を示すブロック図である。図６において、情報検索装置６００は、クラスタリング処理部６０１とインデックス作成部６０２と入力処理部６０３とクラスタ絞込み処理部６０４とクラスタ内検索部６０５とから構成されている。これら各機能は、具体的には、たとえば、図５に示したＲＯＭ５０２、ＲＡＭ５０３、ＨＤ５０５等の記憶領域に記憶されたプログラムをＣＰＵ５０１に実行させることにより、またはＩ／Ｆ５０９により配布されたプログラムを実行することによりその機能を実現する。
【００４５】
本実施の形態では、全体の処理は大きく分けると、生成処理と検索処理の２つの段階に分かれる。生成処理は、検索処理を高速化するためのデータを生成する段階である。すなわち、上述したクラスタリング処理部６０１とインデックス作成部６０２に相当する。インデックス作成部６０２は、データベースや検索エンジンで用いられる技術を用いてインデックスを作成する機能である。生成処理は、一般に時間がかかるが、検索処理ごとに行う必要はなく、最初に一度行えばよい。したがって、検索処理の性能には影響しない。これもデータベースや検索エンジンと同様である。
【００４６】
ただし、生成処理では、クラスタリング処理部６０１は通常のデータベースや検索エンジンにはない処理である。検索処理は、生成処理の結果を利用して検索対象グラフ１００を検索する段階である。すなわち、上述した入力処理部６０３と、クラスタ絞込み処理部６０４と、クラスタ内検索部６０５に相当する。
【００４７】
本実施の形態の基本的な考えは、すべてのクラスタから探す代わりに、問合せグラフ１１０にマッチする可能性のあるクラスタを絞り込むことにより、グラフ検索を高速化することにある。このことは、ものを探す場合、全ての場所を探すのではなく、可能性が高いと思われる場所を探すのと似ている。図１に示したように、コンピュータ企業またはバイオ企業のいずれかのノードしか含まないクラスタには問い合わせグラフにマッチする可能性はない。したがって、まず両者を含む太線の円で表されたクラスタを特定する。特定した後は、そのクラスタ内を検索する。
【００４８】
なお、求めるケースがクラスタ間に跨る可能性があるが、本実施の形態では、この程度の精確さを多少犠牲にすることがあるが、本発明の一番の目的は検索を高速化することにある。このような応用は、インターネットにおけるサーチエンジンなどもこれに類している。今後、情報量はさらに爆発的に増えていくことが予想される。このような傾向は、データ量が大規模になればなるほど強くなる。以下、各機能について具体的に説明する。
【００４９】
クラスタリング処理部６０１は、検索対象グラフ１００をクラスタリングする機能を有する。図７は、図４の検索対象グラフ１００に対応する企業データを示すテーブルであり、図８は、出資元と出資先との関係を示すテーブルである。ここでは、図７に示したテーブルを「ノードテーブル」、図８に示したテーブルを「リンクテーブル」と呼ぶことにする。
【００５０】
検索対象グラフ１００の観点からは、ノードテーブル７００が各ノードＮａ〜Ｎｌの情報を、リンクテーブル８００がリンクの情報をあらわしている。ノードテーブル７００は、ノード識別子と企業名、住所、業種などの企業の属性からなる。ノード識別子は、企業を一意に特定するための情報である。クラスタリングの結果、図４に示した検索対象グラフ１００が３つに分割されたものとする。
【００５１】
図９は、クラスタリング結果を示す説明図である。このクラスタリングにより、検索対象グラフ１００はクラスタＣ1〜Ｃ3に分割される。このクラスタリングは、クラスタリングに望まれる性質である上記（１−３）、（１−４）を明らかに満たしている。
【００５２】
図１０は、分割ノードテーブルを示す説明図である。分割ノードテーブル７００−１〜７００−３は、図９に示したクラスタリング結果に基づいて、ノードテーブル７００がそれぞれのクラスタＣ1〜Ｃ3に分割されたテーブルである。また、図１１は、分割リンクテーブルを示す説明図である。分割リンクテーブル８００−１〜８００−３は、図９に示したクラスタリング結果に基づいて、リンクテーブル８００がそれぞれのクラスタＣ1〜Ｃ3に分割されたテーブルである。
【００５３】
図１２は、クラスタの識別子付与後のノードテーブルを示す説明図である。図１２に示したノードテーブル１２００は、図７に示したノードテーブル７００の各ノードＮａ〜Ｎｌに対応する行ごとに、そのノードが含まれているクラスタの識別子１２０１を付加することで得られる。このようにクラスタリングをおこなうことで、各ノードがどのクラスタに包含されているかが特定できることとなる。
【００５４】
インデックス作成部６０２は、データへのアクセスを高速化するために、インデックスを作成する機能を有する。インデックス作成部６０２としては、たとえば、データベースや検索エンジンで用いられるＢ−ｔｒｅｅを利用することができる。インデックスは、検索でよく用いられる属性に張られるのが一般的である。したがって、次のクラスタの絞込みを高速に行うために、図１２に示したノードテーブル１２００の業種にインデックスを張ることにする。
【００５５】
入力処理部６０３は、問合せグラフ１１０の入力を受け付ける機能を有する。図１３は、ユーザインターフェースを示す説明図である。図１３において、ユーザインターフェース１３００は、グラフ表示画面１３０１と問合せ画面１３０２とから構成される。グラフ表示画面１３０１には、検索対象グラフ１００や検索結果を表示する。
【００５６】
問合せ画面１３０２は、グラフ検索の問合せを行う画面であり、ラジオボタンを選択することでコマンドとグラフ問合せによる二種類の検索をおこなうことができる。コマンド検索は、通常の関係データベースのように、問合せ言語を用いてコマンドをベースに検索するためのものである。グラフ問合せは、視覚的に問合せをグラフとして表し、問い合わせを行うものである。グラフ問合せ入力領域１３０３は、問合せグラフを入力する領域である。
【００５７】
図１４は、図１３に示したグラフ問合せ入力領域１３０３を示す説明図である。右側の領域１４０１は問い合わせを作るためのビルディングブロックである。必要な図形を右側の領域１４０１から左側の領域１４０２に移すことで、問合せグラフ１１０を作成していく。
【００５８】
クラスタ絞込み処理部６０４は、問合せグラフ１１０にマッチする可能性のあるクラスタを、クラスタリング結果を用いて絞り込む機能を有する。具体的には、たとえば、まず、問合せグラフ１１０中のノードの属性値に関する条件（以下、条件Ｊ）とインデックスの張られたノードテーブル１２００を用いることにより、その条件Ｊを満たすノードのノード識別子とクラスタ識別子を特定する。たとえば、条件Ｊを業種とすると、業種が“コンピュータ”であるノードのノード識別子は、図１２に示すノードテーブル１２００から特定することができる。同時に、同じ行に含まれるクラス識別子からクラスタを特定することもできる。
【００５９】
また、条件Ｊが複数ある場合は、さらにクラスタを特定することが可能である。今、問合せグラフ１１０が条件Ｊ１（例：業種がコンピュータ）と条件Ｊ２（例：業種がバイオ）を同時に満たすことを要求しているものとする。条件Ｊ１を満たすクラスタがクラスタＣ1、Ｃ2、条件Ｊ２を満たすクラスタがクラスタＣ2、Ｃ3であったとする。
【００６０】
それぞれの条件Ｊ１，Ｊ２だけを用いると、クラスタはそれぞれ２つにしか絞り込めない。一方、問合せグラフ１１０にマッチする可能性のあるクラスタは、２つの条件Ｊ１，Ｊ２の論理積をとれば、それらを同時に満たす１つのクラスタに絞り込むことができる。具体的には、たとえば、問合せグラフ１１０があらわす条件を、必ず次のような形式（和積標準形）に変換する。
【００６１】
条件Ｊ１  ａｎｄ  条件Ｊ２  ａｎｄ…ａｎｄ  条件Ｊｉ  ａｎｄ…ａｎｄ  条件Ｊｎ
（ただし、条件Ｊｉはｏｒまたはｎｏｔのみを含む論理式で、１≦ｉ≦ｎ。ここでｎは条件数。）
【００６２】
そして、これらの条件Ｊ１〜Ｊｎの中で、ノードテーブル１２００とインデックスを使って高速にノードを検索できる条件を選ぶ。それらを「ノード条件」と呼び、条件Ｊｉについて、ノード条件ＮＪｉ1、ノード条件ＮＪｉ2、…、ノード条件ＮＪｉmとする（１≦ｉ1＜ｉ2＜…＜ｉm≦ｎ、ｍ≦ｎ。ここでｍはノード条件数。）。なお、ノードテーブル１２００は、一般の問合せでは複数である可能性がある。
【００６３】
つぎに、各ノード条件ＮＪｉj（１≦ｊ≦ｍ）に対して、ノードテーブル１２００からノード条件ＮＪｉjを満たす行のノード識別子とクラスタ識別子の２つからなる作業用テーブル（以降、「ノード・クラスタ識別子テーブル」と呼ぶ）ｎｃＷｉjを作成する。
【００６４】
図１５は、ノード・クラスタ識別子テーブルｎｃＷｉjを示す説明図である。図１５において、（ａ）は、業種がコンピュータのノード・クラスタ識別子テーブルｎｃＷｉ1である。このノード・クラスタ識別子テーブルｎｃＷｉ1は、図１２に示したノードテーブル１２００から、業種がコンピュータの行を抽出したテーブルである。（ｂ）は、業種がバイオのノード・クラスタ識別子テーブルｎｃＷｉ2である。このノード・クラスタ識別子テーブルｎｃＷｉ2は、図１２に示したノードテーブル１２００から、業種がバイオの行を抽出したテーブルである。
【００６５】
つぎに、共通するクラスタを特定する。すなわち、ノード・クラスタ識別子テーブルｎｃＷｉ1、ｎｃＷｉ2、…、ｎｃＷｉj、…、ｎｃＷｉmに共通するクラスタ識別子を求め、その結果を「クラスタ識別子テーブル」と呼ぶ作業用テーブルｃＷに格納する。
【００６６】
図１６は、クラスタ識別子テーブルｃＷを示す説明図である。また、必要であれば、クラスタ内検索部６０５における検索処理のために、共通するクラスタごとにノード・クラスタ識別子テーブルｎｃＷｉ1、ｎｃＷｉ2、…、ｎｃＷｉj、…、ｎｃＷｉmの中でそのクラスタ識別子に対応するノード識別子を集めたノード識別子テーブルｎＷＣkを作成する。ここで、Ｃkは、共通するクラスタの識別子をあらわす。
【００６７】
図１７は、ノード識別子テーブルｎＷＣkを示す説明図である。ノード識別子テーブルｎＷＣkは、ノード条件ＮＪｉjの１つに対して作成する。ここでは、業種がコンピュータであるノード条件ＮＪｉjに対して作成している。共通するノード識別子を求めることは、結局２つの集合の共通部分を計算することに当り、既存の方法が知られているので、それを利用して計算することができる。クラスタ識別子テーブルｃＷが主記憶にのる場合は、ハッシングを使って高速に計算することが可能である。
【００６８】
図４に示した検索対象グラフ１００を例にあげると、図１２に示したノードテーブル１２００から業種がコンピュータであるノードとそのノードが含まれるクラスタ識別子を、図１５（ａ）に示すように検索する。同様に、業種がバイオ企業であるノードとそのノードが含まれるクラスタ識別子を、図１５（ｂ）に示すように検索する。
【００６９】
つぎに、（ａ）、（ｂ）の両方に含まれるクラスタ識別子を検索することで、図１６に示したクラスタ識別子テーブルｃＷを検索結果として得る。これにより、検索対象となるクラスタを、クラスタ識別子テーブルｃＷで示されたクラスタに絞り込むことができる。また、クラスタ内検索部６０５で必要であれば、図１７に示すようなノード識別子テーブルｎＷＣ2、ｎＷＣ3を作成する。この例では、業種がコンピュータであるノード条件に対して、作成している。
【００７０】
このように、本実施の形態では、ノード条件ＮＪｉjを用いてクラスタを絞り込む。ただし、問合せグラフ１１０にマッチする部分は、これ以外にもある可能性がある。たとえば、問合せグラフ１１０にマッチする部分グラフが２つのクラスタにまたがっている可能性がある。本実施の形態では、全ての検索結果を検索できるとは限らないが、従来のＲＤＢのジョインを使う場合に比べ、大幅に高速化できる可能性がある。
【００７１】
すなわち、今までＲＤＢで行ってきた検索は、完全な正解を求めるものであったが、本方式は、完全ではなく、近似的な解を求めるものである。応用によっては、全ての検索結果を必要とする場合がある。しかし、条件を満たすものを１つでもいいから高速に検索して欲しいという場合も多い。実際、検索エンジンでは条件を満たす高々上位１０件程度を調べることがほとんどである。また、ビジネスの分野でも、特に調査段階など非定型的な業務の場合、条件を満たすすべての情報を検索する必要がある場合は、それほど多くない。本実施の形態は、このような応用分野を対象とするものである。
【００７２】
クラスタ内検索部６０５は、クラスタ絞込み処理部６０４によって絞り込まれたクラスタを検索して、問合わせグラフ１１０に一致する部分グラフを検索する。具体的には、たとえば、問合せグラフ１１０と完全一致する部分グラフを検索する。
【００７３】
ここで、より具体的には、クラスタはやはり一つのグラフと考えられる。すなわち、問題のサイズは小さくなっているが、従来と同じ問題であることに変わりはない。したがって、従来のＲＤＢの方式をこのクラスタに適用して、精確な解を求めることが可能である。
【００７４】
また、図１７に示したように、ノード識別子が求められている。これらの求められたノードを活用して検索結果を求めることが可能である。具体的には、ノード識別子テーブルｎＷＣkを元に、クラスタ内でノード条件ＮＪｉjの１つを満たすノードを特定する。そして、そのノードを含む周りのノードやリンクが問合せグラフ１１０を満たすかどうかを調べる。
【００７５】
以上を図４に示した検索例に実際に適用することにより説明する。ノード識別子テーブルｎＷＣkは求められているものとする。図１６に示したクラスタ識別子テーブルｃＷにより、クラスタＣ1〜Ｃ3の中から、クラスタＣ2，Ｃ3に絞りこめているので、クラスタＣ2，Ｃ3内を精確に検索する。
【００７６】
まず、クラスタＣ2を検索する場合を説明する。図１７に示したノード識別子テーブルｎＷＣ2より、ノードＮｅについて調べる。ノードＮｅの周り（リンク先ノード）には、バイオ企業のノードがないので、ノードＮｅは問合せグラフ１１０にはマッチしない。したがって、クラスタＣ2には解はない。
【００７７】
つぎに、クラスタＣ3を検索する場合を以下、説明する。同様に、ノード識別子テーブルｎＷＣ3より、ノードＮｉについて調べる。ノードＮｉの周り（リンク先ノード）にはバイオ企業のノードＮｊがある。さらに、ノードＮｉからノードＮｊに振り込まれた金額は、２００百万円である。したがって、問合せグラフ１１０にマッチしているので、ノードＮｉ，ＮｊおよびノードＮｉ，Ｎｊ間のリンクからなる部分グラフが求める解である。
【００７８】
（クラスタリング処理部６０１の詳細説明）
つぎに、クラスタリング処理部６０１について詳細に説明する。２０００年ごろから注目を集めているネットワーク理論がある。この理論によれば、
（２−１）  自然界にあるネットワークの多くは、ノードから出るリンクの数がべき法則に従うという性質を持っている。すなわち、次数（ノードから出ているリンクの数）の少ないノードほど多く、次数の多いノードほど少ない。次数がまわりのノードに比べ大きなノードはハブと呼ばれている。
【００７９】
（２−２）  上記（２−１）を満たすネットワークはハブが攻撃を受けると、ネットワークはばらばらになりやすいということが言われている。その代表例として、Ｗｅｂ、コンピュータネットワーク、航空ネットワーク、食物連鎖、人間関係など多くのものが挙げられている。
【００８０】
図１８は、ネットワークを示す説明図である。このネットワーク（グラフ）は上記（２−１）を説明するものである。（２−１）の条件を満たすようなグラフは、スケールフリー（ｓｃａｌｅ  ｆｒｅｅ）と呼ばれている。Ｗｅｂがスケールフリーであることがわかったのが、２０００年ごろであり、その後、他の自然界や社会の多くのネットワークもスケールフリーであることがわかってきている。図１９は、スケールフリーを示すグラフである。このグラフは、上記（２−１）のべき法則に従うことを説明するものである。
【００８１】
図２０は、（２−２）を説明するものであり、図１８に示したネットワークの分解例を示す説明図である。図２０では、図１８に示したネットワーク（グラフ）をハブを中心に分割している。図２０の分割後の点線で表されたリンクは、図１８においてハブ間に跨っていたリンクをあらわしている。Ｗｅｂであれば、サーチエンジンのようにリンク数が非常に大きいものは非常に少なく、リンク数が少ないノードほど多くなり、その分布はべき法則に従っている。航空ネットワークも同様である。航空ネットワークで、成田国際空港のような大きな空港が運行不能になると航空ネットワークは寸断されてしまう。本実施の形態でも、このことを利用して、ハブを中心としてクラスタを構成する。
【００８２】
基本的には、まず、ｎ個のノードからなるグラフを、ｎ個のクラスタからなるグラフとみなす。各クラスタにはそれぞれ１つのノードが含まれている。そして、これらの中から隣接する２つのクラスタを選び、それらをマージして１つのクラスタとし、全体のクラスタ数を一つ減らす。この処理を繰り返すことにより、グラフのクラスタ数を望むクラスタの数であるｍ個まで減らす。マージされたクラスタには、それまでマージされたクラスタ、クラスタに含まれるノードやリンクに関するすべての情報が記憶されるものとする。
【００８３】
クラスタにマージされたノードやリンクからなる部分グラフがこのクラスタに対応する部分グラフである。問題は、隣接するどの２つのクラスタを選ぶかということである。クラスタリング処理の流れとしては、
（３−１）まず、最初は、ｎ個のノードからなる検索対象グラフ１００をｎ個のクラスタとみなす。
（３−２）そして、未計算のクラスタ対｛Ｃp，Ｃq｝を抽出する（抽出機能）。クラスタ対｛Ｃp，Ｃq｝はリンクにより連結されているものを抽出する。
【００８４】
（３−３）  つぎに、抽出クラスタ対｛Ｃp，Ｃq｝に対して、クラスタ間の結合力ｆpqを以下で計算する（算出機能）。
【００８５】
【数１】
0005407169.tif 000002
【００８６】
ただし、この式において、ｎ（Ｃp）はクラスタＣp内のノード数、ｎ（Ｃq）はクラスタＣq内のノード数、ｄ（Ｃp）はクラスタＣpの次数（クラスタＣp内のノードとＣp以外のクラスタ内のノードを結ぶリンクの総数）、ｄ（Ｃq）はクラスタＣqの次数、ｌ（Ｃp，Ｃq）はクラスタＣp，Ｃq間を連結するリンク数である。また、ν、δ、λは調整用係数であり、それぞれ優先度を付けない場合は、ν＝δ＝λ＝１である。
【００８７】
（３−４）  各結合力ｆpqに基づいて、併合対象クラスタ対を決定する（決定機能）。たとえば、結合力ｆpqが一番大きいクラスタ対｛Ｃp，Ｃq｝を併合対象クラスタ対に決定する。
【００８８】
（３−５）  併合対象クラスタ対に決定されたクラスタ対｛Ｃp，Ｃq｝を一つのクラスタＣpqにマージする（併合機能）。このマージに際し、必要なグラフの変形を行う。結合力ｆpqが同じクラスタ対が複数ある場合は、任意に１つを選ぶものとする。
【００８９】
（３−６）  上記（３−２）から（３−５）をクラスタ数が望むｍ（＜ｎ）になるまで繰り返す（判断機能）。ｍは、アプリケーションで適当な値がわかっている場合はそれを用いればよい。ｍが小さすぎれば、絞込みの効果が少なくなり、一方ｍが大きすぎると、クラスタのサイズが小さくなり、検索対象がクラスタ間に跨る可能性が増える。したがって、それらのバランスをとった選択が一般的には望ましい。たとえば、平方根によりｍを特定してもよく（ｍ＝√ｎ）、クラスタの適切なサイズをｚとした場合、ｍ＝ｎ／ｚとしてもよい。
【００９０】
上記クラスタリング処理の流れの（３−４）で述べている必要なグラフの変形とは以下の操作である。クラスタ対｛Ｃp，Ｃq｝がクラスタＣpqにマージされるものとする。クラスタＣp，Ｃq以外のクラスタＣrからクラスタＣp，Ｃqへのリンクは、クラスタＣrからクラスタＣpqへのリンクと見なす。同様に、クラスタＣp，ＣqからクラスタＣrへのリンクはクラスタＣpqからクラスタＣrへのリンクと見なす。クラスタＣrからクラスタＣp，Ｃqへそれぞれｓ本、ｔ本のリンクがある場合、クラスタＣrとクラスタＣpqとの間には、ｓ＋ｔ本のリンクが残る。
【００９１】
クラスタＣpq内には、クラスタＣp，Ｃq内の部分グラフおよびクラスタＣp，Ｃq間のリンクからなる部分グラフが記憶される。クラスタは表面上は一つのノードに見えるため、これらの情報は、グラフ上では見えない。したがって、クラスタＣp，Ｃq間のリンクもマージによって見えなくなる。
【００９２】
なお、クラスタＣp，Ｃqをマージしても、クラスタＣp，Ｃq以外の任意のクラスタ間のリンク関係には変更は生じない。また、クラスタＣp，Ｃq以外の任意のクラスタＣrの次数にも変更は生じない。したがって、クラスタのすべての対に対して、結合力を一度計算した後は、クラスタリング処理の流れの（３−２）の未計算のクラスタ対とは、具体的には、マージされたクラスタＣpqおよびクラスタＣpqとリンクで繋がっているクラスタを意味する。
【００９３】
（クラスタリングの計算例）
図２１〜図２４は、クラスタリングの計算例を示す説明図である。それぞれ、（１）の初期段階から縮退して最終的に（７）の状態になる。図中の数字は、結合力をｆとしたとき、その逆数（１／ｆ）を示している。こうしているのは、ｆで示すと０以下の小数となってわかりにくく、図を簡略にするためである。
【００９４】
図２１および図２２は簡単な木状のネットワークの例を示している。図２１では調整用係数が、最も単純なν＝δ＝λ＝１であり、図２２はνだけν＝１．２とした例である。図２２では、期待通りのクラスタリングを行っている。図２２では、結合力が同じものが２つ現れるということはなかった。一方、図２１では、（４）の段階で、結合力の逆数が６のものが３つあり、その中で左のものを選択したため、期待通りのクラスタリングではない例になっている。右の２つのうちどちらかを選択すると図２２と同じ期待されるクラスタリングになる。
【００９５】
なお、同じ結合力のものの中から、最適なものを選ぼうとすると、グローバルな視点からの最適化が必要になり、コストを要する。このため、本実施の形態ではグローバルな最適化は行っていない。結合力の利点は、ローカルな情報から計算できることにある。なお、調整用係数を入れた理由は、ノード数、次数、リンク数がそれぞれ同じ重みではないはずであるという考えと、なるべく同じ数値が表れないようにするという狙いを含めている。
【００９６】
ν、λ、δは重み付けのパラメータであり、アプリケーションでこれらの値が明確であれば、それらを用いればよい。ただし、一般には、どう設定すればよいかわからない場合も多い。ν、λ、δについては、わからない場合は、それぞれほぼ１にしておく。ただし、上記の同じ数値が表れないようにすることを考慮して、若干異なるようにしておく。
【００９７】
図２３は簡単な回路を含むネットワークの例を示している。図２３では調整用係数を、最も単純なν＝δ＝λ＝１とし、図２４では２個の調整用係数ν，λを変えて、ν＝１．２、λ＝１．４とした。図２４では、期待通りのクラスタリングを行っているが、図２３では、（４）ですべての結合力の逆数が１６であり、その中で中の三角形の辺に当たる部分を選択したため、期待通りのクラスタリングではない例になっている。三角形の辺以外を選択すると、その後は、図２４と同様、期待されるクラスタリングになる。
【００９８】
図２１の（４）から（５）の段階、あるいは、図２３の（４）から（５）の段階のように、本方式が常に最適なクラスタリングを行うとは限らないが、図２１、図２２、図２４は、最終的に想定していた望ましい最適なクラスタリングになっている。図２３の最終的なクラスタリング結果は、最適なものに比べ、リンクの和が一つ多く、またバランスも少し悪いが、まずまずのクラスタリングになっている。
【００９９】
（情報検索処理）
つぎに、本実施の形態にかかる情報検索装置６００による情報検索処理について説明する。図２５は、本実施の形態にかかる情報検索装置６００による情報検索処理手順を示すフローチャートである。図２５では、クラスタリング処理部６０１によるクラスタリング処理（ステップＳ２５０１）、インデックス作成部６０２によるインデックス作成処理（ステップＳ２５０２）、入力処理部６０３による入力処理（ステップＳ２５０３）、クラスタ絞込み処理部６０４によるクラスタ絞込み処理（ステップＳ２５０４）、クラスタ内検索部６０５によるクラスタ内検索処理（ステップＳ２５０５）の順に実行される。
【０１００】
図２６は、クラスタリング処理の詳細な処理手順を示すフローチャートである。図２６において、まず、検索対象グラフ１００を読み込み（ステップＳ２６０１）、各ノードをそれぞれ包含するクラスタを生成する（ステップＳ２６０２）。検索対象グラフ１００内のノードの総数をｎ、クラスタの数をｋとすると、この段階では、ｋ＝ｎである。
【０１０１】
そして、未計算のクラスタ対があるか否かを判断する（ステップＳ２６０３）。未計算のクラスタ対がある場合（ステップＳ２６０３：Ｙｅｓ）、クラスタ対の結合力を算出する（ステップＳ２６０４）。そして、ステップＳ２６０３に戻る。一方、未計算のクラスタ対がない場合（ステップＳ２６０３：Ｎｏ）、最大結合力のクラスタ対を単一のクラスタにマージする（ステップＳ２６０５）。これにより、ｋの値はｋ＝ｋ−１となる。
【０１０２】
そして、ｋ＝ｍであるか否かを判断する（ステップＳ２６０６）。このｍは、望まれるクラスタ数である。ｋ＝ｍでない場合（ステップＳ２６０６：Ｎｏ）、ｋ＞ｍであるため、ステップＳ２６０３に戻る。一方、ｋ＝ｍである場合（ステップＳ２６０６：Ｙｅｓ）、インデックス作成処理（ステップＳ２５０２）に移行する。
【０１０３】
図２７は、クラスタ絞込み処理の詳細な処理手順を示すフローチャートである。図２７において、まず、問合せグラフ１１０により表現される条件を和積標準形に変換する（ステップＳ２７０１）。つぎに、変換により得られる条件ごとにノード・クラスタ識別子テーブルｎｃＷｉjを作成する（ステップＳ２７０２）。そして、各ノード・クラスタ識別子テーブルｎｃＷｉjに共通するクラスタを特定する（ステップＳ２７０３）。このあと、共通するクラスタごとにノード条件（たとえば、職種）を満たすノード識別子テーブルｎＷＣjを作成する（ステップＳ２７０４）。そして、クラスタ内検索処理（ステップＳ２５０５）に移行する。
【０１０４】
図２８は、クラスタ内検索処理の詳細な処理手順を示すフローチャートである。図２８において、まず、ノード条件を満たす未選択のノードがあるか否かを判断する（ステップＳ２８０１）。未選択のノードがある場合（ステップＳ２８０１：Ｙｅｓ）、ノード条件を満たすノードを選択する（ステップＳ２８０２）。
【０１０５】
そして、周辺探索処理を実行する（ステップＳ２８０３）。たとえば、問合せグラフ１１０によりノード数やリンク数、問合せグラフ１１０を構成するノードとリンクの連結関係がわかるため、選択ノードを中心として、問合せグラフ１１０とノード数、リンク数、連結関係が同一となるように部分グラフを探索する。そして、探索された部分グラフ（探索グラフ）を保存して（ステップＳ２８０４）、ステップＳ２８０１に戻る。
【０１０６】
一方、ステップＳ２８０１において、未選択のノードがない場合（ステップＳ２８０１：Ｎｏ）、問合せグラフ１１０の条件を満たす探索グラフを、ステップＳ２８０４で保存された探索グラフ群の中から抽出する（ステップＳ２８０５）。これにより、問合せグラフ１１０と一致または関連する部分グラフを検索結果として出力する。
【０１０７】
このように、本実施の形態によれば、近似的に検索することにより、グラフの検索を大幅に高速化することが期待できる。また、クラスタ間のリンク数を少なくするクラスタリング処理により、検索結果の精度を上げることが期待できる。
【０１０８】
また、クラスタ対を構成する各クラスタ内のノードの数の少なさに応じて高くなるように結合力を算出することで、包含するノード数が多いクラスタについては結合力が低くなる。したがって、そのようなクラスタの膨張（包含するノード数の増加）を抑制することで、適度な範囲で問合せグラフがマッチする解を得ることができる。
【０１０９】
また、クラスタ対を構成する各クラスタの次数の少なさに応じて高くなるように結合力を算出することで、検索対象グラフ内のハブとなるクラスタについては結合力が低くなる。したがって、ハブを回避することで、ハブ以外のクラスタ対から優先的に縮退させることができる。これにより、バランスよくクラスタリングをおこなうことができ、検索速度の向上を保ちつつ、検索精度の低下を抑制することができる。
【０１１０】
また、一のクラスタ内のノードと他のクラスタ内のノードとが連結するリンクの数の多さに応じて高くなるように結合力を算出することで、つながりの強いクラスタ対から優先的に縮退させることができる。
【０１１１】
また、結合力の算出に際し、ノードの数、次数、リンクの数について、調整用係数により重み付けをおこなうことにより、検索対象グラフの特徴やユーザの用途に応じてクラスタリング処理をカスタマイズすることができる。
【０１１２】
また、クラスタ対の集合の中から、結合力が最大となるクラスタ対を併合対象に決定することで、結びつきの強いクラスタ対から優先的に縮退させることができる。これにより、ハブとは正反対の末端のクラスタから優先的に縮退させることができ、問合せグラフにマッチする可能性があるクラスタの増加とマッチしないクラスタの低減化を同時に実現することができる。
【０１１３】
また、併合後のクラスタの数が所定数ｍに到達したか否かを判断し、所定数ｍに到達していないと判断された場合、併合後のクラスタの集合の中から、あらたにクラスタ対を抽出することで、クラスタ数を適切な数に抑制することができる。これにより、個々のクラスタの過剰な膨張を抑制することで、検索速度の向上を保ちつつ、検索精度の低下を抑制することができる。
【０１１４】
また、問合せグラフが有する条件に基づいて、併合後のクラスタの集合を絞り込み、絞り込まれたクラスタの集合の中から、前記問合せグラフと一致するグラフを検索することで、問合せグラフとマッチする可能性のあるクラスタを特定することができる。これにより、問合せグラフとマッチしないクラスタについての無駄な検索を抑制することができるため、検索速度の向上を図ることができる。
【０１１５】
以上のことから、実施の形態にかかる情報検索プログラム、情報検索装置、および情報検索方法によれば、問合せグラフにマッチする可能性のあるクラスタを絞り込むことにより、検索速度の向上を図ることができるという効果を奏する。
【０１１６】
なお、本実施の形態で説明した情報検索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な媒体であってもよい。
【０１１７】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１１８】
（付記１）ノードとノード間を連結するリンクからなる検索対象グラフの中から問合せグラフと一致するグラフを検索するコンピュータを、
前記検索対象グラフ内の互いに異なるノードを包含するクラスタの集合の中から、一のクラスタと当該一のクラスタ内のノードと前記リンクにより連結されるノードを包含する他のクラスタとからなるクラスタ対を抽出する抽出手段、
前記抽出手段によって抽出されたクラスタ対の結びつきの強さをあらわす結合力を前記クラスタ対ごとに算出する算出手段、
前記算出手段によって算出されたクラスタ対ごとの結合力に基づいて、前記クラスタ対の集合の中から、併合対象を決定する決定手段、
前記決定手段によって併合対象に決定されたクラスタ対を併合する併合手段、
前記併合手段による併合後のクラスタの集合の中から、前記問合せグラフと一致するグラフを検索する検索手段、
前記検索手段によって検索された検索結果を出力する出力手段、
として機能させることを特徴とする情報検索プログラム。
【０１１９】
（付記２）前記算出手段は、
前記クラスタ対を構成する各クラスタ内のノードの数の少なさに応じて高くなるように、前記結合力を算出することを特徴とする付記１に記載の情報検索プログラム。
【０１２０】
（付記３）前記算出手段は、
前記クラスタ対を構成する各クラスタ内のノードから他のクラスタ内のノードに連結するリンクの数の少なさに応じて高くなるように、前記結合力を算出することを特徴とする付記１または２に記載の情報検索プログラム。
【０１２１】
（付記４）前記算出手段は、
前記一のクラスタ内のノードと前記他のクラスタ内のノードとが連結するリンクの数の多さに応じて高くなるように、前記結合力を算出することを特徴とする付記１〜３のいずれか一つに記載の情報検索プログラム。
【０１２２】
（付記５）前記決定手段は、
前記クラスタ対の集合の中から、前記結合力が最大となるクラスタ対を前記併合対象に決定することを特徴とする付記１〜４のいずれか一つに記載の情報検索プログラム。
【０１２３】
（付記６）前記コンピュータを、
前記併合手段による併合後のクラスタの数が所定数に到達したか否かを判断する判断手段として機能させ、
前記抽出手段は、
前記判断手段によって前記所定数に到達していないと判断された場合、前記併合手段による併合後のクラスタの集合の中から、前記クラスタ対を抽出することを特徴とする付記１〜５のいずれか一つに記載の情報検索プログラム。
【０１２４】
（付記７）前記コンピュータを、
前記問合せグラフが有する条件に基づいて、前記併合手段による併合後のクラスタの集合を絞り込む絞込み処理手段として機能させ、
前記検索手段は、
前記絞込み処理手段によって絞り込まれたクラスタの集合の中から、前記問合せグラフと一致するグラフを検索することを特徴とする付記１〜６のいずれか一つに記載の情報検索プログラム。
【０１２５】
（付記８）ノードとノード間を連結するリンクからなる検索対象グラフの中から問合せグラフと一致するグラフを検索する情報検索装置であって、
前記検索対象グラフ内の互いに異なるノードを包含するクラスタの集合の中から、一のクラスタと当該一のクラスタ内のノードと前記リンクにより連結されるノードを包含する他のクラスタとからなるクラスタ対を抽出する抽出手段と、
前記抽出手段によって抽出されたクラスタ対の結びつきの強さをあらわす結合力を前記クラスタ対ごとに算出する算出手段と、
前記算出手段によって算出されたクラスタ対ごとの結合力に基づいて、前記クラスタ対の集合の中から、併合対象を決定する決定手段と、
前記決定手段によって併合対象に決定されたクラスタ対を併合する併合手段と、
前記併合手段による併合後のクラスタの集合の中から、前記問合せグラフと一致するグラフを検索する検索手段と、
前記検索手段によって検索された検索結果を出力する出力手段と、
を備えることを特徴とする情報検索装置。
【０１２６】
（付記９）ノードとノード間を連結するリンクからなる検索対象グラフの中から問合せグラフと一致するグラフを検索する情報検索方法であって、
前記検索対象グラフ内の互いに異なるノードを包含するクラスタの集合の中から、一のクラスタと当該一のクラスタ内のノードと前記リンクにより連結されるノードを包含する他のクラスタとからなるクラスタ対を抽出する抽出工程と、
前記抽出工程によって抽出されたクラスタ対の結びつきの強さをあらわす結合力を前記クラスタ対ごとに算出する算出工程と、
前記算出工程によって算出されたクラスタ対ごとの結合力に基づいて、前記クラスタ対の集合の中から、併合対象を決定する決定工程と、
前記決定工程によって併合対象に決定されたクラスタ対を併合する併合工程と、
前記併合工程による併合後のクラスタの集合の中から、前記問合せグラフと一致するグラフを検索する検索工程と、
前記検索工程によって検索された検索結果を出力する出力工程と、
を含んだことを特徴とする情報検索方法。
【図面の簡単な説明】
【０１２７】
【図１】クラスタリングを用いた検索の概要を示す説明図である。
【図２】クラスタリング例を示す説明図（その１）である。
【図３】クラスタリング例を示す説明図（その２）である。
【図４】検索対象グラフおよび問合せグラフの一例を示す説明図である。
【図５】この発明の実施の形態にかかる情報検索装置のハードウェア構成を示すブロック図である。
【図６】情報検索装置の機能的構成を示すブロック図である。
【図７】図４の検索対象グラフに対応する企業データを示すテーブルである。
【図８】出資元と出資先との関係を示すテーブルである。
【図９】クラスタリング結果を示す説明図である。
【図１０】分割ノードテーブルを示す説明図である。
【図１１】分割リンクテーブルを示す説明図である。
【図１２】クラスタの識別子付与後のノードテーブルを示す説明図である。
【図１３】ユーザインターフェースを示す説明図である。
【図１４】図１３に示したグラフ問合せ入力領域を示す説明図である。
【図１５】ノード・クラスタ識別子テーブルを示す説明図である。
【図１６】クラスタ識別子テーブルを示す説明図である。
【図１７】ノード識別子テーブルを示す説明図である。
【図１８】ネットワークを示す説明図である。
【図１９】スケールフリーを示すグラフである。
【図２０】図１８に示したネットワークの分解例を示す説明図である。
【図２１】クラスタリングの計算例を示す説明図（その１）である。
【図２２】クラスタリングの計算例を示す説明図（その２）である。
【図２３】クラスタリングの計算例を示す説明図（その３）である。
【図２４】クラスタリングの計算例を示す説明図（その４）である。
【図２５】本実施の形態にかかる情報検索装置による情報検索処理手順を示すフローチャートである。
【図２６】クラスタリング処理の詳細な処理手順を示すフローチャートである。
【図２７】クラスタ絞込み処理の詳細な処理手順を示すフローチャートである。
【図２８】クラスタ内検索処理の詳細な処理手順を示すフローチャートである。
【符号の説明】
【０１２８】
１００  検索対象グラフ
１１０  問合せグラフ
６００  情報検索装置
６０１  クラスタリング処理部
６０２  インデックス作成部
６０３  入力処理部
６０４  クラスタ絞込み処理部
６０５  クラスタ内検索部
【図１】
0005407169.tif 000003
【図２】
0005407169.tif 000004
【図３】
0005407169.tif 000005
【図４】
0005407169.tif 000006
【図５】
0005407169.tif 000007
【図６】
0005407169.tif 000008
【図７】
0005407169.tif 000009
【図８】
0005407169.tif 000010
【図９】
0005407169.tif 000011
【図１０】
0005407169.tif 000012
【図１１】
0005407169.tif 000013
【図１２】
0005407169.tif 000014
【図１３】
0005407169.tif 000015
【図１４】
0005407169.tif 000016
【図１５】
0005407169.tif 000017
【図１６】
0005407169.tif 000018
【図１７】
0005407169.tif 000019
【図１８】
0005407169.tif 000020
【図１９】
0005407169.tif 000021
【図２０】
0005407169.tif 000022
【図２１】
0005407169.tif 000023
【図２２】
0005407169.tif 000024
【図２３】
0005407169.tif 000025
【図２４】
0005407169.tif 000026
【図２５】
0005407169.tif 000027
【図２６】
0005407169.tif 000028
【図２７】
0005407169.tif 000029
【図２８】
0005407169.tif 000030