(57)【特許請求の範囲】
【請求項１】
複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを記憶しているデータベースから前記グラフデータを読み出して取得するグラフデータ取得手段と、
前記頂点に少なくとも一種の要素を含む要素集合を関連づけてなる頂点データを記憶しているデータベースから前記頂点データを読み出して取得する頂点データ取得手段と、
前記グラフデータ取得手段により取得された前記グラフデータと、前記頂点データ取得手段により取得された前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフの各頂点に関連付けられた要素集合の積集合がＮ（Ｎ≧１）種以上の要素を含む部分グラフを検出する部分グラフ検出手段と、
を含み、
前記部分グラフ検出手段は、
前記グラフデータに基づいて、前記グラフの部分グラフを順次探索する探索手段と、
前記頂点データに基づいて、前記探索手段により探索された部分グラフの各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを判定する判定手段と、
を含むことを特徴とする部分グラフ検出装置。
【請求項２】
前記探索手段は、
各ノードが前記グラフの頂点の少なくとも一つを含む頂点集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合、を当該親ノードの子ノードとして有する探索木、の各ノードが示す頂点集合を、深さ優先探索アルゴリズムに従った探索順序で前記グラフデータに基づき探索し、
前記判定手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された該頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを、前記頂点データに基づいて判定し、
前記探索手段は、
前記探索木のうちの第１のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第１のノードが示す頂点集合のうちの末端頂点と同じ頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第１のノードよりも探索順序が前のノードである第２のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第１のノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項１に記載の部分グラフ検出装置。
【請求項３】
前記部分グラフ検出手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された頂点集合の各頂点に関連づけられた要素集合の積集合を、基準集合として、探索された当該頂点集合のうちの末端頂点に関連づけて基準集合記憶手段に記憶させる手段をさらに含み、
前記探索手段は、
前記第１のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第１のノードが示す頂点集合のうちの末端頂点に関連づけて前記基準集合記憶手段に記憶される基準集合に含まれる場合、前記第１のノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項２に記載の部分グラフ検出装置。
【請求項４】
前記探索手段は、
各ノードが前記グラフの頂点の少なくとも一つを含む頂点集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木、の各ノードが示す頂点集合を、深さ優先又は幅優先探索アルゴリズムに従った探索順序で前記グラフデータに基づき探索し、
前記判定手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された該頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを、前記頂点データに基づいて判定し、
前記探索手段は、
前記探索木のうちの第１のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第１のノードが示す頂点集合のうちの末端頂点と同じ頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第１のノードが示す頂点集合を含む頂点集合を示す第２のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第１のノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項１に記載の部分グラフ検出装置。
【請求項５】
前記探索手段は、
各ノードが前記グラフの頂点の少なくとも一つを含む頂点集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木、の各ノードが示す頂点集合を、深さ優先探索アルゴリズムに従った探索順序で前記グラフデータに基づき探索し、
前記判定手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された該頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを、前記頂点データに基づいて判定し、
前記探索手段は、
前記探索木のうちの第３のノードが示す頂点集合が一つの頂点のみを含み、かつ、当該頂点に関連づけられた要素集合が、当該頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第３のノードよりも探索順序が前のノードである第４のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第３のノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項１に記載の部分グラフ検出装置。
【請求項６】
前記部分グラフ検出手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された頂点集合の各頂点に関連づけられた要素集合の積集合を、基準集合として、探索された当該頂点集合のうちの末端頂点に関連づけて基準集合記憶手段に記憶させる手段をさらに含み、
前記探索手段は、
前記第３のノードが示す頂点集合が一つの頂点のみを含み、かつ、当該頂点に関連づけられた要素集合が、当該頂点に関連づけて前記基準集合記憶手段に記憶される基準集合に含まれる場合に、前記第３のノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項５に記載の部分グラフ検出装置。
【請求項７】
前記探索手段は、
各ノードが前記グラフの頂点の少なくとも一つを含む頂点集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木、の各ノードが示す頂点集合を、深さ優先又は幅優先探索アルゴリズムに従った探索順序で前記グラフデータに基づき探索し、
前記判定手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された該頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを、前記頂点データに基づいて判定し、
前記探索手段は、
前記探索木のうちの第３のノードが示す頂点集合が一つの頂点のみを含み、当該頂点に関連づけられた要素集合が、当該頂点を末端頂点とする頂点集合を示す第４のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第３のノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項１に記載の部分グラフ検出装置。
【請求項８】
前記探索手段は、
各ノードが前記グラフの頂点の少なくとも一つを含む頂点集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合の末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木、の各ノードが示す頂点集合を、深さ優先探索又は幅優先探索アルゴリズムに従った探索順序で前記グラフデータに基づき探索し、
前記判定手段は、
前記探索手段により複数の頂点を含む頂点集合が探索された場合に、前記探索手段により探索された該頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを、前記頂点データに基づいて判定し、
前記探索手段は、
前記探索手段が探索した頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含んでいない場合、探索した当該頂点集合を示すノードの子孫のノードが示す頂点集合を探索しないこと、
を特徴とする請求項１に記載の部分グラフ検出装置。
【請求項９】
グラフデータ取得手段が、複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを記憶しているデータベースから前記グラフデータを読み出して取得するグラフデータ取得ステップと、
頂点データ取得手段が、前記頂点に少なくとも一種の要素を含む要素集合を関連づけてなる頂点データを記憶しているデータベースから前記頂点データを読み出して取得する頂点データ取得ステップと、
部分グラフ検出手段が、前記グラフデータ取得手段により取得された前記グラフデータと、前記頂点データ取得手段により取得された前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフの各頂点に関連付けられた要素集合の積集合がＮ（Ｎ≧１）種以上の要素を含む部分グラフを検出する部分グラフ検出ステップと、
を含み、
前記部分グラフ検出ステップは、
前記部分グラフ検出手段が、前記グラフデータに基づいて、前記グラフの部分グラフを順次探索する探索ステップと、
前記部分グラフ検出手段が、前記頂点データに基づいて、前記探索ステップで探索された部分グラフの各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かを判定する判定ステップと、
を含むことを特徴とする部分グラフ検出方法。
【請求項１０】
複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを記憶しているデータベースから前記グラフデータを読み出して取得するグラフデータ取得手段、
前記頂点に少なくとも一種の要素を含む要素集合を関連づけてなる頂点データを記憶しているデータベースから前記頂点データを読み出して取得する頂点データ取得手段、
前記グラフデータ取得手段により取得された前記グラフデータに基づいて、前記グラフの部分グラフを順次探索する探索手段、
前記頂点データ取得手段により取得された前記頂点データに基づいて、前記探索手段により探索された部分グラフの各頂点に関連づけられた要素集合の積集合がＮ（Ｎ≧１）種以上の要素を含むか否かを判定する判定手段、
としてコンピュータを機能させるプログラム。
【請求項１１】
複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを記憶しているデータベースから前記グラフデータを読み出して取得するグラフデータ取得手段、
前記頂点に少なくとも一種の要素を含む要素集合を関連づけてなる頂点データを記憶しているデータベースから前記頂点データを読み出して取得する頂点データ取得手段、
前記グラフデータ取得手段により取得された前記グラフデータに基づいて、前記グラフの部分グラフを順次探索する探索手段、
前記頂点データ取得手段により取得された前記頂点データに基づいて、前記探索手段により探索された部分グラフの各頂点に関連づけられた要素集合の積集合がＮ（Ｎ≧１）種以上の要素を含むか否かを判定する判定手段、
としてコンピュータを機能させるプログラムを記録したコンピュータ読み取り可能な情報記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部分グラフ検出装置、部分グラフ検出方法、プログラム、データのデータ構造、及び情報記憶媒体に関する。
【背景技術】
【０００２】
例えば、複数のユーザの各々に購入商品のリストを対応づけてなるデータに基づいて、ある商品又は商品群を購入したユーザのリストやその商品又は商品群を購入していないユーザのリストを取得することが行われている。また、例えば、複数の文献の各々にキーワードのリストを対応づけてなるデータに基づいて、あるキーワード又はキーワード群が設定された文献のリストを取得することが行われている。【０００３】
例えば、下記特許文献１には、複数のユーザの購入商品のリストを基に、ある商品又は商品群（例えば、購入された頻度、回数の大きい商品又は商品群）を購入していないユーザを特定することが開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−２８７１３９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来、例えば、同じ商品又は商品群を購入したユーザのリストをユーザ間の関係（例えば交友関係）を考慮して取得することはできなかった。また例えば、同じキーワード又はキーワード群が設定された文献のリストを文献間の関係（引用関係）を考慮して取得することはできなかった。【０００６】
ところで、例えば、ある医薬又は医薬品群の投与により共通して発現が変化する遺伝子のリストを遺伝子間の関係を考慮して取得することができれば、創薬研究の上で有用な情報を得ることができる。例えば、発現の影響を互いに及ぼし合うような遺伝子間の関係（遺伝子間の相互作用関係）や、一方の遺伝子と他方の遺伝子とが同時に発現するような遺伝子間の関係を考慮して上記のリストを取得することができれば、例えば創薬ターゲットを絞り込む際の有用な情報を得ることができる。しかしながら、ある医薬又は医薬群の投与により共通して発現が変化する遺伝子のリストを遺伝子間の関係を考慮して取得することはできなかった。【０００７】
また、例えば、ある医薬又は医薬品群の投与により共通して発現が変化するタンパク質のリストをタンパク質間の関係を考慮して取得することができれば、創薬研究の上で有用な情報を得ることができる。例えば、互いに結合して複合体を形成するようなタンパク質間の関係（タンパク質間の相互作用関係）を考慮して上記のリストを取得することができれば、例えば創薬ターゲットを絞り込む際の有用な情報を得ることができる。しかしながら、ある医薬又は医薬群の投与により共通して発現が変化するタンパク質のリストをタンパク質間の関係を考慮して取得することはできなかった。【０００８】
本発明は、上記課題に鑑みてなされたものであって、例えば、ある医薬又は医薬群の投与により共通して発現が変化する遺伝子のリストを遺伝子間の関係（例えば遺伝子間の相互作用関係）を考慮して取得すること、ある医薬又は医薬群の投与により共通して発現が変化するタンパク質のリストをタンパク質間の関係（例えば、タンパク質間の相互作用関係）を考慮して取得すること、同じ商品又は商品群を購入したユーザのリストをユーザ間の関係（例えば交友関係）を考慮して取得することや、同じキーワード又はキーワード群が設定された文献のリストを文献間の関係（引用関係）を考慮して取得すること等が可能になる部分グラフ検出装置、部分グラフ検出方法、プログラム、データのデータ構造、及び情報記憶媒体の提供をその目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明に係る部分グラフ検出装置は、複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得手段と、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得手段と、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフの各頂点に関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出手段と、を含むことを特徴とする。【００１０】
また、本発明に係る部分グラフ検出方法は、複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得ステップと、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得ステップと、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフに含まれる各頂点に関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出ステップと、を含むことを特徴とする。【００１１】
また、本発明に係るプログラムは、複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得手段、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得手段、及び、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフに含まれる各頂点に関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出手段、としてコンピュータを機能させることを特徴とする。【００１２】
また、本発明に係る情報記憶媒体は、上記プログラムを記録したコンピュータ読み取り可能な情報記憶媒体である。【００１３】
また、本発明に係るデータ構造は、複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータと、前記頂点に情報を関連づけてなる頂点データと、を含むことを特徴とする。また、本発明に係る情報記憶媒体は、複数の頂点と１又は複数のエッジとを含むグラフを示すグラフデータと、前記頂点に情報を関連づけてなる頂点データと、を含むデータを記録したコンピュータ読み取り可能な情報記憶媒体である。【００１４】
本発明は、複数の頂点と１又は複数のエッジとを含むグラフの部分グラフを検出する技術に関するものである。本発明では、前記グラフを示すグラフデータが取得される。例えば、各頂点が遺伝子一つ一つに対応し各エッジ（辺）が遺伝子間の関係を表すグラフを表すグラフデータが取得される。ここで、遺伝子間の関係とは、例えば、発現の影響を互いに及ぼし合うような遺伝子間の関係（遺伝子間の相互作用関係）や、一方の遺伝子と他方の遺伝子とが同時に発現するような遺伝子間の関係である。また、例えば、各頂点がタンパク質一つ一つに対応し、各エッジ（辺）がタンパク質間の関係を表すグラフデータが取得される。ここで、タンパク質間の関係とは、例えば、互いに結合して複合体を形成するようなタンパク質間の関係（タンパク質間の相互作用関係）である。また、例えば、各頂点がユーザ一人一人に対応し各エッジ（辺）がユーザ間の交友関係を表すグラフを示すグラフデータが取得される。なお、グラフデータは、例えば、隣接リスト、隣接行列として表される。また、本発明では、前記頂点に情報を関連づけてなる頂点データが取得される。そして、グラフデータと、頂点データと、に基づいて、前記部分グラフの各頂点に関連づけられた情報が所定関係を有する部分グラフが検出される。本発明によれば、グラフデータと、頂点データと、に基づいて部分グラフが検出される。その結果、例えば、ある医薬又は医薬群の投与により共通して発現が変化する遺伝子のリストを遺伝子間の関係（例えば、遺伝子間の相互作用関係）を考慮して取得することが可能になる。また、例えば、ある医薬又は医薬群の投与により共通して発現が変化するタンパク質のリストをタンパク質間の関係（例えば、タンパク質間の相互作用関係）を考慮して取得することが可能になる。また、例えば、同じ商品又は商品群を購入したユーザのリストをユーザ間の関係（例えば交友関係）を考慮して取得することが可能になる。【００１５】
また、本発明の一態様では、前記情報は、少なくとも一種の要素を含む要素集合を示し、前記部分グラフ検出手段は、前記グラフの部分グラフであって、該部分グラフの各頂点に関連づけられた要素集合の積集合がＮ（Ｎ≧１）種以上の要素を含む部分グラフの検出を実行するようにしてもよい。例えば、各頂点が遺伝子一つ一つに対応し、かつ、要素集合が、遺伝子の発現を変化させる医薬又は医薬群に対応する場合、ある医薬又は医薬群の投与により共通して発現が変化する遺伝子のリストを遺伝子間の関係（例えば、遺伝子間の相互作用関係）を考慮して取得することが可能になる。また、例えば、各頂点がタンパク質一つ一つに対応し、かつ、要素集合が、タンパク質の発現を変化させる医薬又は医薬群に対応する場合、ある医薬又は医薬群の投与により共通して発現が変化するタンパク質のリストをタンパク質間の関係（例えば、タンパク質間の相互作用関係）を考慮して取得することが可能になる。また、例えば、各頂点がユーザ一人一人に対応し、かつ、要素集合が、ユーザが購入した商品又は商品群に対応する場合、同じ商品又は商品群を購入したユーザのリストをユーザ間の関係（例えば交友関係）を考慮して取得することが可能になる。【００１６】
また、本発明の一態様では、前記部分グラフ検出手段は、「各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木」の各ノードを、深さ優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第１のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、「前記第１のノードが示す頂点集合のうちの末端頂点と同じ頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第１のノードよりも探索順序が前のノードである第２のノード」が示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第１のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。【００１７】
また、本発明の一態様では、前記部分グラフ検出手段は、前記判定が実行された場合に、前記判定対象の頂点集合の各頂点に関連づけられた要素集合の積集合を、基準集合として、当該判定対象の頂点集合のうちの末端頂点に関連づけて基準集合記憶手段に記憶させる手段を含み、前記判定手段は、前記第１のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第１のノードが示す頂点集合のうちの末端頂点に関連づけて前記基準集合記憶手段に記憶される基準集合に含まれる場合、前記第１のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。【００１８】
また、本発明の一態様では、前記部分グラフ検出手段は、「各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木」の各ノードを、深さ優先又は幅優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第１のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、「前記第１のノードが示す頂点集合のうちの末端頂点と同じ頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第１のノードが示す頂点集合を含む頂点集合を示す第２のノード」が示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第１のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。【００１９】
また、本発明の一態様では、前記部分グラフ検出手段は、「各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木」の各ノードを、深さ優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第３のノードが示す頂点集合が一つの頂点のみを含み、かつ、当該頂点に関連づけられた要素集合が、「当該頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第３のノードよりも探索順序が前のノードである第４のノード」が示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第３のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。【００２０】
また、本発明の一態様では、前記部分グラフ検出手段は、前記判定が実行された場合に、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合を、基準集合として、前記判定対象のノードが示す頂点集合のうちの末端頂点に関連づけて基準集合記憶手段に記憶させる手段を含み、前記判定手段は、前記第３のノードが示す頂点集合が一つの頂点のみを含み、かつ、当該頂点に関連づけられた要素集合が、当該頂点に関連づけて前記基準集合記憶手段に記憶される基準集合に含まれる場合に、前記第３のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。【００２１】
また、本発明の一態様では、前記部分グラフ検出手段は、「各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木」の各ノードを、深さ優先又は幅優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第３のノードが示す頂点集合が一つの頂点のみを含み、当該頂点に関連づけられた要素集合が、当該頂点を末端頂点とする頂点集合を示す第４のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第３のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。【００２２】
また、本発明の一態様では、前記部分グラフ検出手段は、「各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合の末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木」の各ノードを、深さ優先探索又は幅優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記ノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がＮ種以上の要素を含んでいない場合、当該ノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないようにしてもよい。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態に係る部分グラフ検出装置を含む部分グラフ検出システムの構成を示す図である。
【図２】グラフデータが示すグラフの一例を示す図である。
【図３】頂点データの内容の一例を示す図である。
【図４】部分グラフＣＳＧの一例を示す図である。
【図５】頂点データの内容の一例を示す図である。
【図６】本発明の実施形態に係る部分グラフ検出装置で実現される機能群を示す図である。
【図７】ツリーの一例を示す図である。
【図８】基準集合テーブルの内容の一例を示す図である。
【図９】本発明の実施形態に係る部分グラフ検出装置で実行される処理の一例を示すフローチャート図である。
【図１０】本発明の実施形態に係る部分グラフ検出装置で実行される処理の一例を示すフローチャート図である。
【図１１】本発明の実施形態に係る部分グラフ検出装置で実行される処理の一例を示すフローチャート図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施形態について図面を参照しながら説明する。
【００２５】
［１．部分グラフ検出システムの構成］
図１は、本発明の実施形態に係る部分グラフ検出装置２を含む部分グラフ検出システム６の構成を示す図である。同図に示すように、部分グラフ検出システム６は、部分グラフ検出装置２と、データベース４と、を含む。部分グラフ検出装置２と、データベース４と、は、ネットワークを介して相互に通信することが可能になっている。
【００２６】
［２．部分グラフ検出装置のハードウェア構成］
部分グラフ検出装置２は、例えば、パーソナルコンピュータである。図１に示すように、部分グラフ検出装置２は、制御部８と、記憶部１０と、通信部１２と、表示部１４と、操作部１６と、を含む。各部は、バス１８を介して通信可能に接続される。
【００２７】
制御部８は、記憶部１０に記憶されたプログラムに従って、各種情報処理を実行する。制御部８は、パーソナルコンピュータとしての処理を行うが、以下では本発明に関連する処理について主に説明する。制御部８によって実行される処理の具体的内容については後に述べる。
【００２８】
記憶部１０はメインメモリと不揮発性メモリとを含む。不揮発性メモリには制御部８によって実行されるプログラムが保持される。このプログラムは、例えばプログラム配信装置からネットワークを介してダウンロードされ、不揮発性メモリに格納される。また、例えば光ディスク又はメモリカードなどのコンピュータ読み取り可能な情報記憶媒体から複写されて不揮発性メモリに格納される。メインメモリには、不揮発性メモリから読み出されるプログラムや制御部８の処理において必要となる種々のデータが必要に応じて書き込まれる。
【００２９】
通信部１２はネットワークインターフェイスカードを含み、例えば、ネットワークを介して到来したデータを制御部８に出力する。表示部１４は例えばモニタを含み、制御部８から入力されるデータを表示する。操作部１６はキーボードやマウスを含み、ユーザの操作内容を示すデータを制御部８に出力する。
【００３０】
［３．データベース］
データベース４は、例えばデータベースサーバのハードディスク（情報記憶媒体）に格納される。なお、データベースは部分グラフ検出装置２の不揮発性メモリ（情報記憶媒体）に格納されるようにしてもよい。
【００３１】
データベース４は、複数の頂点と、一又は複数の辺（エッジ）と、を含むグラフを示すグラフデータを記憶する。なお、グラフの「頂点」は「ノード」と呼ばれる場合もあるが、ここでは、後述のツリー（図７参照）のノードと区別するために「頂点」の語句を用いることとする。
【００３２】
グラフデータは、例えば、隣接リストや隣接行列を示すデータである。図２はグラフデータの一例を示す図である。図２に示すグラフＧは、６つの頂点ｖと、頂点ｖと他の頂点ｖとを連結する辺ｅと、を含んでいる。つまり、図２に示すグラフＧは、６つの頂点｛ｖ１，ｖ２，ｖ３，ｖ４，ｖ５，ｖ６｝と、８つの辺｛ｅ１２，ｅ１３，ｅ１４，ｅ１６，ｅ２３，ｅ３４，ｅ４５，ｅ４６｝と、を含む。
【００３３】
本実施形態の場合、図２に示すグラフＧにおいて各頂点ｖは一つ一つの遺伝子に対応しており、グラフＧは遺伝子間の関係を示している。ここで、遺伝子間の関係とは、例えば、発現の影響を互いに及ぼし合うような遺伝子間の関係（遺伝子間の相互作用関係）や、一方の遺伝子と他方の遺伝子とが同時に発現するような遺伝子間の関係である。頂点ｖｉと頂点ｖｊとを連結する辺ｅｉｊは、頂点ｖｉに対応する遺伝子と頂点ｖｊに対応する遺伝子とが関係を有することを示す。例えば、図２に示すグラフＧでは、辺ｅ１２が頂点ｖ１と頂点ｖ２とを連結しており、頂点ｖ１に対応する遺伝子と頂点ｖ２に対応する遺伝子とが関係を有することが表されている。なお、図２に示すグラフＧでは、頂点ｖ１は辺ｅ１４によって頂点ｖ４と連結されており、さらに、頂点ｖ４は辺ｅ４５によって頂点ｖ５と連結されている。すなわち、頂点ｖ１に対応する遺伝子と頂点ｖ５に対応する遺伝子とが、頂点ｖ４に対応する遺伝子を介して間接的に関係を有することが表されている。
【００３４】
また、データベース４は、グラフＧの各頂点ｖに情報を関連づけてなる頂点データを記憶する。図３は頂点データの一例を示す図である。図３に示す頂点データは、頂点ｖと、少なくとも一種のアイテムｉ（要素）を含むアイテム集合Ｉ（ｖ）と、を関連づけてなるテーブルになっている。本実施形態の場合、アイテム集合Ｉ（ｖｉ）に含まれる各アイテムｉｉは、頂点ｖｉに対応する遺伝子の発現を変化させる医薬に対応する。図３に示す例では、頂点ｖ１に対応づけられたアイテム集合Ｉ（ｖ１）は、アイテムｉ１（医薬Ａ）と、アイテムｉ２（医薬Ｂ）と、アイテムｉ３（医薬Ｃ）と、アイテムｉ４（医薬Ｄ）と、を含んでおり、医薬Ａ、医薬Ｂ、医薬Ｃ、又は医薬Ｄの投与により頂点ｖ１に対応する遺伝子の発現が変化することを表している。なお例えば、アイテムｉを、遺伝子の発現を変化させる、医薬以外の要因に対応させるようにしてもよい。
【００３５】
ところで、図４に示すように、グラフＧのうちの一部である部分グラフＣＳＧでは、該部分グラフＣＳＧに含まれる頂点ｖ１，ｖ３，ｖ４の各々に関連づけられたアイテム集合Ｉ（ｖ１），Ｉ（ｖ３），Ｉ（ｖ４）が、それぞれ、共通のアイテム集合｛ｉ１，ｉ２｝を含んでいる。これは、直接的又は間接的に関係を有する３つの遺伝子（頂点ｖ１，ｖ３，ｖ４に対応する３つの遺伝子）の発現が共通の医薬｛医薬Ａ、医薬Ｂ｝の投与により変化することを表している。この場合、これら３つの遺伝子は、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により発現が変化するのであるから、これら３つの遺伝子の発現は、同一又は類似の医薬の投与により変化する可能性が高いと推測される。これら３つの遺伝子のような、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化する遺伝子群を特定することができれば、例えば、創薬研究の上で有用である。例えば、創薬のターゲットとすべきを遺伝子を絞り込む際に有用である。
【００３６】
この点、部分グラフ検出装置２では、グラフＧの部分グラフであって、該部分グラフの各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）が共通のアイテム集合を含むような部分グラフＣＳＧが検出されるようになっている。その結果、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化する遺伝子群が検出されるようになっている。
【００３７】
なお、グラフＧの各頂点ｖが一つ一つのタンパク質に対応し、かつ、頂点データにおいて各アイテムｉｉが、頂点ｖｉに対応するタンパク質の発現を変化させる医薬に対応するようにしてもよい。
【００３８】
この場合、図２に示すグラフＧは、タンパク質間の関係を示し、頂点ｖｉと頂点ｖｊとを連結する辺ｅｉｊは、頂点ｖｉに対応するタンパク質と頂点ｖｊに対応するタンパク質とが関係を有することを示すことになる。ここで、タンパク質間の関係とは、例えば、互いに結合して複合体を形成するようなタンパク質間の関係（タンパク質間の相互作用関係）である。例えば、図２に示すグラフＧの場合、辺ｅ１２が頂点ｖ１と頂点ｖ２とを連結しているため、頂点ｖ１に対応するタンパク質と頂点ｖ２に対応するタンパク質とが関係を有することが表されていることになる。また、図２に示すグラフＧの場合、頂点ｖ１は辺ｅ１４によって頂点ｖ４と連結されており、さらに、頂点ｖ４は辺ｅ４５によって頂点ｖ５と連結されているので、頂点ｖ１に対応するタンパク質と頂点ｖ５に対応するタンパク質とが、頂点ｖ４に対応するタンパク質を介して間接的に関係を有することが表されていることになる。
【００３９】
また、この場合、データベース４には、図３に示す頂点データと同様の頂点データが記憶される。図３に示す頂点データでは、頂点ｖ１に対応づけられたアイテム集合Ｉ（ｖ１）に、アイテムｉ１（医薬Ａ）と、アイテムｉ２（医薬Ｂ）と、アイテムｉ３（医薬Ｃ）と、アイテムｉ４（医薬Ｄ）と、が含まれているため、医薬Ａ、医薬Ｂ、医薬Ｃ、又は医薬Ｄの投与により頂点ｖ１に対応するタンパク質の発現が変化することが表されていることになる。なお例えば、アイテムｉを、タンパク質の発現を変化させる、医薬以外の要因（例えば、ヒートショック、窒素枯渇環境など）に対応させるようにしてもよい。
【００４０】
先述のように（図４参照）、グラフＧのうちの一部である部分グラフＣＳＧでは、該部分グラフＣＳＧに含まれる頂点ｖ１，ｖ３，ｖ４の各々に関連づけられたアイテム集合Ｉ（ｖ１），Ｉ（ｖ３），Ｉ（ｖ４）が、それぞれ、共通のアイテム集合｛ｉ１，ｉ２｝を含んでいる。これは、直接的又は間接的に関係を有する３つのタンパク質（頂点ｖ１，ｖ３，ｖ４に対応する３つのタンパク質）の発現が、共通の医薬｛医薬Ａ、医薬Ｂ｝の投与により変化することを表している。この場合、これら３つのタンパク質は、直接的又は間接的に関係を有し、且つ、共通の医薬の投与により発現が変化するので、これら３つのタンパク質の発現は、同一又は類似の医薬の投与により変化する可能性が高いと推測される。これら３つのタンパク質のような、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化するタンパク質群を特定することができれば、創薬研究の上で有用である。例えば、創薬のターゲットとすべきタンパク質を絞り込む際に有用である。
【００４１】
この点、先述のように、部分グラフ検出装置２では、グラフＧの部分グラフであって、該部分グラフの各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）が共通のアイテム集合を含むような部分グラフＣＳＧが検出されるようになっている。その結果、例えば、グラフＧの各頂点ｖが一つのタンパク質に対応し、かつ、各アイテムｉｉが、頂点ｖｉに対応するタンパク質の発現を変化させる医薬に対応するような場合には、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化するタンパク質群が検出されるようにもなる。
【００４２】
また、グラフＧの各頂点ｖが一人一人のユーザに対応し、頂点データにおいて各アイテムｉｉが、頂点ｖｉに対応するユーザが購入した商品に対応するようにしてもよい。
【００４３】
この場合、図２に示すグラフＧはユーザ間の交友関係を示し、頂点ｖｉと頂点ｖｊとを連結する辺ｅｉｊは、頂点ｖｉに対応するユーザと頂点ｖｊに対応するユーザとが友人関係にあることを示すことになる。例えば、図２に示すグラフＧの場合、辺ｅ１２が頂点ｖ１と頂点ｖ２とを連結しているため、頂点ｖ１に対応するユーザと頂点ｖ２に対応するユーザとが友人関係にあることが表されていることになる。また、図２に示すグラフＧの場合、頂点ｖ１は辺ｅ１４によって頂点ｖ４と連結され、さらに、頂点ｖ４は辺ｅ４５によって頂点ｖ５と連結されているため、頂点ｖ１に対応するユーザと頂点ｖ５に対応するユーザとが、頂点ｖ４に対応するユーザを介して間接的に交友関係を有することが表されていることになる。
【００４４】
図５に、各アイテムｉｉを、頂点ｖｉに対応するユーザが購入した商品に対応させた場合の頂点データの一例を示す。図５に示す例では、頂点ｖ１に対応づけられたアイテム集合Ｉ（ｖ１）に、アイテムｉ１（りんご）と、アイテムｉ２（みかん）と、アイテムｉ３（ぶどう）と、アイテムｉ４（ナシ）と、が含まれているため、頂点ｖ１に対応するユーザがりんご、みかん、ぶどう及びナシを購入したことが表されていることになる。なお、ここでは、アイテムｉ１〜ｉ５が同種の商品（果物）になっているが、アイテムｉ１〜ｉ５は異なる種類の商品であってもよい。
【００４５】
先述のように（図４参照）、グラフＧのうちの一部である部分グラフＣＳＧでは、該部分グラフＣＳＧに含まれる頂点ｖ１，ｖ３，ｖ４の各々に関連づけられたアイテム集合Ｉ（ｖ１），Ｉ（ｖ３），Ｉ（ｖ４）が、それぞれ、共通のアイテム集合｛ｉ１，ｉ２｝を含んでいる。これは、直接的又は間接的に交友関係を有する３名のユーザ（頂点ｖ１，ｖ３，ｖ４に対応する３名のユーザ）が共通の商品｛りんご、みかん｝を購入していることを表している。この場合、共通の商品｛りんご、みかん｝又はこれらの商品に関連する他の商品に関する情報が、頂点ｖ１，ｖ３，ｖ４に対応する３名のユーザの間で口コミによって伝わる可能性が高いと推測される。これら３名のユーザのような、直接的又は間接的に交友関係を有し、かつ、共通の商品を購入したユーザ群を特定することができれば、例えば、商品の広告宣伝のターゲットとすべきユーザを好適に絞り込むことができるようになり、その結果として、商品の広告宣伝が効率的に行えるようになる。
【００４６】
この点、部分グラフ検出装置２では、グラフＧの部分グラフであって、該部分グラフの各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）が共通のアイテム集合を含むような部分グラフＣＳＧが検出されるようになっている。その結果、直接的又は間接的に交友関係にあり、かつ、共通の商品を購入したユーザ群が検出されるようになっている。
【００４７】
以下、各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）が共通のアイテム集合を含むような部分グラフＣＳＧを検出するための技術について説明する。なお、以下では、各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）が共通のアイテム集合を含むような部分グラフＣＳＧのことを、共通部分グラフＣＳＧと記載する。
【００４８】
［４．機能ブロック］
図６は、部分グラフ検出装置２で実現される機能のうち、本発明に関連するものを主として示す機能ブロック図である。同図に示すように、部分グラフ検出装置２は、グラフデータ取得部２０と、頂点データ取得部２２と、部分グラフ検出部２４と、を機能的に含む。これらの機能は、記憶部１０から読み出された上記プログラムに従って制御部８が動作することによって実現される。
【００４９】
［４−１．グラフデータ取得部］
グラフデータ取得部２０は、例えば制御部８と通信部１２とを主として実現される。グラフデータ取得部２０は、複数の頂点を含むグラフを示すグラフデータを取得する。本実施形態の場合、グラフデータ取得部２０は、例えば図２に示すようなグラフＧのグラフデータをデータベース４から読み出して取得する。
【００５０】
［４−２．頂点データ取得部］
頂点データ取得部２２は、例えば制御部８と通信部１２とを主として実現される。頂点データ取得部２２は、グラフに含まれる複数の頂点の各々に情報を対応づけてなる頂点データを取得する。ここで、「情報」とは、グラフＧの頂点間の接続関係を示す情報以外の情報である。例えば、頂点が遺伝子に対応する場合、上記の「情報」とは、遺伝子に関する情報である。ここで、「遺伝子に関する情報」とは、例えば、遺伝子の発現を変化させるような医薬を示す情報である。また例えば、頂点がタンパク質に対応する場合、上記の「情報」とは、タンパク質に関する情報である。ここで、「タンパク質に関する情報」とは、例えば、タンパク質の発現を変化させるような医薬を示す情報である。さらに例えば、頂点がユーザに対応する場合、上記の「情報」とは、ユーザに関する情報である。ここで、「ユーザに関する情報」とは、例えば、ユーザの属性を示す情報や、ユーザが購入した商品を示す情報である。本実施形態の場合、頂点データ取得部２２は、例えば図３又は図５に示すような頂点データをデータベース４から読み出して取得する。
【００５１】
［４−３．部分グラフ検出部］
部分グラフ検出部２４は、例えば制御部８を主として実現される。部分グラフ検出部２４は、グラフデータと、頂点データと、に基づいて、グラフの部分グラフであって、該部分グラフの各頂点に関連づけられた情報が所定関係を有するような部分グラフを検出する。本実施形態の場合、部分グラフ検出部２４は、グラフＧの部分グラフであって、該部分グラフの各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）の積集合がＮ（Ｎは正の整数）種以上のアイテム（商品）を含む共通部分グラフＣＳＧを検出する。具体的には、例えば、「共通のＮ種以上の医薬の投与により共通して発現が変化する複数の遺伝子」に対応する複数の頂点ｖを含む共通部分グラフＣＳＧが検出される。また例えば、「共通のＮ種以上の医薬の投与により共通して発現が変化する複数のタンパク質」に対応する複数の頂点ｖを含む共通部分グラフＣＳＧが検出される。また例えば、共通のＮ種以上の商品を購入した複数のユーザに対応する複数の頂点ｖを含む共通部分グラフＣＳＧが検出される。
【００５２】
なお本実施形態では、特に、閉じている共通部分グラフＣＳＧ（以下、閉共通部分グラフＣＣＳＧと記載する）が検出される。閉共通部分グラフＣＣＳＧとは、共通部分グラフＣＳＧであって、該共通部分グラフＣＳＧに含まれる頂点ｖに隣接しているどの頂点ｖを該共通部分グラフＣＳＧに追加しても、共通アイテム集合が変わってしまうような共通部分グラフＣＳＧのことである。
【００５３】
以下、閉共通部分グラフＣＣＳＧの具体例について説明する。ここでは、共通アイテム集合に２種以上のアイテムが含まれる部分グラフが共通部分グラフＣＳＧであることとして説明する。例えば、部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合は、｛ｉ１，ｉ２｝であるから（図３参照）、部分グラフ｛ｖ１、ｖ４｝は共通部分グラフＣＳＧである。しかし、部分グラフ｛ｖ１，ｖ４｝に頂点ｖ４に隣接する頂点ｖ３（図１、図４参照）を追加しても、共通アイテム集合は｛ｉ１，ｉ２｝のままで変化しないから、部分グラフ｛ｖ１，ｖ４｝は閉共通部分グラフＣＣＳＧではない。一方、部分グラフ｛ｖ１，ｖ４｝に頂点ｖ３が追加された部分グラフ｛ｖ１，ｖ３，ｖ４｝の共通アイテム集合は｛ｉ１、ｉ２｝であるから（図３参照）、部分グラフ｛ｖ１，ｖ３，ｖ４｝は共通部分グラフＣＳＧである。また、部分グラフ｛ｖ１，ｖ３，ｖ４｝に、頂点ｖ１，ｖ３，ｖ４のいずれかに隣接する頂点ｖ２，ｖ５，ｖ６のいずれを追加しても、共通アイテム集合は｛ｉ１，ｉ２｝から｛ｉ１｝に変化するので、部分グラフ｛ｖ１，ｖ３，ｖ４｝は、閉共通部分グラフＣＣＳＧである。
【００５４】
共通アイテム集合が同じ場合、閉共通部分グラフＣＣＳＧの頂点数は、閉じていない共通部分グラフＣＳＧの頂点数よりも多くなる。例えば、部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合と、部分グラフ｛ｖ１，ｖ３，ｖ４｝の共通アイテム集合とはともに｛ｉ１，ｉ２｝であるが、閉共通部分グラフＣＣＳＧである部分グラフ｛ｖ１，ｖ３，ｖ４｝の方が、閉共通部分グラフＣＣＳＧではない部分グラフ｛ｖ１，ｖ４｝よりも頂点の数が多い。
【００５５】
より多くの頂点を含む共通部分グラフＣＳＧを検出することができれば、例えば、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化する遺伝子群として、より遺伝子数が多いものが検出されるようになるので、より多くの遺伝子に影響を及ぼす医薬を同定することができ、例えば創薬の際に有用である。また、例えば、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化するタンパク質群として、よりタンパク質数が多いものが検出されるようになるので、より多くのタンパク質に影響を及ぼす医薬を同定することができ、例えば創薬の際に有用である。また、例えば、直接的又は間接的に交友関係を有し、かつ、共通の商品を購入したユーザ群として、よりユーザ数が多いものが検出されるようになり、その結果として、商品の広告宣伝をより効率的に行えるようになる。そこで、本実施形態では、より多くの頂点を含む共通部分グラフＣＳＧを得るために、特に閉共通部分グラフＣＣＳＧを検出するようにしている。部分グラフ検出部２４の動作の詳細については後述する。
【００５６】
［５．処理］
部分グラフ検出装置２で実行される、共通部分グラフＣＳＧ（特に閉共通部分グラフＣＣＳＧ）を検出するための処理について説明する。なお、以下では、上記のＮの値が２である場合、すなわち、各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）の積集合が二種以上のアイテムｉを含むような共通部分グラフＣＳＧを検出する場合について説明する。
【００５７】
［５−１．処理の概要］
まず処理の概要について説明する。図７は処理の概要を説明するための図である。部分グラフ検出装置２では、深さ優先探索アルゴリズムを用いて、図７に示すようなツリーＴ（探索木）が生成されることによって共通部分グラフＣＳＧ（特に閉共通部分グラフＣＣＳＧ）が検出される。図７に示すツリーＴは、グラフＧの各頂点ｖ１〜ｖ６に対応するルートノードｎｒ（ｎｒ１〜ｎｒ６）と、ルートノードｎｒ１〜ｎｒ６よりも下位のノードｎｃ（ｎｃ１〜ｎｃＭ）と、を含む。また、図に示すツリーＴの各ノードｎには、そこまでの経路に含まれる頂点ｖの集合を示す頂点集合Ｖ（ｎ）と、頂点集合Ｖ（ｎ）のうちの全ての頂点ｖが有する共通のアイテムｉの集合を示す共通アイテム集合Ｉ（ｎ）と、が含まれている。図７では、各ノードｎの左側領域に頂点集合Ｖ（ｎ）が表され、右側領域に共通アイテム集合Ｉ（ｎ）が表されている。なお、以下、ツリーＴのノードｎに含まれる頂点集合Ｖ（ｎ）のことを、ツリーＴのノードｎの頂点集合Ｖ（ｎ）と呼び、ツリーＴのノードｎに含まれるアイテム集合Ｉ（ｎ）のことを、ツリーＴのノードｎのアイテム集合Ｉ（ｎ）と呼ぶ。
【００５８】
同図に示すツリーＴでは、各ノード（ノードｎｘとする）の頂点集合Ｖ（ｎｘ）に他の頂点ｖが一つ追加された頂点集合が、その子のノードｎｘ＋１の頂点集合Ｖ（ｎｘ＋１）になっている。具体的には、ノードｎｘの頂点集合Ｖ（ｎｘ）に当該頂点集合Ｖ（ｎｘ）のうちの末端頂点に隣接する一つの頂点が新たな末端頂点として追加された頂点集合が、ノードｎｘ＋１の頂点集合Ｖ（ｎｘ＋１）になっている。
【００５９】
例えば、ノードｎｒ１の頂点集合Ｖ（ｎｒ１）である｛ｖ１｝に、末端頂点である頂点ｖ１に隣接する頂点ｖ２が追加された頂点集合｛ｖ１，ｖ２｝が、ノードｎｒ１の子のノードｎｃ１の頂点集合Ｖ（ｎｃ１）になっている。この場合、追加された頂点ｖ２が頂点集合Ｖ（ｎｃ１）の末端頂点になっている。また例えば、ノードｎｃ１の頂点集合Ｖ（ｎｃ１）である｛ｖ１，ｖ２｝に、末端頂点である頂点ｖ２に隣接する頂点ｖ３が追加された頂点集合｛ｖ１，ｖ２，ｖ３｝が、ノードｎｃ１の子のノードｎｃ２の頂点集合Ｖ（ｎｃ２）になっている。この場合、追加された頂点ｖ３が頂点集合Ｖ（ｎｃ２）の末端頂点になっている。このように、親のノードｎｘの頂点集合Ｖ（ｎｘ）に当該頂点集合Ｖ（ｎｘ）の末端頂点に隣接する頂点が追加された頂点集合が、子のノードｎｘ＋１の頂点集合Ｖ（ｎｘ＋１）になっている。
【００６０】
各ノードｎの頂点集合Ｖ（ｎ）に含まれる各頂点は、当該頂点集合Ｖ（ｎ）に含まれる他のいずれかの頂点と隣接するようになっており、各ノードｎの頂点集合Ｖ（ｎ）は、当該頂点集合Ｖ（ｎ）を含む部分グラフを表していることになる。
【００６１】
部分グラフ検出部２４は、深さ優先探索アルゴリズムに従った探索順序で、ツリーＴの各ノードｎを判定対象とし、判定対象のノードｎの頂点集合Ｖ（ｎ）が複数の頂点ｖを含む場合に、当該頂点集合Ｖ（ｎ）が示す部分グラフが共通部分グラフＣＳＧであるか否かの判定を実行する。すなわち、頂点集合Ｖ（ｎ）の各頂点ｖに関連付けられたアイテム集合Ｉ（ｖ）の積集合が二種以上のアイテムを含むか否かの判定を実行する。こうして、部分グラフ検出部２４は、ツリーＴに基づいて共通部分グラフＣＳＧを検出する。なお、ここでは、図７に示すようなツリーＴを生成するために深さ優先探索アルゴリズムを用いているが、幅優先探索アルゴリズムを用いるようにしてもよい。
【００６２】
［５−２．基準集合テーブルについて］
部分グラフ検出装置２では、無駄な処理を実行しないようにするためのデータとして、基準集合テーブルが記憶される。ここで、基準集合テーブルについて説明しておく。
【００６３】
まず、基準集合テーブルを設ける意義について説明しておく。あるノード（ノードｎｘとする）と他ノード（ノードｎｙとする）との間に以下の３つの関係がすべて成立する場合、ノードｎｘの子孫のノード（ノードｎｘｄとする）の頂点集合Ｖ（ｎｘｄ）を含む部分グラフは閉部分グラフにはならない。
【００６４】
（関係１）ノードｎｘの頂点集合Ｖ（ｎｘ）の末端頂点と、ノードｎｙの頂点集合Ｖ （ｎｙ）の末端頂点と、が共通すること。
（関係２）ノードｎｙがノードｎｘよりも前に判定対象とされること。
（関係３）ノードｎｙの共通アイテム集合Ｉ（ｎｙ）⊇ノードｎｘの共通アイテム集合Ｉ（ｎｘ）であること。
【００６５】
ノードｎｘｄが示す頂点集合Ｖ（ｎｘｄ）を含む部分グラフが閉部分グラフにならないということは、ノードｎｘｄが示す頂点集合Ｖ（ｎｘｄ）を含む部分グラフは閉共通部分グラフＣＣＳＧにはなり得ないということである。そこで、本実施形態では、部分グラフ検出部２４は、あるノードｎｘ（第１のノード）と他ノードｎｙ（第２のノード）との間に関係１〜３がすべて成立する場合、ノードｎｘの子孫のノードｎｘｄの頂点集合Ｖ（ｎｘｄ）を判定対象として当該頂点集合Ｖ（ｎｘｄ）が表す部分グラフが共通部分グラフＣＳＧであるか否かを判定しないようになっている。その結果として、ツリーＴのすべてのノードｎを判定対象として、判定対象のノードｎの頂点集合Ｖ（ｎ）が表す部分グラフが共通部分グラフであるか否かの判定を実行しなくても、閉共通部分グラフＣＣＳＧが検出可能になり、処理負荷の軽減が図られる。
【００６６】
ここで、あるノードｎｘと他ノードｎｙとの間に関係１〜３がすべて成立する場合にノードｎｘの子孫のノードｎｘｄの頂点集合Ｖ（ｎｘｄ）が表す部分グラフが閉部分グラフにならない理由を説明する。
【００６７】
まず、ノードｎｙがノードｎｘよりも前に生成されるノードである場合（関係２）、ノードｎｘの頂点集合Ｖ（ｎｘ）の末端頂点と、ノードｎｙの頂点集合Ｖ （ｎｙ）の末端頂点と、が共通していれば（関係１）、「ノードｎｙの頂点集合Ｖ（ｎｙ）⊇ノードｎｘの頂点集合Ｖ（ｎｘ）」の関係（以下、この関係を「関係４」と記載する。）が成立する。例えば、図７において、ノードｎｃ１０と、ノードｎｃ１０よりも前に生成されるノードｎｃ７と、の間では、「ノードｎｃ７の頂点集合Ｖ（ｎｃ７）⊇ノードｎｃ１０の頂点集合Ｖ（ｎｃ１０）」が成立している。
【００６８】
従って、ノードｎｘの頂点集合Ｖ（ｎｘ）にその末端頂点に隣接する頂点ｖが追加された頂点集合を、ノードｎｘの子孫のノードｎｘｄの頂点集合Ｖ（ｎｘｄ）とし、ノードｎｙの頂点集合Ｖ（ｎｙ）に同じ頂点ｖが追加された頂点集合を、ノードｎｙの子孫のノードｎｙｄの頂点集合Ｖ（ｎｙｄ）とした場合、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）と、ノードｎｙｄの頂点集合Ｖ（ｎｙｄ）との間には、「ノードｎｙｄの頂点集合Ｖ（ｎｙｄ）⊇ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）」の関係（以下、この関係を「関係５」と記載する。）が成立する。例えば、図７において、ノードｎｃ７の子孫のノードｎｃ８と、ノードｎｃ１０の子孫のノードｎｃ１１と、の間には、「ノードｎｃ８の頂点集合Ｖ（ｎｃ８）⊇ノードｎｃ１１の頂点集合Ｖ（ｎｃ１１）」が成立している。
【００６９】
ここで、上記関係５が成立する場合、ノードｎｙｄの頂点集合Ｖ（ｎｙｄ）の各頂点に関連付けられたアイテム集合の積集合（すなわち、共通アイテム集合Ｉ（ｎｙｄ））に含まれるアイテムの数が、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）の各頂点に関連付けられたアイテム集合の積集合（すなわち、共通アイテム集合Ｉ（ｎｘｄ））に含まれるアイテムの数よりも多くなることはない。頂点集合に含まれる頂点の数が多くなるほど、その頂点集合の各頂点に関連付けられたアイテム集合の積集合に含まれるアイテムの数が減るからである。このため、上記関係５が成立する場合、「ノードｎｙｄの共通アイテム集合Ｉ（ｎｙｄ）⊆ノードｎｘｄの共通アイテム集合Ｉ（ｎｘｄ）」の関係（以下、この関係を「関係６」と記載する。）が成立することになる。
【００７０】
一方、「ノードｎｙの共通アイテム集合Ｉ（ｎｙ）⊇ノードｎｘの共通アイテム集合Ｉ（ｎｘ）」である場合（関係３）、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）と、ノードｎｙｄの頂点集合Ｖ（ｎｙｄ）とは、それぞれ、頂点集合Ｖ（ｎｘｄ）及び頂点集合Ｖ（ｎｙｄ）のそれぞれに同じ頂点ｖが追加された頂点集合であるため、ノードｎｘｄの共通アイテム集合Ｉ（ｎｘｄ）と、ノードｎｙｄの共通アイテム集合Ｉ（ｎｙｄ）と、の間には、「ノードｎｙｄの共通アイテム集合Ｉ（ｎｙｄ）⊇ノードｎｘｄの共通アイテム集合Ｉ（ｎｘｄ）」の関係（以下、この関係を「関係７」と記載する。）が成立することになる。
【００７１】
以上のように、上記関係１〜３がすべて成立する場合、上記関係６，７が同時に成立することになる。上記関係６，７が同時に成立する場合とは、ノードｎｘｄの共通アイテム集合Ｉ（ｎｘｄ）と、ノードｎｙｄの共通アイテム集合Ｉ（ｎｙｄ）とが、「ノードｎｙｄの共通アイテム集合Ｉ（ｎｙｄ）＝ノードｎｘｄの共通アイテム集合Ｉ（ｎｘｄ）」の関係を有する場合である。このため、上記関係１〜３がすべて成立する場合には、ノードｎｙｄの共通アイテム集合Ｉ（ｎｙｄ）と、ノードｎｘｄの共通アイテム集合Ｉ（ｎｘｄ）と、の間に、「ノードｎｙｄのアイテム集合Ｉ（ｎｙｄ）＝ノードｎｘｄのアイテム集合Ｉ（ｎｘｄ）」の関係が成立することになる。これは、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）に、ノードｎｙｄの頂点集合Ｖ（ｎｙｄ）に含まれ、かつ、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）に含まれない頂点ｖを追加しても、共通アイテム集合が変わらないことを示している。つまり、あるノードｎｘと他のノードｎｙとの間に上記関係１〜３がすべて成立する場合に、ノードｎｘの子孫のノードｎｘｄの頂点集合Ｖ（ｎｘｄ）が表す部分グラフは閉部分グラフにならないということになる。
【００７２】
例えば、図７に示す場合、ノードｎｃ１０の子のノードｎｃ１１の共通アイテム集合Ｉ（ｎｃ１１）と、ノードｎｃ７の子のノードｎｃ８の共通アイテム集合Ｉ（ｎｃ８）とは、ともに｛ｉ１｝であり、等しくなっている。そして、ノードｎｃ８の頂点集合Ｖ（ｎｃ８）に含まれ、かつ、ノードｎｃ１１の頂点集合Ｖ（ｎｃ１１）に含まれない頂点ｖ３をノードｎｃ１１の頂点集合Ｖ（ｎｃ１１）に追加しても共通アイテム集合は｛ｉ１｝のままで変化しない。よって、頂点集合Ｖ（ｎｃ１１）が表す部分グラフは閉部分グラフにはならない。
【００７３】
なお、上記関係１と上記関係２とが成立する場合、上記関係４が成立することは以上で述べた。そのため、「あるノードｎｘと他ノードｎｙとの間に上記関係１，３，４がすべて成立する場合に、ノードｎｘの子のノードｎｃｘ（言い換えれば、ノードｎｃｘの頂点集合Ｖ（ｎｘｄ））を判定対象として上記の判定を行わない」とは、「ノードｎｘとノードｎｙとの間に上記関係１，３，４がすべて成立する場合に、頂点集合Ｖ（ｎｘｄ）を判定対象として上記の判定を行わない」ともいうことができる。
【００７４】
ところで、ツリーＴの各ノードを幅優先探索アルゴリズムに従った探索順序で判定対象とする場合にも、あるノードｎｘ（第１のノード）と他のノードｎｙ（第２のノード）との間に、上記関係１、上記関係３、及び下記関係２’がすべて成立する場合に、ノードｎｘの子孫のノードｎｘｄの頂点集合Ｖ（ｎｘｄ）が表す部分グラフが共通部分グラフＣＳＧであるか否かを判定しないようにすることが可能である。
（関係２’）ノードｎｘがノードｎｙよりも前に判定対象とされること。
【００７５】
このようにすれば、ツリーＴの各ノードを幅優先探索アルゴリズムに従った探索順序で判定対象とする場合においても、すべての頂点集合Ｖ（ｎ）を判定対象として当該頂点集合Ｖ（ｎ）が表す部分グラフが共通部分グラフＣＳＧであるか否かを判定しなくても、閉共通部分グラフＣＣＳＧが検出可能になる。なぜなら、ノードｎｘがノードｎｙよりも前に判定対象にされるノードである場合（関係２’）、幅優先探索アルゴリズムの探索順序を考慮すると、ノードｎｘの頂点集合Ｖ（ｎｘ）の末端頂点と、ノードｎｙの頂点集合Ｖ （ｎｙ）の末端頂点と、が共通しているのなら（関係１）、上記関係４「ノードｎｙの頂点集合Ｖ（ｎｙ）⊇ノードｎｘの頂点集合Ｖ（ｎｘ）」が成立する。従って、上記関係１、上記関係３、及び上記関係４が成立するのだから、深さ優先探索アルゴリズムの場合と同様に、上記関係５〜７が成立することになる。また、その結果、「ノードｎｙｄのアイテム集合Ｉ（ｎｙｄ）＝ノードｎｘｄのアイテム集合Ｉ（ｎｘｄ）」の関係が成立することとなり、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）に、ノードｎｙｄの頂点集合Ｖ（ｎｙｄ）に含まれ、かつ、ノードｎｘｄの頂点集合Ｖ（ｎｘｄ）に含まれない頂点ｖを追加しても、共通アイテム集合が変わらないということになるからである。この場合も、上記関係１、３、４がすべて成立する場合に、頂点集合Ｖ（ｎｘｄ）を判定対象として上記の判定を行わないようにしているということができる。
【００７６】
基準集合テーブルは、あるノードｎｘと他ノードｎｙとの間に上記関係１〜３がすべて成立する場合に、ノードｎｘの子のノードｎｃｘの頂点集合Ｖ（ｎｘｄ）を判定対象として上記の判定を行わないようするために用いられる。図８は、基準集合テーブルの一例を示す図である。基準集合テーブルは、グラフＧに含まれる各頂点ｖと、該頂点ｖを末端頂点とする頂点集合Ｖ（ｎ）の各頂点に関連付けられたアイテム集合の積集合である基準集合（すなわち、アイテム集合Ｉ（ｎ））を少なくとも１つ含む基準集合群Ｐ（ｖ）と、を関連付けてなるテーブルである。この基準集合テーブルの役割については後述する。
【００７７】
［５−３．処理の詳細］
図９は制御部８が実行する処理を示すフロー図である。以下、図９を参照しながら制御部８が行う処理の詳細について説明する。なお、図９に示す処理を制御部８が実行することによって、グラフデータ取得部２０、頂点データ取得部２２、及び部分グラフ検出部２４が実現される。なお、図９のＳ１０１の処理は、グラフデータ取得部２０及び頂点データ取得部２２に対応しており、図９のＳ１０２以降の処理は部分グラフ検出部２４に対応している。
【００７８】
まず、制御部８は、共通部分グラフＣＳＧを検出するための前処理（Ｓ１０１〜Ｓ１０４）を実行する。
【００７９】
まず、制御部８はグラフデータと頂点データとをデータベース４から読み出して取得する（Ｓ１０１）。そして、制御部８は、読み出したグラフデータを加工する。具体的には、二種以上のアイテムｉを含まないアイテム集合Ｉ（ｖ）が関連付けられている頂点ｖにつながる辺ｅを削除し、他の頂点ｖとのつながりを切断する（Ｓ１０２）。上述したように、共通部分グラフＣＳＧは、すべての頂点ｖが二種以上の共通のアイテムを有するような部分グラフである。二種以上のアイテムｉを含んでいないアイテム集合Ｉ（ｖ）が関連付けられている頂点ｖ、すなわち、二種以上のアイテムｉを有しない頂点ｖを含む部分グラフは共通部分グラフＣＳＧにはなり得ない。このため、このような頂点ｖをＳ１０３以降の処理で無視するためにＳ１０２の処理が実行される。Ｓ１０２の処理が実行されることによって、無駄な処理が実行されなくなり、共通部分グラフＣＳＧの検出にかかる時間が短縮される。
【００８０】
その後、制御部８は基準集合テーブルを初期化する（Ｓ１０３）。具体的には、各頂点ｖの基準集合群Ｐ（ｖ）がｎｕｌｌに初期化される。また、制御部８は、グラフＧに含まれる頂点ｖの集合を頂点集合Ｖａとして取得する（Ｓ１０４）。
【００８１】
そして、制御部８は、頂点集合Ｖａに含まれる各頂点ｖを処理対象の頂点ｖｘとして順次選択し、Ｓ１０５〜Ｓ１０８の処理を実行する。例えば頂点ｖ１が選択された場合には、Ｓ１０５〜Ｓ１０８の処理が実行されることによって、図７に示すツリーＴのうちの、頂点ｖ１に対応するルートノードｎｒ１よりも下位のノードｎｃが生成され、頂点ｖ１を含むような共通部分グラフＣＳＧの検出が実行される。
【００８２】
まず、制御部８は、頂点集合Ｖａに含まれる頂点ｖの集合を頂点集合Ｖｂとして取得する（Ｓ１０５）。そして、制御部８は、頂点ｖｘに対応するルートノードｎｒｘを生成し、記憶部１０に保存する（Ｓ１０６）。例えば、頂点ｖｘが頂点ｖ１である場合、ルートノードｎｒ１が生成される。ルートノードｎｒ１の頂点集合Ｖ（ｎｒ１）は｛ｖ１｝であり、共通アイテム集合Ｉ（ｎｒ１）は｛ｉ１，ｉ２，ｉ３，ｉ４｝である。なお、頂点集合Ｖ（ｎｒ１）の末端頂点はｖ１である。その後、制御部８はサブルーチンＳを実行する（Ｓ１０７）。
【００８３】
ここで、サブルーチンＳについて説明する。図１０及び図１１はサブルーチンＳの処理を示すフロー図である。サブルーチンＳは、頂点集合に相当する引数ＶＰと、一つの頂点ｖに対応する引数ｖｐと、ツリーＴの一つのノードｎに対応する引数ｎｐと、の３つの引数を有する。Ｓ１０７の処理では、頂点集合Ｖｂを引数ＶＰとし、頂点ｖｘを引数ｖｐとし、ルートノードｎｒｘを引数ｎｐとして、サブルーチンＳが呼び出される。
【００８４】
図１０に示すように、サブルーチンＳでは、まず、頂点集合ＶＰに含まれる頂点ｖのうちの、頂点ｖｐに隣接する頂点ｖの集合が隣接頂点集合Ｖｎとして取得される（Ｓ２０１）。そして、制御部８は、隣接頂点集合Ｖｎが空集合であるか否かを判定する（Ｓ２０２）。隣接頂点集合Ｖｎが空集合である場合（Ｓ２０２のＹ）、すなわち、頂点集合ＶＰに含まれる頂点ｖのうちに頂点ｖｐに隣接する頂点ｖが存在しない場合、制御部８はサブルーチンＳを終了して、図９のＳ１０８の処理を実行する。すなわち、頂点集合Ｖａから頂点ｖｘが除かれ（Ｓ１０８）、頂点集合Ｖａから他の頂点ｖが新たな処理対象の頂点ｖｘとして選択されてＳ１０５〜Ｓ１０８の処理が再実行される。
【００８５】
一方、隣接頂点集合Ｖｎが空集合でない場合（Ｓ２０２のＮ）、制御部８は、隣接頂点集合Ｖｎに含まれる各頂点ｖを処理対象の頂点ｖｎｘとして順次選択して、Ｓ２０３〜Ｓ２０９の処理を実行する。
【００８６】
まず、制御部８は頂点データを参照して、頂点ｖｎｘに関連づけられたアイテム集合Ｉ（ｖｎｘ）を取得する。そして、制御部８は、アイテム集合Ｉ（ｖｎｘ）と、ツリーＴのノードｎｐの共通アイテム集合Ｉ（ｎｐ）と、の積集合を共通アイテム集合Ｉｃとして取得する（Ｓ２０３）。なお、ノードｎｐの共通アイテム集合Ｉ（ｎｐ）とは、上述のように、ノードｎｐの頂点集合Ｖ（ｎｐ）の各頂点ｖに関連づけられたアイテム集合Ｉ（ｖ）の積集合である。
【００８７】
そして、制御部８（判定手段）は、共通アイテム集合Ｉｃに二種以上のアイテムｉが含まれるか否かを判定する（Ｓ２０４）。なお、Ｓ２０４の処理では、ノードｎｐの頂点集合Ｖ（ｎｐ）に頂点ｖｎｘを追加してなる頂点集合が示す部分グラフを判定対象として、該部分グラフの全頂点ｖが二種以上の共通のアイテムを共有するか否かが判定されていることになる。つまり、ノードｎｐの頂点集合Ｖ（ｎｐ）に頂点ｖｎｘを追加してなる部分グラフが共通部分グラフＣＳＧであるか否かが判定されていることになる。
【００８８】
なお、上述のように、ノードｎｐの頂点集合Ｖ（ｎｐ）に当該頂点集合Ｖ（ｎｐ）のうちの頂点ｖｐ（末端頂点）に隣接する頂点ｖｎｘを追加してなる頂点集合は、ノードｎｐの子のノードに相当する。また、Ｓ２０３で取得された共通アイテム集合Ｉｃは、ノードｎｐの子のノードが示す頂点集合（部分グラフ）の全頂点ｖの共通アイテム集合に相当する。このため、Ｓ２０４の処理では、ノードｎｐの子のノードが示す頂点集合（部分グラフ）の全頂点ｖが二種以上の共通のアイテムを共有するか否かが判定されているともいうことができる。すなわち、ノードｎｐの子のノードが示す頂点集合（部分グラフ）が共通部分グラフＣＳＧであるか否かが判定されているともいうことができる。
【００８９】
共通アイテム集合Ｉｃに二種以上のアイテムｉが含まれる場合（Ｓ２０４のＹ）、制御部８は、基準集合テーブル（図８参照）から、頂点ｖｎｘに対応する基準集合群Ｐ（ｖｎｘ）を読み出し、共通アイテム集合Ｉｃが、基準集合群Ｐ（ｖｎｘ）のうちのいずれかの基準集合Ｉｐの部分集合であるか否かを判定する（Ｓ２０５）。この処理の役割については後述する。
【００９０】
共通アイテム集合Ｉｃがいずれの基準集合Ｉｐの部分集合でもない場合（Ｓ２０５のＮ）、制御部８は、記憶部１０（基準集合記憶手段）に記憶される基準集合テーブル（図８参照）において、頂点ｖｎｘに対応する基準集合群Ｐ（ｖｎｘ）に共通アイテム集合Ｉｃを基準集合Ｉｐとして追加する（Ｓ２０６）。その後、制御部８は、ツリーＴのうちの、ノードｎｐの子のノードｎｃであって、かつ、頂点ｖｎｘに対応するノードｎｃｘを生成し、記憶部１０に保存する（Ｓ２０７）。この場合、ノードｎｃｘの頂点集合Ｖ（ｎｃｘ）は、ノードｎｐの頂点集合Ｖ（ｎｐ）に頂点ｖｎｘを追加した頂点集合に設定され、共通アイテム集合Ｉ（ｎｃｘ）は共通アイテム集合Ｉｃに設定される。また、頂点集合Ｖ（ｎｃｘ）の末端頂点は頂点ｖｎｘになる。
【００９１】
ここで、Ｓ２０７で生成されるノードｎｃｘは一つの共通部分グラフＣＳＧを表している。なぜなら、ノードｎｃｘの頂点集合Ｖ（ｎｃｘ）は頂点ｖの集合を示し、共通アイテム集合Ｉ（ｎｃｘ）は、頂点集合Ｖ（ｎｃｘ）に含まれる頂点ｖが共通に有するアイテムｉの集合を示し、かつ、二種以上のアイテムｉを含んでいるからである（Ｓ２０４参照）。このため、ノードｎｃｘを生成することは共通部分グラフＣＳＧを検出することに相当する。
【００９２】
その後、頂点集合ＶＰから頂点ｖｎｘが除かれ（Ｓ２０８）、サブルーチンＳが再帰的に呼び出される（Ｓ２０９）。この場合、サブルーチンＳは、頂点集合ＶＰを引数ＶＰとし、頂点ｖｎｘを引数ｖｐとし、Ｓ２０７で生成されたノードｎｃｘを引数ｎｐとして呼び出される。このサブルーチンＳの呼び出しによって、図７に示すツリーＴのうちのノードｎｃｘより下位のノードｎｃが生成される。
【００９３】
なお、Ｓ２０４の処理において、共通アイテム集合Ｉｃに二種以上のアイテムｉが含まれないと判定された場合（Ｓ２０４のＮ）、制御部８（制限手段）はＳ２０５〜Ｓ２０９の処理を実行しない。この場合、隣接頂点集合Ｖｎに含まれる他の頂点ｖが新たな処理対象の頂点ｖｎｘとして選択され、Ｓ２０３の処理が実行される。
【００９４】
ここで、Ｓ２０４の処理の役割について説明する。ここでは、図９のＳ１０７の処理でサブルーチンＳが、ノードｎｒ１を引数ｎｐとして呼び出され、かつ、Ｓ２０４の処理において、頂点ｖ２が処理対象の頂点ｖｎｘとして選択されている場合を想定する。この場合、上述したように、Ｓ２０４の処理では、ノードｎｒ１の頂点集合Ｖ（ｎｒ１）である｛ｖ１｝に頂点ｖ２を追加してなる頂点集合｛ｖ１，ｖ２｝、言い換えれば、ノードｎｒ１の子のノードｎｃ１に対応する頂点集合｛ｖ１，ｖ２｝が、共通部分グラフＣＳＧであるか否かが判定されることになる。すなわち部分グラフ｛ｖ１，ｖ２｝が共通部分グラフＣＳＧであるか否かが判定されることになる。そして、頂点ｖ１と頂点ｖ２とが共通に有するアイテムｉはアイテムｉ１のみであるため（図３参照）、Ｓ２０４の処理では、共通アイテム集合Ｉｃに二種以上のアイテムｉが含まれないと判定される。すなわち、部分グラフ｛ｖ１，ｖ２｝が共通部分グラフＣＳＧでないと判定される。その結果、Ｓ２０５〜Ｓ２０９の処理が実行されなくなる。すなわち、図７に示すノードｎｃ１が生成されなくなる。また、頂点ｖｎｘ（ｖ２）を引数ｖｐとし、かつ、ノードｎｃ１を引数ｎｐとしたようなサブルーチンＳの呼び出しも行われなくなり、図７に示すノードｎｃ１よりも下位のノードｎｃ２〜ｎｃ５も生成されなくなる。つまり、ノードｎｃ１の子孫のノード（ノードｎｘとする）の頂点集合Ｖ（ｎｘ）を判定対象とした、頂点集合Ｖ（ｎｘ）により表される部分グラフが共通部分グラフＣＳＧであるか否かの判定が実行されなくなる。
【００９５】
例えば、頂点ｖｎｘ（ｖ２）を引数ｖｐとし、かつ、ノードｎｃ１を引数ｎｐとしたようなサブルーチンＳの呼び出しが行われた場合には、Ｓ２０４の処理では、ノードｎｃ１の頂点集合Ｖ（ｎｃ１）である｛ｖ１，ｖ２｝に、頂点ｖｎｘ（ｖ２）に隣接する頂点ｖ３が追加されてなる頂点集合｛ｖ１，ｖ２，ｖ３｝、すなわち部分グラフ｛ｖ１，ｖ２，ｖ３｝が共通部分グラフＣＳＧであるか否かの判定処理が実行されることになる。例えば、部分グラフ｛ｖ１，ｖ２｝の各頂点ｖが二種以上の共通のアイテムｉを有しておらず、部分グラフ｛ｖ１，ｖ２｝が共通部分グラフＣＳＧでない場合、当然のことながら、その部分グラフ｛ｖ１，ｖ２｝に頂点ｖ３を追加してなる部分グラフ｛ｖ１，ｖ２，ｖ３｝も共通部分グラフＣＳＧにはなり得ない。このため、上記のような判定処理は不要である。この点、本実施の形態では、Ｓ２０４の処理において部分グラフ｛ｖ１，ｖ２｝が共通部分グラフＣＳＧでないと判定された場合、Ｓ２０５〜Ｓ２０９の処理が実行されなくなるため、部分グラフ｛ｖ１，ｖ２，ｖ３｝が共通部分グラフＣＳＧであるか否かの判定も行われなくなる。すなわち、不要な処理が実行されないように図られる。
【００９６】
また、Ｓ２０５の処理において、共通アイテム集合Ｉｃが基準集合群Ｐ（ｖｎｘ）のうちのいずれかの基準集合ＩＰの部分集合であると判定された場合、制御部８（制限手段）はＳ２０６以降の処理を実行しない。この場合、隣接頂点集合Ｖｎに含まれる他の頂点ｖが新たに頂点ｖｎｘとして選択され、Ｓ２０３の処理が実行される。
【００９７】
ここで、基準集合テーブル（図８参照）と、Ｓ２０５の処理と、の役割について説明する。ここでは、例えば、図１１のＳ２０９でサブルーチンＳが、頂点ｖ３を引数ｖｐとし、かつ、ノードｎｃ６を引数ｎｐとして呼び出され、頂点ｖ４を処理対象の頂点ｖｎｘとして、Ｓ２０３〜Ｓ２０６の処理が実行される場合を想定する。この場合、上述したように、Ｓ２０４の処理では、ノードｎｃ６の頂点集合Ｖ（ｎｃ６）である｛ｖ１，ｖ３｝に、頂点ｖｎｘ（ｖ３）に隣接する頂点ｖ４が末端頂点として追加されてなる頂点集合｛ｖ１，ｖ３，ｖ４｝、言い換えれば、ノードｎｃ７に対応する頂点集合｛ｖ１，ｖ３，ｖ４｝が共通部分グラフＣＳＧであるか否かが判定される。すなわち部分グラフ｛ｖ１，ｖ３，ｖ４｝が共通部分グラフＣＳＧであるか否かが判定される。そして、頂点ｖ１，ｖ３，ｖ４が共通に有するアイテムｉはアイテムｉ１，ｉ２であるため（図３参照）、Ｓ２０４の処理では、共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝に二種以上のアイテムｉが含まれると判定される。すなわち、部分グラフ｛ｖ１，ｖ３，ｖ４｝が共通部分グラフＣＳＧであると判定される。また、この時点における基準集合テーブル（図８参照）では、頂点ｖ４に対応する基準集合群Ｐ（ｖ４）が初期状態（ｎｕｌｌの状態）になっているため、Ｓ２０５の処理では、共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合群Ｐ（ｖ４）のいずれの基準集合Ｉｐの部分集合でもないと判定される。その結果、Ｓ２０６の処理が実行され、基準集合テーブル（図８参照）において、頂点ｖ４に対応する基準集合群Ｐ（ｖ４）に共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合として追加される。
【００９８】
さらに、ここで、図９のＳ１０７でサブルーチンＳが、頂点ｖ１を引数ｖｐとし、ノードｎｒ１を引数ｎｐとして呼び出され、頂点ｖ４を処理対象の頂点ｖｎｘとして、Ｓ２０３〜Ｓ２０５の処理が実行される場合を想定する。この場合、上述したように、Ｓ２０４の処理では、ノードｎｒ１の頂点集合Ｖ（ｎｒ１）である｛ｖ１｝に、頂点ｖ１に隣接する頂点ｖ４が末端頂点として追加されてなる頂点集合｛ｖ１，ｖ４｝、言い換えれば、ノードｎｃ１０に対応する頂点集合｛ｖ１，ｖ４｝が共通部分グラフＣＳＧであるか否かが判定される。すなわち部分グラフ｛ｖ１，ｖ４｝が共通部分グラフＣＳＧであるか否かが判定される。そして、頂点ｖ１，ｖ４が共通に有するアイテムｉはアイテムｉ１，ｉ２であるため（図３参照）、Ｓ２０４の処理では、共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝に二種以上のアイテムｉが含まれると判定される。すなわち、部分グラフ｛ｖ１，ｖ４｝が共通部分グラフＣＳＧであると判定される。一方、この時点における基準集合テーブル（図８参照）では、頂点ｖ４に対応する基準集合群Ｐ（ｖ４）に基準集合Ｉｐ｛ｉ１，ｉ２｝が含まれている。ここで、基準集合Ｉｐ｛ｉ１，ｉ２｝は、既に生成済みのノードｎｃ７の共通アイテム集合Ｉ（ｎｃ７）である。頂点ｖ４に対応する基準集合群Ｐ（ｖ４）に基準集合Ｉｐ｛ｉ１，ｉ２｝が含まれているため、Ｓ２０５の処理では、部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合群Ｐ（ｖ４）のいずれかの基準集合Ｉｐの部分集合であると判定される。その結果、Ｓ２０６〜Ｓ２０８の処理が実行されなくなる。すなわち、Ｓ２０７の処理が実行されず、図７に示すノードｎｃ１０が生成されなくなる。また、Ｓ２０８の処理が実行されず、頂点ｖｎｘ（ｖ４）を引数ｖｐとし、かつ、ノードｎｃ１０を引数ｎｐとしたようなサブルーチンＳの呼び出しも行われなくなる。その結果、図７に示すノードｎｃ１０よりも下位のノードｎｃ１１〜ｎｃ１２も生成されなくなる。つまり、ノードｎｃ１０の子孫のノード（ノードｎｘとする）の頂点集合Ｖ（ｎｘ）が判定対象として取得されず、頂点集合Ｖ（ｎｘ）により表される部分グラフが共通部分グラフＣＳＧであるか否かも判定されなくなる。
【００９９】
例えば、頂点ｖｎｘ（ｖ４）を引数ｖｐとし、かつ、ノードｎｃ１０を引数ｎｐとしたようなサブルーチンＳの呼び出しが行われた場合には、Ｓ２０４の処理では、ノードｎｃ１０の頂点集合Ｖ（ｎｃ１０）である｛ｖ１，ｖ４｝に、頂点ｖｎｘ（ｖ４）に隣接する頂点ｖ５が追加されてなる頂点集合｛ｖ１，ｖ４，ｖ５｝、すなわち部分グラフ｛ｖ１，ｖ４，ｖ５｝が共通部分グラフＣＳＧであるか否かが判定されることになる。この点、本実施の形態では、Ｓ２０５の処理において、部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合群Ｐ（ｖ４）のいずれかの基準集合Ｉｐの部分集合であると判定された場合、Ｓ２０５〜Ｓ２０９の処理が実行されなくなるため、ノードｎｃ１０の子のノードｎｃ１１の頂点集合Ｖ（ｎｃ１１）により表される部分グラフ｛ｖ１，ｖ４，ｖ５｝が共通部分グラフＣＳＧであるか否かの判定も行われなくなる。
【０１００】
Ｓ２０５の処理で部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合群Ｐ（ｖ４）のいずれかの基準集合Ｉｐ｛ｉ１，ｉ２｝の部分集合であると判定される場合とは、頂点ｖ４を含む部分グラフに関してすでに検出済みの共通アイテム集合に含まれないような共通アイテム集合が検出される可能性がない場合である。
【０１０１】
また、Ｓ２０５の処理で部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合群Ｐ（ｖ４）のいずれかの基準集合Ｉｐ｛ｉ１，ｉ２｝の部分集合であると判定される場合とは、上述のように基準集合Ｉｐ｛ｉ１，ｉ２｝は既に生成済みのノードｎｃ７の共通アイテム集合Ｉ（ｎｃ７）に相当するので、既に生成済みのノードｎｃ７の共通アイテム集合Ｉ（ｎｃ７）にノードｎｃ１０の共通アイテム集合Ｉ（ｎｃ１０）が含まれる場合である。さらに、ノードｎｃ７の頂点集合Ｖ（ｎｃ７）の末端頂点と、ノードｎｃ１０の頂点集合Ｖ（ｎｃ１０）の末端頂点と、はともに頂点ｖ４なのであるから、Ｓ２０５の処理で部分グラフ｛ｖ１，ｖ４｝の共通アイテム集合Ｉｃ｛ｉ１，ｉ２｝が基準集合群Ｐ（ｖ４）のいずれかの基準集合Ｉｐ｛ｉ１，ｉ２｝の部分集合であると判定される場合とは、ノードｎｃ７をノードｎｙとし、ノードｎｃ１０をノードｎｘとした場合に、ノードｎｙとノードｎｘとの間で上記の関係１〜３がすべて成立する場合である。このような場合には、部分グラフ｛ｖ１，ｖ４｝に頂点ｖ５が追加されてなる頂点集合｛ｖ１，ｖ４，ｖ５｝、すなわち部分グラフ｛ｖ１，ｖ４，ｖ５｝が閉部分グラフでないのは明らかだから、共通部分グラフＣＳＧであるか否かの判定処理を実行する必要がない。この点、本実施の形態では、このような不必要な判定処理が実行されないようになる。
【０１０２】
図９に示すように、すべての頂点ｖについてＳ１０５〜Ｓ１０８の処理が実行された場合、制御部８は共通部分グラフＣＳＧの検出結果を出力する（Ｓ１０９）。上述したように、記憶部１０に保持されたツリーＴのノードｎｃは共通部分グラフＣＳＧ（本実施形態の場合、閉共通部分グラフＣＣＳＧ）を表している。Ｓ１０９の処理では、記憶部１０に保持されたツリーＴのノードｎｃに基づいて、例えば、頂点ｖ又は辺ｅの数が最も多いような共通部分グラフＣＳＧが表示出力される。または、頂点ｖ又は辺ｅの数が所定の基準数よりも多いような共通部分グラフＣＳＧが表示出力される。または、検出されたすべての共通部分グラフＣＳＧが表示出力される。以上が、部分グラフ検出装置２で実行される処理の詳細である。
【０１０３】
［５．まとめ］
上記の部分グラフ検出システム６では、例えば、複数の遺伝子に対応する複数の頂点ｖｉを含み、該複数の遺伝子の関係を示すグラフＧのグラフデータが記憶される。また、複数の頂点ｖｉの各々にアイテム集合Ｉ（ｖｉ）を対応づけてなる頂点データが記憶され、この頂点データは各遺伝子の発現を変化させる医薬を示すデータとなっている。そして、部分グラフ検出装置２では、これらのデータに基づいて、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化する遺伝子群を表す共通部分グラフＣＳＧが検出される。この検出結果を用いることによって、例えば、創薬のターゲットとすべき遺伝子を絞り込む上で有用な情報が得られるようになる。
【０１０４】
また例えば、部分グラフ検出システム６では、複数のタンパク質に対応する頂点ｖｉを含み、かつ、該複数のタンパク質の関係を示すグラフＧのグラフデータが記憶され、各タンパク質の発現を変化させる医薬を示す頂点データが記憶される。この場合、直接的又は間接的に関係を有し、かつ、共通の医薬の投与により共通して発現が変化するタンパク質群を表す共通部分グラフＣＳＧが検出される。この検出結果を用いることによって、例えば、創薬のターゲットとすべきタンパク質を絞り込む上で有用な情報が得られるようになる。
【０１０５】
また例えば、部分グラフ検出システム６では、複数のユーザに対応する複数の頂点ｖｉを含み、かつ、該複数のユーザの交友関係を示すグラフＧのグラフデータが記憶され、各ユーザが購入した商品を示す頂点データが記憶される。この場合、直接的又は間接的に交友関係を有し、かつ、共通の商品を購入したユーザ群を表す共通部分グラフＣＳＧが検出される。この検出結果を用いることによって、例えば、上述したように、商品の広告宣伝を効率的に行えるようにもなる。
【０１０６】
ところで、図１０のＳ２０４及びＳ２０５の少なくとも一方を省略しても、共通部分グラフＣＳＧの検出は可能である。例えば、図１０のＳ２０４及びＳ２０５の少なくとも一方を省略しても、閉共通部分グラフＣＣＳＧの検出は可能である。例えば、すべての頂点集合、すなわち、すべての部分グラフを判定対象として上記のような判定処理を行ってすべての共通部分グラフを検出し、これらのうちから閉共通部分グラフを特定することが考えられる。しかしながら、この場合、例えば、グラフＧに含まれる頂点ｖの数（例えば、１００００個）が非常に多い場合には、すべての共通部分グラフＣＳＧの検出に膨大な時間がかかる可能性がある。
【０１０７】
この点、上記の部分グラフ検出装置２では、例えば、図１０のＳ２０４又はＳ２０５の処理が実行されることによって、不必要な処理の実行が抑制される。つまり、上記判定処理が、閉部分グラフでない部分グラフを判定対象としては行われなくなる。このため、共通部分グラフＣＳＧ（閉共通部分グラフＣＣＳＧ）の検出にかかる時間が短縮される。そのため、グラフＧに含まれる頂点ｖの数が非常に多い場合であっても、共通部分グラフＣＳＧ（閉共通部分グラフＣＣＳＧ）の検出が比較的短時間で行われるようになる。
【０１０８】
［６．変形例］
なお、本発明は、以上に説明した実施形態に限定されるものではない。
【０１０９】
［６−１．変形例１］
例えば、図９乃至図１１の処理では、頂点集合Ｖ（ｎｘ）が複数の頂点を含むようなノードｎｘと、他のノードｎｙと、の間で上記関係１〜３がすべて成立している場合に、ノードｎｘの子孫となるノードｎｘｄの頂点集合Ｖ（ｎｘｄ）を判定対象とした上記判定処理が省略されるようになっている。しかしながら、頂点集合Ｖ（ｎｘ）が一の頂点のみを含むようなノードｎｘ（第３のノード）と、ノードｎｙ（第４のノード）と、の間で上記関係１〜３（又は上記関係１，３，４）がすべて成立している場合に、ノードｎｘの子孫となるノードｎｘｄの頂点集合Ｖ（ｎｘｄ）を判定対象とした上記判定処理が省略されるようにしてもよい。
【０１１０】
例えば、制御部８は、図９のＳ１０７の処理を実行する前に、図１０のＳ２０５と類似の処理を実行するようにしてもよい。すなわち、制御部８は、頂点ｖｘに対応する基準集合群Ｐ（ｖｘ）を基準集合テーブル（図８参照）から取得し、頂点ｖｘのアイテム集合Ｉ（ｖｘ）が基準集合群Ｐ（ｖｘ）のうちのいずれかのアイテム集合ＩＰの部分集合であるか否かを判定するようにしてもよい。そして、アイテム集合Ｉ（ｖｘ）がいずれのアイテム集合ＩＰの部分集合でもない場合にＳ１０７の処理を実行し、アイテム集合Ｉ（ｖｘ）がいずれかのアイテム集合ＩＰの部分集合である場合には、Ｓ１０７の処理を実行しないで、Ｓ１０８の処理を実行するようにしてもよい。このようにしても、共通部分グラフＣＳＧ（閉共通部分グラフＣＣＳＧ）を検出するために不必要な処理の実行が抑制される。
【０１１１】
また、ツリーＴの各ノードを幅優先探索アルゴリズムに従った探索順序で判定対象とする場合は、頂点集合Ｖ（ｎｘ）が一の頂点のみを含むようなノードｎｘ（第３のノード）と、ノードｎｙ（第４のノード）と、の間で上記関係１，２’，３（又は上記関係１，３，４）がすべて成立している場合に、ノードｎｘの子孫となるノードｎｘｄの頂点集合Ｖ（ｎｘｄ）を判定対象とした上記判定処理が省略されるようにしてもよい。こうすれば、ツリーＴの各ノードを幅優先探索アルゴリズムに従った探索順序で判定対象とする場合も、共通部分グラフＣＳＧ（閉共通部分グラフＣＣＳＧ）を検出するために不必要な処理の実行が抑制される。
【０１１２】
［６−２．変形例２］
また、共通部分グラフＣＳＧを検出するための処理は上記に説明したものに限られない。例えば、まず、Ｎ種以上のアイテムｉを含む基準アイテム集合Ｉｄが決定されるようにしてもよい。その後、各頂点ｖに関連付けられたアイテム集合Ｉ（ｖ）が該基準アイテム集合Ｉｄを含むような共通部分グラフＣＳＧが検出されるようにしてもよい。この場合、制御部８は、図１０のＳ２０３の処理において、アイテム集合Ｉｄが共通アイテム集合Ｉｃの部分集合であるか否かが判定されるようにすればよい。
【０１１３】
［６−３．変形例３］
例えば、図５に示す頂点データにおけるアイテムｉは、ユーザが利用している又は過去に利用したことのあるサービスに対応するようにしてもよい。この場合、頂点データは各ユーザが利用している又は過去に利用したことのあるサービスを示すデータになる。このようにすれば、直接的又は間接的に交友関係にあり、かつ、共通のサービスを利用している又は利用したことのあるユーザ群を検出することが可能になる。そして、この検出結果を用いることによって、例えば、サービスの広告宣伝を効率的に行えるようになる。
【０１１４】
［６−４．変形例４］
例えば、グラフデータは、複数の文献に対応する複数の頂点ｖを含み、該複数の文献の関係（例えば引用関係）を示すグラフのデータであってもよい。このグラフでは、例えば、第１の文献が第２の文献を引用している場合、第１の文献に対応する頂点ｖ１と第２の文献に対応する頂点ｖ２が辺ｅ１２によって連結される。また、この場合、頂点データにおけるアイテムｉは、例えば、文献に関連するキーワードに対応するようにしてもよい。この場合、頂点データは各文献のキーワードを示すデータになる。この変形例１によれば、上記のグラフデータ及び頂点データに基づいて、例えば、直接的又は間接的に引用関係にあり、かつ、共通のキーワードが設定された文献群を検出できるようになる。なお例えば、アイテムｉは文献の著者に対応させるようにしてもよい。
【０１１５】
[６−５．その他]
また、グラフＧは、遺伝子、タンパク質、ユーザ、文献以外の関係を示すグラフであってもよい。すなわち、グラフＧに含まれる頂点ｖは、遺伝子、タンパク質、ユーザ、文献以外に対応する頂点であってもよい。また、頂点データにおいて頂点ｖに関連づけられる情報は、頂点間の接続関係を示す情報以外の情報であれば、ユーザに関する情報、キーワード、医薬に限らず、どのような情報であってもよい。
【０１１６】
また、以上では、グラフＧが無向グラフである場合について述べたが、グラフＧは有向グラフであってもよい。この場合、図７のツリーＴは、頂点間の有向関係を考慮して生成される。例えば、制御部８は、図１０のＳ２０１のステップにおいて、頂点集合ＶＰに含まれる頂点ｖｐに隣接する頂点ｖのうち、頂点ｖｐから伸びる辺に接続された頂点ｖの集合を、隣接頂点集合Ｖｎとして取得するようにする。
【０１１７】
［７．実験］
なお、本実施形態に係る方法Ａと他の方法Ｂとのそれぞれで、「Ｍ」本以上の辺を含む閉共通部分グラフＣＣＳＧの集合Ｃを検出する実験を試みたので、その実験内容及び実験結果について説明する。
【０１１８】
ここでは、以下の条件を全て満足するような閉共通部分グラフＣＣＳＧの集合Ｃを検出することとする。
・２種以上の共通のアイテムが、集合Ｃのどの閉共通部分グラフＣＣＳＧにも含まれる。（各閉共通部分グラフＣＣＳＧの共通アイテム集合の積集合には２種以上のアイテムが含まれる）。
・集合Ｃに含まれるすべての閉共通部分グラフＣＣＳＧは、集合Ｃに含まれる他のどの閉共通部分グラフＣＣＳＧとも頂点を共通しない。
【０１１９】
また、実験に用いたマシン環境を以下に示すとおりである。
・ＣＰＵ：３．２ＧＢ  ＡＭＤ  Ｏｐｔｅｒｏｎ（登録商標）
・メモリ容量：１ＧＢ
・ＯＳ：Ｌｉｎｕｘ（ｋｅｒｎｅｌ２．６）
【０１２０】
（方法Ａ）
フェーズＡ１：図９乃至図１１に示す処理を行って、閉共通部分グラフＣＣＳＧを特定する。
フェーズＡ２：フェーズＡ１で特定した閉共通部分グラフＣＣＳＧのうちから「Ｍ」本以上の辺を含む閉共通部分グラフＣＣＳＧを特定する。
フェーズＡ３：フェーズＡ２で特定した閉共通部分グラフＣＣＳＧの共通アイテム集合に基づき集合Ｃを検出する。
【０１２１】
（方法Ｂ）
フェーズＢ１：アプリオリ法により２種以上のアイテムを含む頻出アイテム集合を検出する。ここで、頻出アイテム集合とは、頻出アイテム集合を含むアイテム集合に関連づけられた頂点が「Ｆ」個以上存在するアイテム集合である。なお、本実験では、頻出アイテム集合を検出するためにフリーのデータマイニングソフト「Ｗｅｋａ」を用いた。
フェーズＢ２：頻出アイテム集合ごとに、該頻出アイテム集合を含むアイテム集合に関連づけられた頂点からなる、辺が「Ｍ」本以上の閉共通部分グラフＣＣＳＧを特定することにより、集合Ｃを検出する。
【０１２２】
なお、方法Ｂにおいて「Ｆ」の値を「２」に設定し且つ「Ｍ」の値を「１」に設定した場合、方法ＡのフェーズＡ１が行われた場合に特定される閉共通部分グラフＣＣＳＧと同じ閉共通部分グラフＣＣＳＧが特定される。
【０１２３】
まず最初の実験では、「Ｆ」の値を「２」に設定し且つ「Ｍ」の値を「１０」に設定した上で、実験対象グラフから集合Ｃを検出した。なお、実験対象グラフとしては、頂点が「文献」に対応し、辺が「文献間の引用関係」に対応し、かつ、頂点に関連づけられたアイテムが「文献の著者」に対応するようなグラフを用いた。なお、著者の総数は１６６３８人である。また、実験対象グラフの頂点、辺の数は以下のとおりである。
・頂点の数：２２１７８個
・辺の数：１１２３０４本
【０１２４】
方法Ａでは、７．９秒で集合Ｃの検出が完了した。一方、方法Ｂでは、実験開始から１０１秒経過したところでメモリ不足となり、その結果、処理が強制的に停止された。これは、フェーズＢ１において頻出アイテム集合を検出するために大量の頻出アイテム集合候補が生成されるためであると考えられる。
【０１２５】
また次の実験では、「Ｆ」の値を「４」に設定し且つ「Ｍ」の値を「７」に設定した上で、実験対象グラフから集合Ｃを検出した。なお、実験対象グラフとしては、頂点が「遺伝子」に対応し、辺が「遺伝子間の相互作用関係」に対応し、かつ、頂点に関連づけられたアイテムが「遺伝子の発現を変化させる要因」に対応するようなグラフを用いた。なお、上記要因の総数は１７３種である。また、実験対象グラフの頂点、辺の数は以下のとおりである。
・頂点の数：６１５２個
・辺の数：３３１８本
【０１２６】
方法Ａでは、３５．９秒で集合Ｃの検出が完了した。一方、方法Ｂでは、実験開始から１７３０２秒経過したところでメモリ不足となり、その結果、処理が強制的に停止された。先述の実験と同様、これは、フェーズＢ１において頻出アイテム集合を検出するために大量の頻出アイテム集合候補が生成されるためであると考えられる。
【０１２７】
上記の実験結果より、本実施形態に係る方法Ａでは、方法Ｂに比べて、処理に必要なメモリの量が軽減され、処理時間も短縮される。
【図１】
0005605571.tif 000002
【図２】
0005605571.tif 000003
【図３】
0005605571.tif 000004
【図４】
0005605571.tif 000005
【図５】
0005605571.tif 000006
【図６】
0005605571.tif 000007
【図７】
0005605571.tif 000008
【図８】
0005605571.tif 000009
【図９】
0005605571.tif 000010
【図１０】
0005605571.tif 000011
【図１１】
0005605571.tif 000012