(57)【要約】【課題】ノード間の関連性を示せるクラスタを生成する。【解決手段】アークスコア設定部１４が、関心度に応じたアークスコアをグラフＧに設定し（Ｓ１１）、ノードスコア計算部１５が、そのアークスコアを基にして、そのグラフのノードスコアを計算し（Ｓ１３）、クラスタ生成部１６が、計算されたノードスコアを基にして、グラフＧのクラスタを生成する（Ｓ１５）。【選択図】図５
2008181333.tif 000002
【特許請求の範囲】
【請求項１】
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算するノードスコア計算手段と、
前記計算されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備えることを特徴とするクラスタ生成装置。
【請求項２】
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定される関心度に応じたアークスコアが設定され、当該アークスコアを基にして、前記グラフのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段と、
指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定するノードスコア設定手段と、
前記設定されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備えることを特徴とするクラスタ生成装置。
【請求項３】
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算する第１のノードスコア計算手段と、
前記ノードスコアを基にして、前記グラフの一部を削除するグラフ処理手段と、
一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算する第２のノードスコア計算手段と、
当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備えることを特徴とするクラスタ生成装置。
【請求項４】
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定される関心度に応じたアークスコアが設定され、当該アークスコアを基にして、前記グラフのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段と、
指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定するノードスコア設定手段と、
前記設定されたノードスコアを基にして、前記グラフの一部を削除するグラフ処理手段と、
一部を削除された前記グラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算するノードスコア計算手段と、
当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備えることを特徴とするクラスタ生成装置。
【請求項５】
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのサブグラフを検索する際に用いられるパターンが記憶されるパターンデータベースと、
指定された条件にマッチするパターンを検索するパターン検索手段と、
検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記サブグラフのノードについてのノードスコアを計算するノードスコア計算手段と、
前記ノードスコアを基にして、前記サブグラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備えることを特徴とするクラスタ生成装置。
【請求項６】
指定される関心度に対応する関心項目に対応づけて予めラベルが記憶されるラベル記憶手段を備え、
前記アークスコア設定手段は、指定された関心度に対応する関心項目に前記ラベル記憶手段で対応づけられたラベルをもつアークに、当該指定された関心度に応じたアークスコアを設定する
ことを特徴とする請求項１、３、４、５のいずれかに記載のクラスタ生成装置。
【請求項７】
請求項１記載のクラスタ生成装置の前記アークスコア設定手段が、前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置の前記ノードスコア計算手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置の前記クラスタ生成手段が、前記計算されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
ことを特徴とするクラスタ生成方法。
【請求項８】
請求項２記載のクラスタ生成装置の前記ノードスコア設定手段が、指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定し、
当該クラスタ生成装置のクラスタ生成手段が、前記設定されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
ことを特徴とするクラスタ生成方法。
【請求項９】
請求項３記載のクラスタ生成装置の前記アークスコア設定手段が、前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置の第１のノードスコア計算手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置のグラフ処理手段が、前記ノードスコアを基にして、前記グラフの一部を削除し、
当該クラスタ生成装置の第２のノードスコア計算手段が、一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
ことを特徴とするクラスタ生成方法。
【請求項１０】
請求項４記載のクラスタ生成装置の前記ノードスコア設定手段が、指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定し、
当該クラスタ生成装置のグラフ処理手段が、前記設定されたノードスコアを基にして、前記グラフの一部を削除し、
当該クラスタ生成装置のアークスコア設定手段が、一部を削除された前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置のノードスコア計算手段が、一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
ことを特徴とするクラスタ生成方法。
【請求項１１】
請求項５記載のクラスタ生成装置の前記パターン検索手段が、指定された条件にマッチするパターンを前記パターンデータベースから検索し、
当該クラスタ生成装置のアークスコア設定手段が、検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置のノードスコア計算手段が、前記アークスコアを基にして、前記サブグラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、前記ノードスコアを基にして、前記サブグラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
ことを特徴とするクラスタ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフのクラスタを生成するクラスタ生成装置およびクラスタ生成方法に関するものである。
【背景技術】
【０００２】
インスタンスをもつノード間がアークによって接続されたグラフまたはそのサブグラフを分割したものをクラスタといい、クラスタは、その中ではノードのインスタンス同士が類似し、クラスタが異なればノードのインスタンス同士が類似しないように生成される。
【０００３】
この出願の発明に関連する先行技術文献情報としては下記のものがある。
【０００４】
非特許文献１では、サブグラフを検索する技術を開示している。グラフはＲＤＦで表現され、検索にはクエリが使用される。
【０００５】
非特許文献２では、クラスタを生成する技術を開示している。クラスタ生成には、エッジの密度の差異が用いられる。
【０００６】
非特許文献３では、サブグラフを検索する技術を開示している。ここでは、グラフは重み付きグラフであり、ノードのオーソリティ値とハブ値をＨＩＴＳアルゴリズムで計算する。そして、複数の情報のそれぞれをもつノード間にあるパスで、しかもそのパスを構成するノードについて計算された値がしきい値以上のものを検索する。
【０００７】
非特許文献４では、指定されたシードのウェブページと周辺のウェブページを収集し、それらのグラフを生成する。そして、そのグラフのノードのオーソリティ値とハブ値をＨＩＴＳアルゴリズムで計算し、その値が上位のウェブページがグラフの中心的なノード（コア）であることとする。
【非特許文献１】"SPARQL Query Language for RDF", [online], インターネット＜ＵＲＬ：http://www.w3.org/TR/rdf-sparql-query/＞
【非特許文献２】M.E..J.Newman, "Detecting community structure in networks", Europian Physical Journal B, 38:321-330, 2004
【非特許文献３】S.Mukherjea, B. Bamba, "BioPatentMiner: an information retrieval system for biomedical patents", VLDB, 2004
【非特許文献４】D.Gibson, J. Kleinberg, and P.Paghavan, "Inferring web communities from link topology", ACM Conf. on Hypertext and Hypermedia, 1998
【発明の開示】
【発明が解決しようとする課題】
【０００８】
非特許文献１に記載の技術では、１つのサブグラフを検索するだけなので、複数の情報の関連性を示せない。また、グラフ構造の知識が必要である。
【０００９】
非特許文献２に記載の技術では、クラスタを生成できるが、複数の情報の関連性を示せない。また、関心の対象が考慮されない。
【００１０】
非特許文献３に記載の技術では、検索できるのはパスなので、複数の情報の関連性を十分に示せない。
【００１１】
非特許文献４に記載の技術では、生成されるのは、シードを中心とした１つのグラフ（クラスタ）だけなので、複数の情報の関連性を示せない。また、関心の対象が考慮されない。
【００１２】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、グラフからそのノード間の関連性を示せるクラスタを生成できるクラスタ生成装置およびクラスタ生成方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明では、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフまたはそのサブグラフのアークに、指定された関心度に応じたアークスコアを設定し、そのアークスコアを基にして、グラフなどのノードについてのノードスコアを計算し、計算されたノードスコアを基にして、グラフなどのクラスタを生成する。
【発明の効果】
【００１４】
本発明によれば、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。
【００１６】
［第１の実施の形態］
図１は、第１の実施の形態に係るクラスタ生成装置１Ａの構成図である。
【００１７】
クラスタ生成装置１Ａは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００１８】
クラスタ生成装置１Ａは、有向グラフであるグラフＧを表示するためのデータ群が記憶されたグラフデータベース１１と、ユーザ端末２で入力操作をさせるための入力用インタフェースを生成する入力用インタフェース生成部１２と、ユーザ端末２のユーザの関心の対象として想定された項目（関心項目という）に対応づけて、その関心項目に関連するラベルを記憶したラベル記憶部１３と、グラフＧのアークにスコア（アークスコアという）を設定するアークスコア設定部１４と、そのグラフＧのノードについてスコア（ノードスコアという）を計算するノードスコア計算部１５と、そのグラフＧからクラスタを生成するクラスタ生成部１６と、データベースインタフェース１７と、処理結果を伝えるための出力用インタフェースを生成する出力用インタフェース生成部１８とを備える。
【００１９】
クラスタは、グラフＧの一部を分割して得られた各部分と同じものである。分割して得られるものなので、クラスタ同士では重複がない。また、サブグラフ内では分離している部分がないから、クラスタ内でも同様である。クラスタは、その中ではノードのインスタンス同士が類似し、クラスタが異なればノードのインスタンス同士が類似しないように生成される。
【００２０】
クラスタ生成装置１Ａは、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをクラスタ生成装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。他の実施の形態でも同様である。
【００２１】
図２は、グラフデータベース１１に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２２】
グラフデータベース１１に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１１に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２３】
グラフＧでは、例えば、「ＸＭＬ」や「Ｂプロジェクト」などのインスタンスをもつノードが、「ｒｍ：技術キーワード」や「ｒｍ：著者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「Ｐｅｒｓｏｎ：山田太郎」などの概念であるクラス「Ｐｅｒｓｏｎ：人」などが定義される。
【００２４】
図３は、グラフデータベース１１に記憶されたデータ群の一部を例示した図である。
【００２５】
例えば、最初のデータ「＜ｏｒｇ：Ｄプロジェクト＞＜ｒｍ：技術キーワード＞”ＸＭＬ”」は、インスタンス「ｏｒｇ：Ｄプロジェクト」をもつノードからインスタンス「ＸＭＬ」のノードへ向かうアークがラベル「ｒｍ：技術キーワード」をもつことを示している。また、例えば、最後のデータ「＜ｐｅｒｓｏｎ：鈴木花子＞＜ｒｄｆ：ｔｙｐｅ＞＜Ｐｅｒｓｏｎ：人＞」は、インスタンス「ｐｅｒｓｏｎ：鈴木花子」をもつノードのクラスが「ｐｅｒｓｏｎ：人」であることを示している。
【００２６】
なお、各データは、実際にはＲＤＦ（以下の文献に記載）で表現されている。
【００２７】
「Resource Description Framework(RDF)Model and Syntax Specification」, Ora Lassia, Ralph R.Swick編,[online], インターネット<URL:http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/>
「RDF Vocabulary Description Language 1.0: RDF Schema」, Dan Brickley, R.V.Guha編,[online], インターネット<URL:http://www.w3.org/TR/rdf-schema/>
図４は、ラベル記憶部１３の記憶内容を示す図である。
【００２８】
例えば、関心項目「所属」には、ラベル「ｐｅｒｓｏｎ：所属」、ラベル「ｒｍ：学会ＫＷ」、ラベル「ｒｍ：会員」が対応づけられている。
【００２９】
また、関心項目「学術論文」には、ラベル「ｒｍ：著者」、ラベル「ｒｍ：著者ＫＷ」が対応づけられている。
【００３０】
また、関心項目「サービス開発」には、ラベル「ｍｓ：ＫＷ」、ラベル「ｍｓ：担当者」、ラベル「ｍｓ：参考文献」、ラベル「ｍｓ：著者」が対応づけられている。
【００３１】
かかるラベルは、対応する関心項目に関連するものとして、グラフＧのラベルから選択されたものである。
【００３２】
（第１の実施の形態の動作）
図５は、第１の実施の形態のシーケンス図である。
【００３３】
クラスタ生成装置１Ａでは、入力用インタフェース生成部１２が、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６に示したように表示させる（Ｓ３）。ここでの操作により特定された１以上のキーワードＫＷと１以上のクラスＣＬの一方または両方、各関心項目の関心度（大、中、小のいずれか）の組合せ、並びに、しきい値ＴＨをユーザ端末２がクラスタ生成装置１Ａに送信する（Ｓ５）。しきい値ＴＨは、これを例えば低く設定して、ノードを多く含むクラスタを表示させるためのものである。なお、これらのキーワードＫＷなどは、クラスタ生成装置１Ａに記憶しておき、それを適宜読み出して使用してもよい。
【００３４】
（アークスコア設定）
クラスタ生成装置１Ａは、アークスコア設定部１４が、グラフＧのアークにアークスコアを設定する（Ｓ１１）。具体的には、アークスコアを含むクエリをデータベースインタフェース１７に送信する（Ｓ１１１）ことで、アークスコアが設定されたグラフＧを取得する（Ｓ１１２）。
【００３５】
例えば、関心項目「所属」にラベル記憶部１３で対応づけられたラベル「ｐｅｒｓｏｎ：所属」、ラベル「ｒｍ：学会ＫＷ」、ラベル「ｒｍ：会員」に対し、関心項目「所属」の関心度に応じたアークスコアを設定する。
【００３６】
また、関心項目「学術論文」にラベル記憶部１３で対応づけられたラベル「ｒｍ：著者」、ラベル「ｒｍ：著者ＫＷ」に対し、関心項目「学術論文」の関心度に応じたアークスコアを設定する。
【００３７】
また、関心項目「サービス開発」にラベル記憶部１３で対応づけられたラベル「ｍｓ：ＫＷ」、ラベル「ｍｓ：担当者」、ラベル「ｍｓ：参考文献」、ラベル「ｍｓ：著者」に対し、関心項目「サービス開発」の関心度に応じたアークスコアを設定する。
【００３８】
例えば、関心度が「大」の場合はアークスコア「１．０」を設定し、関心度が「中」の場合はアークスコア「０．１」を設定し、関心度が「小」の場合はアークスコア「０．０１」を設定する。なお、関心度を数値とし、その数値である関心度に相関するアークスコアを設定してもよい。
【００３９】
そのグラフＧの各ノードのインスタンスをそのノードのクラスに置き換え、同一のインスタンス（クラス）をもつノードではその中の１つのみ残し、そのようにしてなるグラフに上記の各アークスコアを当てはめると、その一部は、例えば図７のようになる。
【００４０】
（ノードスコア計算）
次に、クラスタ生成装置１Ａは、ノードスコア計算部１５が、グラフＧのノードのスコア（ノードスコアという）を計算する（Ｓ１３）。
【００４１】
図８は、ノードスコア計算のフローチャートを示す図である。かかる計算は、アークスコアを基にしたものであり、リンク解析ともいう。
【００４２】
ノードスコア計算部１５は、まず、グラフＧのノードに、その重要度を示すこととなる、ノードスコアの初期値「１」を設定する（Ｓ１０１）。
【００４３】
次に、各ノードにつき、例えば、PageRankのアルゴリズムを用いた、図９の式により、ノードスコアを計算する（Ｓ１０３）。
【００４４】
そして、このノードスコアで、グラフＧに設定されたノードスコアの初期値を更新する（Ｓ１０５）。このような計算更新を、ノードスコアが収束するまで、再帰的に行う。これにより、ノードスコアが重要度を示すこととなる。
【００４５】
グラフＧに各アークスコアを当てはめたグラフの一部が、例えば図１０に示すようなものであった場合、同図に示すように、例えば、インスタンス「ＸＭＬ」をもつノードのノードスコアは０．４となる。インスタンス「Person:電々三郎」をもつノードのノードスコアは０．９となる。インスタンス「org:H3G」をもつノードのノードスコアは０．６となる。
【００４６】
次に、クラスタ生成装置１Ａは、クラスタ生成部１６が、グラフＧからクラスタを生成する（Ｓ１５）。ここでは、グラフＧでキーワードＫＷに等しいインスタンスをもつノードまたはグラフＧでクラスＣＬが定義されたノードである各ノードにつき、そのノード（キーノードという）を含むクラスタを生成する。キーノードと同数のクラスタが生成される。
【００４７】
図１１は、１つのクラスタを生成するフローチャートを示す図であり、このフローチャートによるクラスタ生成が各キーノードについて同時に行われる。
【００４８】
まず、クラスタ生成部１６は、グラフＧから所定条件を満たさないノードを除外する（Ｓ２０１）。ここでは、キーノードを起点とし、起点に単一のアークで接続されたノードであり且つしきい値以下のノードスコアをもつノードを除外する（Ｓ２０１）。次に、除外されなかったノードを候補としてこれををクラスタに含める又は除外する処理を１候補づつ行うのだが、まず、未処理である１つの候補が、他のクラスタ生成でも候補になっているか否かを判定する（Ｓ２０３）。ＮＯと判定された場合は、候補を本クラスタ生成に係るクラスタに含める（Ｓ２０５）。一方、ＹＥＳと判定された場合は、候補と本クラスタ生成に係るキーノードとの間のアーク数、候補と他のクラスタ生成に係るキーノードとの間のアーク数を計算し、それらの中で本クラスタ生成に係るアーク数が最大であるか否かを判定する（Ｓ２０７）。ＮＯと判定された場合は、候補を本クラスタ生成の候補から除外する（Ｓ２０９）。ＹＥＳと判定された場合は、候補と他のクラスタ生成に係るキーノードとの間のアーク数の中で、候補と本クラスタ生成に係るキーノードとの間のアーク数と同数のものがあるか否かを判定する（Ｓ２１１）。つまり、他にもアーク数が最大のものがあるか否かを判定する（Ｓ２１１）。ＮＯと判定された場合は、候補を本クラスタ生成に係るクラスタに含める（Ｓ２０５）。ＹＥＳと判定された場合は、候補のノードスコアとその候補の本クラスタ生成に係る起点のノードスコアとの差分、候補のノードスコアとその候補の他のクラスタ生成に係る起点のノードスコアとの差分を計算し、その中で本クラスタ生成に係る差分が最小か否かを判定する（Ｓ２１３）。ＮＯと判定された場合は、候補を本クラスタ生成に係るクラスタに含め候補から除外する（Ｓ２０９）。ＹＥＳと判定された場合は、候補を本クラスタ生成に係るクラスタに含める（Ｓ２０５）。
【００４９】
ステップＳ２０５、Ｓ２０５を行ったら、次に、未処理の候補があるか否かを判定する（Ｓ２１５）。ＹＥＳと判定された場合は、ステップＳ２０３に戻る。ＮＯと判定された場合は、クラスタに含められたノードの１つを新たな起点とし（Ｓ２１７）、ステップＳ２０１に戻る。そのステップＳ２０１では、その新たな起点に単一のアークで接続されたノードであり且つしきい値以下のノードスコアをもつノードを除外する（Ｓ２０１）。
【００５０】
なお、ある起点に単一のアークで接続されたノードからクラスタに含ませられたものが複数あり（便宜的にノードｎ１１，ｎ１２という）、その中の１つ（ノードｎ１１とする）が新たな起点となって、その起点に単一のアークで接続されたノード（ノードｎ１１１という）がクラスタに含ませられた場合は、ノードｎ１１１よりもノードｎ１２が先に起点となる。
【００５１】
図１２は、２つのクラスタが生成された様子を示す図であり、アークの矢印とラベル、ノードのインスタンスについては、記載省略している。
【００５２】
同図に示すように、ノードＩ１とキーノードＫＩ１との間のアーク数は「３」であり、ノードＩ１とキーノードＫＩ２との間のアーク数は「２」であるから、ノードＩ１は、キーノードＫＩ１を含むクラスタＣ１でなく、キーノードＫＩ２を含むクラスタＣ２に含められる。
【００５３】
また、同図に示すように、ノードＩ２とキーノードＫＩ１との間のアーク数は「２」であり、ノードＩ２とキーノードＫＩ２との間のアーク数は「２」である。また、ノードＩ２のノードスコア「０．６」とクラスタＣ１に係る起点Ｉ３のノードスコア「０．９」との差分は「０．３」であり、ノードＩ２のノードスコア「０．６」とクラスタＣ２に係る起点Ｉ４のノードスコア「０．８」との差分は「０．２」であるから、ノードＩ２はクラスタＣ２に含められる。
【００５４】
次に、図５に戻り、出力用インタフェース生成部１８が、生成された各クラスタの出力用インタフェースを生成し、これをユーザ端末２に送信し（Ｓ１９）、各クラスタを表示させる（Ｓ２１）。
【００５５】
第１の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフＧのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段（アークスコア設定部１４）と、そのアークスコアを基にして、グラフＧのノードについてのノードスコアを計算するノードスコア計算手段（ノードスコア計算部１５）と、その計算されたノードスコアを基にして、グラフＧのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段（クラスタ生成部１６）とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【００５６】
また、キーノード以外のノード（中間ノード）についてのノードスコアを用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【００５７】
また、図１１のステップＳ２０７、Ｓ２１１、Ｓ２１３を行うので、ノード間の関連性を示せるクラスタを生成することができる。
【００５８】
また、関心度に応じたアークスコアを設定するので、関心度に適したクラスタを生成することができる。
【００５９】
また、ラベル記憶部１３において、関心項目に対応づけて予めラベルを記憶させ、指定された関心度に対応する関心項目に対応づけられたラベルをもつアークに、当該関心度に応じたアークスコアを設定するので、関心度に応じたクラスタを生成することができる。［第２の実施の形態］
図１３は、第２の実施の形態に係るクラスタ生成装置１Ｂの構成図である。
【００６０】
クラスタ生成装置１Ｂは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００６１】
クラスタ生成装置１Ｂは、グラフデータベース１１と、入力用インタフェース生成部１２と、ノードスコア記憶部１３Ａと、ノードスコア設定部１４Ａと、クラスタ生成部１６と、データベースインタフェース１７と、出力用インタフェース生成部１８とを備える。
【００６２】
本実施の形態では、予め関心度の組合せのそれぞれにつき、図１０に示したようなノードスコアが計算され、ノードスコア記憶部１３Ａが、組合せに対応づけてノードスコアを記憶している。
【００６３】
（第２の実施の形態の動作）
図１４は、第２の実施の形態のシーケンス図である。
【００６４】
ステップＳ５までは、第１の実施の形態と同様である。
【００６５】
続いて、ノードスコア設定部１４Ａは、ユーザ端末２から送信された関心度の組合せに対応するノードスコアを選択し（Ｓ１１Ａ）、それをグラフＧのノードに設定する（Ｓ１１Ｂ）。具体的には、ノードスコアを含むクエリをデータベースインタフェース１７に送信する（Ｓ１１５）ことで、ノードスコアが設定されたグラフを取得する（Ｓ１１６）。
【００６６】
そして、第１の実施の形態と同様に、そのノードスコアを設定したグラフからクラスタを生成する（Ｓ１５）。以降も、第１の実施の形態と同様である。
【００６７】
第２の実施の形態によれば、グラフＧのアークに、指定される関心度に応じたアークスコアが設定され、そのアークスコアを基にして、グラフＧのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段（ノードスコア記憶部１３Ａ）と、指定された関心度に対応づけてノードスコア記憶手段（１３Ａ）に記憶されたノードスコアをグラフＧに設定するノードスコア設定手段（ノードスコア設定部１４Ａ）と、設定されたノードスコアを基にして、グラフＧのクラスタを生成するクラスタ生成手段（１６）とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【００６８】
また、関心度の組合せに対応するノードスコアを選択するので、関心度の組合せに適したクラスタを生成することができる。
【００６９】
［第３の実施の形態］
図１５は、第３の実施の形態に係るクラスタ生成装置１Ｃの構成図である。
【００７０】
クラスタ生成装置１Ｃは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００７１】
クラスタ生成装置１Ｃは、グラフデータベース１１と、入力用インタフェース生成部１２と、ラベル記憶部１３と、アークスコア設定部１４と、ノードスコア計算部１５と、クラスタ生成部１６と、データベースインタフェース１７と、出力用インタフェース生成部１８と、グラフ処理部１９とを備える。
【００７２】
図１６は、第３の実施の形態のシーケンス図である。
【００７３】
予めクラスタ生成装置１Ｃにしきい値ＴＨＳが設定される。しきい値ＴＨＳは、経験的にしきい値ＴＨより低くなるように設定される。
【００７４】
ステップＳ１３までは、第１の実施の形態と同様である。
【００７５】
続いて、グラフ処理部１９が、そのグラフの一部を削除する（Ｓ１４Ａ）。ここでは、いずれかのキーノードに少なくとも１つのアークで接続され且つしきい値ＴＨＳより大きいノードスコアをもつノードを検出し、それ以外のノードとそのノードに接続されたアークを削除する。
【００７６】
そして、そのグラフについてステップＳ１３と同様のノードスコア計算を行う（Ｓ１４Ｂ）。以降も、第１の実施の形態と同様である。
【００７７】
第３の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフＧのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段（１４）と、そのアークスコアを基にして、グラフＧのノードについてのノードスコアを計算する第１のノードスコア計算手段（ステップＳ１３が該当する）と、そのノードスコアを基にして、グラフＧの一部を削除するグラフ処理手段（グラフ処理部１９）と、一部を削除されたグラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算する第２のノードスコア計算手段（ステップＳ１４Ｂが該当する）と、そのノードスコアを基にして、グラフＧのクラスタを生成するクラスタ生成手段（１６）とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【００７８】
また、キーノードを含む部分以外を削除した後のグラフでノードスコアを計算するので、キーノードを含む部分でのノード間の関連性を示せるクラスタを生成することができる。
【００７９】
［第４の実施の形態］
図１７は、第４の実施の形態に係るクラスタ生成装置１Ｄの構成図である。
【００８０】
クラスタ生成装置１Ｄは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００８１】
クラスタ生成装置１Ｄは、グラフデータベース１１と、入力用インタフェース生成部１２と、ラベル記憶部１３と、ノードスコア記憶部１３Ａと、アークスコア設定部１４、ノードスコア設定部１４Ａと、ノードスコア計算部１５と、クラスタ生成部１６と、データベースインタフェース１７と、出力用インタフェース生成部１８と、グラフ処理部１９とを備える。
【００８２】
（第４の実施の形態の動作）
第４の実施の形態では、クラスタ生成装置１Ｄに、しきい値ＴＨより低くなるようにしきい値ＴＨＳが予め設定される。
【００８３】
図１８は、第４の実施の形態のシーケンス図である。
【００８４】
ステップＳ１１Ｂまでは、第２の実施の形態と同様である。
【００８５】
続いて、グラフ処理部１９が、第３の実施の形態と同様なしきい値ＴＨＳを用いた判定により、そのグラフの一部を削除する（Ｓ１４Ａ）。そして、一部を削除したグラフについて、第１の実施の形態のステップＳ１１と同様なアークスコア設定を行い（Ｓ１２）、続いて、当該グラフについて、第１の実施の形態のステップＳ１３と同様なノードスコア計算を行う（Ｓ１４Ｂ）。以降も、第１の実施の形態と同様である。
【００８６】
第４の実施の形態によれば、グラフＧのアークに、指定される関心度に応じたアークスコアが設定され、そのアークスコアを基にして、グラフＧのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段（１３Ａ）と、指定された関心度に対応づけてノードスコア記憶手段（１３Ａ）に記憶されたノードスコアをグラフＧに設定するノードスコア設定手段（１４Ａ）と、その設定されたノードスコアを基にして、グラフの一部を削除するグラフ処理手段（１９）と、一部を削除されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段（１４）と、一部を削除されたグラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算するノードスコア計算手段（１５）と、そのノードスコアを基にして、グラフＧのクラスタを生成するクラスタ生成手段（１６）とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【００８７】
また、関心度の組合せに対応するノードスコアを選択するので、関心度の組合せに適したクラスタを生成することができる。
【００８８】
また、キーノードを含む部分以外を削除した後のグラフでノードスコアを計算するので、キーノードを含む部分でのノード間の関連性を示せるクラスタを生成することができる。
【００８９】
［第５の実施の形態］
図１９は、第５の実施の形態に係るクラスタ生成装置１Ｅの構成図である。
【００９０】
グラフ検索装置１Ｅは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００９１】
クラスタ生成装置１Ｅは、グラフデータベース１１と、パターンデータベース１１Ａと、入力用インタフェース生成部１２と、ラベル記憶部１３と、アークスコア設定部１４と、パターン検索部１４Ｂと、ノードスコア計算部１５と、クラスタ生成部１６と、データベースインタフェース１７と、出力用インタフェース生成部１８とを備える。
【００９２】
パターンデータベース１１Ａには、グラフＧからサブグラフを検索するためのパターンが記憶される。
【００９３】
（パターンの説明）
ここでパターンについて説明する。
【００９４】
パターンは、グラフデータベース１１に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを図２０のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。パスパターンはパスを検索するパターンであり、サブグラフパターンはサブグラフを検索するものである。
【００９５】
パスパターンは、例えば、同図のようなグラフ（パス）である。
【００９６】
パターンはグラフと同様に、実際にはデータ群であるが、それを逐一説明するのは冗長であるから、パターンの説明はグラフ化されたもので行う。
【００９７】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、同図に示すように、？とそれに後続する単語からなる。
【００９８】
また、一般的にパターンでは、必要があれば、変数が設定された一部のノードに、そのパターンにより検索されるグラフにおける、同位置のノードがもつインスタンスの上位概念を示すクラスが予め定義される。
【００９９】
同図のパスパターンでは、キーワードＫＷ「セマンティックｗｅｂ」がインスタンスであるノードを一方端とすると、他方端のノードにクラスＣＬ「Ｐｅｒｓｏｎ：人」が定義されている。
【０１００】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【０１０１】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、（４）場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。
【０１０２】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【０１０３】
図２１は、第５の実施の形態のシーケンス図である。
【０１０４】
ステップＳ５までは、第１の実施の形態と同様である。
【０１０５】
次に、キーワードＫＷに等しいインスタンスをもつノードをもつパターンや、グラフＧでクラスＣＬが定義されたノードのインスタンスに等しいインスタンスをもつノードをもつパターンや、その両方をもつパターンを検索する（Ｓ１１Ｃ）。
【０１０６】
次に、アークスコア設定部１４が、グラフＧでそのパターンにマッチするサブグラフにおけるアークに対し、第１の実施の形態のステップＳ１１と同様に、アークスコアを設定する（Ｓ１２）。具体的には、パターンの内容やアークスコアを含むクエリをデータベースインタフェース１７に送信する（Ｓ１２Ａ）ことで、グラフＧでそのパターンにマッチするサブグラフであってアークスコアが設定されたグラフを取得する（Ｓ１２Ｂ）。
【０１０７】
そして、そのグラフについて、第１の実施の形態と同様のノードスコア計算を行う（Ｓ１３）。以降も、第１の実施の形態と同様である。
【０１０８】
第５の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフＧのサブグラフを検索する際に用いられるパターンが記憶されるパターンデータベース１１Ａと、指定された条件にマッチするパターンを検索するパターン検索手段（パターン検索部１４Ｂ）と、検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段（１４）と、そのアークスコアを基にして、サブグラフのノードについてのノードスコアを計算するノードスコア計算手段（１５）と、そのノードスコアを基にして、サブグラフのクラスタを生成するクラスタ生成手段（１６）とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
【図面の簡単な説明】
【０１０９】
【図１】第１の実施の形態に係るクラスタ生成装置１Ａの構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】グラフＧを表示するためのデータ群の一部を例示した図である。
【図４】ラベル記憶部１３の記憶内容を示す図である。
【図５】第１の実施の形態のシーケンス図である。
【図６】表示された入力用インタフェースを例示した図である。
【図７】アークスコアの一部をグラフに当てはめた図である。
【図８】ノードスコア計算のフローチャートを示す図である。
【図９】ノードスコアの計算式を示した図である。
【図１０】ノードスコア計算の例にしたグラフを示す図である。
【図１１】１つのクラスタを生成するフローチャートを示す図
【図１２】２つのクラスタが生成された様子を示す図である。
【図１３】第２の実施の形態に係るクラスタ生成装置１Ｂの構成図である。
【図１４】第２の実施の形態のシーケンス図である。
【図１５】第３の実施の形態に係るクラスタ生成装置１Ｃの構成図である。
【図１６】第３の実施の形態のシーケンス図である。
【図１７】第４の実施の形態に係るクラスタ生成装置１Ｄの構成図である。
【図１８】第４の実施の形態のシーケンス図である。
【図１９】第５の実施の形態に係るクラスタ生成装置１Ｅの構成図である。
【図２０】パスパターンを例示した図である。
【図２１】第５の実施の形態のシーケンス図である。
【符号の説明】
【０１１０】
１Ａ、１Ｂ、１Ｃ、１Ｄ、１Ｅ：クラスタ生成装置
１１  グラフデータベース
１１Ａ  パターンデータベース
１３  ラベル記憶部
１３Ａ  ノードスコア記憶部
１４  アークスコア設定部
１４Ａ  ノードスコア設定部
１５  ノードスコア計算部
１６  クラスタ生成部
１９  グラフ処理部
【図１】
2008181333.tif 000003
【図２】
2008181333.tif 000004
【図３】
2008181333.tif 000005
【図４】
2008181333.tif 000006
【図５】
2008181333.tif 000007
【図６】
2008181333.tif 000008
【図７】
2008181333.tif 000009
【図８】
2008181333.tif 000010
【図９】
2008181333.tif 000011
【図１０】
2008181333.tif 000012
【図１１】
2008181333.tif 000013
【図１２】
2008181333.tif 000014
【図１３】
2008181333.tif 000015
【図１４】
2008181333.tif 000016
【図１５】
2008181333.tif 000017
【図１６】
2008181333.tif 000018
【図１７】
2008181333.tif 000019
【図１８】
2008181333.tif 000020
【図１９】
2008181333.tif 000021
【図２０】
2008181333.tif 000022
【図２１】
2008181333.tif 000023