中心性値計算装置および中心性値計算方法
【課題】グラフのサブグラフに含まれるノードの中心性を示す中心性値を計算する。
【解決手段】グラフ検索部１６は、グラフデータベース１１のグラフＧから、指定された条件を基にして、サブグラフを検索する（Ｓ１７）。中心性値計算部１７は、サブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する（Ｓ２７）。
【解決手段】グラフ検索部１６は、グラフデータベース１１のグラフＧから、指定された条件を基にして、サブグラフを検索する（Ｓ１７）。中心性値計算部１７は、サブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する（Ｓ２７）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフのサブグラフに含まれるノードの中心性を示す中心性値を計算する中心性値計算装置および中心性値計算方法に関するものである。
【背景技術】
【０００２】
インスタンスをもつノード間がアークによって接続されたグラフでは、そのグラフにおけるノードの中心性を示す中心性値が、そのグラフの特徴を示すことが多いので、その中心性値が計算される。
【０００３】
この出願の発明に関連する先行技術文献情報としては下記のものがある。
【０００４】
非特許文献１では、中心性値計算に類似のものとしてノードの重要度を計算する技術を開示している。
【０００５】
非特許文献２では、グラフの部分（本明細書ではサブグラフという）を検索する技術を開示している。特に、非特許文献２では、グラフをアークで分割して得たサブグラフをクラスタと称している。
【０００６】
非特許文献３、４でも、サブグラフの検索技術を開示している。特に、ここでは、指定されたノードを含み且つ指定された出現頻度のサブグラフをする。
【０００７】
非特許文献５では、中心性値計算に類似のものとしてに類似のものとして、ウェブページが多くのウェブページに参照されている場合は、その参照されているページのランクを高くする技術を開示している。
【非特許文献１】金光 淳、“社会ネットワーク分析の中心性分析”、勁草書房（６章１節「グラフ理論による中心概念のモデル」）
【非特許文献２】M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks", PHYSICAL REVIEW E 69, 0266133 2004.
【非特許文献３】猪口 昭博、外２名、“多頻度グラフマイニング手法の一般化”、[online]、２００４年、［平成１９年１月４日検索］、インターネット＜ＵＲＬ：http://www.ar.sanken.osaka-u.ac.jp/~motoda/papers/jjsai04_inokuchi.pdf＞
【非特許文献４】茂木 明、外５名、“部分グラフを制約とするグラフ構造データからの知識獲得”、[online]、２００４年、［平成１９年１月４日検索］、インターネット＜ＵＲＬ：http://www-kasm.nii.ac.jp/jsai2004_schedule/pdf/000128.pdf＞
【非特許文献５】Sergey Brin, Rajeev Motwani, Terry Winograd, "The PageRank Citation Ranking: Bringing Order to the Web Lawrence Page", [online]，１９９８年,インターネット＜ＵＲＬ：http://www-db.stanford.edu/~backrub/pageranksub.ps＞
【発明の開示】
【発明が解決しようとする課題】
【０００８】
非特許文献２、３、４の技術では、サブグラフを検索するが、中心性値を計算しないので、そのサブグラフの特徴を知ることができない。
【０００９】
非特許文献１、５の技術では、中心性値に類似のものを計算するが、サブグラフを検索しないので、計算量が多く、サブグラフの特徴を早期に知ることができない。
【００１０】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、グラフのサブグラフに含まれるノードの中心性を示す中心性値を計算する中心性値計算装置および中心性値計算方法を提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明は、インスタンスをもつノード間がアークによって接続されたグラフから、指定された条件を基にして、サブグラフを検索するグラフ検索手段と、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する中心性値計算手段とを備える。
【発明の効果】
【００１２】
本発明によれば、グラフのサブグラフに含まれるノードの中心性値を計算するので、サブグラフの特徴を早期に知ることができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。
【００１４】
図１は、本実施の形態に係る中心性値計算装置１の構成図である。
【００１５】
中心性値計算装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００１６】
中心性値計算装置１は、有向グラフであるグラフＧを表示するためのデータ群が記憶されたグラフデータベース１１と、ユーザ端末２で入力操作をさせるための入力用インタフェースを生成する入力用インタフェース生成部１２と、グラフＧを基にテンプレートグラフを生成するときに使用される一時記憶データベース１３と、サブグラフの検索に用いられるパスパターンやサブグラフパターンが記憶されるパターンデータベース１４と、各種パラメータが記憶されたパラメータ記憶部１５と、グラフＧのサブグラフを検索するグラフ検索部１６と、そのノードの中心性値を計算する中心性値計算部１７と、グラフ検索部１６および中心性値計算部１７と各データベースとを中継するデータベースインタフェース１８と、処理結果を伝えるための出力用インタフェースを生成する出力用インタフェース生成部１９とを備える。
【００１７】
中心性値計算装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータを中心性値計算装置１として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。
【００１８】
図２は、グラフデータベース１１に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００１９】
グラフデータベース１１に記憶されたデータ群を全てを使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベースに記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２０】
グラフＧでは、例えば、「ＸＭＬ」や「Ｂプロジェクト」などのインスタンスをもつノードが、「ｒｍ：技術キーワード」や「ｒｍ：著者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「Ｐｅｒｓｏｎ：山田太郎」などの概念であるクラス「Ｐｅｒｓｏｎ：人」などが定義される。
【００２１】
図３に示すように、「Ｔ−０４１」で示され、その元データの著者が山田太郎でり、題名が「セマンティックｗｅｂ」入門であり、キーワードがセマンティックｗｅｂである、元データは、グラフデータベース１１では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１１に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。
【００２２】
図４は、グラフデータベース１１に記憶されたデータ群の一部を例示した図である。
【００２３】
例えば、データ「＜ｏｒｇ：Ｄプロジェクト＞＜ｒｍ：技術キーワード＞”ＸＭＬ”」は、インスタンス「ｏｒｇ：Ｄプロジェクト」をもつノードからインスタンス「ＸＭＬ」のノードへ向かうアークがラベル「ｒｍ：技術キーワード」をもつことを示している。また、例えば、データ「＜Ｐｅｒｓｏｎ：鈴木花子＞＜ｒｄｆ：ｔｙｐｅ＞＜Ｐｅｒｓｏｎ：人＞」は、インスタンス「Ｐｅｒｓｏｎ：鈴木花子」をもつノードのクラスが「Ｐｅｒｓｏｎ：人」であることを示している。
【００２４】
ＲＤＦについては、以下の文献に記載されている。
【００２５】
「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/>
（本実施の形態の動作）
図５は、本実施の形態のシーケンス図である。
【００２６】
中心性値計算装置１では、入力用インタフェース生成部１２が、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６に示したように表示させる（Ｓ３）。ここでの操作により特定されたキーワードＫＷ（例えば、キーワードＫＷ「セマンティックｗｅｂ」）およびクラスＣＬ（例えば、クラスＣＬ「Ｐｅｒｓｏｎ：人」）を、ユーザ端末２が中心性値計算装置１に送信する（Ｓ５）。
【００２７】
なお、これらのキーワードＫＷなどは、クラスタ生成装置１Ａに記憶しておき、それを適宜読み出して使用してもよい。
【００２８】
（パスパターン生成）
中心性値計算装置１では、グラフ検索部１６が、例えば、パスパターンを生成する（Ｓ９）。また、必要ならば、それをパターンデータベース１４に記憶させる（Ｓ１１）。
【００２９】
あるいは、ステップＳ９、Ｓ１１をせず、予めそのように生成し、パターンデータベース１４に記憶させておいたパスパターンを検索する（Ｓ９Ａ）。ステップＳ９Ａについては後述する。
【００３０】
さて、パスパターン生成では、例えば、グラフＧからパスを検索し、このパスからパスパターンを生成する。これをパス検索の実施例１、２で説明する。
【００３１】
なお、グラフ検索部１６は、グラフＧからパス、サブグラフを取得する際、グラフＧを扱う際、パターンをパターンデータベース１４に記憶させる際、パターンデータベース１４を検索する際、データベースインタフェース１８にクエリを送信するのだが、それについては冗長なのでの言及しないこととする。
【００３２】
（パス検索の実施例１）
グラフ検索部１６は、例えば、「キーワードＫＷが一方端のノードのインスタンスである」かつ「クラスＣＬが他方端のノードのクラスである」という条件と予めパラメータ記憶部１５に記憶された条件つまり「パス内のノード数≦６である」とからなるパス検索条件（後者の条件を除いたものでもよい。以下、パス検索条件という）を満たすパスを検索する（Ｓ９ａ）。「パス内のノード数≦６である」の「６」は予め設定されるものであり、別の数を設定しておいてもよい。
【００３３】
（パス検索の実施例２）
グラフ検索部１６は、または、以下のようにパス検索する。まず、グラフＧを一時記憶データベース１３にグラフＧ’としてコピーする。そして、図７に示すように、グラフＧ’で同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称（「Ｌｉｔｅｒａｌ」など）に置換する。そして、図８に示すように、グラフＧ’内の複数の同一部分について１つを残しそれ以外を削除する。そして、仮の名称を予めパラメータ記憶部１５に記憶してあるインスタンス（例えば、グラフＧのインスタンスから選択されたもの）に置換する。こうして、生成されたものをテンプレートグラフという。そして、パス検索条件を満たすパスをテンプレートグラフから検索する（Ｓ９ｂ）。
【００３４】
（パスパターン生成の実施例１）
パスパターン生成時のグラフ検索部１６は、図９に示すように、検索されたパスにおいてキーワードＫＷがインスタンスであるノード以外のノードのインスタンスと全てのアークのラベルを変数（？とそれに後続する単語であり、以下同様）に置換する。こうして、置換後のもの（パスパターン）を生成する。
【００３５】
パスパターンは、後述するサブグラフパターンと同様に、パターンの一種である。
【００３６】
パスパターンは分岐および閉ループをもたないものであり、サブグラフパターンは分岐および閉ループをもっていてもよいものである。
【００３７】
（パターンの説明）
ここでパターンについて説明する。
【００３８】
パターンは、グラフデータベース１１に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを図９のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。パスパターンはパスを検索するパターンであり、サブグラフパターンはサブグラフを検索するものである。
【００３９】
パスパターンは、例えば、同図のようなグラフ（パス）である。
【００４０】
パターンはグラフと同様に、実際にはデータ群であるが、それを逐一説明するのは冗長であるから、パターンの説明はグラフ化されたもので行う。
【００４１】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、同図に示すように、？とそれに後続する単語からなる。
【００４２】
また、一般的にパターンでは、必要があれば、変数が設定された一部のノードに、そのパターンにより検索されるグラフにおける、同位置のノードがもつインスタンスの上位概念を示すクラスが予め定義される。
【００４３】
同図のパスパターンでは、キーワードＫＷ「セマンティックｗｅｂ」がインスタンスであるノードを一方端とすると、他方端のノードにクラスＣＬ「Ｐｅｒｓｏｎ：人」が定義されている。
【００４４】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００４５】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、（４）場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。
【００４６】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【００４７】
（パスパターン生成の実施例２）
グラフ検索部１６は、または、図１０に３例示すように、検索されたパスにおいてキーワードＫＷがインスタンスであるノード以外のノードのインスタンスを変数に置換する。こうして、置換後のもの（パスパターン）を生成する。
【００４８】
（パスパターン生成の実施例３）
グラフ検索部１６は、または、以下のようにパスパターンを生成する。この実施例３の場合は、事前のパス検索は不要である。
【００４９】
まず、予めパラメータ記憶部１５には、図１１に示すような、アークスコア記憶部が構成される。
【００５０】
アークスコア記憶部は、グラフＧのアークがもつ各ラベルのスコア（アークスコア）を記憶している。グラフＧの各ノードのインスタンスをそのノードのクラスに置換し、同一のインスタンス（クラス）をもつノードではその中の１つのみ残し、そのようにしてなるグラフにアークスコア記憶部の各アークスコアを当てはめると、その一部は、例えば図１２のようになる。
【００５１】
図１３は、アークスコア記憶部を用いたパターン生成のフローチャートを示す図である。
【００５２】
グラフ検索部１６は、まず、グラフＧのノードに、その重要度を示すこととなる、ノードスコアの初期値「１」を設定する（Ｓ１０１）。
【００５３】
次に、グラフ検索部１６は、各ノードにつき、図１４の式により、ノードスコアを計算する（Ｓ１０３）。
【００５４】
そして、このノードスコアで、グラフＧに設定されたノードスコアの初期値を更新する（Ｓ１０５）。このような計算更新を、ノードスコアが収束するまで、再帰的に行う。これにより、ノードスコアが重要度を示すこととなる。
【００５５】
グラフＧにアークスコア記憶部の各アークスコアを当てはめたグラフの一部が、例えば図１５に示すようなものであった場合、同図に示すように、例えば、インスタンス「ＸＭＬ」をもつノードのノードスコアは０．４となる。インスタンス「Person:電々三郎」をもつノードのノードスコアは０．９となる。インスタンス「org:H3G」をもつノードのノードスコアは０．６となる。
【００５６】
なお、図１４の式は一例であり、他の式を用いてもよい。
【００５７】
次に、グラフ検索部１６は、パス検索条件を満たすパスをグラフＧから検索する（Ｓ１０７）。
【００５８】
次に、グラフ検索部１６は、図１６の式により、その各パスのパススコアを計算する（Ｓ１０９）。
【００５９】
次に、グラフ検索部１６は、その各パスにつき、キーワードＫＷをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換する（Ｓ１０１）。
【００６０】
次に、グラフ検索部１６は、全てのパスをパスグループ（同一のパスからなる）ごとに区分し、各パスグループにつき、図１７の式により、スコアを計算する（Ｓ１１３）。そして、スコアが予め定めたしきい値以下の各パスグループを削除する（Ｓ１１５）。
【００６１】
次に、グラフ検索部１６は、残った各パスグループにつき、１パス以外を削除する（Ｓ１１７）。
【００６２】
これにより、図１８に２つ示すようなパスパターンが生成される。
【００６３】
さて、上述のように、ステップＳ９、１１をせず、パスパターンを検索してもよい（Ｓ９Ａ）。
【００６４】
例えば、「キーワードＫＷが一方端のノードのインスタンスである」かつ「クラスＣＬが他方端のノードのクラスである」という条件と予めパラメータ記憶部１５に記憶された条件つまり「パスパターン内のノード数≦６である」とからなるパスパターン検索条件（後者の条件を除いたものでもよい。以下、パスパターン検索条件という）を満たすパスパターンを検索する（Ｓ９Ａ）。「パスパターン内のノード数≦６である」の「６」は予め設定されるものであり、別の数を設定しておいてもよい。
【００６５】
いずれにしても、中心性値計算装置１では、グラフ検索部１６によりパスパターンが生成あるいは検索される。
【００６６】
このパスパターンでは、その一方端のノードのインスタンスがキーワードＫＷであり、他方端のノードにはクラスＣＬが定義されている。前者のノードをキーワードノードという。後者のノードをクラスノードという。なお、キーワードノード、クラスノードは、パス、後述するサブグラフパターンにおいても用いることとする。
【００６７】
（サブグラフパターン生成）
図７に戻り、グラフ検索部１６は、例えば、サブグラフパターンを生成し（Ｓ１３）、必要ならば、それをパターンデータベース１４に記憶させる（Ｓ１５）。
【００６８】
ステップＳ１３でグラフ検索部１６は、例えば、生成あるいは検索したパスパターンでサブグラフパターンを生成する（Ｓ１３）。あるいは、パスパターンを使用せずにサブグラフパターンを生成する（Ｓ１３）。
【００６９】
あるいは、そのように生成し、パターンデータベース１４に記憶させておいたサブグラフパターンを検索する（Ｓ１３Ａ）。ステップＳ１３Ａについては後述する。
【００７０】
以下、実施例１〜４は、パスパターンを使用してサブグラフパターンを生成するものであり、実施例５は、パスパターンを使用せずにサブグラフパターンを生成するものである。
【００７１】
なお、パスパターンをサブグラフパターンとして扱ってもよい。
【００７２】
（サブグラフパターン生成の実施例１）
グラフ検索部１６は、例えば、図１９に示すように、同一のパスパターンからキーワードノードとクラスノードとそのクラスの定義以外の部分を重複させたサブグラフパターンを生成し、変数が重複しないようにする。
【００７３】
（サブグラフパターン生成の実施例２）
グラフ検索部１６は、または、例えば、図２０に示すように、キーワードノードのインスタンスが同じかつクラスノードのクラスが同じパスパターン同士を当該両ノードでマージしたものサブグラフパターンを生成し、変数が重複しないようにする。
【００７４】
（サブグラフパターン生成の実施例３）
グラフ検索部１６は、または、例えば、図２１に示すように、クラスノードのインスタンスが同じパスパターン同士をクラスノードでマージしたものサブグラフパターンを生成し、変数が重複しないようにする。
【００７５】
（サブグラフパターン生成の実施例４）
グラフ検索部１６は、または、例えば、クラスノードのインスタンスが同じマージ対象同士をクラスノードでマージしたものサブグラフパターンを生成し、変数が重複しないようにする。
【００７６】
例えば、２以上のパスパターン同士をマージする。または、２以上のこれまで説明したサブグラフパターン同士をマージする。例えば、図２２に示すように、２つのサブグラフパターン同士をマージする。または、１以上のパスパターンと１以上のサブグラフパターンをマージする。例えば、図２３に示すように、１つのパスパターンと１つのサブグラフパターンをマージする。
【００７７】
（サブグラフパターン生成の実施例５）
グラフ検索部１６は、または、以下のようにサブグラフパターンを生成する。
【００７８】
まず、グラフＧにおいてキーワードＫＷに等しいインスタンスをもつノード（キーワードノード）に接続されたアークのラベルを取得する。
【００７９】
グラフ検索部１６は、例えばキーワードＫＷが「セマンティックＷｅｂ」のとき、図２４の太線のアークがもつ、下線のラベル「ｒｍ：技術キーワード」を取得する。
【００８０】
以下、このラベルが取得されたときのことについて説明する。
【００８１】
次に、グラフ検索部１６は、まず、このラベルを含むパスパターンを生成する。具体的には、例えば、図２５に示すように、ラベル「ｍｓ：技術キーワード」をもつアークが一方の端位置のノード（キーワードノード）に接続され、クラスＣＬが定義されたノード（クラスノード）を他方の端位置に有する、パスパターンＰｍを生成する。
【００８２】
次に、グラフ検索部１６が、パスパターンＰｍにマッチするパスをグラフＧから取得する。
【００８３】
そして、グラフ検索部１６は、取得されたパスの中で、キーワードノードのインスタンス同士が同じ、かつ、クラスノードのインスタンスが同じもの同士を、キーワードノードとクラスノードでマージする。
【００８４】
例えば、図２６に示すような、サブグラフＳＧｍ１、ＳＧｍ２が生成される。また、取得されたパスそのものが、これ以降、サブグラフ（ここでは、サブグラフＳＧｍ１という）として扱われる。
【００８５】
これ以降は、図２６に示すような、同じインスタンスをキーワードノードにもつサブグラフのグループについての処理が行われ、同様の処理が他のグループについても行われる。
【００８６】
なお、説明としては、図２６に示す各サブグラフについての処理を説明し、他のグループについての説明は省略する。
【００８７】
さて、図２６を例にすると、グラフ検索部１６は、サブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３の中の１つ（例えばＳＧｍ１）またはそのサブグラフ（以下、第１サブグラフ）と他のサブグラフ（例えばＳＧｍ２）またはそのサブグラフ（以下、第２サブグラフ）とからなる組み合わせであって、第１および第２サブグラフのそれぞれが、キーワードノードと対象クラスノードとをそれぞれ端位置にもつ２以上のパスからなり且つ対象クラスノードのクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出する。
【００８８】
例えば、図２７に示すように、サブグラフＳＧｍ２にサブグラフＳＧｍ２ａが含まれているとすると、サブグラフＳＧｍ１とサブグラフＳＧｍ２ａとからなる組み合わせが検出される。
【００８９】
次に、グラフ検索部１６は、検出された組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換する。こうして、置換後のもの（サブグラフパターン）が生成する。
【００９０】
例えば、図２６、図２７に示したサブグラフＳＧｍ１からは、図２８に示すサブグラフパターンＰｍ１が生成される。
【００９１】
次に、グラフ検索部１６は、生成したサブグラフパターンのキーワードノードのインスタンスとしてキーワードＫＷを設定する。
【００９２】
例えば、図２８に示したサブグラフパターンＰｍ１からは、図２９に示すサブグラフパターンＰｍ１’が生成される。
【００９３】
さて、上述したように、ステップＳ１３、Ｓ１５をせず、サブグラフパターンを検索してもよい（Ｓ１３Ａ）。
【００９４】
例えば、「キーワードＫＷが一方端のノードのインスタンスである」かつ「クラスＣＬが他方端のノードのクラスである」という条件と予めパラメータ記憶部１５に記憶された条件つまり「サブグラフパターン内のノード数≦６である」とからなるサブグラフパターン検索条件（後者の条件を除いたものでもよい。以下、サブグラフパターン検索条件という）を満たすサブグラフパターンを検索する（Ｓ１３Ａ）。「サブグラフパターン内のノード数≦６である」の「６」は予め設定されるものであり、別の数を設定しておいてもよい。
【００９５】
あるいは、ステップＳ３では、図３０に示すように、サブグラフパターンを表示させ、それが操作で選択されたら、そのサブグラフパターンが検索されたこととしてもよい。
【００９６】
いずれにしても、中心性値計算装置１では、グラフ検索部１６によりサブグラフパターンが生成あるいは検索される。
【００９７】
（サブグラフの検索、マージ）
図７に戻り、グラフ検索部１６は、サブグラフをグラフＧから検索する（Ｓ１７）。複数のサブグラフが検索された場合は、それらを重複部分でマージすることで１つのサブグラフにする（Ｓ１９）。
【００９８】
サブグラフの検索では、生成あるいは検索されたサブグラフパターンに対応するクエリが生成され、そのクエリにマッチするサブグラフが検索される。クエリの一例として、図２０のサブグラフパターンに対応するクエリを図３１に示す。
【００９９】
また、ここでは、例えば、図１９のサブグラフパターンにより、図３２の太線のサブグラフと、図３３の太線のサブグラフとが検索され、これらがマージされ、図３４の太線のサブグラフのようにマージされる。
【０１００】
ここで得られるサブグラフは１つであり、これを以下ではサブグラフＳＧという。ステップＳ１７で検索されたサブグラフが１つの場合は、それをサブグラフＳＧという。
【０１０１】
（中心性値計算部１７の動作）
次に、中心性値計算部１７は、予め設定されている場合、クラスＣＬの定義、キーワードＫＷをもつノードとそのノードへのアークをサブグラフＳＧから除去する（Ｓ２１）。
【０１０２】
ここでは、例えば、図３５に示すように、クラスＣＬ「Ｐｅｒｓｏｎ：人」の定義と、キーワードＫＷ「セマンティックｗｅｂ」をもつノードとそのノードへのアークとが除去され、太線のサブグラフが残る。これを以下ではサブグラフＳＧという。
【０１０３】
次に、中心性値計算部１７は、予め除去すべきアークのラベルがパラメータ記憶部１５に設定されている場合、そのラベルをもつアークをサブグラフＳＧから除去する（Ｓ２３）。
【０１０４】
ここでは、例えば、図３６に示すように、ラベル「ｐｊ：担当者」をもつアークが除去され、太線のサブグラフが残る。これを以下ではサブグラフＳＧという。
【０１０５】
次に、予めサブグラフＳＧを縮める縮退ルールがパラメータ記憶部１５に記憶された場合、その縮退ルールによりサブグラフＳＧの一部を除去し、その残りの部分を接続する（Ｓ２５）。
【０１０６】
ここでは、例えば、縮退ルールによりノードとアークを除去し、それらで接続されていたノード同士を１つのアークだけで接続する。図３７に示す縮退ルールにより、図３８に示すサブグラフを、図３９に示すサブグラフにするのである。
【０１０７】
こうして、縮退ルールにより、後述する中心性値計算に適さないノードを計算対象から除外することができる。
【０１０８】
こうして得られたサブグラフを以下ではサブグラフＳＧという。
【０１０９】
次に、中心性値計算部１７は、サブグラフＳＧの各ノードの中心性値を計算し（Ｓ２７）、予め設定されている場合は、予めパラメータ記憶部１５に記憶された閾値以下の中心性値をもつノードを除外する。
【０１１０】
そして、出力用インタフェース生成部１９が、除外されていないノードのインスタンスが中心性値の高い順に並ぶ出力用インタフェースを生成し、これをユーザ端末２に送信し（Ｓ２９）、表示させる（Ｓ３１）。
【０１１１】
なお、ステップＳ２１、Ｓ２３、Ｓ２５は、必要なときに実行すればよく、の一部または全部を省略してもよい。
【０１１２】
また、中心性値によりノードを除外せずに、全ノードのインスタンスを表示させてもよい。また、ノードのインスタンスに対応づけて、そのノードの中心性値を表示させてもよい。
【０１１３】
（中心性値計算の実施例１）
上記の中心性値計算では、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、各ノードｉにつき、接続されたアークの数ｄｉを求め、図４０（ａ）の式により中心性値を計算する。
【０１１４】
図４１は、計算対象のサブグラフＳＧの一例であり、アークの向きおよびラベルを省略して示す。このサブグラフＳＧからは、図４０（ｂ）のような数ｄｉと中心性値が計算される。
【０１１５】
（中心性値計算の実施例２）
あるいは、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、各ノードｉにつき、他の各ノードとの間のアークの数を求め、その最大値ｍｄｉを求め、図４２（ａ）の式により中心性値を計算する。
【０１１６】
図４１のサブグラフＳＧからは、図４２（ｂ）のような値ｍｄｉと中心性値が計算される。
【０１１７】
（中心性値計算の実施例３）
あるいは、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、各ノードｉにつき、他の各ノードとの間のアークの数を求め、その総和ｍｉを求め、図４３（ａ）の式により中心性値を計算する。
【０１１８】
図４１のサブグラフＳＧからは、図４３（ｂ）のような総和ｍｉと中心性値が計算される。
【０１１９】
（中心性値計算の実施例４）
あるいは、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、ｎ個の中の２個の組合せ数ｎＣ２を求め、各ノードｉにつき、そのノードとそのノードに接続されるアークとがない場合に接続が絶たれる２つのノードの組の数ｃｄｐｉを求め、各ノードｉにつき、図４４（ａ）の式により中心性値を計算する。
【０１２０】
例えば、図４１で、インスタンス「ｒｍ：Ｔ−０４８」をもつノードとそのノードに接続されるアークとがない場合、例えば、インスタンス「ｒｍ：Ｔ−０４１」をもつノードとインスタンス「Ｐｅｒｓｏｎ：田中一郎」をもつノードとが接続を絶たれるので、この２つのノードの組がｃｄｐｉの中の１を占めることになる。
【０１２１】
図４１のサブグラフからは、図４４（ｂ）のようなｍｉと中心性値が計算される。
【０１２２】
以上説明したように、本実施の形態によれば、グラフ検索手段（グラフ検索部１６）は、インスタンスをもつノード間がアークによって接続されたグラフＧから、指定された条件を基にして、サブグラフを検索し（Ｓ１７）、中心性値計算手段（中心性値計算部１７）こうして得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する（Ｓ２７）ので、サブグラフの特徴を早期に知ることができる。
【０１２３】
また、パス検索の実施例２で説明したように、グラフ検索手段（１６）は、グラフに等しいグラフにおいて同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称に置換し、複数の同一部分について１つ以外を削除し、仮の名称を予め定められたインスタンスに置換し、置換後のグラフであるテンプレートグラフから、指定された条件を基にして、パスを検索する。そして、当該パスを基にして、グラフからサブグラフを検索し（Ｓ１７）、中心性値計算手段（１７）が、ノードの中心性値を計算する（Ｓ２７）。よって、サブグラフの特徴を早期に知ることができる。
【０１２４】
また、パスパターン生成の実施例３で説明したように、グラフのアークについてのアークスコアが予め記憶されるアークスコア記憶手段（パラメータ記憶部１５）を備え、グラフ検索手段（１６）は、アークスコアを基にして、グラフのノードについてのノードスコアを計算し（図１３、Ｓ１０３）、グラフから、指定された条件を基にして、パスを検索し（図１３、Ｓ１０７）、ノードスコアを基にして、各パスのパススコアを計算し（図１３、Ｓ１０９）、各パスにつき、予め定められたキーワードをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換し（図１３、Ｓ１１１）、全てのパスを同一のパスからなるパスグループごとに区分し、パススコアを基にして、各パスグループにつき、スコアを計算し（図１３、Ｓ１１３）、スコアが予め定めたしきい値以下の各パスグループを削除し（図１３、Ｓ１１５）、残った各パスグループにつき、１パス以外を削除する（図１３、Ｓ１１５）。そして、残った各パスパターンを基にして、グラフからサブグラフを検索し（Ｓ１７）、中心性値計算手段（１７）が、ノードの中心性値を計算する（Ｓ２７）。よって、サブグラフの特徴を早期に知ることができる。
【０１２５】
また、サブグラフパターン生成の実施例５で説明したように、グラフ検索手段（１６）は、グラフから、指定されたキーワード（ＫＷ）に等しいインスタンスをもつノードに接続されたアークのラベルを取得し（図２４ではラベル「ｒｍ：技術キーワード」）、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラス（ＣＬ）が定義されたノードを他方の端位置に有する、パスパターン（図２５ではパターンＰｍ）を生成し、このパスパターンにマッチするパスをグラフから検索し、検索されたパスの中で、クラス（ＣＬ）が定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせ（図２７ではサブグラフＳＧｍ１とサブグラフＳＧｍ２ａの組合せ）であって、第１および第２サブグラフのそれぞれが、キーワード（ＫＷ）に等しいインスタンスをもつノードである第１ノードとクラス（ＣＬ）が定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードにクラス（ＣＬ）が定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせ（図２７のサブグラフＳＧｍ１とサブグラフＳＧｍ２ａの組合せ）を検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換し（図２８ではサブグラフパターンＰｍ１）、第１ノードのインスタンスとしてキーワード（ＫＷ）を設定してなるパターン（図２９ではサブグラフパターンＰｍ１’）を生成する。そして、生成したサブグラフパターンを基にして、グラフからサブグラフを検索し（Ｓ１７）、中心性値計算手段（１７）が、ノードの中心性値を計算する（Ｓ２７）。よって、サブグラフの特徴を早期に知ることができる。
【図面の簡単な説明】
【０１２６】
【図１】本実施の形態に係る中心性値計算装置１の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】グラフＧを表示するためのデータ群の一部を例示した図である。
【図５】本実施の形態のシーケンス図である。
【図６】表示された入力用インタフェースを例示した図である。
【図７】パス検索の実施例２で使用されるテンプレートグラフを生成する途中の状態を例示した図である。
【図８】テンプレートグラフを例示した図である。
【図９】パスパターンを例示した図である。
【図１０】パスパターン生成の実施例２で生成したパスパターンを例示した図である。
【図１１】パスパターン生成の実施例３で使用されるアークスコア記憶部の記憶内容を例示した図である。
【図１２】アークスコアの一部をグラフに当てはめた図である。
【図１３】アークスコア記憶部を用いたパターン生成のフローチャートを示す図である。
【図１４】ノードスコアの計算式を示した図である。
【図１５】ノードスコア計算の例にしたグラフを示す図である。
【図１６】パススコアの計算式を示した図である。
【図１７】パスグループのスコアの計算式を示した図である。
【図１８】パスパターン生成の実施例３で生成したパスパターンを例示した図である。
【図１９】サブグラフパターン生成の実施例１で生成したサブグラフパターンを例示した図である。
【図２０】サブグラフパターン生成の実施例２で生成したサブグラフパターンを例示した図である。
【図２１】サブグラフパターン生成の実施例３で生成したサブグラフパターンを例示した図である。
【図２２】サブグラフパターン生成の実施例４で生成したサブグラフパターンを例示した図である。
【図２３】サブグラフパターン生成の実施例４で生成したサブグラフパターンを例示した図である。
【図２４】キーワードノードに接続されたアークとそのインスタンスを例示した図である。
【図２５】パターンＰｍを例示した図である。
【図２６】サブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３を例示した図である。
【図２７】サブグラフの組み合わせが検出される様子を例示した図である。
【図２８】パターンＰｍ１を例示した図である。
【図２９】キーワードＫＷが設定されたパターンＰｍ１’を例示した図である。
【図３０】表示された入力用インタフェースを例示した図である。
【図３１】クエリを例示した図である。
【図３２】サブグラフを例示した図である。
【図３３】サブグラフを例示した図である。
【図３４】マージ後のサブグラフを例示した図である。
【図３５】一部除去後のサブグラフを例示した図である。
【図３６】一部除去後のサブグラフを例示した図である。
【図３７】縮退ルールを例示した図である。
【図３８】縮退ルールによる一部除去前のサブグラフを例示した図である。
【図３９】縮退ルールによる一部除去前のサブグラフを例示した図である。
【図４０】中心性値計算の実施例１で使用される式、各インスタンスに対応する数ｄｉと中心性値を例示した図である。
【図４１】中心性値計算の例にしたグラフを示す図である。
【図４２】中心性値計算の実施例２で使用される式、各インスタンスに対応する値ｍｄｉと中心性値を例示した図である。
【図４３】中心性値計算の実施例３で使用される式、各インスタンスに対応する総和ｍｉと中心性値を例示した図である。
【図４４】中心性値計算の実施例４で使用される式、各インスタンスに対応する数ｃｄｐｉと中心性値を例示した図である。
【符号の説明】
【０１２７】
１ 中心性値計算装置
１１ グラフデータベース
１４ パターンデータベース
１６ グラフ検索部
１７ 中心性値計算部
【技術分野】
【０００１】
本発明は、グラフのサブグラフに含まれるノードの中心性を示す中心性値を計算する中心性値計算装置および中心性値計算方法に関するものである。
【背景技術】
【０００２】
インスタンスをもつノード間がアークによって接続されたグラフでは、そのグラフにおけるノードの中心性を示す中心性値が、そのグラフの特徴を示すことが多いので、その中心性値が計算される。
【０００３】
この出願の発明に関連する先行技術文献情報としては下記のものがある。
【０００４】
非特許文献１では、中心性値計算に類似のものとしてノードの重要度を計算する技術を開示している。
【０００５】
非特許文献２では、グラフの部分（本明細書ではサブグラフという）を検索する技術を開示している。特に、非特許文献２では、グラフをアークで分割して得たサブグラフをクラスタと称している。
【０００６】
非特許文献３、４でも、サブグラフの検索技術を開示している。特に、ここでは、指定されたノードを含み且つ指定された出現頻度のサブグラフをする。
【０００７】
非特許文献５では、中心性値計算に類似のものとしてに類似のものとして、ウェブページが多くのウェブページに参照されている場合は、その参照されているページのランクを高くする技術を開示している。
【非特許文献１】金光 淳、“社会ネットワーク分析の中心性分析”、勁草書房（６章１節「グラフ理論による中心概念のモデル」）
【非特許文献２】M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks", PHYSICAL REVIEW E 69, 0266133 2004.
【非特許文献３】猪口 昭博、外２名、“多頻度グラフマイニング手法の一般化”、[online]、２００４年、［平成１９年１月４日検索］、インターネット＜ＵＲＬ：http://www.ar.sanken.osaka-u.ac.jp/~motoda/papers/jjsai04_inokuchi.pdf＞
【非特許文献４】茂木 明、外５名、“部分グラフを制約とするグラフ構造データからの知識獲得”、[online]、２００４年、［平成１９年１月４日検索］、インターネット＜ＵＲＬ：http://www-kasm.nii.ac.jp/jsai2004_schedule/pdf/000128.pdf＞
【非特許文献５】Sergey Brin, Rajeev Motwani, Terry Winograd, "The PageRank Citation Ranking: Bringing Order to the Web Lawrence Page", [online]，１９９８年,インターネット＜ＵＲＬ：http://www-db.stanford.edu/~backrub/pageranksub.ps＞
【発明の開示】
【発明が解決しようとする課題】
【０００８】
非特許文献２、３、４の技術では、サブグラフを検索するが、中心性値を計算しないので、そのサブグラフの特徴を知ることができない。
【０００９】
非特許文献１、５の技術では、中心性値に類似のものを計算するが、サブグラフを検索しないので、計算量が多く、サブグラフの特徴を早期に知ることができない。
【００１０】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、グラフのサブグラフに含まれるノードの中心性を示す中心性値を計算する中心性値計算装置および中心性値計算方法を提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明は、インスタンスをもつノード間がアークによって接続されたグラフから、指定された条件を基にして、サブグラフを検索するグラフ検索手段と、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する中心性値計算手段とを備える。
【発明の効果】
【００１２】
本発明によれば、グラフのサブグラフに含まれるノードの中心性値を計算するので、サブグラフの特徴を早期に知ることができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。
【００１４】
図１は、本実施の形態に係る中心性値計算装置１の構成図である。
【００１５】
中心性値計算装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００１６】
中心性値計算装置１は、有向グラフであるグラフＧを表示するためのデータ群が記憶されたグラフデータベース１１と、ユーザ端末２で入力操作をさせるための入力用インタフェースを生成する入力用インタフェース生成部１２と、グラフＧを基にテンプレートグラフを生成するときに使用される一時記憶データベース１３と、サブグラフの検索に用いられるパスパターンやサブグラフパターンが記憶されるパターンデータベース１４と、各種パラメータが記憶されたパラメータ記憶部１５と、グラフＧのサブグラフを検索するグラフ検索部１６と、そのノードの中心性値を計算する中心性値計算部１７と、グラフ検索部１６および中心性値計算部１７と各データベースとを中継するデータベースインタフェース１８と、処理結果を伝えるための出力用インタフェースを生成する出力用インタフェース生成部１９とを備える。
【００１７】
中心性値計算装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータを中心性値計算装置１として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。
【００１８】
図２は、グラフデータベース１１に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００１９】
グラフデータベース１１に記憶されたデータ群を全てを使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベースに記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２０】
グラフＧでは、例えば、「ＸＭＬ」や「Ｂプロジェクト」などのインスタンスをもつノードが、「ｒｍ：技術キーワード」や「ｒｍ：著者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「Ｐｅｒｓｏｎ：山田太郎」などの概念であるクラス「Ｐｅｒｓｏｎ：人」などが定義される。
【００２１】
図３に示すように、「Ｔ−０４１」で示され、その元データの著者が山田太郎でり、題名が「セマンティックｗｅｂ」入門であり、キーワードがセマンティックｗｅｂである、元データは、グラフデータベース１１では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１１に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。
【００２２】
図４は、グラフデータベース１１に記憶されたデータ群の一部を例示した図である。
【００２３】
例えば、データ「＜ｏｒｇ：Ｄプロジェクト＞＜ｒｍ：技術キーワード＞”ＸＭＬ”」は、インスタンス「ｏｒｇ：Ｄプロジェクト」をもつノードからインスタンス「ＸＭＬ」のノードへ向かうアークがラベル「ｒｍ：技術キーワード」をもつことを示している。また、例えば、データ「＜Ｐｅｒｓｏｎ：鈴木花子＞＜ｒｄｆ：ｔｙｐｅ＞＜Ｐｅｒｓｏｎ：人＞」は、インスタンス「Ｐｅｒｓｏｎ：鈴木花子」をもつノードのクラスが「Ｐｅｒｓｏｎ：人」であることを示している。
【００２４】
ＲＤＦについては、以下の文献に記載されている。
【００２５】
「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/>
（本実施の形態の動作）
図５は、本実施の形態のシーケンス図である。
【００２６】
中心性値計算装置１では、入力用インタフェース生成部１２が、入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６に示したように表示させる（Ｓ３）。ここでの操作により特定されたキーワードＫＷ（例えば、キーワードＫＷ「セマンティックｗｅｂ」）およびクラスＣＬ（例えば、クラスＣＬ「Ｐｅｒｓｏｎ：人」）を、ユーザ端末２が中心性値計算装置１に送信する（Ｓ５）。
【００２７】
なお、これらのキーワードＫＷなどは、クラスタ生成装置１Ａに記憶しておき、それを適宜読み出して使用してもよい。
【００２８】
（パスパターン生成）
中心性値計算装置１では、グラフ検索部１６が、例えば、パスパターンを生成する（Ｓ９）。また、必要ならば、それをパターンデータベース１４に記憶させる（Ｓ１１）。
【００２９】
あるいは、ステップＳ９、Ｓ１１をせず、予めそのように生成し、パターンデータベース１４に記憶させておいたパスパターンを検索する（Ｓ９Ａ）。ステップＳ９Ａについては後述する。
【００３０】
さて、パスパターン生成では、例えば、グラフＧからパスを検索し、このパスからパスパターンを生成する。これをパス検索の実施例１、２で説明する。
【００３１】
なお、グラフ検索部１６は、グラフＧからパス、サブグラフを取得する際、グラフＧを扱う際、パターンをパターンデータベース１４に記憶させる際、パターンデータベース１４を検索する際、データベースインタフェース１８にクエリを送信するのだが、それについては冗長なのでの言及しないこととする。
【００３２】
（パス検索の実施例１）
グラフ検索部１６は、例えば、「キーワードＫＷが一方端のノードのインスタンスである」かつ「クラスＣＬが他方端のノードのクラスである」という条件と予めパラメータ記憶部１５に記憶された条件つまり「パス内のノード数≦６である」とからなるパス検索条件（後者の条件を除いたものでもよい。以下、パス検索条件という）を満たすパスを検索する（Ｓ９ａ）。「パス内のノード数≦６である」の「６」は予め設定されるものであり、別の数を設定しておいてもよい。
【００３３】
（パス検索の実施例２）
グラフ検索部１６は、または、以下のようにパス検索する。まず、グラフＧを一時記憶データベース１３にグラフＧ’としてコピーする。そして、図７に示すように、グラフＧ’で同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称（「Ｌｉｔｅｒａｌ」など）に置換する。そして、図８に示すように、グラフＧ’内の複数の同一部分について１つを残しそれ以外を削除する。そして、仮の名称を予めパラメータ記憶部１５に記憶してあるインスタンス（例えば、グラフＧのインスタンスから選択されたもの）に置換する。こうして、生成されたものをテンプレートグラフという。そして、パス検索条件を満たすパスをテンプレートグラフから検索する（Ｓ９ｂ）。
【００３４】
（パスパターン生成の実施例１）
パスパターン生成時のグラフ検索部１６は、図９に示すように、検索されたパスにおいてキーワードＫＷがインスタンスであるノード以外のノードのインスタンスと全てのアークのラベルを変数（？とそれに後続する単語であり、以下同様）に置換する。こうして、置換後のもの（パスパターン）を生成する。
【００３５】
パスパターンは、後述するサブグラフパターンと同様に、パターンの一種である。
【００３６】
パスパターンは分岐および閉ループをもたないものであり、サブグラフパターンは分岐および閉ループをもっていてもよいものである。
【００３７】
（パターンの説明）
ここでパターンについて説明する。
【００３８】
パターンは、グラフデータベース１１に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを図９のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。パスパターンはパスを検索するパターンであり、サブグラフパターンはサブグラフを検索するものである。
【００３９】
パスパターンは、例えば、同図のようなグラフ（パス）である。
【００４０】
パターンはグラフと同様に、実際にはデータ群であるが、それを逐一説明するのは冗長であるから、パターンの説明はグラフ化されたもので行う。
【００４１】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、同図に示すように、？とそれに後続する単語からなる。
【００４２】
また、一般的にパターンでは、必要があれば、変数が設定された一部のノードに、そのパターンにより検索されるグラフにおける、同位置のノードがもつインスタンスの上位概念を示すクラスが予め定義される。
【００４３】
同図のパスパターンでは、キーワードＫＷ「セマンティックｗｅｂ」がインスタンスであるノードを一方端とすると、他方端のノードにクラスＣＬ「Ｐｅｒｓｏｎ：人」が定義されている。
【００４４】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００４５】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、（４）場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。
【００４６】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【００４７】
（パスパターン生成の実施例２）
グラフ検索部１６は、または、図１０に３例示すように、検索されたパスにおいてキーワードＫＷがインスタンスであるノード以外のノードのインスタンスを変数に置換する。こうして、置換後のもの（パスパターン）を生成する。
【００４８】
（パスパターン生成の実施例３）
グラフ検索部１６は、または、以下のようにパスパターンを生成する。この実施例３の場合は、事前のパス検索は不要である。
【００４９】
まず、予めパラメータ記憶部１５には、図１１に示すような、アークスコア記憶部が構成される。
【００５０】
アークスコア記憶部は、グラフＧのアークがもつ各ラベルのスコア（アークスコア）を記憶している。グラフＧの各ノードのインスタンスをそのノードのクラスに置換し、同一のインスタンス（クラス）をもつノードではその中の１つのみ残し、そのようにしてなるグラフにアークスコア記憶部の各アークスコアを当てはめると、その一部は、例えば図１２のようになる。
【００５１】
図１３は、アークスコア記憶部を用いたパターン生成のフローチャートを示す図である。
【００５２】
グラフ検索部１６は、まず、グラフＧのノードに、その重要度を示すこととなる、ノードスコアの初期値「１」を設定する（Ｓ１０１）。
【００５３】
次に、グラフ検索部１６は、各ノードにつき、図１４の式により、ノードスコアを計算する（Ｓ１０３）。
【００５４】
そして、このノードスコアで、グラフＧに設定されたノードスコアの初期値を更新する（Ｓ１０５）。このような計算更新を、ノードスコアが収束するまで、再帰的に行う。これにより、ノードスコアが重要度を示すこととなる。
【００５５】
グラフＧにアークスコア記憶部の各アークスコアを当てはめたグラフの一部が、例えば図１５に示すようなものであった場合、同図に示すように、例えば、インスタンス「ＸＭＬ」をもつノードのノードスコアは０．４となる。インスタンス「Person:電々三郎」をもつノードのノードスコアは０．９となる。インスタンス「org:H3G」をもつノードのノードスコアは０．６となる。
【００５６】
なお、図１４の式は一例であり、他の式を用いてもよい。
【００５７】
次に、グラフ検索部１６は、パス検索条件を満たすパスをグラフＧから検索する（Ｓ１０７）。
【００５８】
次に、グラフ検索部１６は、図１６の式により、その各パスのパススコアを計算する（Ｓ１０９）。
【００５９】
次に、グラフ検索部１６は、その各パスにつき、キーワードＫＷをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換する（Ｓ１０１）。
【００６０】
次に、グラフ検索部１６は、全てのパスをパスグループ（同一のパスからなる）ごとに区分し、各パスグループにつき、図１７の式により、スコアを計算する（Ｓ１１３）。そして、スコアが予め定めたしきい値以下の各パスグループを削除する（Ｓ１１５）。
【００６１】
次に、グラフ検索部１６は、残った各パスグループにつき、１パス以外を削除する（Ｓ１１７）。
【００６２】
これにより、図１８に２つ示すようなパスパターンが生成される。
【００６３】
さて、上述のように、ステップＳ９、１１をせず、パスパターンを検索してもよい（Ｓ９Ａ）。
【００６４】
例えば、「キーワードＫＷが一方端のノードのインスタンスである」かつ「クラスＣＬが他方端のノードのクラスである」という条件と予めパラメータ記憶部１５に記憶された条件つまり「パスパターン内のノード数≦６である」とからなるパスパターン検索条件（後者の条件を除いたものでもよい。以下、パスパターン検索条件という）を満たすパスパターンを検索する（Ｓ９Ａ）。「パスパターン内のノード数≦６である」の「６」は予め設定されるものであり、別の数を設定しておいてもよい。
【００６５】
いずれにしても、中心性値計算装置１では、グラフ検索部１６によりパスパターンが生成あるいは検索される。
【００６６】
このパスパターンでは、その一方端のノードのインスタンスがキーワードＫＷであり、他方端のノードにはクラスＣＬが定義されている。前者のノードをキーワードノードという。後者のノードをクラスノードという。なお、キーワードノード、クラスノードは、パス、後述するサブグラフパターンにおいても用いることとする。
【００６７】
（サブグラフパターン生成）
図７に戻り、グラフ検索部１６は、例えば、サブグラフパターンを生成し（Ｓ１３）、必要ならば、それをパターンデータベース１４に記憶させる（Ｓ１５）。
【００６８】
ステップＳ１３でグラフ検索部１６は、例えば、生成あるいは検索したパスパターンでサブグラフパターンを生成する（Ｓ１３）。あるいは、パスパターンを使用せずにサブグラフパターンを生成する（Ｓ１３）。
【００６９】
あるいは、そのように生成し、パターンデータベース１４に記憶させておいたサブグラフパターンを検索する（Ｓ１３Ａ）。ステップＳ１３Ａについては後述する。
【００７０】
以下、実施例１〜４は、パスパターンを使用してサブグラフパターンを生成するものであり、実施例５は、パスパターンを使用せずにサブグラフパターンを生成するものである。
【００７１】
なお、パスパターンをサブグラフパターンとして扱ってもよい。
【００７２】
（サブグラフパターン生成の実施例１）
グラフ検索部１６は、例えば、図１９に示すように、同一のパスパターンからキーワードノードとクラスノードとそのクラスの定義以外の部分を重複させたサブグラフパターンを生成し、変数が重複しないようにする。
【００７３】
（サブグラフパターン生成の実施例２）
グラフ検索部１６は、または、例えば、図２０に示すように、キーワードノードのインスタンスが同じかつクラスノードのクラスが同じパスパターン同士を当該両ノードでマージしたものサブグラフパターンを生成し、変数が重複しないようにする。
【００７４】
（サブグラフパターン生成の実施例３）
グラフ検索部１６は、または、例えば、図２１に示すように、クラスノードのインスタンスが同じパスパターン同士をクラスノードでマージしたものサブグラフパターンを生成し、変数が重複しないようにする。
【００７５】
（サブグラフパターン生成の実施例４）
グラフ検索部１６は、または、例えば、クラスノードのインスタンスが同じマージ対象同士をクラスノードでマージしたものサブグラフパターンを生成し、変数が重複しないようにする。
【００７６】
例えば、２以上のパスパターン同士をマージする。または、２以上のこれまで説明したサブグラフパターン同士をマージする。例えば、図２２に示すように、２つのサブグラフパターン同士をマージする。または、１以上のパスパターンと１以上のサブグラフパターンをマージする。例えば、図２３に示すように、１つのパスパターンと１つのサブグラフパターンをマージする。
【００７７】
（サブグラフパターン生成の実施例５）
グラフ検索部１６は、または、以下のようにサブグラフパターンを生成する。
【００７８】
まず、グラフＧにおいてキーワードＫＷに等しいインスタンスをもつノード（キーワードノード）に接続されたアークのラベルを取得する。
【００７９】
グラフ検索部１６は、例えばキーワードＫＷが「セマンティックＷｅｂ」のとき、図２４の太線のアークがもつ、下線のラベル「ｒｍ：技術キーワード」を取得する。
【００８０】
以下、このラベルが取得されたときのことについて説明する。
【００８１】
次に、グラフ検索部１６は、まず、このラベルを含むパスパターンを生成する。具体的には、例えば、図２５に示すように、ラベル「ｍｓ：技術キーワード」をもつアークが一方の端位置のノード（キーワードノード）に接続され、クラスＣＬが定義されたノード（クラスノード）を他方の端位置に有する、パスパターンＰｍを生成する。
【００８２】
次に、グラフ検索部１６が、パスパターンＰｍにマッチするパスをグラフＧから取得する。
【００８３】
そして、グラフ検索部１６は、取得されたパスの中で、キーワードノードのインスタンス同士が同じ、かつ、クラスノードのインスタンスが同じもの同士を、キーワードノードとクラスノードでマージする。
【００８４】
例えば、図２６に示すような、サブグラフＳＧｍ１、ＳＧｍ２が生成される。また、取得されたパスそのものが、これ以降、サブグラフ（ここでは、サブグラフＳＧｍ１という）として扱われる。
【００８５】
これ以降は、図２６に示すような、同じインスタンスをキーワードノードにもつサブグラフのグループについての処理が行われ、同様の処理が他のグループについても行われる。
【００８６】
なお、説明としては、図２６に示す各サブグラフについての処理を説明し、他のグループについての説明は省略する。
【００８７】
さて、図２６を例にすると、グラフ検索部１６は、サブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３の中の１つ（例えばＳＧｍ１）またはそのサブグラフ（以下、第１サブグラフ）と他のサブグラフ（例えばＳＧｍ２）またはそのサブグラフ（以下、第２サブグラフ）とからなる組み合わせであって、第１および第２サブグラフのそれぞれが、キーワードノードと対象クラスノードとをそれぞれ端位置にもつ２以上のパスからなり且つ対象クラスノードのクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出する。
【００８８】
例えば、図２７に示すように、サブグラフＳＧｍ２にサブグラフＳＧｍ２ａが含まれているとすると、サブグラフＳＧｍ１とサブグラフＳＧｍ２ａとからなる組み合わせが検出される。
【００８９】
次に、グラフ検索部１６は、検出された組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換する。こうして、置換後のもの（サブグラフパターン）が生成する。
【００９０】
例えば、図２６、図２７に示したサブグラフＳＧｍ１からは、図２８に示すサブグラフパターンＰｍ１が生成される。
【００９１】
次に、グラフ検索部１６は、生成したサブグラフパターンのキーワードノードのインスタンスとしてキーワードＫＷを設定する。
【００９２】
例えば、図２８に示したサブグラフパターンＰｍ１からは、図２９に示すサブグラフパターンＰｍ１’が生成される。
【００９３】
さて、上述したように、ステップＳ１３、Ｓ１５をせず、サブグラフパターンを検索してもよい（Ｓ１３Ａ）。
【００９４】
例えば、「キーワードＫＷが一方端のノードのインスタンスである」かつ「クラスＣＬが他方端のノードのクラスである」という条件と予めパラメータ記憶部１５に記憶された条件つまり「サブグラフパターン内のノード数≦６である」とからなるサブグラフパターン検索条件（後者の条件を除いたものでもよい。以下、サブグラフパターン検索条件という）を満たすサブグラフパターンを検索する（Ｓ１３Ａ）。「サブグラフパターン内のノード数≦６である」の「６」は予め設定されるものであり、別の数を設定しておいてもよい。
【００９５】
あるいは、ステップＳ３では、図３０に示すように、サブグラフパターンを表示させ、それが操作で選択されたら、そのサブグラフパターンが検索されたこととしてもよい。
【００９６】
いずれにしても、中心性値計算装置１では、グラフ検索部１６によりサブグラフパターンが生成あるいは検索される。
【００９７】
（サブグラフの検索、マージ）
図７に戻り、グラフ検索部１６は、サブグラフをグラフＧから検索する（Ｓ１７）。複数のサブグラフが検索された場合は、それらを重複部分でマージすることで１つのサブグラフにする（Ｓ１９）。
【００９８】
サブグラフの検索では、生成あるいは検索されたサブグラフパターンに対応するクエリが生成され、そのクエリにマッチするサブグラフが検索される。クエリの一例として、図２０のサブグラフパターンに対応するクエリを図３１に示す。
【００９９】
また、ここでは、例えば、図１９のサブグラフパターンにより、図３２の太線のサブグラフと、図３３の太線のサブグラフとが検索され、これらがマージされ、図３４の太線のサブグラフのようにマージされる。
【０１００】
ここで得られるサブグラフは１つであり、これを以下ではサブグラフＳＧという。ステップＳ１７で検索されたサブグラフが１つの場合は、それをサブグラフＳＧという。
【０１０１】
（中心性値計算部１７の動作）
次に、中心性値計算部１７は、予め設定されている場合、クラスＣＬの定義、キーワードＫＷをもつノードとそのノードへのアークをサブグラフＳＧから除去する（Ｓ２１）。
【０１０２】
ここでは、例えば、図３５に示すように、クラスＣＬ「Ｐｅｒｓｏｎ：人」の定義と、キーワードＫＷ「セマンティックｗｅｂ」をもつノードとそのノードへのアークとが除去され、太線のサブグラフが残る。これを以下ではサブグラフＳＧという。
【０１０３】
次に、中心性値計算部１７は、予め除去すべきアークのラベルがパラメータ記憶部１５に設定されている場合、そのラベルをもつアークをサブグラフＳＧから除去する（Ｓ２３）。
【０１０４】
ここでは、例えば、図３６に示すように、ラベル「ｐｊ：担当者」をもつアークが除去され、太線のサブグラフが残る。これを以下ではサブグラフＳＧという。
【０１０５】
次に、予めサブグラフＳＧを縮める縮退ルールがパラメータ記憶部１５に記憶された場合、その縮退ルールによりサブグラフＳＧの一部を除去し、その残りの部分を接続する（Ｓ２５）。
【０１０６】
ここでは、例えば、縮退ルールによりノードとアークを除去し、それらで接続されていたノード同士を１つのアークだけで接続する。図３７に示す縮退ルールにより、図３８に示すサブグラフを、図３９に示すサブグラフにするのである。
【０１０７】
こうして、縮退ルールにより、後述する中心性値計算に適さないノードを計算対象から除外することができる。
【０１０８】
こうして得られたサブグラフを以下ではサブグラフＳＧという。
【０１０９】
次に、中心性値計算部１７は、サブグラフＳＧの各ノードの中心性値を計算し（Ｓ２７）、予め設定されている場合は、予めパラメータ記憶部１５に記憶された閾値以下の中心性値をもつノードを除外する。
【０１１０】
そして、出力用インタフェース生成部１９が、除外されていないノードのインスタンスが中心性値の高い順に並ぶ出力用インタフェースを生成し、これをユーザ端末２に送信し（Ｓ２９）、表示させる（Ｓ３１）。
【０１１１】
なお、ステップＳ２１、Ｓ２３、Ｓ２５は、必要なときに実行すればよく、の一部または全部を省略してもよい。
【０１１２】
また、中心性値によりノードを除外せずに、全ノードのインスタンスを表示させてもよい。また、ノードのインスタンスに対応づけて、そのノードの中心性値を表示させてもよい。
【０１１３】
（中心性値計算の実施例１）
上記の中心性値計算では、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、各ノードｉにつき、接続されたアークの数ｄｉを求め、図４０（ａ）の式により中心性値を計算する。
【０１１４】
図４１は、計算対象のサブグラフＳＧの一例であり、アークの向きおよびラベルを省略して示す。このサブグラフＳＧからは、図４０（ｂ）のような数ｄｉと中心性値が計算される。
【０１１５】
（中心性値計算の実施例２）
あるいは、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、各ノードｉにつき、他の各ノードとの間のアークの数を求め、その最大値ｍｄｉを求め、図４２（ａ）の式により中心性値を計算する。
【０１１６】
図４１のサブグラフＳＧからは、図４２（ｂ）のような値ｍｄｉと中心性値が計算される。
【０１１７】
（中心性値計算の実施例３）
あるいは、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、各ノードｉにつき、他の各ノードとの間のアークの数を求め、その総和ｍｉを求め、図４３（ａ）の式により中心性値を計算する。
【０１１８】
図４１のサブグラフＳＧからは、図４３（ｂ）のような総和ｍｉと中心性値が計算される。
【０１１９】
（中心性値計算の実施例４）
あるいは、中心性値計算部１７は、サブグラフＳＧのノード数ｎを求め、ｎ個の中の２個の組合せ数ｎＣ２を求め、各ノードｉにつき、そのノードとそのノードに接続されるアークとがない場合に接続が絶たれる２つのノードの組の数ｃｄｐｉを求め、各ノードｉにつき、図４４（ａ）の式により中心性値を計算する。
【０１２０】
例えば、図４１で、インスタンス「ｒｍ：Ｔ−０４８」をもつノードとそのノードに接続されるアークとがない場合、例えば、インスタンス「ｒｍ：Ｔ−０４１」をもつノードとインスタンス「Ｐｅｒｓｏｎ：田中一郎」をもつノードとが接続を絶たれるので、この２つのノードの組がｃｄｐｉの中の１を占めることになる。
【０１２１】
図４１のサブグラフからは、図４４（ｂ）のようなｍｉと中心性値が計算される。
【０１２２】
以上説明したように、本実施の形態によれば、グラフ検索手段（グラフ検索部１６）は、インスタンスをもつノード間がアークによって接続されたグラフＧから、指定された条件を基にして、サブグラフを検索し（Ｓ１７）、中心性値計算手段（中心性値計算部１７）こうして得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する（Ｓ２７）ので、サブグラフの特徴を早期に知ることができる。
【０１２３】
また、パス検索の実施例２で説明したように、グラフ検索手段（１６）は、グラフに等しいグラフにおいて同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称に置換し、複数の同一部分について１つ以外を削除し、仮の名称を予め定められたインスタンスに置換し、置換後のグラフであるテンプレートグラフから、指定された条件を基にして、パスを検索する。そして、当該パスを基にして、グラフからサブグラフを検索し（Ｓ１７）、中心性値計算手段（１７）が、ノードの中心性値を計算する（Ｓ２７）。よって、サブグラフの特徴を早期に知ることができる。
【０１２４】
また、パスパターン生成の実施例３で説明したように、グラフのアークについてのアークスコアが予め記憶されるアークスコア記憶手段（パラメータ記憶部１５）を備え、グラフ検索手段（１６）は、アークスコアを基にして、グラフのノードについてのノードスコアを計算し（図１３、Ｓ１０３）、グラフから、指定された条件を基にして、パスを検索し（図１３、Ｓ１０７）、ノードスコアを基にして、各パスのパススコアを計算し（図１３、Ｓ１０９）、各パスにつき、予め定められたキーワードをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換し（図１３、Ｓ１１１）、全てのパスを同一のパスからなるパスグループごとに区分し、パススコアを基にして、各パスグループにつき、スコアを計算し（図１３、Ｓ１１３）、スコアが予め定めたしきい値以下の各パスグループを削除し（図１３、Ｓ１１５）、残った各パスグループにつき、１パス以外を削除する（図１３、Ｓ１１５）。そして、残った各パスパターンを基にして、グラフからサブグラフを検索し（Ｓ１７）、中心性値計算手段（１７）が、ノードの中心性値を計算する（Ｓ２７）。よって、サブグラフの特徴を早期に知ることができる。
【０１２５】
また、サブグラフパターン生成の実施例５で説明したように、グラフ検索手段（１６）は、グラフから、指定されたキーワード（ＫＷ）に等しいインスタンスをもつノードに接続されたアークのラベルを取得し（図２４ではラベル「ｒｍ：技術キーワード」）、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラス（ＣＬ）が定義されたノードを他方の端位置に有する、パスパターン（図２５ではパターンＰｍ）を生成し、このパスパターンにマッチするパスをグラフから検索し、検索されたパスの中で、クラス（ＣＬ）が定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせ（図２７ではサブグラフＳＧｍ１とサブグラフＳＧｍ２ａの組合せ）であって、第１および第２サブグラフのそれぞれが、キーワード（ＫＷ）に等しいインスタンスをもつノードである第１ノードとクラス（ＣＬ）が定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードにクラス（ＣＬ）が定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせ（図２７のサブグラフＳＧｍ１とサブグラフＳＧｍ２ａの組合せ）を検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換し（図２８ではサブグラフパターンＰｍ１）、第１ノードのインスタンスとしてキーワード（ＫＷ）を設定してなるパターン（図２９ではサブグラフパターンＰｍ１’）を生成する。そして、生成したサブグラフパターンを基にして、グラフからサブグラフを検索し（Ｓ１７）、中心性値計算手段（１７）が、ノードの中心性値を計算する（Ｓ２７）。よって、サブグラフの特徴を早期に知ることができる。
【図面の簡単な説明】
【０１２６】
【図１】本実施の形態に係る中心性値計算装置１の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】グラフＧを表示するためのデータ群の一部を例示した図である。
【図５】本実施の形態のシーケンス図である。
【図６】表示された入力用インタフェースを例示した図である。
【図７】パス検索の実施例２で使用されるテンプレートグラフを生成する途中の状態を例示した図である。
【図８】テンプレートグラフを例示した図である。
【図９】パスパターンを例示した図である。
【図１０】パスパターン生成の実施例２で生成したパスパターンを例示した図である。
【図１１】パスパターン生成の実施例３で使用されるアークスコア記憶部の記憶内容を例示した図である。
【図１２】アークスコアの一部をグラフに当てはめた図である。
【図１３】アークスコア記憶部を用いたパターン生成のフローチャートを示す図である。
【図１４】ノードスコアの計算式を示した図である。
【図１５】ノードスコア計算の例にしたグラフを示す図である。
【図１６】パススコアの計算式を示した図である。
【図１７】パスグループのスコアの計算式を示した図である。
【図１８】パスパターン生成の実施例３で生成したパスパターンを例示した図である。
【図１９】サブグラフパターン生成の実施例１で生成したサブグラフパターンを例示した図である。
【図２０】サブグラフパターン生成の実施例２で生成したサブグラフパターンを例示した図である。
【図２１】サブグラフパターン生成の実施例３で生成したサブグラフパターンを例示した図である。
【図２２】サブグラフパターン生成の実施例４で生成したサブグラフパターンを例示した図である。
【図２３】サブグラフパターン生成の実施例４で生成したサブグラフパターンを例示した図である。
【図２４】キーワードノードに接続されたアークとそのインスタンスを例示した図である。
【図２５】パターンＰｍを例示した図である。
【図２６】サブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３を例示した図である。
【図２７】サブグラフの組み合わせが検出される様子を例示した図である。
【図２８】パターンＰｍ１を例示した図である。
【図２９】キーワードＫＷが設定されたパターンＰｍ１’を例示した図である。
【図３０】表示された入力用インタフェースを例示した図である。
【図３１】クエリを例示した図である。
【図３２】サブグラフを例示した図である。
【図３３】サブグラフを例示した図である。
【図３４】マージ後のサブグラフを例示した図である。
【図３５】一部除去後のサブグラフを例示した図である。
【図３６】一部除去後のサブグラフを例示した図である。
【図３７】縮退ルールを例示した図である。
【図３８】縮退ルールによる一部除去前のサブグラフを例示した図である。
【図３９】縮退ルールによる一部除去前のサブグラフを例示した図である。
【図４０】中心性値計算の実施例１で使用される式、各インスタンスに対応する数ｄｉと中心性値を例示した図である。
【図４１】中心性値計算の例にしたグラフを示す図である。
【図４２】中心性値計算の実施例２で使用される式、各インスタンスに対応する値ｍｄｉと中心性値を例示した図である。
【図４３】中心性値計算の実施例３で使用される式、各インスタンスに対応する総和ｍｉと中心性値を例示した図である。
【図４４】中心性値計算の実施例４で使用される式、各インスタンスに対応する数ｃｄｐｉと中心性値を例示した図である。
【符号の説明】
【０１２７】
１ 中心性値計算装置
１１ グラフデータベース
１４ パターンデータベース
１６ グラフ検索部
１７ 中心性値計算部
【特許請求の範囲】
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフから、指定された条件を基にして、サブグラフを検索するグラフ検索手段と、
前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する中心性値計算手段と
を備えることを特徴とする中心性値計算装置。
【請求項２】
前記グラフは、ノードのインスタンスのクラスが定義されたものであり、
前記グラフ検索手段は、
前記グラフに等しいグラフにおいて同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称に置換し、複数の同一部分について１つ以外を削除し、仮の名称を予め定められたインスタンスに置換し、置換後のグラフであるテンプレートグラフから、指定された条件を基にして、パスを検索し、当該パスを基にして、前記グラフからサブグラフを検索する
ことを特徴とする請求項１記載の中心性値計算装置。
【請求項３】
前記グラフのアークについてのアークスコアが予め記憶されるアークスコア記憶手段を備え、
前記グラフ検索手段は、
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
前記グラフから、指定された条件を基にして、パスを検索し、前記ノードスコアを基にして、各パスのパススコアを計算し、各パスにつき、予め定められたキーワードをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換し、全てのパスを同一のパスからなるパスグループごとに区分し、前記パススコアを基にして、各パスグループにつき、スコアを計算し、スコアが予め定めたしきい値以下の各パスグループを削除し、残った各パスグループにつき、１パス以外を削除し、残った各パスパターンを基にして、前記グラフからサブグラフを検索する
ことを特徴とする請求項１記載の中心性値計算装置。
【請求項４】
前記グラフは、アークがラベルをもち且つインスタンスのクラスが定義されたグラフであり、
前記グラフ検索手段は、
このグラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パスパターンを生成し、
このパスパターンにマッチするパスを前記グラフから検索し、
検索されたパスの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換し、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるサブグラフパターンを生成し、
このサブグラフパターンにマッチするサブグラフを前記グラフから検索する
ことを特徴とする請求項１記載の中心性値計算装置。
【請求項５】
請求項２記載の中心性値計算装置の前記グラフ検索手段が、前記グラフに等しいグラフにおいて同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称に置換し、複数の同一部分について１つ以外を削除し、仮の名称を予め定められたインスタンスに置換し、置換後のグラフであるテンプレートグラフから、指定された条件を基にして、パスを検索し、当該パスを基にして、前記グラフからサブグラフを検索し、 当該中心性値計算装置の中心性値計算手段が、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する
ことを特徴とする中心性値計算方法。
【請求項６】
請求項３記載の中心性値計算装置の前記グラフ検索手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
前記グラフから、指定された条件を基にして、パスを検索し、前記ノードスコアを基にして、各パスのパススコアを計算し、各パスにつき、予め定められたキーワードをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換し、全てのパスを同一のパスからなるパスグループごとに区分し、前記パススコアを基にして、各パスグループにつき、スコアを計算し、スコアが予め定めたしきい値以下の各パスグループを削除し、残った各パスグループにつき、１パス以外を削除し、残った各パスパターンを基にして、前記グラフからサブグラフを検索し、
当該中心性値計算装置の中心性値計算手段が、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する
ことを特徴とする中心性値計算方法。
【請求項７】
請求項４記載の中心性値計算装置の前記グラフ検索手段が、このグラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パスパターンを生成し、
このパスパターンにマッチするパスを前記グラフから検索し、
検索されたパスの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換し、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるサブグラフパターンを生成し、
このサブグラフパターンにマッチするサブグラフを前記グラフから検索し、
当該中心性値計算装置の中心性値計算手段が、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する
ことを特徴とする中心性値計算方法。
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフから、指定された条件を基にして、サブグラフを検索するグラフ検索手段と、
前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する中心性値計算手段と
を備えることを特徴とする中心性値計算装置。
【請求項２】
前記グラフは、ノードのインスタンスのクラスが定義されたものであり、
前記グラフ検索手段は、
前記グラフに等しいグラフにおいて同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称に置換し、複数の同一部分について１つ以外を削除し、仮の名称を予め定められたインスタンスに置換し、置換後のグラフであるテンプレートグラフから、指定された条件を基にして、パスを検索し、当該パスを基にして、前記グラフからサブグラフを検索する
ことを特徴とする請求項１記載の中心性値計算装置。
【請求項３】
前記グラフのアークについてのアークスコアが予め記憶されるアークスコア記憶手段を備え、
前記グラフ検索手段は、
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
前記グラフから、指定された条件を基にして、パスを検索し、前記ノードスコアを基にして、各パスのパススコアを計算し、各パスにつき、予め定められたキーワードをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換し、全てのパスを同一のパスからなるパスグループごとに区分し、前記パススコアを基にして、各パスグループにつき、スコアを計算し、スコアが予め定めたしきい値以下の各パスグループを削除し、残った各パスグループにつき、１パス以外を削除し、残った各パスパターンを基にして、前記グラフからサブグラフを検索する
ことを特徴とする請求項１記載の中心性値計算装置。
【請求項４】
前記グラフは、アークがラベルをもち且つインスタンスのクラスが定義されたグラフであり、
前記グラフ検索手段は、
このグラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パスパターンを生成し、
このパスパターンにマッチするパスを前記グラフから検索し、
検索されたパスの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換し、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるサブグラフパターンを生成し、
このサブグラフパターンにマッチするサブグラフを前記グラフから検索する
ことを特徴とする請求項１記載の中心性値計算装置。
【請求項５】
請求項２記載の中心性値計算装置の前記グラフ検索手段が、前記グラフに等しいグラフにおいて同じクラスが定義された複数のノードのインスタンスを当該クラスに対応する仮の名称に置換し、複数の同一部分について１つ以外を削除し、仮の名称を予め定められたインスタンスに置換し、置換後のグラフであるテンプレートグラフから、指定された条件を基にして、パスを検索し、当該パスを基にして、前記グラフからサブグラフを検索し、 当該中心性値計算装置の中心性値計算手段が、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する
ことを特徴とする中心性値計算方法。
【請求項６】
請求項３記載の中心性値計算装置の前記グラフ検索手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
前記グラフから、指定された条件を基にして、パスを検索し、前記ノードスコアを基にして、各パスのパススコアを計算し、各パスにつき、予め定められたキーワードをインスタンスとしてもつノード以外のノードのインスタンスを変数に置換し、全てのパスを同一のパスからなるパスグループごとに区分し、前記パススコアを基にして、各パスグループにつき、スコアを計算し、スコアが予め定めたしきい値以下の各パスグループを削除し、残った各パスグループにつき、１パス以外を削除し、残った各パスパターンを基にして、前記グラフからサブグラフを検索し、
当該中心性値計算装置の中心性値計算手段が、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する
ことを特徴とする中心性値計算方法。
【請求項７】
請求項４記載の中心性値計算装置の前記グラフ検索手段が、このグラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パスパターンを生成し、
このパスパターンにマッチするパスを前記グラフから検索し、
検索されたパスの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置換し、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるサブグラフパターンを生成し、
このサブグラフパターンにマッチするサブグラフを前記グラフから検索し、
当該中心性値計算装置の中心性値計算手段が、前記グラフ検索手段により得られたサブグラフに含まれる各ノードにつき、当該サブグラフにおける中心性を示す中心性値を計算する
ことを特徴とする中心性値計算方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【公開番号】特開２００８−１８１３３２（Ｐ２００８−１８１３３２Ａ）
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願番号】特願２００７−１４１８６（Ｐ２００７−１４１８６）
【出願日】平成１９年１月２４日（２００７．１．２４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願日】平成１９年１月２４日（２００７．１．２４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]