(57)【要約】【課題】グラフ構造から特定の部分グラフ構造の出現頻度を算出する際の算出コストを低減する。【解決手段】情報処理装置１は、出現頻度を算出する対象となる部分グラフの対称性を示す自己同型写像の数を算出し、検索対象となる検索対象グラフの各頂点を起点として前記部分グラフとの照合処理を行って、前記検索対象グラフにおける前記部分グラフの出現箇所を抽出し、抽出した前記出現箇所の数と算出した前記自己同型写像の数とに基づいて、前記部分グラフの前記出現頻度を算出する。【選択図】図５
2017201480.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
出現頻度を算出する対象となる部分グラフの対称性を示す自己同型写像の数を算出し、
検索対象となる検索対象グラフの各頂点を起点として前記部分グラフとの照合処理を行って、前記検索対象グラフにおける前記部分グラフの出現箇所を抽出し、
抽出した前記出現箇所の数と、算出した前記自己同型写像の数とに基づいて、前記部分グラフの前記出現頻度を算出する
処理を実行させることを特徴とする部分グラフ出現頻度算出プログラム。
【請求項２】
前記出現頻度を算出する処理は、前記出現箇所の数を前記自己同型写像の数で除算することで、前記部分グラフの前記出現頻度を算出する
ことを特徴とする請求項１に記載の部分グラフ出現頻度算出プログラム。
【請求項３】
前記抽出する処理は、前記出現頻度が閾値以上であるか否かを判定する場合に、前記部分グラフの出現箇所を抽出する際、抽出した前記出現箇所の数が、前記閾値と前記自己同型写像の数とから得られる、重複を含む出現箇所の数以上であるか否かを判定し、前記抽出した前記出現箇所の数が前記重複を含む出現箇所の数以上であると判定した場合には、前記抽出する処理を終了する
ことを特徴とする請求項１または請求項２に記載の部分グラフ出現頻度算出プログラム。
【請求項４】
出現頻度を算出する対象となる部分グラフの対称性を示す自己同型写像の数を算出する第１の算出部と、
検索対象となる検索対象グラフの各頂点を起点として前記部分グラフとの照合処理を行って、前記検索対象グラフにおける前記部分グラフの出現箇所を抽出する抽出部と、
前記抽出部によって抽出された前記出現箇所の数と、前記第１の算出部によって算出された前記自己同型写像の数とに基づいて、前記部分グラフの前記出現頻度を算出する第２の算出部と、
を有することを特徴とする部分グラフ出現頻度算出装置。
【請求項５】
コンピュータが、
出現頻度を算出する対象となる部分グラフの対称性を示す自己同型写像の数を算出し、
検索対象となる検索対象グラフの各頂点を起点として前記部分グラフとの照合処理を行って、前記検索対象グラフにおける前記部分グラフの出現箇所を抽出し、
抽出した前記出現箇所の数と、算出した前記自己同型写像の数とに基づいて、前記部分グラフの前記出現頻度を算出する
各処理を実行することを特徴とする部分グラフ出現頻度算出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部分グラフ出現頻度算出プログラムなどに関する。
【背景技術】
【０００２】
分子構造、係り受け解析済テキスト、ウェブグラフなど、グラフ構造を有するデータの解析において、特定の部分グラフ構造の出現頻度を考慮して解析する要望がある。
【０００３】
例えば、グラフ構造を有するデータから頻度の高い部分構造を抽出する第１の方法が開示されている（例えば、特許文献１参照）。かかる方法では、グラフデータベースから保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、その連結グラフの出現回数を算出する。特にリスト（列）を対象とする抽出方法としては、グラフデータベースから保持するグラフにおいて、親ノードを持たないノードから子ノードを持たないノードまでの全ての経路をノード列として列挙する。列挙した全てのノード列を対象として、同型の部分構造、つまりノードのラベルを順に並べてできるラベル列が一致する部分ノード列の出現回数と出現箇所を特定する。
【０００４】
また、グラフ構造を有するデータに特定の部分グラフ構造が出現するか否かを区別する第２の方法が知られている（例えば、非特許文献１〜３参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１３−３６６９号公報
【非特許文献】
【０００６】
【非特許文献１】A.Inokuchi，T.Washio  and  H.Motoda，“An  Apriori-based  algorithm  for  mining  frequent  substructures  from  graph  data”，In  Proc.  of  the  4th  PKDD，pp.13−23，2000．
【非特許文献２】X.Yan  and  J.Han，“gSpan:Graph-based  substructure  pattern  mining”，In  Proc.  of  ICDM，pp.721−724，2002．
【非特許文献３】D.J.Cook  and  L.B.Holder，“Substructure  discovery  using  minimum  description  length  and  background  knowledge”，Journal  of  Artificial  Intelligence  Research．vol.  1，pp.231−255，1994．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の技術では、グラフ構造から特定の部分グラフ構造の出現頻度を算出する際の算出コストがかかるという問題がある。
【０００８】
例えば、第１の方法においてリスト（列）を対象とする抽出方法では、データの全ての経路をノード列として列挙し、列挙した全てのノード列を対象として部分ノード列の出現頻度を特定するが、列挙したノード列の一部が同一の箇所を示す場合があるため、重複を除いた正確な出現頻度の算出には特許文献１［００７４］〜［００７８］に記載されているような追加の処理を要する。また、この方法はリスト（列）に限らないツリーおよび一般のグラフを対象とする場合には適用することができない。なお、ツリーおよび一般のグラフを対象とする場合においても、出現した部分構造を列挙した後に正確な出現頻度を算出する方法を用いる場合には、同様に重複を除くための追加の処理を要するため、算出コストがかかる。
【０００９】
また、第２の方法では、データに特定の部分グラフ構造が出現するか否かを区別するが、そもそもデータから特定の部分グラフ構造の出現頻度を算出する技術ではない。
【００１０】
本発明は、１つの側面では、グラフ構造から特定の部分グラフ構造の出現頻度を算出する際の算出コストを低減することを目的とする。
【課題を解決するための手段】
【００１１】
１つの態様では、部分グラフ出現頻度算出プログラムは、コンピュータに、出現頻度を算出する対象となる部分グラフの対称性を示す自己同型写像の数を算出し、検索対象となる検索対象グラフの各頂点を起点として前記部分グラフとの照合処理を行って、前記検索対象グラフにおける前記部分グラフの出現箇所を抽出し、抽出した前記出現箇所と算出した前記自己同型写像の数とに基づいて、前記部分グラフの前記出現頻度を算出する、処理を実行させる。
【発明の効果】
【００１２】
１実施態様によれば、グラフ構造から特定の部分グラフ構造の出現頻度を算出する際の算出コストを低減することができる。
【図面の簡単な説明】
【００１３】
【図１】図１は、実施例１に係る情報処理装置の構成を示す機能ブロック図である。
【図２Ａ】図２Ａは、出現箇所抽出処理の流れの一例を示す図（１）である。
【図２Ｂ】図２Ｂは、出現箇所抽出処理の流れの一例を示す図（２）である。
【図２Ｃ】図２Ｃは、出現箇所抽出処理の流れの一例を示す図（３）である。
【図２Ｄ】図２Ｄは、出現箇所抽出処理の流れの一例を示す図（４）である。
【図２Ｅ】図２Ｅは、出現箇所抽出処理の流れの一例を示す図（５）である。
【図３Ａ】図３Ａは、重複判定処理の流れの一例を示す図（１）である。
【図３Ｂ】図３Ｂは、重複判定処理の流れの一例を示す図（２）である。
【図３Ｃ】図３Ｃは、重複判定処理の流れの一例を示す図（３）である。
【図３Ｄ】図３Ｄは、重複判定処理の流れの一例を示す図（４）である。
【図３Ｅ】図３Ｅは、重複判定処理の流れの一例を示す図（５）である。
【図３Ｆ】図３Ｆは、重複判定処理の流れの一例を示す図（６）である。
【図３Ｇ】図３Ｇは、重複判定処理の流れの一例を示す図（７）である。
【図３Ｈ】図３Ｈは、重複判定処理の流れの一例を示す図（８）である。
【図３Ｉ】図３Ｉは、重複判定処理の流れの一例を示す図（９）である。
【図３Ｊ】図３Ｊは、重複判定処理の流れの一例を示す図（１０）である。
【図３Ｋ】図３Ｋは、重複判定処理の流れの一例を示す図（１１）である。
【図３Ｌ】図３Ｌは、重複判定処理の流れの一例を示す図（１２）である。
【図３Ｍ】図３Ｍは、重複判定処理の流れの一例を示す図（１３）である。
【図３Ｎ】図３Ｎは、重複判定処理の流れの一例を示す図（１４）である。
【図３Ｏ】図３Ｏは、重複判定処理の流れの一例を示す図（１５）である。
【図４】図４は、実施例１に係る部分グラフ出現頻度算出処理のフローチャートを示す図である。
【図５】図５は、実施例２に係る情報処理装置の構成を示す機能ブロック図である。
【図６Ａ】図６Ａは、部分グラフ同型写像数算出処理の流れの一例を示す図（１）である。
【図６Ｂ】図６Ｂは、部分グラフ同型写像数算出処理の流れの一例を示す図（２）である。
【図７】図７は、実施例２に係る部分グラフ出現頻度算出処理のフローチャートを示す図である。
【図８】図８は、実施例３に係る部分グラフ出現頻度算出処理のフローチャートを示す図である。
【図９】図９は、部分グラフ出現頻度算出プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１４】
以下に、本願の開示する部分グラフ出現頻度算出プログラム、部分グラフ出現頻度算出装置および部分グラフ出現頻度算出方法の実施例を図面に基づいて詳細に説明する。なお、実施例では、部分グラフ出現頻度算出装置を情報処理装置として説明する。本発明は、実施例により限定されるものではない。
【実施例１】
【００１５】
［実施例１に係る情報処理装置の構成］
図１は、実施例１に係る情報処理装置の構成を示す機能ブロック図である。図１に示す情報処理装置１は、検索対象のグラフ構造のグラフから特定の部分グラフの出現頻度を算出する際に、検索対象のグラフの各頂点を起点として特定の部分グラフとマッチング（照合処理）を行い、特定の部分グラフの出現箇所を抽出する。情報処理装置１は、抽出した部分グラフの出現箇所全てを使った組み合わせについて、それぞれ同一箇所を指しているか否かを判定し、同一箇所を指している場合には、どちらか一方を削除する。そして、情報処理装置１は、重複していない部分グラフの出現箇所の数を出現頻度として出力する。
【００１６】
情報処理装置１は、制御部１０と、記憶部２０とを有する。
【００１７】
制御部１０は、ＣＰＵ（Central  Processing  Unit）などの電子回路に対応する。そして、制御部１０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部１０は、入力部１１と、出現箇所抽出部１２と、重複判定部１３と、重複削除部１４と、出現頻度出力部１５とを有する。なお、出現箇所抽出部１２は、抽出部の一例である。
【００１８】
記憶部２０は、例えば、ＲＡＭ、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。記憶部２０は、部分グラフ情報２１と、検索対象グラフ情報２２とを有する。部分グラフ情報２１は、出現頻度を算出する対象となる特定の部分グラフを示す情報である。検索対象グラフ情報２２は、検索対象となるグラフを示す情報である。なお、出現頻度を算出する対象となる特定の部分グラフは、以降、「算出対象の部分グラフ」という。
【００１９】
入力部１１は、算出対象の部分グラフおよび検索対象のグラフを入力し、入力したそれぞれのグラフを記憶部２０に格納する。
【００２０】
出現箇所抽出部１２は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチング（照合処理）を行い、マッチする部分グラフの出現箇所を抽出する。出現箇所抽出部１２は、抽出した部分グラフの出現箇所の情報を記憶部２０に格納する。なお、出現箇所抽出部１２の処理の詳細は、後述する。
【００２１】
重複判定部１３は、出現箇所抽出部１２によって抽出された全ての部分グラフの出現箇所について、他の部分グラフの出現箇所と重複しているか否かを判定する。例えば、重複判定部１３は、記憶部２０に記憶された部分グラフの出現箇所の情報を用いて、抽出された全ての部分グラフの出現箇所について、総当たりとなるように、２つの部分グラフの出現箇所の組み合わせを生成する。そして、重複判定部１３は、生成したそれぞれの組み合わせに対する重複判定を行う。すなわち、重複判定部１３は、抽出された全ての部分グラフの出現箇所について、同一の出現箇所を指しているか否かを判定する。なお、重複判定部１３の処理の詳細は、後述する。
【００２２】
重複削除部１４は、重複している場合には、重複しているいずれかを削除する。すなわち、重複削除部１４は、２つの部分グラフが同一の出現箇所を指している場合には、どちらか一方の部分グラフを削除する。
【００２３】
出現頻度出力部１５は、重複削除部１４によって削除された後、残った重複のない部分グラフの出現箇所の数を出現頻度として出力する。
【００２４】
［出現箇所抽出処理の流れの一例］
図２Ａ〜図２Ｅは、出現箇所抽出処理の流れの一例を示す図である。なお、図２Ａ〜図２Ｅでは、算出対象の部分グラフａ０は、ラベルがＢである頂点が、ラベルがＡである３個の頂点とそれぞれ隣接する接続関係を有するグラフである。検索対象のグラフは、符号ｂ０で表わされ、構成するラベルをＡ，Ｂ，Ｃとするグラフである。頂点は、ノードと同義である。なお、算出対象の部分グラフａ０は、各頂点の箇所（位置）を区別するために左上に数字を添える。検索対象のグラフｂ０は、各頂点の箇所（位置）を区別するために左上に数字を添える。
【００２５】
図２Ａに示すように、入力部１１は、算出対象の部分グラフａ０および検索対象のグラフｂ０を入力する。そして、出現箇所抽出部１２は、検索対象のグラフｂ０の各頂点を起点として部分グラフａ０とマッチングを行う。例えば、出現箇所抽出部１２は、検索対象のグラフｂ０について、部分グラフａ０におけるラベルＡ（添え字１）の頂点とマッチする頂点の位置を抽出する。ここでは、検索対象のグラフｂ０について、添え字１、２、４、５、６がそれぞれ示すラベルＡの頂点の位置が抽出される。
【００２６】
図２Ｂに示すように、出現箇所抽出部１２は、部分グラフａ０の接続関係に従い、検索対象のグラフｂ０で抽出されたラベルＡに隣接する頂点を検索する。例えば、出現箇所抽出部１２は、部分グラフａ０におけるラベルＡ（添え字１）の頂点とラベルＢ（添え字２）の頂点との接続関係に従い、検索対象のグラフｂ０においてラベルＡ（添え字１）に隣接するラベルＢの頂点を検索する。すなわち、出現箇所抽出部１２は、検索対象のグラフｂ０について、部分グラフａ０におけるラベルＡ（添え字１）に隣接するラベルＢの頂点にマッチする頂点を検索する。ここでは、添え字３が示すラベルＢの頂点が検索される。出現箇所抽出部１２は、検索対象のグラフｂ０において添え字２、４、５、６が示すそれぞれのラベルＡについても、同様に、隣接するラベルＢの頂点を検索する。
【００２７】
図２Ｃに示すように、出現箇所抽出部１２は、部分グラフａ０の接続関係に従い、検索対象のグラフｂ０で抽出されたラベルＢに隣接する頂点を検索する。例えば、出現箇所抽出部１２は、部分グラフａ０における添え字１、２、３が示すラベルＡ、Ｂ、Ａの頂点の接続関係に従い、検索対象のグラフｂ０においてラベルＢ（添え字３）に隣接するラベルＡの頂点を検索する。すなわち、出現箇所抽出部１２は、検索対象のグラフｂ０について、部分グラフａ０におけるラベルＢ（添え字２）に隣接するラベルＡの頂点にマッチする頂点を検索する。ここでは、添え字２が示すラベルＡの頂点が検索される。添え字４が示すラベルＡの頂点が検索される。出現箇所抽出部１２は、検索対象のグラフｂ０において添え字２、４、５、６が示すそれぞれのラベルＡから接続されるそれぞれのラベルＢについても、同様に、隣接するラベルＡの頂点を検索する。
【００２８】
図２Ｄに示すように、出現箇所抽出部１２は、部分グラフａ０の接続関係に従い、検索対象のグラフｂ０で抽出されたラベルＢに隣接する頂点を検索する。例えば、出現箇所抽出部１２は、部分グラフａ０における添え字１、２、３、４が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係に従い、検索対象のグラフｂ０においてラベルＢ（添え字３）に隣接するラベルＡの頂点を検索する。すなわち、出現箇所抽出部１２は、検索対象のグラフｂ０について、部分グラフａ０におけるラベルＢ（添え字２）に隣接するラベルＡの頂点にマッチする頂点を検索する。ここでは、添え字４が示すラベルＡの頂点が検索される。添え字５が示すラベルＡの頂点が検索される。出現箇所抽出部１２は、検索対象のグラフｂ０において添え字２、４、５、６が示すそれぞれのラベルＡから接続されるそれぞれのラベルＢについても、同様に、隣接するラベルＡの頂点を検索する。なお、出現箇所抽出部１２は、検索対象のグラフｂ０において添え字６が示すラベルＡから接続されるラベルＢ（添え字７）について、隣接する頂点にラベルＡの対象が無く、該当する頂点を検索できない。
【００２９】
図２Ｅに示すように、出現箇所抽出部１２は、部分グラフａ０の接続関係に従い、検索対象のグラフｂ０の中で算出対象の部分グラフａ０の接続関係とマッチした部分グラフの出現箇所を抽出する。ここでは、出現箇所抽出部１２は、２４個の出現箇所を抽出する。
【００３０】
［重複判定処理の流れの一例］
図３Ａ〜図３Ｏは、重複判定処理の流れの一例を示す図である。なお、図３Ａ〜図３Ｏでは、重複判定部１３が、図２Ａ〜図２Ｅで示した出現箇所抽出処理によって抽出された出現箇所の重複判定を行う。図３Ａでは、検索対象のグラフｂ０の中で算出対象の部分グラフａ０の接続関係とマッチした出現箇所が抽出されている。なお、図３Ａに示された出現箇所は、図２Ｅで示した出現箇所と同じである。
【００３１】
図３Ａ〜図３Ｈでは、重複判定部１３は、抽出された全ての出現箇所の部分グラフのうち部分グラフｃ１について、他の部分グラフとの組み合わせに対する重複判定を行う。
【００３２】
図３Ａに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ２との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ１は、添え字１、２、３、４が示すラベルＡ、Ａ、Ｂ、Ａの頂点の接続関係である。部分グラフｃ２は、添え字１、２、３、５が示すラベルＡ、Ａ、Ｂ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ２と重複せず、すなわち異なる。
【００３３】
図３Ｂに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ３との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ１は、添え字１、２、３、４が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。部分グラフｃ３は、添え字１、２、３、４が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ３と重複し、すなわち同一である。そこで、重複削除部１４は、部分グラフｃ３を削除する。なお、重複削除部１４は、どちらか一方の部分グラフを削除すれば良く、部分グラフｃ１を削除しても良い。
【００３４】
図３Ｃに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ４との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ４は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ４と重複せず、すなわち異なる。
【００３５】
図３Ｄに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ５との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ５は、添え字１、３、２、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ５と重複せず、すなわち異なる。
【００３６】
図３Ｅに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ６との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ６は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ６と重複せず、すなわち異なる。
【００３７】
図３Ｆに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ７との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ７は、添え字１、３、２、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ７と重複せず、すなわち異なる。
【００３８】
図３Ｇに示すように、重複判定部１３は、部分グラフｃ１について、他の部分グラフｃ８との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ８は、添え字１、２、３、４が示すラベルＡ、Ａ、Ｂ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ８と重複し、すなわち同一である。そこで、重複削除部１４は、部分グラフｃ８を削除する。なお、重複削除部１４は、どちらか一方の部分グラフを削除すれば良く、部分グラフｃ１を削除しても良い。
【００３９】
このようにして、重複判定部１３は、抽出された全ての出現箇所の部分グラフのうち部分グラフｃ１について、順番に、他の部分グラフとの組み合わせに対する重複判定を行う。
【００４０】
そして、図３Ｈに示すように、重複判定部１３は、部分グラフｃ１について、最後に、他の部分グラフｃ２４との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ２４は、添え字１、３、２、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ１は、部分グラフｃ２４と重複せず、すなわち異なる。
【００４１】
図３Ｉ〜図３Ｋでは、重複判定部１３は、抽出された全ての出現箇所の部分グラフのうち部分グラフｃ２について、他の部分グラフとの組み合わせに対する重複判定を行う。
【００４２】
図３Ｉに示すように、重複判定部１３は、部分グラフｃ２について、他の部分グラフｃ４との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ２は、添え字１、３、２、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。部分グラフｃ４は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ２は、部分グラフｃ４と重複せず、すなわち異なる。
【００４３】
図３Ｊに示すように、重複判定部１３は、部分グラフｃ２について、他の部分グラフｃ５との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ５は、添え字１、３、２、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ２は、部分グラフｃ５と重複し、すなわち同一である。そこで、重複削除部１４は、部分グラフｃ５を削除する。なお、重複削除部１４は、どちらか一方の部分グラフを削除すれば良く、部分グラフｃ２を削除しても良い。
【００４４】
図３Ｋに示すように、重複判定部１３は、部分グラフｃ２について、他の部分グラフｃ６との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ６は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ２は、部分グラフｃ６と重複せず、すなわち異なる。
【００４５】
図３Ｌ〜図３Ｍでは、重複判定部１３は、抽出された全ての出現箇所の部分グラフのうち部分グラフｃ４について、他の部分グラフとの組み合わせに対する重複判定を行う。
【００４６】
図３Ｌに示すように、重複判定部１３は、部分グラフｃ４について、他の部分グラフｃ６との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ４は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。部分グラフｃ６は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ４は、部分グラフｃ６と重複し、すなわち同一である。そこで、重複削除部１４は、部分グラフｃ６を削除する。なお、重複削除部１４は、どちらか一方の部分グラフを削除すれば良く、部分グラフｃ４を削除しても良い。
【００４７】
図３Ｍに示すように、重複判定部１３は、部分グラフｃ４について、最後に、他の部分グラフｃ２３との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ２３は、添え字１、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ４は、部分グラフｃ２３と重複し、すなわち同一である。そこで、重複削除部１４は、部分グラフｃ２３を削除する。なお、重複削除部１４は、どちらか一方の部分グラフを削除すれば良く、部分グラフｃ４を削除しても良い。
【００４８】
図３Ｎでは、重複判定部１３は、抽出された全ての出現箇所の部分グラフのうち部分グラフｃ９について、他の部分グラフとの組み合わせに対する重複判定を行う。
【００４９】
図３Ｎに示すように、重複判定部１３は、部分グラフｃ９について、最後に、他の部分グラフｃ２１との組み合わせに対する重複判定を行う。ここでは、部分グラフｃ９は、添え字２、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。部分グラフｃ２１は、添え字２、３、４、５が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係である。したがって、部分グラフｃ９は、部分グラフｃ２１と重複し、すなわち同一である。そこで、重複削除部１４は、部分グラフｃ２１を削除する。なお、重複削除部１４は、どちらか一方の部分グラフを削除すれば良く、部分グラフｃ９を削除しても良い。
【００５０】
図３Ｏに示すように、重複判定部１３によって重複判定された結果、重複のない部分グラフの出現箇所が残る。ここでは、部分グラフｃ１、ｃ２、ｃ４、ｃ９の部分グラフの出現箇所が残る。そして、出現頻度出力部１５は、残った部分グラフの出現箇所の数「４」を出現頻度として出力する。
【００５１】
［部分グラフ出現頻度算出処理のフローチャート］
図４は、実施例１に係る部分グラフ出現頻度算出処理のフローチャートを示す図である。
【００５２】
図４に示すように、入力部１１は、検索対象のグラフのデータセットおよび出現頻度を算出する対象となる部分グラフ（算出対象の部分グラフ）を入力する（ステップＳ１１）。
【００５３】
そして、出現箇所抽出部１２は、検索対象のグラフから算出対象の部分グラフとマッチする部分グラフの出現箇所を抽出する（ステップＳ１２）。例えば、出現箇所抽出部１２は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチングを行う。出現箇所抽出部１２は、検索対象のグラフの中でマッチする部分グラフの出現箇所を抽出する。そして、出現箇所抽出部１２は、抽出した部分グラフの出現箇所の情報を記憶部２０に格納する。
【００５４】
そして、重複判定部１３は、抽出した部分グラフの出現箇所の重複チェックを行い、重複削除部１４が重複する部分グラフを削除する（ステップＳ１３）。例えば、重複判定部１３は、抽出した部分グラフの出現箇所の情報を用いて、総当たりとなるように、２つの部分グラフの出現箇所の組み合わせに対する重複判定を行う。そして、重複削除部１４は、重複判定の結果、重複している場合には、組み合わせに含まれる２つの部分グラフのうちどちらか一方の部分グラフを削除する。
【００５５】
そして、出現頻度出力部１５は、重複を除いた部分グラフの出現箇所の数を出現頻度として出力する（ステップＳ１４）。
【００５６】
このようにして、情報処理装置１は、検索対象のグラフ構造のグラフから算出対象の部分グラフの出現頻度を算出する際に、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチする部分グラフの出現箇所を抽出する。そして、情報処理装置１は、抽出した部分グラフの出現箇所全てを使った組み合わせに対して、それぞれ同一箇所を指しているか否かの重複判定を行い、同一箇所を指している場合には、どちらか一方を削除する。かかる構成によれば、情報処理装置１は、検索対象のグラフ構造の全ての経路をノード列として抽出し、抽出した全てのノード列を対象として算出対象の部分グラフの出現頻度を特定する場合の処理を、リスト（列）に限らない一般の部分グラフ構造の抽出に拡張することが可能となる。
【実施例２】
【００５７】
ところで、実施例１では、情報処理装置１は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチする部分グラフの出現箇所を抽出したうえで、以下の処理を行う。情報処理装置１は、抽出した部分グラフの出現箇所全てを使った組み合わせに対して、それぞれ同一箇所を指しているか否かの重複判定を行い、重複していない部分グラフの出現箇所の数を出現頻度として求める。しかしながら、情報処理装置１は、これに限定されず、算出対象の部分グラフの対称性を示す自己同型写像の数を算出しても良い。ここでいう「自己同型写像」とは、グラフの頂点の添え字の付け替えで、付け替える前の接続関係を保つ写像のことをいう。そして、情報処理装置１は、抽出した部分グラフの出現箇所の数と、算出した自己同型写像の数とに基づいて、重複していない算出対象の部分グラフの出現箇所の数を出現頻度として算出する。
【００５８】
そこで、実施例２では、情報処理装置１は、算出対象の部分グラフの自己同型写像の数を算出し、抽出した部分グラフの出現箇所の数と、算出した自己同型写像の数とに基づいて、重複していない算出対象の部分グラフの出現頻度を算出する場合を説明する。
【００５９】
［実施例２に係る情報処理装置の構成］
図５は、実施例２に係る情報処理装置の構成を示す機能ブロック図である。なお、図１に示す情報処理装置１と同一の構成については同一符号を付すことで、その重複する構成および動作の説明については省略する。実施例１と実施例２とが異なるところは、重複判定部１３および重複削除部１４を削除し、部分グラフ同型写像数算出部３１および出現頻度算出部３２を追加した点である。なお、部分グラフ同型写像数算出部３１は、第１の算出部の一例である。出現頻度算出部３２は、第２の算出部の一例である。
【００６０】
部分グラフ同型写像数算出部３１は、出現頻度を算出する対象となる部分グラフの対象性を示す自己同型写像の数を算出する。例えば、部分グラフ同型写像数算出部３１は、算出対象の部分グラフの各頂点を起点として自己の部分グラフを検索対象のグラフとしてマッチングを行い、算出対象の部分グラフの自己同型写像の数を算出する。なお、部分グラフ同型写像数算出部３１の処理の詳細は、後述する。
【００６１】
ここで、算出対象の部分グラフの自己同型写像の数を算出する理由を説明する。まず、出現箇所抽出部１２は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチする部分グラフの出現箇所を抽出する。かかる検索対象のグラフにおける算出対象の部分グラフの各出現箇所は、算出対象の部分グラフの自己同型写像の数だけ重複して抽出される。なぜなら、算出対象の部分グラフの各頂点と検索対象のグラフとの各頂点の組み合わせの中で、算出対象の部分グラフと検索対象のグラフとのラベルおよび接続関係がマッチする組み合わせが全て抽出されるからである。したがって、頂点の添え字の付け替えで同一箇所となる組み合わせの数は、算出対象の部分グラフの自己同型写像の数だけ重複して抽出されることになる。そこで、部分グラフ同型写像数算出部３１は、算出対象の部分グラフの自己同型写像の数を予め算出するのである。
【００６２】
出現頻度算出部３２は、出現箇所抽出部１２によって抽出された検索対象のグラフにおける算出対象の部分グラフの出現箇所の数と、算出対象の部分グラフの自己同型写像の数とに基づいて、重複していない算出対象の部分グラフの出現箇所の数を出現頻度として算出する。例えば、出現頻度算出部３２は、検索対象のグラフにおける算出対象の部分グラフの出現箇所の数を、算出対象の部分グラフの自己同型写像の数で除算することで、検索対象のグラフに算出対象の部分グラフが出現する出現頻度を算出する。これにより、出現頻度算出部３２は、算出対象の部分グラフの自己同型写像の数を用いることで、出現箇所抽出部１２によって抽出された部分グラフの出現箇所に対する重複判定を行わないで、該当する出現頻度を算出する。この結果、出現頻度算出部３２は、検索対象のグラフにおける算出対象の部分グラフの出現頻度の算出コストを低減できる。
【００６３】
［部分グラフ同型写像数算出処理の流れの一例］
図６Ａ〜図６Ｂは、部分グラフ同型写像数算出処理の流れの一例を示す図である。なお、図６Ａでは、算出対象の部分グラフａ０は、ラベルがＢである頂点が、ラベルがＡである３個の頂点とそれぞれ隣接する接続関係を示すグラフである。検索対象のグラフは、符号ｅ０で表わされ、算出対象の部分グラフａ０と同じ接続関係を示すグラフである。頂点は、ノードと同義である。なお、算出対象の部分グラフａ０は、各頂点の箇所（位置）を区別するために左上に数字を添える。検索対象のグラフｅ０は、各頂点の箇所（位置）を区別するために左上に数字を添える。
【００６４】
図６Ａに示すように、部分グラフ同型写像数算出部３１は、検索対象のグラフｅ０の各頂点を起点として部分グラフａ０とマッチングを行う。例えば、部分グラフ同型写像数算出部３１は、検索対象のグラフｅ０について、部分グラフａ０におけるラベルＡ（添え字１）の頂点とマッチする頂点の位置を抽出する。ここでは、検索対象のグラフｅ０について、添え字１、２、４がそれぞれ示すラベルＡの頂点の位置が抽出される。
【００６５】
次に、部分グラフ同型写像数算出部３１は、部分グラフａ０の接続関係に従い、検索対象のグラフｅ０で抽出されたラベルＡに隣接する頂点を検索する。例えば、部分グラフ同型写像数算出部３１は、部分グラフａ０におけるラベルＡ（添え字１）の頂点とラベルＢ（添え字３）の頂点との接続関係に従い、検索対象のグラフｅ０においてラベルＡ（添え字１）に隣接するラベルＢの頂点を検索する。すなわち、部分グラフ同型写像数算出部３１は、検索対象のグラフｅ０について、部分グラフａ０におけるラベルＡ（添え字１）に隣接するラベルＢの頂点にマッチする頂点を検索する。ここでは、添え字３が示すラベルＢの頂点が検索される。部分グラフ同型写像数算出部３１は、検索対象のグラフｅ０において添え字２、４が示すそれぞれのラベルＡについても、同様に、隣接するラベルＢの頂点を検索する。
【００６６】
次に、部分グラフ同型写像数算出部３１は、部分グラフａ０の接続関係に従い、検索対象のグラフｅ０で抽出されたラベルＢに隣接する頂点を検索する。例えば、部分グラフ同型写像数算出部３１は、部分グラフａ０における添え字１、３、２が示すラベルＡ、Ｂ、Ａの頂点の接続関係に従い、検索対象のグラフｅ０においてラベルＢ（添え字３）に隣接するラベルＡの頂点を検索する。すなわち、部分グラフ同型写像数算出部２１は、検索対象のグラフｅ０について、部分グラフａ０におけるラベルＢ（添え字３）に隣接するラベルＡの頂点にマッチする頂点を検索する。ここでは、添え字２が示すラベルＡの頂点が検索される。添え字４が示すラベルＡの頂点が検索される。部分グラフ同型写像数算出部３１は、検索対象のグラフｅ０において添え字２、４が示すそれぞれのラベルＡから接続されるそれぞれのラベルＢについても、同様に、隣接するラベルＡの頂点を検索する。
【００６７】
次に、部分グラフ同型写像数算出部３１は、部分グラフａ０の接続関係に従い、検索対象のグラフｅ０で抽出されたラベルＢに隣接する頂点を検索する。例えば、部分グラフ同型写像数算出部３１は、部分グラフａ０における添え字１、３、２、４が示すラベルＡ、Ｂ、Ａ、Ａの頂点の接続関係に従い、検索対象のグラフｅ０においてラベルＢ（添え字３）に隣接するラベルＡの頂点を検索する。すなわち、部分グラフ同型写像数算出部３１は、検索対象のグラフｅ０について、部分グラフａ０におけるラベルＢ（添え字３）に隣接するラベルＡの頂点にマッチする頂点を検索する。ここでは、添え字４が示すラベルＡの頂点が検索される。添え字２が示すラベルＡの頂点が検索される。出現箇所抽出部１２は、検索対象のグラフｅ０において添え字２、４が示すそれぞれのラベルＡから接続されるそれぞれのラベルＢについても、同様に、隣接するラベルＡの頂点を検索する。
【００６８】
図６Ｂに示すように、部分グラフ同型写像数算出部３１は、部分グラフａ０の接続関係に従い、検索対象のグラフｅ０の中で算出対象の部分グラフａ０の接続関係とマッチした部分グラフの出現箇所を抽出する。そして、部分グラフ同型写像数算出部３１は、抽出された部分グラフの出現箇所の数を自己同型写像数として算出する。ここでは、抽出された出現箇所の部分グラフが、算出対象の部分グラフａ０の自己同型写像である。そして、算出対象の部分グラフａ０の自己同型写像の数は、６個と算出される。
【００６９】
この結果、出現頻度算出部３２は、検索対象のグラフにおける算出対象の部分グラフの出現箇所の数を、算出対象の部分グラフの自己同型写像の数で除算することで、検索対象のグラフに算出対象の部分グラフが出現する出現頻度を算出する。ここでは、検索対象のグラフが図２Ａ〜図２Ｅで示したグラフであり、算出対象の部分グラフが図６Ａで示したグラフであるとする。すると、検索対象における部分グラフの出現箇所の数は、図２Ｅで示した２４個であり、算出対象の部分グラフの自己同型写像の数は、６であるので、出現頻度は、２４を６で除算して得られる「４」となる。
【００７０】
［部分グラフ出現頻度算出処理のフローチャート］
図７は、実施例２に係る部分グラフ出現頻度算出処理のフローチャートを示す図である。
【００７１】
図７に示すように、入力部１１は、検索対象のグラフのデータセットおよび出現頻度を算出する対象となる部分グラフ（算出対象の部分グラフ）を入力する（ステップＳ２１）。
【００７２】
そして、部分グラフ同型写像数算出部３１は、算出対象の部分グラフの自己同型写像の数ｎを計算する（ステップＳ２２）。例えば、部分グラフ同型写像数算出部３１は、算出対象の部分グラフの各頂点を起点として自己の部分グラフとマッチングを行い、算出対象の部分グラフの自己同型写像の数を算出する。そして、部分グラフ同型写像数算出部３１は、算出した算出対象の部分グラフの自己同型写像の数を記憶部２０に保持する。
【００７３】
そして、出現箇所抽出部１２は、検索対象のグラフから算出対象の部分グラフとマッチする部分グラフの出現箇所を抽出する（ステップＳ２３）。例えば、出現箇所抽出部１２は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチングを行う。出現箇所抽出部１２は、検索対象のグラフの中でマッチする部分グラフの出現箇所を抽出する。そして、出現箇所抽出部１２は、抽出した部分グラフの出現箇所の情報を記憶部２０に格納する。
【００７４】
そして、出現頻度算出部３２は、抽出した部分グラフの出現箇所の数を、算出対象の部分グラフの自己同型写像の数ｎで除算して得られた数を出現頻度として出力する（ステップＳ２４）。
【００７５】
このようにして、情報処理装置１は、出現頻度を算出する対象となる部分グラフの対称性を示す自己同型写像の数を算出する。情報処理装置１は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとの照合処理を行って、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出する。情報処理装置１は、抽出した出現箇所の数と算出した自己同型写像の数とに基づいて、算出対象の部分グラフの出現頻度を算出する。これにより、情報処理装置１は、検索対象のグラフにおける算出対象の部分グラフの出現頻度を計算する計算コストを低減することが可能となる。すなわち、情報処理装置１は、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出した際において、２つの部分グラフが同一箇所を指しているか否かを示す重複判定が不要となり、計算コストを低減することが可能となる。
【００７６】
また、情報処理装置１は、抽出した出現箇所の数を示す出現回数を、算出対象の部分グラフの自己同型写像の数で除算することで、検索対象のグラフにおける算出対象の部分グラフの出現頻度を算出する。これにより、情報処理装置１は、検索対象のグラフにおける算出対象の部分グラフの出現頻度を計算する計算コストを低減することが可能となる。
【００７７】
ここで、実施例１に係る部分グラフ出現頻度算出処理と、実施例２に係る部分グラフ出現頻度算出処理の計算時間を比較する。まず、実施例１に係る部分グラフ出現頻度算出処理は、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出し、抽出した部分グラフの出現箇所全ての組み合わせに対する重複判定を行い、出現頻度を求める。したがって、実施例１に係る部分グラフ出現頻度算出処理の計算時間Ｃａ１は、以下の式（１）で表わせる。なお、Ｃａ１のＴ１は、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出する抽出時間を示し、出現箇所抽出部１２によって抽出される際の時間である。Ｃａ１のＯ（部分グラフ数２）は、抽出した部分グラフの出現箇所全てを用いた全ての組み合わせを示し、Ｔ２は、各組み合わせに対する重複判定処理の時間である。Ｏ（部分グラフ数２）×Ｔ２は、重複判定部１３によって実行される際の時間である。なお、重複削除部１４による削除処理の時間は、省略する。
Ｃａ１＝Ｔ１＋Ｏ（部分グラフ数２）×Ｔ２・・・式（１）
【００７８】
一方、実施例２に係る部分グラフ出現頻度算出処理は、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出するとともに、算出対象の部分グラフの自己同型写像の数を算出し、抽出した部分グラフの出現箇所の数と、算出した自己同型写像の数とに基づいて、出現頻度を求める。したがって、実施例２に係る部分グラフ出現頻度算出処理の計算時間Ｃａ２は、以下の式（２）で表わせる。なお、Ｃａ２のＴ１は、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出する抽出時間を示し、式（１）で示したＴ１と同じである。Ｃａ２のＴ３は、算出対象の部分グラフの自己同型写像の数の計算時間を示し、部分グラフ同型写像数算出部３１によって算出される際の時間である。なお、出現頻度算出部３２による算出時間は、省略する。
Ｃａ２＝Ｔ１＋Ｔ３・・・式（２）
【００７９】
式（１）で表わされるＣａ１の計算時間と式（２）で表わされるＣａ２の計算時間とが異なるところは、式（１）ではＯ（部分グラフ数２）×Ｔ２であるのに対し、式（２）ではＴ３であるところである。例えば、算出対象の部分グラフが図２Ａで示した符号ａ０であるとする。検索対象のグラフが図２Ａで示した符号ｂ０であるとする。すると、抽出した部分グラフの出現箇所が２４個となるのは、前述したとおりである。そうすると、Ｏ（部分グラフ数２）は、２４個の部分グラフの中から２個の部分グラフを取り出す組み合わせを示す２４Ｃ２（＝２７６）と算出される。そして、Ｔ２は、１個の組み合わせに対する重複判定処理の時間であるから、最大７回の枝探索を行う時間となる。よって、Ｏ（部分グラフ数２）×Ｔ２は、最大約２０００回の枝探索の時間と算出される。
【００８０】
一方、算出対象の部分グラフが符号ａ０であり、検索対象のグラフが符号ｂ０である場合に、Ｔ３は、算出対象の部分グラフの自己同型写像の数の計算時間であるから、最大３０回の枝探索の時間となる。
【００８１】
この結果、実施例２に係る部分グラフ出現頻度算出処理は、実施例１に係る部分グラフ出現頻度算出処理と比べて、約０．０２倍の算出時間となり、算出コストを低減できる。また、実施例１に係る部分グラフ出現頻度算出処理では、抽出した部分グラフの出現箇所の数が２乗に比例して計算量が増大する。これに対して、実施例２に係る部分グラフ出現頻度算出処理では、抽出した部分グラフの出現箇所の数に関わらず、算出対象の部分グラフの自己同型写像の数を計算する計算量で済む。つまり、実施例２に係る部分グラフ出現頻度算出処理は、グラフ構造から部分グラフ構造の出現頻度を算出する際の算出コストを低減することができる。
【実施例３】
【００８２】
ところで、実施例２では、情報処理装置１は、検索対象のグラフにおける算出対象の部分グラフの出現箇所を抽出したうえで、以下の処理を行う。すなわち、情報処理装置１は、算出対象の部分グラフの自己同型写像の数を算出し、抽出した部分グラフの出現箇所の数と、算出対象の部分グラフの自己同型写像の数とに基づいて、重複していない算出対象の部分グラフの出現箇所の数を出現頻度として算出する。しかしながら、情報処理装置１は、これに限定されず、検索対象のグラフにおける算出対象の部分グラフの出現頻度があらかじめ定められた閾値以上であるか否かを判定しても良い。
【００８３】
そこで、実施例３では、情報処理装置１は、検索対象のグラフにおける算出対象の部分グラフの出現箇所の出現頻度があらかじめ定められた閾値以上であるか否かを判定する場合を説明する。
【００８４】
実施例３を実現するために、出現箇所抽出部１２は、以下の処理を行えば良い。出現箇所抽出部１２は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチングを行い、マッチする部分グラフの出現箇所を抽出する。このとき、出現箇所抽出部１２は、現に抽出した部分グラフの出現箇所の数が、閾値と算出対象の部分グラフの自己同型写像の数とから得られる、重複を含む出現箇所の数以上であるか否かを判定する。出現箇所抽出部１２は、現に抽出した部分グラフの出現箇所の数が、閾値と算出対象の部分グラフの自己同型写像の数とから得られる、重複を含む出現箇所の数以上である場合に、出現頻度が閾値以上であると判断する。そして、出現箇所抽出部１２は、これ以降の出現箇所抽出処理を終了しても良い。ここで、閾値と算出対象の部分グラフの自己同型写像の数とから得られる、重複を含む出現箇所の数は、算出対象の部分グラフの自己同型写像の数がｎであり、閾値がｔであるとすると、ｎ×ｔの計算式で表わせる。なお、算出対象の部分グラフの出現箇所がｔ以上であることは、重複を含む出現箇所の数がｎ×（ｔ−１）＋１以上となった時点で判定可能である。なぜならば、出現箇所がｔ−１以下であるならば、重複を含む出現箇所は高々ｎ×（ｔ−１）であるからである。
【００８５】
［部分グラフ出現頻度算出処理のフローチャート］
図８は、実施例３に係る部分グラフ出現頻度算出処理のフローチャートを示す図である。
【００８６】
図８に示すように、入力部１１は、検索対象のグラフのデータセット、出現頻度を算出する対象となる部分グラフ（算出対象の部分グラフ）および判定頻度（閾値）ｔを入力する（ステップＳ３１）。
【００８７】
そして、部分グラフ同型写像数算出部３１は、算出対象の部分グラフの自己同型写像の数ｎを計算する（ステップＳ３２）。例えば、部分グラフ同型写像数算出部３１は、算出対象の部分グラフの各頂点を起点として自己の部分グラフとマッチングを行い、算出対象の部分グラフの自己同型写像の数を算出する。
【００８８】
そして、出現箇所抽出部１２は、検索対象のグラフから算出対象の部分グラフとマッチする部分グラフの出現箇所を抽出する（ステップＳ３３）。例えば、出現箇所抽出部１２は、検索対象のグラフの各頂点を起点として算出対象の部分グラフとマッチングを行う。出現箇所抽出部１２は、検索対象のグラフの中でマッチする部分グラフの出現箇所を抽出する。
【００８９】
そして、出現箇所抽出部１２は、抽出した部分グラフの出現箇所がｎ×（ｔ−１）＋１以上であるか否かを判定する（ステップＳ３４）。抽出した部分グラフの出現箇所がｎ×（ｔ−１）＋１以上であると判定した場合には（ステップＳ３４；Ｙｅｓ）、出現箇所抽出部１２は、出現頻度が判定頻度ｔ以上であることを出力する（ステップＳ３５）。そして、出現箇所抽出部１２は、これ以降の部分グラフ出現頻度算出処理を終了する。
【００９０】
一方、抽出した部分グラフの出現箇所がｎ×（ｔ−１）＋１未満であると判定した場合には（ステップＳ３４；Ｎｏ）、出現箇所抽出部１２は、マッチングが終了したか否かを判定する（ステップＳ３６）。マッチングが終了していないと判定した場合には（ステップＳ３６；Ｎｏ）、出現箇所抽出部１２は、次のマッチングをおこなうべく、ステップＳ３３に移行する。
【００９１】
一方、マッチングが終了したと判定した場合には（ステップＳ３６；Ｙｅｓ）、出現箇所抽出部１２は、出現頻度が判定頻度ｔ未満であることを出力する（ステップＳ３７）。そして、出現箇所抽出部１２は、部分グラフ出現頻度算出処理を終了する。
【００９２】
このようにして、情報処理装置１は、出現頻度が閾値以上であるか否かを判定する場合に、部分グラフの出現箇所を抽出する際、抽出した出現箇所の数が、閾値と自己同型写像の数とから得られる、重複を含む出現箇所の数以上であるか否かを判定する。情報処理装置１は、抽出した出現箇所の数が重複を含む出現箇所の数以上であると判定した場合には、抽出する処理を終了する。かかる構成によれば、情報処理装置１は、部分グラフの出現箇所を抽出する際に、出現頻度が閾値以上であるか否かを判定する処理を一緒に判定できるので、当該判定する処理の計算コストを低減できる。
【００９３】
［その他］
なお、実施例１〜３では、グラフについて、頂点にＡやＢなどのラベルがついている場合を説明したが、これに限定されず、頂点にラベルがついていない場合であっても良い。また、グラフについて、頂点や枝にラベルがついている場合であっても良いし、頂点にラベルがついていなくても枝にラベルがついている場合であっても良い。
【００９４】
また、図示した情報処理装置１の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、情報処理装置１の分散・統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、出現頻度算出部３２と、出現頻度出力部１５とを１つの部として統合しても良い。また、記憶部２０を情報処理装置１の外部装置としてネットワーク経由で接続するようにしても良い。
【００９５】
また、上記実施例で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図５に示した情報処理装置１と同様の機能を実現する部分グラフ出現頻度算出プログラムを実行するコンピュータの一例を説明する。図９は、部分グラフ出現頻度算出プログラムを実行するコンピュータの一例を示す図である。
【００９６】
図９に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０３と、ユーザからのデータの入力を受け付ける入力装置２１５と、表示装置２０９を制御する表示制御部２０７とを有する。また、コンピュータ２００は、記憶媒体からプログラムなどを読取るドライブ装置２１３と、ネットワークを介して他のコンピュータとの間でデータの授受を行う通信制御部２１７とを有する。また、コンピュータ２００は、各種情報を一時記憶するメモリ２０１と、ＨＤＤ２０５を有する。そして、メモリ２０１、ＣＰＵ２０３、ＨＤＤ２０５、表示制御部２０７、ドライブ装置２１３、入力装置２１５、通信制御部２１７は、バス２１９で接続されている。
【００９７】
ドライブ装置２１３は、例えばリムーバブルディスク２１１用の装置である。ＨＤＤ２０５は、部分グラフ出現頻度算出プログラム２０５ａおよび部分グラフ出現頻度算出処理関連情報２０５ｂを記憶する。
【００９８】
ＣＰＵ２０３は、部分グラフ出現頻度算出プログラム２０５ａを読み出して、メモリ２０１に展開し、プロセスとして実行する。かかるプロセスは、情報処理装置１の各機能部に対応する。部分グラフ出現頻度算出処理関連情報２０５ｂは、部分グラフ情報２１および検索対象グラフ情報２２に対応する。そして、例えばリムーバブルディスク２１１が、部分グラフ出現頻度算出プログラム２０５ａなどの各情報を記憶する。
【００９９】
なお、部分グラフ出現頻度算出プログラム２０５ａについては、必ずしも最初からＨＤＤ２０５に記憶させておかなくても良い。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に当該プログラムを記憶させておく。そして、コンピュータ２００がこれらから部分グラフ出現頻度算出プログラム２０５ａを読み出して実行するようにしても良い。
【符号の説明】
【０１００】
１  情報処理装置
１０  制御部
１１  入力部
１２  出現箇所抽出部
１３  重複判定部
１４  重複削除部
１５  出現頻度出力部
２０  記憶部
２１  部分グラフ情報
２２  検索対象グラフ情報
【図１】
2017201480.tif 000003
【図２Ａ】
2017201480.tif 000004
【図２Ｂ】
2017201480.tif 000005
【図２Ｃ】
2017201480.tif 000006
【図２Ｄ】
2017201480.tif 000007
【図２Ｅ】
2017201480.tif 000008
【図３Ａ】
2017201480.tif 000009
【図３Ｂ】
2017201480.tif 000010
【図３Ｃ】
2017201480.tif 000011
【図３Ｄ】
2017201480.tif 000012
【図３Ｅ】
2017201480.tif 000013
【図３Ｆ】
2017201480.tif 000014
【図３Ｇ】
2017201480.tif 000015
【図３Ｈ】
2017201480.tif 000016
【図３Ｉ】
2017201480.tif 000017
【図３Ｊ】
2017201480.tif 000018
【図３Ｋ】
2017201480.tif 000019
【図３Ｌ】
2017201480.tif 000020
【図３Ｍ】
2017201480.tif 000021
【図３Ｎ】
2017201480.tif 000022
【図３Ｏ】
2017201480.tif 000023
【図４】
2017201480.tif 000024
【図５】
2017201480.tif 000025
【図６Ａ】
2017201480.tif 000026
【図６Ｂ】
2017201480.tif 000027
【図７】
2017201480.tif 000028
【図８】
2017201480.tif 000029
【図９】
2017201480.tif 000030