グラフ検索装置およびその動作方法
【課題】ノードの関係性を枝狩り以外の方法で抽出し、俯瞰図を目視以外の方法で比較する。
【解決手段】クエリ発行部１４は、グラフデータベース１２に記憶されたグラフからサブグラフを検索する。ノード間係数計算部１６は、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する。
【解決手段】クエリ発行部１４は、グラフデータベース１２に記憶されたグラフからサブグラフを検索する。ノード間係数計算部１６は、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ検索装置およびその動作方法に関するものである。
【背景技術】
【０００２】
様々なデータをグラフとして表現して、複数のデータソース間の関係等を、統一した表現で表す方法が確立されている。また、グラフとして表現されたデータから、特徴的な関係を発見するグラフマイニングなどの手法に関する研究が進んでいる。
【０００３】
産業技術総合研究所（松尾ら）の研究は、係数を求めたい複数の事柄に関するキーワードを用いて、インターネット上で情報検索を行い、その検索結果の重なり（共起）を求め、複数の事柄間の関係を求めることに関する。
【０００４】
しかし、この研究では、複数のデータが異なる関係で結ばれている状態から、ノード間の関係を分析することには触れられていない。
【０００５】
下記の特許文献１記載の「パターンに基づく関係抽出システム」は、複数のノードを、グラフパターンの１変数に代入してクエリパターンを得て、このクエリパターンによる検索を行い、特定種類のノードの値の重複具合から、ノード間の関係性を求める技術を公開している。
【０００６】
しかし、グラフパターンの違いに応じて、異なる観点毎に特定種類のノード同士の関係を計算し、ユーザに提示することはできない。また、複数のクエリパターンを基に算出されるノード間の関係性を比較することは明記されていない。
【０００７】
下記の特許文献２記載の「複数のサブグラフのユーザ提示順位決定システム」は、グラフパターンを用いた検索において、複数の検索結果から得られるグラフを順序付けする技術を公開している。
【０００８】
しかし、グラフパターンの違いに応じて、異なる観点毎に特定種類のノード同士の関係を計算し、ユーザに提示することはできない。また、複数のクエリパターンを基に算出されるノード間の関係性を比較することは明記されていない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−１８１３３１号公報
【特許文献２】特開２００７−１４０７１４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、上記の事情に鑑みてなされたものであり、以下の問題を解決することを目的とする。
【００１１】
つまり、様々な種類のノードとアークから構成されたグラフデータから、１種類のノードの関係性を俯瞰したい場合、
課題１：ノードの関係性を単純な枝狩り以外の方法で抽出することが困難であること、
課題２：様々な関係性から算出される俯瞰図（無向グラフ）を目視以外の方法で比較することができないこと、を本発明によって解決する。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、第１の本発明に係るグラフ検索装置は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、前記グラフデータベースに記憶された前記グラフからサブグラフを検索するグラフ検索手段と、前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算するノード間係数計算手段とを備えることを特徴とする。
【００１３】
第２の本発明に係るグラフ検索装置は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索するグラフ検索手段と、前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算するノード間係数計算手段とを備えることを特徴とする。
【００１４】
例えば、前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算する。
【００１５】
例えば、前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用するようになっていることを特徴とする。
【００１６】
例えば、前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する。
【００１７】
第３の本発明に係るグラフ検索装置の動作方法は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフからサブグラフを検索し、前記グラフ検索装置のノード間係数計算手段が、前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算することを特徴とする。
【００１８】
第４の本発明に係るグラフ検索装置の動作方法は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索し、前記グラフ検索装置のノード間係数計算手段が、前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算することを特徴とする。
【００１９】
例えば、前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算する。
【００２０】
例えば、前記グラフ検索装置は、前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、前記動作方法は、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用することを特徴とする。
【００２１】
例えば、前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する。
【発明の効果】
【００２２】
本発明のグラフ検索装置によれば、グラフからサブグラフを検索し、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算するので、課題１を解決つまりノード間の関係を枝狩りをせずに求めることができ、課題２の解決つまり、目視せずにノード間係数によって無向グラフを比較することができる。
【図面の簡単な説明】
【００２３】
【図１】本実施の形態に係るグラフ検索装置の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】パターンをグラフ化して例示した図である。
【図５】グラフＧからサブグラフを検索するときのシーケンス図である。
【図６】表示された入力用インタフェースを例示した図である。
【図７】サブグラフＳＧａ１、ＳＧａ２、ＳＧａ３を示した図である。
【図８】ステップＳ１９におけるサブグラフＳＧａについての処理の具体例を示す図である。
【図９】ステップＳ１９におけるサブグラフＳＧｂについての処理の具体例を示す図である。
【図１０】ステップＳ１９におけるサブグラフＳＧｃについての処理の具体例を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一または類似のものには同一符号を付与し、重複説明を省略する。
【００２５】
図１は、本実施の形態に係るグラフ検索装置の構成図である。
【００２６】
グラフ検索装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００２７】
グラフ検索装置１は、表示装置３に表示される入力用インタフェースと出力用インタフェースを生成しユーザ端末２に送信するユーザインタフェース１１と、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベース１２と、
サブグラフの検索に用いられるパターンが記憶されるパターンデータベース１３と、サブグラフやパターンを検索するクエリ発行部１４と、サブグラフのグラフパターン係数を計算するグラフパターン係数計算部１５と、サブグラフを基にした無向グラフ（俯瞰図）におけるノード間の関係を示すノード間係数を計算するノード間係数計算部１６とを備える。
【００２８】
図２は、グラフデータベース１２に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２９】
グラフデータベース１２に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１２に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００３０】
グラフＧでは、例えば、「Ｂ技術」や「論文Ｆ」などのインスタンスをもつノードが、「ＫＷ」や「著者」などのラベルをもつアークで接続される。また、図示しないが、グラフＧでは、ノードにそのインスタンス「山田太郎」などの概念であるクラス「人」などが定義される。
【００３１】
図３に示すように、「論文Ｆ」で示され、その元データの著者が山田太郎でり、題名が「Ｂ技術入門」であり、キーワードがＢ技術である、元データは、グラフデータベース１２では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１２に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。ＲＤＦについては、以下の文献に記載されている。
【００３２】
「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/>
図１に戻り、パターンデータベース１３には、サブグラフの検索に用いられるパターンが記憶される。
【００３３】
図４は、パターンデータベース１３に記憶されたパターンのうちの４パターンをグラフ化して例示した図である。
【００３４】
パターンは、グラフデータベース１２に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを本図のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。なお、データ群である実際のパターンを逐一説明するのは冗長なのでグラフ化されたパターンで便宜的に説明する。
【００３５】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、図に示すように、？とそれに後続する単語からなる。
【００３６】
ここでは、クラス「技術用語」が定義されたノードを一方の端位置に有し、クラス「人」が定義されたノードを他方の端位置に有し、
各ノードがインスタンスをもたず、各アークがラベルをもつ、パターンＰａ、Ｐｂ、Ｐｃがパターンデータベース１３に記憶されていることとする。
【００３７】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００３８】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有するものである。
【００３９】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【００４０】
図１に戻り、クエリ発行部１４は、パターンデータベース１３からパターンを検索する。また、クエリ発行部１４は、グラフＧのサブグラフを検索する。
【００４１】
グラフ検索装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをグラフ検索装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。
【００４２】
（本実施の形態の動作）
図５は、グラフＧからサブグラフを検索するときのシーケンス図である。
【００４３】
グラフ検索装置１では、ユーザインタフェース１１が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６のように表示させる（Ｓ３）。
【００４４】
例として、ユーザは、ページ記述言語（以下、抽象化して「Ａ技術」という）、暗号通信（以下、抽象化して「Ｂ技術」という）、本人認証（以下、抽象化して「Ｃ技術」という）および課金（以下、抽象化して「Ｄ技術」という）という４つの技術間の「人」を介した関係の強さを知りたいとする。
【００４５】
この例では、ユーザの操作により、「Ａ技術」〜「Ｄ技術」を包含する「技術用語」という情報（クラス「技術用語」という）と、「人」という情報（クラス「人」という）が、入力用インタフェース内に含まれた情報から選択されたこととする。
【００４６】
また、ユーザ端末２では、ユーザの操作により、ネットワーク密度「０．７」とクラスタ係数「０．５」が指定されたこととする。
【００４７】
ユーザ端末２は、クラス「技術用語」、クラス「人」、ネットワーク密度「０．７」およびクラスタ係数「０．５」（これらを総称して「パラメータ」という）をグラフ検索装置１に送信する（Ｓ５）。
【００４８】
グラフ検索装置１では、クエリ発行部１４が、クラス「技術用語」とクラス「人」を含む検索構文であるクエリをパターンデータベース１３に送信し、これにより、クラス「技術用語」が定義されたノードを一方の端位置に有し、クラス「人」が定義されたノードを他方の端位置に有するパターンをパターンデータベース１３から検索する（Ｓ７）。
【００４９】
次に、クエリ発行部１４が、そのパターンをクエリに変換し、それをグラフデータベース１２に送信する（Ｓ９）ことで、そのパターンにマッチするサブグラフをグラフＧから取得する（Ｓ１１）。
【００５０】
なお、このパターンは、ユーザ端末２での操作により検索されたものであるが、ここで使用するものとして予めグラフ検索装置１が記憶したパターンを用いてよい。また、この検索は、ユーザ端末２での操作により行われるが、これを予め決めた時刻に行ってもよい。また、クラス「技術用語」とクラス「人」は、ユーザ端末２での操作によりグラフ検索装置１が得るものであるが、一方または両方のクラスを予めグラフ検索装置１が記憶しておき、それを用いてもよい。
【００５１】
さて、前述のＳ１１を行うことで、ここでは、図４のパターンＰａから、図７に太線で示したサブグラフＳＧａ１、ＳＧａ２、ＳＧａ３が取得されたこととする。
【００５２】
この各サブグラフでは、一方の端位置のノード（つまりクラス「技術用語」が定義されたノード）のインスタンスが「Ｂ技術」であるが、パターンＰａからは、一方の端位置のノードのインスタンスが「Ａ技術」であるサブグラフや、一方の端位置のノードのインスタンスが「Ｃ技術」であるサブグラフも取得される。
【００５３】
各サブグラフでは、一方の端位置のノード（つまりクラス「技術用語」が定義されたノード）を「キーノード」といい、他方の端位置のノード（つまりクラス「人」が定義されたノード）を「ターゲットノード」という。
【００５４】
ここでは、図４のパターンＰａから取得された複数のサブグラフをトータルしたものをサブグラフＳＧａという。また、同様に、パターンＰｂから取得された複数のサブグラフをトータルしたものをサブグラフＳＧｂという。また、同様に、パターンＰｃから取得された複数のサブグラフをトータルしたものをサブグラフＳＧｃという。
【００５５】
図６に戻り、各サブグラフＳＧａ、ＳＧｂ、ＳＧｃがグラフパターン係数計算部１５に与えられる（Ｓ１３）と、グラフパターン係数計算部１５が、各サブグラフのグラフパターン係数を計算する（Ｓ１５）。
【００５６】
次に、グラフパターン係数計算部１５は、例えば、式（１）により、
【数１】
【００５７】
グラフパターン係数であるネットワーク密度を計算する。ここで、Ｎは、サブグラフ内のノード数である。ｋｉは、ｉ番目のノードに接続されたアーク数である。
【００５８】
または、例えば、式（２）により、
【数２】
【００５９】
グラフパターン係数であるクラスタ係数を計算する。ここで、Ｎは、サブグラフ内のノード数である。ｋｉは、ｉ番目のノードに接続されたアーク数である。Ｅｉは、ｉ番目のノードに１本のアークで接続されたノード間を接続するアーク数である。
【００６０】
次に、グラフパターン係数計算部１５は、パラメータ内のネットワーク密度「０．７」を含む範囲（例えば、０．７±０．０２の範囲）に、計算されたネットワーク密度が含まれ、かつ、パラメータ内のクラスタ係数「０．５」を含む範囲（例えば、０．５±０．０２の範囲）に計算されたクラスタ係数が含まれるというような条件を満たすか否かを判定する（Ｓ１７）。
【００６１】
なお、条件は、パラメータ内のネットワーク密度を含む範囲に、計算されたネットワーク密度が含まれる、「または」、パラメータ内のクラスタ係数を含む範囲に計算されたクラスタ係数が含まれるというような条件でもよい。
【００６２】
また、条件は、（１）計算されたネットワーク密度が、パラメータ内のネットワーク密度以上であるという条件と、（２）計算されたクラスタ係数が、パラメータ内のクラスタ係数以上であるという条件とを組み合わせたものでもよい。
【００６３】
また、計算値がパラメータ内の値未満、または、以下、または、より大きいという条件を使用してもよい。
【００６４】
さて、グラフパターン係数計算部１５は、ステップＳ１７で条件を満たさないと判定すると、制御をステップＳ７に戻す。
【００６５】
ここでは、クエリ発行部１４は、図４のパターンとは異なるパターンをパターンデータベース１３から検索する（Ｓ７）。クエリ発行部１４は、例えば、クラス「技術用語」が定義されたノードを一方の端位置に有し、クラス「人」が定義されたノードを他方の端位置に有し、これら各端位置のノード間に３本のアークが直列に接続されたパターン、つまり、各端位置のノード間に２本のアークが直列に接続された、図４のパターンとは異なるパターンをパターンデータベース１３から検索する（Ｓ７）。
【００６６】
一方、ステップＳ１７で条件を満たしたと判定されたなら、ノード間係数計算部１６は、ノード間係数を計算する（Ｓ１９）。
【００６７】
図８は、ステップＳ１９における処理の一部つまりサブグラフＳＧａについての具体例を示す図である。
【００６８】
図８（ａ）に示すように、サブグラフＳＧａには、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「中村二郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山本幸子」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフＳＧａ１、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフＳＧａ２、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフＳＧａ３、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、が含まれる。
【００６９】
ノード間係数計算部１６は、サブグラフＳＧａを基にこれから作ろうとする無向グラフ（以下、グラフＲＧａという）内の各インスタンス「Ａ技術」、「Ｂ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ａ技術」、「Ｂ技術」）、グラフＲＧａ内の各インスタンス「Ａ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ａ技術」、「Ｃ技術」）、グラフＲＧａ内の各インスタンス「Ａ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ａ技術」、「Ｄ技術」）、グラフＲＧａ内の各インスタンス「Ｂ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ｂ技術」、「Ｃ技術」）、グラフＲＧａ内の各インスタンス「Ｂ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ｂ技術」、「Ｄ技術」）、グラフＲＧａ内の各インスタンス「Ｃ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ｃ技術」、「Ｄ技術」）を計算する。
【００７０】
例えば、ノード間係数ＲＧａ（ｘ、ｙ）は、式（３）（ただし、αはａ）により計算される。
【００７１】
ＲＧα（ｘ，ｙ）
＝｜Ｘ∩Ｙ｜／ｍｉｎ（｜Ｘ｜，｜Ｙ｜） …（３）
ただし、
Ｘは、インスタンス「ｘ」を有するキーノードを含むサブグラフの集合、
Ｙは、インスタンス「ｙ」を有するキーノードを含むサブグラフの集合、
｜Ｘ｜は、Ｘ内のサブグラフの数、
｜Ｙ｜は、Ｙ内のサブグラフの数、
ｍｉｎ（｜Ｘ｜，｜Ｙ｜）は、｜Ｘ｜と｜Ｙ｜の小さい方、
｜Ｘ∩Ｙ｜は、ＸとＹ共通なインスタンスを有するターゲットノードの数である。
【００７２】
図８（ｂ）に示すように、各
ノード間係数ＲＧａ（「Ａ技術」、「Ｂ技術」）は約０．３、ノード間係数ＲＧａ（「Ａ技術」、「Ｃ技術」）は０、ノード間係数ＲＧａ（「Ａ技術」、「Ｄ技術」）は０、
ノード間係数ＲＧａ（「Ｂ技術」、「Ｃ技術」）は１、ノード間係数ＲＧａ（「Ｂ技術」、「Ｄ技術」）は１、ノード間係数ＲＧａ（「Ｃ技術」、「Ｄ技術」）は０となる。
【００７３】
図８（ｃ）に示すようにグラフＲＧａは表される。ノード間係数が０のノード間のアークは図示省略している。
【００７４】
図９は、ステップＳ１９における処理の一部つまりサブグラフＳＧｂについての具体例を示す図である。
【００７５】
図９（ａ）に示すように、サブグラフＳＧｂには、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、が含まれる。
【００７６】
ノード間係数計算部１６は、サブグラフＳＧｂを基にこれから作ろうとする無向グラフ（以下、グラフＲＧｂという）内の各インスタンス「Ａ技術」、「Ｂ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ａ技術」、「Ｂ技術」）、グラフＲＧｂ内の各インスタンス「Ａ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ａ技術」、「Ｃ技術」）、グラフＲＧｂ内の各インスタンス「Ａ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ａ技術」、「Ｄ技術」）、グラフＲＧｂ内の
各インスタンス「Ｂ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ｂ技術」、「Ｃ技術」）、グラフＲＧｂ内の各インスタンス「Ｂ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ｂ技術」、「Ｄ技術」）、グラフＲＧｂ内の各インスタンス「Ｃ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ｃ技術」、「Ｄ技術」）を計算する。
【００７７】
例えば、ノード間係数ＲＧｂ（ｘ、ｙ）は、前述の式（３）（ただし、αはｂ）により計算される。
【００７８】
図９（ｂ）に示すように、各ノード間係数ＲＧｂ（「Ａ技術」、「Ｂ技術」）は０、
ノード間係数ＲＧｂ（「Ａ技術」、「Ｃ技術」）は０、ノード間係数ＲＧｂ（「Ａ技術」、「Ｄ技術」）は０、ノード間係数ＲＧｂ（「Ｂ技術」、「Ｃ技術」）は０、
ノード間係数ＲＧｂ（「Ｂ技術」、「Ｄ技術」）は１、ノード間係数ＲＧｂ（「Ｃ技術」、「Ｄ技術」）は０となる。
【００７９】
図９（ｃ）に示すようにグラフＲＧｂは表される。ノード間係数が０のノード間のアークは図示省略している。
【００８０】
図１０は、ステップＳ１９における処理の一部つまりサブグラフＳＧａについての具体例を示す図である。
【００８１】
図１０（ａ）に示すように、サブグラフＳＧｃには、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「中村二郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山本幸子」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、が含まれる。
【００８２】
ノード間係数計算部１６は、サブグラフＳＧｃを基にこれから作ろうとする無向グラフ（以下、グラフＲＧｃという）内の各インスタンス「Ａ技術」、「Ｂ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ａ技術」、「Ｂ技術」）、グラフＲＧｃ内の各インスタンス「Ａ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ａ技術」、「Ｃ技術」）、グラフＲＧｃ内の各インスタンス「Ａ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ａ技術」、「Ｄ技術」）、グラフＲＧｃ内の
各インスタンス「Ｂ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ｂ技術」、「Ｃ技術」）、グラフＲＧｃ内の各インスタンス「Ｂ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ｂ技術」、「Ｄ技術」）、グラフＲＧｃ内の各インスタンス「Ｃ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ｃ技術」、「Ｄ技術」）を計算する。
【００８３】
例えば、ノード間係数ＲＧｂ（ｘ、ｙ）は、前述の式（３）（ただし、αはｃ）により計算される。
【００８４】
図１０（ｂ）に示すように、各ノード間係数ＲＧｃ（「Ａ技術」、「Ｂ技術」）は約０．３、ノード間係数ＲＧｃ（「Ａ技術」、「Ｃ技術」）は０．５、ノード間係数ＲＧｃ（「Ａ技術」、「Ｄ技術」）は約０．３、ノード間係数ＲＧｃ（「Ｂ技術」、「Ｃ技術」）は１、ノード間係数ＲＧｃ（「Ｂ技術」、「Ｄ技術」）は１、ノード間係数ＲＧｃ（「Ｃ技術」、「Ｄ技術」）は１となる。
【００８５】
図１０（ｃ）に示すようにグラフＲＧｃは表される。
【００８６】
図５に戻り、ノード間係数計算部１６は、計算したノード間係数を含むグラフＲＧａ、ＲＧｂ、ＲＧｃをユーザインタフェース１１に渡す（Ｓ２１）。
【００８７】
ユーザインタフェース１１は、グラフＲＧａ、ＲＧｂ、ＲＧｃに基づく出力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ２３）、図８（ｃ）、図９（ｃ）、図１０（ｃ）のように表示させる（Ｓ２５）。
【００８８】
なお、ノード間係数計算部１６は、ノード間係数に基づいて、グラフＲＧａ、ＲＧｂ、ＲＧｃに順位を付与し、ユーザインタフェース１１は、その順位を表示させてもよい。
【００８９】
順位は、例えば、（１）ノード間係数の総和に応じたものとすること、（２）０でないノード間係数に対応するアークの総数に応じたものとすること、などが考えられる。
【００９０】
以上説明したように、本実施の形態に係るグラフ検索装置によれば、グラフＧからサブグラフＳＧａなどを検索し、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノード（クラス「技術用語」が定義されたインスタンス「Ａ技術」などを有するノード）を備える無向グラフ（グラフＲＧａなど）における各ノード間の関係を示すノード間係数（ノード間係数ＲＧａ（「Ａ技術」、「Ｂ技術」）など）を計算するので、課題１を解決つまりノード間の関係を枝狩りをせずに求めることができ、課題２の解決つまり、目視せずにノード間係数によって無向グラフを比較することができる。
【００９１】
具体的には、各無向グラフは、該無効グラフに対応するパターン（Ｐａなど）に対応して生成される。１つの無効グラフには、「Ａ技術」と「Ｂ技術」の関係などが表現されており、よって、そのような関係をパターンの違いに応じて比べることができる。
【００９２】
また、グラフ検索手段（クエリ発行部１４）が、グラフＧからサブグラフＳＧａなどを検索し、ノード間係数計算手段（ノード間係数計算部１６）が、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノード（インスタンス「Ａ技術」などを有するノード）を備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、前記種類以外のインスタンスを有する部分（クラス「人」が定義されたノードなど）を用いて当該ノード間係数を計算する。
【００９３】
また、グラフ検索手段が、グラフＧから、予め指定された第１の種類のノード（クラス「技術用語」が定義されたノード）と予め指定された第２の種類のノード（クラス「人」が定義されたノード）とを有するサブグラフを、複数の前記第１の種類のノードのインスタンス（Ａ技術〜Ｄ技術）のそれぞれにつき１以上検索し、ノード間係数計算手段が、第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、式（３）により、つまり、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合（Ｘ）と、他方のノードのインスタンスを有する前記サブグラフからなる集合（Ｙ）との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算する。
【００９４】
また、ノード間計算手段は、式（３）により、つまり、各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算する
また、グラフ検索装置は、検索されたサブグラフＳＧａ１、ＳＧａ２、ＳＧａ３をトータルしたサブグラフＳＧａなどの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段（グラフパターン係数計算部１５）を備え、予め指定された値（ネットワーク密度「０．７」やクラスタ係数「０．５」）に合致するグラフパターン係数に対応するサブグラフを使用する（ステップＳ１７：ＹＥＳ）。
【００９５】
また、ノード間係数計算手段は、複数の無向グラフＲＧａ、ＲＧｂ、ＲＧｃに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する。これは、課題２の解決にも貢献する。
【符号の説明】
【００９６】
１…グラフ検索装置
２…ユーザ端末
３…表示装置
１２…グラフデータベース
１１…ユーザインタフェース
１３…パターンデータベース
１４…クエリ発行部
１５…グラフパターン係数計算部
１６…ノード間係数計算部
【技術分野】
【０００１】
本発明は、グラフ検索装置およびその動作方法に関するものである。
【背景技術】
【０００２】
様々なデータをグラフとして表現して、複数のデータソース間の関係等を、統一した表現で表す方法が確立されている。また、グラフとして表現されたデータから、特徴的な関係を発見するグラフマイニングなどの手法に関する研究が進んでいる。
【０００３】
産業技術総合研究所（松尾ら）の研究は、係数を求めたい複数の事柄に関するキーワードを用いて、インターネット上で情報検索を行い、その検索結果の重なり（共起）を求め、複数の事柄間の関係を求めることに関する。
【０００４】
しかし、この研究では、複数のデータが異なる関係で結ばれている状態から、ノード間の関係を分析することには触れられていない。
【０００５】
下記の特許文献１記載の「パターンに基づく関係抽出システム」は、複数のノードを、グラフパターンの１変数に代入してクエリパターンを得て、このクエリパターンによる検索を行い、特定種類のノードの値の重複具合から、ノード間の関係性を求める技術を公開している。
【０００６】
しかし、グラフパターンの違いに応じて、異なる観点毎に特定種類のノード同士の関係を計算し、ユーザに提示することはできない。また、複数のクエリパターンを基に算出されるノード間の関係性を比較することは明記されていない。
【０００７】
下記の特許文献２記載の「複数のサブグラフのユーザ提示順位決定システム」は、グラフパターンを用いた検索において、複数の検索結果から得られるグラフを順序付けする技術を公開している。
【０００８】
しかし、グラフパターンの違いに応じて、異なる観点毎に特定種類のノード同士の関係を計算し、ユーザに提示することはできない。また、複数のクエリパターンを基に算出されるノード間の関係性を比較することは明記されていない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−１８１３３１号公報
【特許文献２】特開２００７−１４０７１４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、上記の事情に鑑みてなされたものであり、以下の問題を解決することを目的とする。
【００１１】
つまり、様々な種類のノードとアークから構成されたグラフデータから、１種類のノードの関係性を俯瞰したい場合、
課題１：ノードの関係性を単純な枝狩り以外の方法で抽出することが困難であること、
課題２：様々な関係性から算出される俯瞰図（無向グラフ）を目視以外の方法で比較することができないこと、を本発明によって解決する。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、第１の本発明に係るグラフ検索装置は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、前記グラフデータベースに記憶された前記グラフからサブグラフを検索するグラフ検索手段と、前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算するノード間係数計算手段とを備えることを特徴とする。
【００１３】
第２の本発明に係るグラフ検索装置は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索するグラフ検索手段と、前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算するノード間係数計算手段とを備えることを特徴とする。
【００１４】
例えば、前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算する。
【００１５】
例えば、前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用するようになっていることを特徴とする。
【００１６】
例えば、前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する。
【００１７】
第３の本発明に係るグラフ検索装置の動作方法は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフからサブグラフを検索し、前記グラフ検索装置のノード間係数計算手段が、前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算することを特徴とする。
【００１８】
第４の本発明に係るグラフ検索装置の動作方法は、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索し、前記グラフ検索装置のノード間係数計算手段が、前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算することを特徴とする。
【００１９】
例えば、前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算する。
【００２０】
例えば、前記グラフ検索装置は、前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、前記動作方法は、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用することを特徴とする。
【００２１】
例えば、前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する。
【発明の効果】
【００２２】
本発明のグラフ検索装置によれば、グラフからサブグラフを検索し、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算するので、課題１を解決つまりノード間の関係を枝狩りをせずに求めることができ、課題２の解決つまり、目視せずにノード間係数によって無向グラフを比較することができる。
【図面の簡単な説明】
【００２３】
【図１】本実施の形態に係るグラフ検索装置の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】パターンをグラフ化して例示した図である。
【図５】グラフＧからサブグラフを検索するときのシーケンス図である。
【図６】表示された入力用インタフェースを例示した図である。
【図７】サブグラフＳＧａ１、ＳＧａ２、ＳＧａ３を示した図である。
【図８】ステップＳ１９におけるサブグラフＳＧａについての処理の具体例を示す図である。
【図９】ステップＳ１９におけるサブグラフＳＧｂについての処理の具体例を示す図である。
【図１０】ステップＳ１９におけるサブグラフＳＧｃについての処理の具体例を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一または類似のものには同一符号を付与し、重複説明を省略する。
【００２５】
図１は、本実施の形態に係るグラフ検索装置の構成図である。
【００２６】
グラフ検索装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００２７】
グラフ検索装置１は、表示装置３に表示される入力用インタフェースと出力用インタフェースを生成しユーザ端末２に送信するユーザインタフェース１１と、インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベース１２と、
サブグラフの検索に用いられるパターンが記憶されるパターンデータベース１３と、サブグラフやパターンを検索するクエリ発行部１４と、サブグラフのグラフパターン係数を計算するグラフパターン係数計算部１５と、サブグラフを基にした無向グラフ（俯瞰図）におけるノード間の関係を示すノード間係数を計算するノード間係数計算部１６とを備える。
【００２８】
図２は、グラフデータベース１２に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２９】
グラフデータベース１２に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１２に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００３０】
グラフＧでは、例えば、「Ｂ技術」や「論文Ｆ」などのインスタンスをもつノードが、「ＫＷ」や「著者」などのラベルをもつアークで接続される。また、図示しないが、グラフＧでは、ノードにそのインスタンス「山田太郎」などの概念であるクラス「人」などが定義される。
【００３１】
図３に示すように、「論文Ｆ」で示され、その元データの著者が山田太郎でり、題名が「Ｂ技術入門」であり、キーワードがＢ技術である、元データは、グラフデータベース１２では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１２に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。ＲＤＦについては、以下の文献に記載されている。
【００３２】
「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/>
図１に戻り、パターンデータベース１３には、サブグラフの検索に用いられるパターンが記憶される。
【００３３】
図４は、パターンデータベース１３に記憶されたパターンのうちの４パターンをグラフ化して例示した図である。
【００３４】
パターンは、グラフデータベース１２に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを本図のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。なお、データ群である実際のパターンを逐一説明するのは冗長なのでグラフ化されたパターンで便宜的に説明する。
【００３５】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、図に示すように、？とそれに後続する単語からなる。
【００３６】
ここでは、クラス「技術用語」が定義されたノードを一方の端位置に有し、クラス「人」が定義されたノードを他方の端位置に有し、
各ノードがインスタンスをもたず、各アークがラベルをもつ、パターンＰａ、Ｐｂ、Ｐｃがパターンデータベース１３に記憶されていることとする。
【００３７】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００３８】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有するものである。
【００３９】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【００４０】
図１に戻り、クエリ発行部１４は、パターンデータベース１３からパターンを検索する。また、クエリ発行部１４は、グラフＧのサブグラフを検索する。
【００４１】
グラフ検索装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをグラフ検索装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。
【００４２】
（本実施の形態の動作）
図５は、グラフＧからサブグラフを検索するときのシーケンス図である。
【００４３】
グラフ検索装置１では、ユーザインタフェース１１が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図６のように表示させる（Ｓ３）。
【００４４】
例として、ユーザは、ページ記述言語（以下、抽象化して「Ａ技術」という）、暗号通信（以下、抽象化して「Ｂ技術」という）、本人認証（以下、抽象化して「Ｃ技術」という）および課金（以下、抽象化して「Ｄ技術」という）という４つの技術間の「人」を介した関係の強さを知りたいとする。
【００４５】
この例では、ユーザの操作により、「Ａ技術」〜「Ｄ技術」を包含する「技術用語」という情報（クラス「技術用語」という）と、「人」という情報（クラス「人」という）が、入力用インタフェース内に含まれた情報から選択されたこととする。
【００４６】
また、ユーザ端末２では、ユーザの操作により、ネットワーク密度「０．７」とクラスタ係数「０．５」が指定されたこととする。
【００４７】
ユーザ端末２は、クラス「技術用語」、クラス「人」、ネットワーク密度「０．７」およびクラスタ係数「０．５」（これらを総称して「パラメータ」という）をグラフ検索装置１に送信する（Ｓ５）。
【００４８】
グラフ検索装置１では、クエリ発行部１４が、クラス「技術用語」とクラス「人」を含む検索構文であるクエリをパターンデータベース１３に送信し、これにより、クラス「技術用語」が定義されたノードを一方の端位置に有し、クラス「人」が定義されたノードを他方の端位置に有するパターンをパターンデータベース１３から検索する（Ｓ７）。
【００４９】
次に、クエリ発行部１４が、そのパターンをクエリに変換し、それをグラフデータベース１２に送信する（Ｓ９）ことで、そのパターンにマッチするサブグラフをグラフＧから取得する（Ｓ１１）。
【００５０】
なお、このパターンは、ユーザ端末２での操作により検索されたものであるが、ここで使用するものとして予めグラフ検索装置１が記憶したパターンを用いてよい。また、この検索は、ユーザ端末２での操作により行われるが、これを予め決めた時刻に行ってもよい。また、クラス「技術用語」とクラス「人」は、ユーザ端末２での操作によりグラフ検索装置１が得るものであるが、一方または両方のクラスを予めグラフ検索装置１が記憶しておき、それを用いてもよい。
【００５１】
さて、前述のＳ１１を行うことで、ここでは、図４のパターンＰａから、図７に太線で示したサブグラフＳＧａ１、ＳＧａ２、ＳＧａ３が取得されたこととする。
【００５２】
この各サブグラフでは、一方の端位置のノード（つまりクラス「技術用語」が定義されたノード）のインスタンスが「Ｂ技術」であるが、パターンＰａからは、一方の端位置のノードのインスタンスが「Ａ技術」であるサブグラフや、一方の端位置のノードのインスタンスが「Ｃ技術」であるサブグラフも取得される。
【００５３】
各サブグラフでは、一方の端位置のノード（つまりクラス「技術用語」が定義されたノード）を「キーノード」といい、他方の端位置のノード（つまりクラス「人」が定義されたノード）を「ターゲットノード」という。
【００５４】
ここでは、図４のパターンＰａから取得された複数のサブグラフをトータルしたものをサブグラフＳＧａという。また、同様に、パターンＰｂから取得された複数のサブグラフをトータルしたものをサブグラフＳＧｂという。また、同様に、パターンＰｃから取得された複数のサブグラフをトータルしたものをサブグラフＳＧｃという。
【００５５】
図６に戻り、各サブグラフＳＧａ、ＳＧｂ、ＳＧｃがグラフパターン係数計算部１５に与えられる（Ｓ１３）と、グラフパターン係数計算部１５が、各サブグラフのグラフパターン係数を計算する（Ｓ１５）。
【００５６】
次に、グラフパターン係数計算部１５は、例えば、式（１）により、
【数１】
【００５７】
グラフパターン係数であるネットワーク密度を計算する。ここで、Ｎは、サブグラフ内のノード数である。ｋｉは、ｉ番目のノードに接続されたアーク数である。
【００５８】
または、例えば、式（２）により、
【数２】
【００５９】
グラフパターン係数であるクラスタ係数を計算する。ここで、Ｎは、サブグラフ内のノード数である。ｋｉは、ｉ番目のノードに接続されたアーク数である。Ｅｉは、ｉ番目のノードに１本のアークで接続されたノード間を接続するアーク数である。
【００６０】
次に、グラフパターン係数計算部１５は、パラメータ内のネットワーク密度「０．７」を含む範囲（例えば、０．７±０．０２の範囲）に、計算されたネットワーク密度が含まれ、かつ、パラメータ内のクラスタ係数「０．５」を含む範囲（例えば、０．５±０．０２の範囲）に計算されたクラスタ係数が含まれるというような条件を満たすか否かを判定する（Ｓ１７）。
【００６１】
なお、条件は、パラメータ内のネットワーク密度を含む範囲に、計算されたネットワーク密度が含まれる、「または」、パラメータ内のクラスタ係数を含む範囲に計算されたクラスタ係数が含まれるというような条件でもよい。
【００６２】
また、条件は、（１）計算されたネットワーク密度が、パラメータ内のネットワーク密度以上であるという条件と、（２）計算されたクラスタ係数が、パラメータ内のクラスタ係数以上であるという条件とを組み合わせたものでもよい。
【００６３】
また、計算値がパラメータ内の値未満、または、以下、または、より大きいという条件を使用してもよい。
【００６４】
さて、グラフパターン係数計算部１５は、ステップＳ１７で条件を満たさないと判定すると、制御をステップＳ７に戻す。
【００６５】
ここでは、クエリ発行部１４は、図４のパターンとは異なるパターンをパターンデータベース１３から検索する（Ｓ７）。クエリ発行部１４は、例えば、クラス「技術用語」が定義されたノードを一方の端位置に有し、クラス「人」が定義されたノードを他方の端位置に有し、これら各端位置のノード間に３本のアークが直列に接続されたパターン、つまり、各端位置のノード間に２本のアークが直列に接続された、図４のパターンとは異なるパターンをパターンデータベース１３から検索する（Ｓ７）。
【００６６】
一方、ステップＳ１７で条件を満たしたと判定されたなら、ノード間係数計算部１６は、ノード間係数を計算する（Ｓ１９）。
【００６７】
図８は、ステップＳ１９における処理の一部つまりサブグラフＳＧａについての具体例を示す図である。
【００６８】
図８（ａ）に示すように、サブグラフＳＧａには、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「中村二郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山本幸子」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフＳＧａ１、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフＳＧａ２、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフＳＧａ３、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、が含まれる。
【００６９】
ノード間係数計算部１６は、サブグラフＳＧａを基にこれから作ろうとする無向グラフ（以下、グラフＲＧａという）内の各インスタンス「Ａ技術」、「Ｂ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ａ技術」、「Ｂ技術」）、グラフＲＧａ内の各インスタンス「Ａ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ａ技術」、「Ｃ技術」）、グラフＲＧａ内の各インスタンス「Ａ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ａ技術」、「Ｄ技術」）、グラフＲＧａ内の各インスタンス「Ｂ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ｂ技術」、「Ｃ技術」）、グラフＲＧａ内の各インスタンス「Ｂ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ｂ技術」、「Ｄ技術」）、グラフＲＧａ内の各インスタンス「Ｃ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧａ（「Ｃ技術」、「Ｄ技術」）を計算する。
【００７０】
例えば、ノード間係数ＲＧａ（ｘ、ｙ）は、式（３）（ただし、αはａ）により計算される。
【００７１】
ＲＧα（ｘ，ｙ）
＝｜Ｘ∩Ｙ｜／ｍｉｎ（｜Ｘ｜，｜Ｙ｜） …（３）
ただし、
Ｘは、インスタンス「ｘ」を有するキーノードを含むサブグラフの集合、
Ｙは、インスタンス「ｙ」を有するキーノードを含むサブグラフの集合、
｜Ｘ｜は、Ｘ内のサブグラフの数、
｜Ｙ｜は、Ｙ内のサブグラフの数、
ｍｉｎ（｜Ｘ｜，｜Ｙ｜）は、｜Ｘ｜と｜Ｙ｜の小さい方、
｜Ｘ∩Ｙ｜は、ＸとＹ共通なインスタンスを有するターゲットノードの数である。
【００７２】
図８（ｂ）に示すように、各
ノード間係数ＲＧａ（「Ａ技術」、「Ｂ技術」）は約０．３、ノード間係数ＲＧａ（「Ａ技術」、「Ｃ技術」）は０、ノード間係数ＲＧａ（「Ａ技術」、「Ｄ技術」）は０、
ノード間係数ＲＧａ（「Ｂ技術」、「Ｃ技術」）は１、ノード間係数ＲＧａ（「Ｂ技術」、「Ｄ技術」）は１、ノード間係数ＲＧａ（「Ｃ技術」、「Ｄ技術」）は０となる。
【００７３】
図８（ｃ）に示すようにグラフＲＧａは表される。ノード間係数が０のノード間のアークは図示省略している。
【００７４】
図９は、ステップＳ１９における処理の一部つまりサブグラフＳＧｂについての具体例を示す図である。
【００７５】
図９（ａ）に示すように、サブグラフＳＧｂには、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、が含まれる。
【００７６】
ノード間係数計算部１６は、サブグラフＳＧｂを基にこれから作ろうとする無向グラフ（以下、グラフＲＧｂという）内の各インスタンス「Ａ技術」、「Ｂ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ａ技術」、「Ｂ技術」）、グラフＲＧｂ内の各インスタンス「Ａ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ａ技術」、「Ｃ技術」）、グラフＲＧｂ内の各インスタンス「Ａ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ａ技術」、「Ｄ技術」）、グラフＲＧｂ内の
各インスタンス「Ｂ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ｂ技術」、「Ｃ技術」）、グラフＲＧｂ内の各インスタンス「Ｂ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ｂ技術」、「Ｄ技術」）、グラフＲＧｂ内の各インスタンス「Ｃ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｂ（「Ｃ技術」、「Ｄ技術」）を計算する。
【００７７】
例えば、ノード間係数ＲＧｂ（ｘ、ｙ）は、前述の式（３）（ただし、αはｂ）により計算される。
【００７８】
図９（ｂ）に示すように、各ノード間係数ＲＧｂ（「Ａ技術」、「Ｂ技術」）は０、
ノード間係数ＲＧｂ（「Ａ技術」、「Ｃ技術」）は０、ノード間係数ＲＧｂ（「Ａ技術」、「Ｄ技術」）は０、ノード間係数ＲＧｂ（「Ｂ技術」、「Ｃ技術」）は０、
ノード間係数ＲＧｂ（「Ｂ技術」、「Ｄ技術」）は１、ノード間係数ＲＧｂ（「Ｃ技術」、「Ｄ技術」）は０となる。
【００７９】
図９（ｃ）に示すようにグラフＲＧｂは表される。ノード間係数が０のノード間のアークは図示省略している。
【００８０】
図１０は、ステップＳ１９における処理の一部つまりサブグラフＳＧａについての具体例を示す図である。
【００８１】
図１０（ａ）に示すように、サブグラフＳＧｃには、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「中村二郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山本幸子」を有するターゲットノードを有するサブグラフ、インスタンス「Ａ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｂ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｃ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「山田太郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「田中一郎」を有するターゲットノードを有するサブグラフ、インスタンス「Ｄ技術」を有するキーノードおよびインスタンス「鈴木花子」を有するターゲットノードを有するサブグラフ、が含まれる。
【００８２】
ノード間係数計算部１６は、サブグラフＳＧｃを基にこれから作ろうとする無向グラフ（以下、グラフＲＧｃという）内の各インスタンス「Ａ技術」、「Ｂ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ａ技術」、「Ｂ技術」）、グラフＲＧｃ内の各インスタンス「Ａ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ａ技術」、「Ｃ技術」）、グラフＲＧｃ内の各インスタンス「Ａ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ａ技術」、「Ｄ技術」）、グラフＲＧｃ内の
各インスタンス「Ｂ技術」、「Ｃ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ｂ技術」、「Ｃ技術」）、グラフＲＧｃ内の各インスタンス「Ｂ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ｂ技術」、「Ｄ技術」）、グラフＲＧｃ内の各インスタンス「Ｃ技術」、「Ｄ技術」をそれぞれするノード間のノード間係数ＲＧｃ（「Ｃ技術」、「Ｄ技術」）を計算する。
【００８３】
例えば、ノード間係数ＲＧｂ（ｘ、ｙ）は、前述の式（３）（ただし、αはｃ）により計算される。
【００８４】
図１０（ｂ）に示すように、各ノード間係数ＲＧｃ（「Ａ技術」、「Ｂ技術」）は約０．３、ノード間係数ＲＧｃ（「Ａ技術」、「Ｃ技術」）は０．５、ノード間係数ＲＧｃ（「Ａ技術」、「Ｄ技術」）は約０．３、ノード間係数ＲＧｃ（「Ｂ技術」、「Ｃ技術」）は１、ノード間係数ＲＧｃ（「Ｂ技術」、「Ｄ技術」）は１、ノード間係数ＲＧｃ（「Ｃ技術」、「Ｄ技術」）は１となる。
【００８５】
図１０（ｃ）に示すようにグラフＲＧｃは表される。
【００８６】
図５に戻り、ノード間係数計算部１６は、計算したノード間係数を含むグラフＲＧａ、ＲＧｂ、ＲＧｃをユーザインタフェース１１に渡す（Ｓ２１）。
【００８７】
ユーザインタフェース１１は、グラフＲＧａ、ＲＧｂ、ＲＧｃに基づく出力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ２３）、図８（ｃ）、図９（ｃ）、図１０（ｃ）のように表示させる（Ｓ２５）。
【００８８】
なお、ノード間係数計算部１６は、ノード間係数に基づいて、グラフＲＧａ、ＲＧｂ、ＲＧｃに順位を付与し、ユーザインタフェース１１は、その順位を表示させてもよい。
【００８９】
順位は、例えば、（１）ノード間係数の総和に応じたものとすること、（２）０でないノード間係数に対応するアークの総数に応じたものとすること、などが考えられる。
【００９０】
以上説明したように、本実施の形態に係るグラフ検索装置によれば、グラフＧからサブグラフＳＧａなどを検索し、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノード（クラス「技術用語」が定義されたインスタンス「Ａ技術」などを有するノード）を備える無向グラフ（グラフＲＧａなど）における各ノード間の関係を示すノード間係数（ノード間係数ＲＧａ（「Ａ技術」、「Ｂ技術」）など）を計算するので、課題１を解決つまりノード間の関係を枝狩りをせずに求めることができ、課題２の解決つまり、目視せずにノード間係数によって無向グラフを比較することができる。
【００９１】
具体的には、各無向グラフは、該無効グラフに対応するパターン（Ｐａなど）に対応して生成される。１つの無効グラフには、「Ａ技術」と「Ｂ技術」の関係などが表現されており、よって、そのような関係をパターンの違いに応じて比べることができる。
【００９２】
また、グラフ検索手段（クエリ発行部１４）が、グラフＧからサブグラフＳＧａなどを検索し、ノード間係数計算手段（ノード間係数計算部１６）が、サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノード（インスタンス「Ａ技術」などを有するノード）を備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、前記種類以外のインスタンスを有する部分（クラス「人」が定義されたノードなど）を用いて当該ノード間係数を計算する。
【００９３】
また、グラフ検索手段が、グラフＧから、予め指定された第１の種類のノード（クラス「技術用語」が定義されたノード）と予め指定された第２の種類のノード（クラス「人」が定義されたノード）とを有するサブグラフを、複数の前記第１の種類のノードのインスタンス（Ａ技術〜Ｄ技術）のそれぞれにつき１以上検索し、ノード間係数計算手段が、第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、式（３）により、つまり、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合（Ｘ）と、他方のノードのインスタンスを有する前記サブグラフからなる集合（Ｙ）との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算する。
【００９４】
また、ノード間計算手段は、式（３）により、つまり、各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算する
また、グラフ検索装置は、検索されたサブグラフＳＧａ１、ＳＧａ２、ＳＧａ３をトータルしたサブグラフＳＧａなどの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段（グラフパターン係数計算部１５）を備え、予め指定された値（ネットワーク密度「０．７」やクラスタ係数「０．５」）に合致するグラフパターン係数に対応するサブグラフを使用する（ステップＳ１７：ＹＥＳ）。
【００９５】
また、ノード間係数計算手段は、複数の無向グラフＲＧａ、ＲＧｂ、ＲＧｃに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する。これは、課題２の解決にも貢献する。
【符号の説明】
【００９６】
１…グラフ検索装置
２…ユーザ端末
３…表示装置
１２…グラフデータベース
１１…ユーザインタフェース
１３…パターンデータベース
１４…クエリ発行部
１５…グラフパターン係数計算部
１６…ノード間係数計算部
【特許請求の範囲】
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、
前記グラフデータベースに記憶された前記グラフからサブグラフを検索するグラフ検索手段と、
前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算するノード間係数計算手段と
を備えることを特徴とするグラフ検索装置。
【請求項２】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、
前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索するグラフ検索手段と、
前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算するノード間係数計算手段と
を備えることを特徴とするグラフ検索装置。
【請求項３】
前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算することを特徴とする請求項２記載のグラフ検索装置。
【請求項４】
前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用するようになっていることを特徴とする請求項１ないし３のいずれかに記載のグラフ検索装置。
【請求項５】
前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する
ことを特徴とする請求項１ないし４のいずれかに記載のグラフ検索装置。
【請求項６】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、
前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフからサブグラフを検索し、
前記グラフ検索装置のノード間係数計算手段が、前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算する
ことを特徴とするグラフ検索装置の動作方法。
【請求項７】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、
前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索し、
前記グラフ検索装置のノード間係数計算手段が、前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算する
ことを特徴とするグラフ検索装置の動作方法。
【請求項８】
前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算することを特徴とする請求項７記載のグラフ検索装置の動作方法。
【請求項９】
前記グラフ検索装置は、前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、
前記動作方法は、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用する
ことを特徴とする請求項６ないし８のいずれかに記載のグラフ検索装置の動作方法。
【請求項１０】
前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する
ことを特徴とする請求項６ないし９のいずれかに記載のグラフ検索装置の動作方法。
【請求項１１】
請求項１ないし５のいずれかに記載のグラフ検索装置としてコンピュータを動作させるコンピュータプログラム。
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、
前記グラフデータベースに記憶された前記グラフからサブグラフを検索するグラフ検索手段と、
前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算するノード間係数計算手段と
を備えることを特徴とするグラフ検索装置。
【請求項２】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースと、
前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索するグラフ検索手段と、
前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算するノード間係数計算手段と
を備えることを特徴とするグラフ検索装置。
【請求項３】
前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算することを特徴とする請求項２記載のグラフ検索装置。
【請求項４】
前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用するようになっていることを特徴とする請求項１ないし３のいずれかに記載のグラフ検索装置。
【請求項５】
前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する
ことを特徴とする請求項１ないし４のいずれかに記載のグラフ検索装置。
【請求項６】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、
前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフからサブグラフを検索し、
前記グラフ検索装置のノード間係数計算手段が、前記サブグラフにおける予め指定された種類のインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、当該サブグラフにおける前記種類以外のインスタンスを有する部分を用いて当該ノード間係数を計算する
ことを特徴とするグラフ検索装置の動作方法。
【請求項７】
インスタンスをもつノード間がアークによって接続されたグラフが記憶されるグラフデータベースを有するグラフ検索装置の動作方法であって、
前記グラフ検索装置のグラフ検索手段が、前記グラフデータベースに記憶された前記グラフから、予め指定された第１の種類のノードと予め指定された第２の種類のノードとを有するサブグラフを、複数の前記第１の種類のノードのインスタンスのそれぞれにつき１以上検索し、
前記グラフ検索装置のノード間係数計算手段が、前記第１の種類のノードのインスタンスをそれぞれ有するノードを備える無向グラフにおける各ノード間の関係を示すノード間係数を計算する際に、対応する２つの前記第１の種類のノードの内の一方のノードのインスタンスを有する前記サブグラフからなる集合と、他方のノードのインスタンスを有する前記サブグラフからなる集合との間で、共通な前記第２の種類のノードのインスタンスの数が多いほど高くなるように当該ノード間係数を計算する
ことを特徴とするグラフ検索装置の動作方法。
【請求項８】
前記ノード間計算手段は、前記各集合内のサブグラフの数の少ない方の数が少ないほど高くなるようにノード間係数を計算することを特徴とする請求項７記載のグラフ検索装置の動作方法。
【請求項９】
前記グラフ検索装置は、前記検索されたサブグラフをトータルしたサブグラフの特徴量を示すグラフパターン係数を計算するグラフパターン係数計算手段を備え、
前記動作方法は、予め指定された値に合致するグラフパターン係数に対応する前記検索されたサブグラフを使用する
ことを特徴とする請求項６ないし８のいずれかに記載のグラフ検索装置の動作方法。
【請求項１０】
前記ノード間係数計算手段は、複数の前記無向グラフに順位を付与する際に、対応する無向グラフについて計算したノード間係数に応じて当該順位を付与する
ことを特徴とする請求項６ないし９のいずれかに記載のグラフ検索装置の動作方法。
【請求項１１】
請求項１ないし５のいずれかに記載のグラフ検索装置としてコンピュータを動作させるコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−２７７４３８（Ｐ２０１０−２７７４３８Ａ）
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願番号】特願２００９−１３０９７７（Ｐ２００９−１３０９７７）
【出願日】平成２１年５月２９日（２００９．５．２９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願日】平成２１年５月２９日（２００９．５．２９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]