(57)【要約】  ＳＮＳやＷＷＷのリンクなどの極めて多数のノードをもつグラフ間の類似度を、妥当な計算時間で求めること。  グラフのノードに、そのノードのラベルに一意的な値が付与される。好適には、この値は、固定長ビット列である。このときのビット列の長さは、ラベルの種類を表現するに足りる桁数よりも十分大きい数に選ばれる。１つのグラフにつき、深さ優先探索、幅優先探索などの既存のグラフ探索技法により、そのグラフのノードを順次訪問する。その際、この発明のシステムは、１つのノードにあるとき、そのノードに隣接する全てのノードのビット列ラベル値と、そのノードのノードのビット列ラベル値とに計算を施して、ビット列値を計算する。この発明のシステムは、その計算されたビット列値と、もともとそのノードがもっているビット列ラベル値からハッシュ計算を施して、別のビット列ラベル値を計算し、それを、そのノードのラベル値とする。こうして、１つのグラフの全てのノードを訪問し終わったとき、全てのノードのラベル値は、書き換えられていることになる。グラフの類似度を比較したい別のグラフについても同様の処理を行なうと、別のグラフでも、全てのノードのラベル値が、書き換えられていることになる。すると、１つのグラフにおいて、全ノード数に対する、別のグラフと一致するラベル値の割合を計算することにより、類似度を求めることができる。
2011001806.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、各ノードに離散ラベルが付与された、２つのグラフの間の類似度を計算する方法であって、
前記２つのグラフの各々に、所与のノードと、その隣接ノードに、異なる離散ラベルに異なる値が対応するように、ラベル値を付与するステップと、
前記２のグラフにおいて、順次ノードを辿るステップと、
前記ノードを辿る間に、訪問しているノードのラベル値と、該訪問しているノードに隣接しているノードのラベル値とのハッシュ計算により新たなラベル値を計算して、該新たなラベル値で、該訪問しているノードのラベル値を更新するステップと、
前記２つのグラフのノードに付与されている、一致するラベル列の個数に基づき、前記２つのグラフの間の類似度を計算するステップを有する、
方法。
【請求項２】
前記ラベル値が、固定幅のビット列である、請求項１に記載の方法。
【請求項３】
前記ハッシュ計算が、前記訪問しているノードのラベル値のビットシフトした値と、前記隣接しているノードのラベル値のＸＯＲした値とをＸＯＲして行われる、請求項２に記載の方法。
【請求項４】
前記ハッシュ計算が、前記訪問しているノードのラベル値のビット回転した値と、前記隣接しているノードのラベル値をソートし、重複度をカウントし、カウント値を加算し、カウント値分ビット回転し、ＸＯＲした値とをＸＯＲして行われる、請求項２に記載の方法。
【請求項５】
前記ソートが、基数ソートである、請求項４に記載の方法。
【請求項６】
前記２つのグラフのうちの１つのグラフが、所与のグラフの第１のノードを含む第１の部分グラフであり、前記２つのグラフのうちのもう１つのグラフが、該所与のグラフの第２のノードを含む第２の部分グラフであり、
計算された前記２つのグラフの間の類似度が、該第１のノードと該第２のノードの間の類似度と見なされる、請求項１に記載の方法。
【請求項７】
コンピュータの処理によって、各ノードに離散ラベルが付与された、２つのグラフの間の類似度を計算するシステムであって、
前記２つのグラフの各々に、所与のノードと、その隣接ノードに、異なる離散ラベルに異なる値が対応するように、ラベル値を付与する手段と、
前記２のグラフにおいて、順次ノードを辿る手段と、
前記ノードを辿る間に、訪問しているノードのラベル値と、該訪問しているノードに隣接しているノードのラベル値とのハッシュ計算により新たなラベル値を計算して、該新たなラベル値で、該訪問しているノードのラベル値を更新する手段と、
前記２つのグラフのノードに付与されている、一致するラベル列の個数に基づき、前記２つのグラフの間の類似度を計算する手段を有する、
システム。
【請求項８】
前記ラベル値が、固定幅のビット列である、請求項７に記載のシステム。
【請求項９】
前記ハッシュ計算が、前記訪問しているノードのラベル値のビットシフトした値と、前記隣接しているノードのラベル値のＸＯＲした値とをＸＯＲして行われる、請求項８に記載のシステム。
【請求項１０】
前記ハッシュ計算が、前記訪問しているノードのラベル値のビット回転した値と、前記隣接しているノードのラベル値をソートし、重複度をカウントし、カウント値を加算し、カウント値分ビット回転し、ＸＯＲした値とをＸＯＲして行われる、請求項８に記載のシステム。
【請求項１１】
前記ソートが、基数ソートである、請求項１０に記載のシステム。
【請求項１２】
前記２つのグラフのうちの１つのグラフが、所与のグラフの第１のノードを含む第１の部分グラフであり、前記２つのグラフのうちのもう１つのグラフが、該所与のグラフの第２のノードを含む第２の部分グラフであり、
計算された前記２つのグラフの間の類似度が、該第１のノードと該第２のノードの間の類似度と見なされる、請求項７に記載のシステム。
【請求項１３】
コンピュータの処理によって、各ノードに離散ラベルが付与された、２つのグラフの間の類似度を計算するプログラムであって、
前記コンピュータに、
前記２つのグラフの各々に、所与のノードと、その隣接ノードに、異なる離散ラベルに異なる値が対応するように、ラベル値を付与するステップと、
前記２のグラフにおいて、順次ノードを辿るステップと、
前記ノードを辿る間に、訪問しているノードのラベル値と、該訪問しているノードに隣接しているノードのラベル値とのハッシュ計算により新たなラベル値を計算して、該新たなラベル値で、該訪問しているノードのラベル値を更新するステップと、
前記２つのグラフのノードに付与されている、一致するラベル列の個数に基づき、前記２つのグラフの間の類似度を計算するステップを実行させる、
プログラム。
【請求項１４】
前記ラベル値が、固定幅のビット列である、請求項１３に記載のプログラム。
【請求項１５】
前記ハッシュ計算が、前記訪問しているノードのラベル値のビットシフトした値と、前記隣接しているノードのラベル値のＸＯＲした値とをＸＯＲして行われる、請求項１４に記載のプログラム。
【請求項１６】
前記ハッシュ計算が、前記訪問しているノードのラベル値のビット回転した値と、前記隣接しているノードのラベル値をソートし、重複度をカウントし、カウント値を加算し、カウント値分ビット回転し、ＸＯＲした値とをＸＯＲして行われる、請求項１４に記載のプログラム。
【請求項１７】
前記ソートが、基数ソートである、請求項１６に記載のプログラム。
【請求項１８】
前記２つのグラフのうちの１つのグラフが、所与のグラフの第１のノードを含む第１の部分グラフであり、前記２つのグラフのうちのもう１つのグラフが、該所与のグラフの第２のノードを含む第２の部分グラフであり、
計算された前記２つのグラフの間の類似度が、該第１のノードと該第２のノードの間の類似度と見なされる、請求項１３に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータ上でグラフとして表現されたデータ構造の対象物の類似度を計算あるいは評価する技術に関するものである。
【背景技術】
【０００２】
グラフとは、互いに識別するためのラベルをもつ頂点（ノードとも呼ばれる）と、頂点を繋ぐ辺（エッジや、枝、リンクとも呼ばれる）からなる数学的対象であり、現実的な対象物を考慮すると、例えば、道路地図、化学式などが、グラフであらわされることが分かる。【０００３】
例えば、道路地図においては、交差点がノードであり、道がエッジであるとみなすことができる。化学式においては、元素がノードであり、元素間の結合がエッジであるとみなすことができる。このように考えると、グラフは、遺伝子、タンパク質構造、電気回路、地理学、建築学などの非常に広い範囲にその応用を見出すことが分かる。【０００４】
最近では、ソーシャル・ネットワーキング・サービス（ＳＮＳ）にもグラフ構造が適用されつつある。すなわち、ＳＮＳの個々のユーザをノードとし、それらのユーザ間のと別の間の友好関係などをエッジとみなすことにより、ＳＮＳの特定の状態をグラフで表現することができる。同様の趣旨で、ＷＷＷのリンク構造も、グラフで表現することができる。【０００５】
このように、現実の対象をグラフとして表現したとき、２つのグラフが一致するかどうか、あるいは類似するかどうかを評価したい、ということは、自然に出てくる要望である。例えば、ある薬品の化学式のグラフと、別の薬品の化学式のグラフが類似していると評価できると、その２つの薬品の薬効は似ていると推定可能である。【０００６】
ところが、従来の研究によると、２つのグラフが同じかどうかを判別する問題は、多項式時間アルゴリズムが知られておらず、あるグラフが別のグラフに含まれるかどうかを判別するためのアルゴリズムも、ＮＰ完全である。【０００７】
そのようなアルゴリズムも、比較的少ない数のノードしかないグラフなら妥当な計算時間で解が得られるが、遺伝子配列を扱うバイオインフォマティックスでは、ノードの数が数千から数万、ＳＮＳでは数百万と、ナイーブなグラフ類似度計算技法が現実的な計算量で扱える範囲を大きく上回ってしまう。【０００８】
そこで、従来により、２つのグラフの同一性または類似度を高速で計算するための技法が提案されている。【０００９】
Thomas E. Portegys, School of Information Technology, Illinois State University, "General Graph Identification With Hashing"  http://www.itk.ilstu.edu/faculty/portegys/research/graph/graph-hash.pdfは、MD5ハッシングという技法によって、２つのグラフの同一性を高速に判定する技法を開示する。しかし、この技法では、グラフの同一性が判定できるのみで、類似度の計算には適用できない。【００１０】
特にそのグラフに関連するハッシュ作成については、特開平７−３３４３６６号公報に、グラフＳの全ての部分グラフのハッシュ値を記憶するハッシュテーブルを持ち、過去に存在した部分グラフと現在到達しているそのリダクション先の部分グラフの組を記憶することの記載がある。しかし、この技法では、再帰的にアプローチでハッシュ値を与えるため、有向非巡回グラフには適用できるものの、ループを含むより一般的なグラフには適用できない。【００１１】
米国特許第６４７３８８１号は、トランジスタ・レベルの設計自動化ツールが、タイミング解析、電気的規則のチェック、ノイズの解析などを通じて、回路デザインのパターンマッチングを行なう技術を開示する。しかし、この技法は、キーノードなどという回路特有の性質を用いており、一般的なグラフ比較に拡張することは困難である。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平７−３３４３６６号公報
【特許文献２】米国特許第６４７３８８１号
【非特許文献】
【００１３】
【非特許文献１】Thomas E. Portegys, School of Information Technology, Illinois State University, "General Graph Identification With Hashing"  http://www.itk.ilstu.edu/faculty/portegys/research/graph/graph-hash.pdf
【発明の概要】
【発明が解決しようとする課題】
【００１４】
従って、この発明の目的は、ＳＮＳやＷＷＷのリンクなどの極めて多数のノードをもつグラフ間の類似度を、妥当な計算時間で求めることを可能ならしめる、グラフ比較技法を提供することにある。
【課題を解決するための手段】
【００１５】
上記の課題は、この発明により、極めて有利に解決される。まず前提として、比較すべきグラフのデータは、行列表現、リスト表現などの、グラフ表現のための公知データ構造を用いて表現され、コンピュータのハードディスクなどの記憶装置上に保存される。グラフの各ノードは、個々にラベルをもち、ラベルは離散的な値をもつと想定する。例えば、遺伝子であれば、ラベルは、アデニン、チミン、グアニン、シトシンの４種類であり、タンパク質であるなら、グリシン、トリプトファン、イソロイシンなど２０種類のアミノ酸であり、化学式であれば、水素、ヘリウム、リチウム、ベリリウム、ホウ素、炭素、窒素、酸素以下、高々１００種類程度である。【００１６】
この発明によれば先ず、グラフのノードに、そのノードのラベルに一意的な値が付与される。好適には、この値は、固定長ビット列である。このときのビット列の長さは、ラベルの種類を表現するに足りる桁数よりも十分大きい数に選ばれる。後述するハッシュ衝突の可能性を減らすためである。【００１７】
そのような準備の下、この発明のシステムは、１つのグラフにつき、深さ優先探索、幅優先探索などの既存のグラフ探索技法により、そのグラフのノードを順次訪問する。その際、この発明のシステムは、１つのノードにあるとき、そのノードに隣接する全てのノードのビット列ラベル値と、そのノードのノードのビット列ラベル値とに計算を施して、ビット列値を計算する。この発明のシステムは、その計算されたビット列値と、もともとそのノードがもっているビット列ラベル値からハッシュ計算を施して、別のビット列ラベル値を計算し、それを、そのノードのラベル値とする。【００１８】
こうして、１つのグラフの全てのノードを訪問し終わったとき、全てのノードのラベル値は、書き換えられていることになる。グラフの類似度を比較したい別のグラフについても同様の処理を行なうと、別のグラフでも、全てのノードのラベル値が、書き換えられていることになる。【００１９】
すると、例えば、１つのグラフにおいて、全ノード数に対する、別のグラフと一致するラベル値の割合を計算することにより、類似度を求めることができる。後の実施例では、もう少し複雑な類似度の計算方法が説明される。【００２０】
本発明によれば、隣接ノードのラベル値から、自ノードのラベル値を計算する方法として、複数の方法のうちの１つを使用することができる。【００２１】
１つの方法は、隣接ノード全てのラベル値をＸＯＲした値と、自ノードのラベル値をビット回転した値のＸＯＲを計算して、それを自ノードのラベル値とすることである。【００２２】
別の方法は、隣接ノード全てのラベル値をソートし、その結果同一のラベル値が連続して現れると、それらを１つのラベル値で代表させ、連続して現れる回数（カウント値と称する）を加算する。そうして得られたラベル値を、カウント値分だけビット回転させ、その結果全てをＸＯＲした値と、自ノードのラベル値をビット回転した値のＸＯＲを計算して、それを自ノードのラベル値とすることである。【００２３】
本発明は、これ以外にも、隣接ノード全てのラベル値と自ノードのラベル値から自ノードのラベル値を計算する様々な方法を使用することができる。
【発明の効果】
【００２４】
この発明によれば、１つのノードとその隣接ノードのラベル値とのハッシュ値を以って、その１つのノードの新ラベル値とする計算の結果得られたラベル値に基づき、グラフの類似度を計算するようにしたことによって、グラフのノードの数をNとしたとき、O(N2)以下のオーダーの計算量で高速にグラフの類似度が計算できる、という効果が得られる。知られている他のグラフ類似度比較技法では、指数オーダーであったり、少なくともO(N3)程度なので、特にNが大きい場合に、この発明は、高速化の効果が大きい。【００２５】
また、隣接ノードのラベル値をきちんと反映させる計算であるので、結果の類似度の信頼性も高い。
【図面の簡単な説明】
【００２６】
【図１】本発明を実施するためのハードウェア構成のブロック図である。
【図２】本発明に係る機能論理ブロック図である。
【図３】本発明に従い、グラフのノードのラベル値を計算する処理のフローチャートを示す図である。
【図４】計算ステップに従う、グラフのノードのラベル値の変化を示す図である。
【図５】自ノードのラベルと、隣接ノードのラベル集合から、自ノードの新しいラベル値を計算する処理を示す概念的なフローチャートを示す図である。
【図６】自ノードのラベルと、隣接ノードのラベル集合から、自ノードの新しいラベル値を計算する一実施例の処理を示すフローチャートを示す図である。
【図７】自ノードのラベルと、隣接ノードのラベル集合から、自ノードの新しいラベル値を計算する別の実施例の処理を示すフローチャートを示す図である。
【図８】図６の具体的な処理を示す図である。
【図９】図７の具体的な処理を示す図である。
【図１０】複数のグラフを一括で比較する処理のフローチャートを示す図である。
【図１１】図１０の処理で呼ばれる類似度比較ルーチンの処理のフローチャートを示す図である。
【発明を実施するための形態】
【００２７】
以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
【００２８】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標）  ４、Ｃｏｒｅ（商標）２  Ｄｕｏ、Ｘｅｏｎ（商標）、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、大量のグラフ・データを格納できるように、例えば、３２０ＧＢ以上の容量をもつものであることが望ましい。
【００２９】
ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システムが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ  ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ  ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。
【００３０】
ハードディスク・ドライブ１０８にはまた、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などのプログラム言語処理系も格納されている。このプログラム言語処理系は、後で説明する、グラフ・データ処理用のモジュールまたはツールを作成し、維持するために使用される。
【００３１】
ハードディスク・ドライブ１０８にはさらに、プログラム言語処理系でコンパイルするためのソースコードを書くためのテキスト・エディタ、及び、Ｅｃｌｉｐｓｅ（商標）などの開発環境を含んでいてもよい。
【００３２】
キーボード１１０及びマウス１１２は、オペレーティング・システムまたは、ハードディスク・ドライブ１０８から主記憶１０６にロードされ、ディスプレイ１１４に表示されたプログラム（図示しない）を起動したり、文字を打ち込んだりするために使用される。
【００３３】
ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。ディスプレイ１１４は、図示しないが、処理すべきグラフ・データや、グラフの類似度を表示するために使用される。
【００３４】
図２は、本発明に係る処理モジュールの機能ブロック図である。これらのモジュールは、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）など既存のプログラム言語で書かれ、実行可能バイナリ形式でハードディスク・ドライブ１０８に格納され、マウス１１２またはキーボード１１０の操作に応答して、オペレーティング・システム（図示しない）の働きで、主記憶１０６に呼び出されて、実行される。
【００３５】
グラフ・データ作成モジュール２０２は、所与のグラフを、コンピュータ可読なデータ構造に変換する。このとき、例えば、ノード数n、平均隣接ノード数dのグラフgとして、次のようなデータ構造を用いる。
【００３６】
g.nodelist：ノードリストを表す長さnのリスト
g.labellist：ノードラベルリストを表す長さnのリスト
g.labellistx：g.labellistと同じデータ構造で、ラベル書込み用バッファとして使用される、長さnのリスト
g.adjacencymatrix：グラフの隣接行列。ノードiとノードjにリンクがあれば行列の要素(i, j)は1、そうでなければ0を持つ。大きさはn × nになるが、0要素を省略するスパース行列というデータ構造を使えばn × dで済む。
【００３７】
このとき、ノードの異なるラベルの種類をpとすると、p << 2mのようなmを選んで、ラベルをmビットのデータとする。このように、2mをpよりも十分大きくとる理由は、ラベルにおけるハッシュ衝突の可能性を減らすためである。
【００３８】
そうして、例えば、2m-1 < P1 < 2mであるような素数P1と、P1よりも十分大きい素数P2を用意して、i番目のラベル値をLHiとすると、例えば、下記のような式で、
ラベルLi ( i = 1, .., p )の各々に、異なるmビットのラベル値を付与することができる。
for ( i = 1; i <= p; i++ )    {
LHi = (P2 * i) % P1;
}
ここで、%は、割算の余りを計算する演算子である。
あるいは、これ以外の任意の乱数生成ルーチンを使用することもできる。
【００３９】
グラフ・データ作成モジュール２０２は、このようにして決められたラベル値LHiを、グラフの各ノードに、そのラベルLiに応じて付与しつつ、グラフ・データを構成する。すなわち、グラフ・データ作成モジュール２０２は、図４(a)にあるようなグラフを、例えば深さ優先でグラフを辿りながら、g.nodelistを順次作成し、併せてそのラベル値LHiをg.labellistに記録しつつ、隣接関係をg.adjacencymatrixに記録していく。その結果、図４(b)にあるように、各ラベルにラベル値としてビット列が付与される。図４(b)の例では、Ａ = #1000, Ｂ = #0101, Ｃ = #1100である。言うまでもなく、ラベルに対して付与するラベル値は、２つのグラフで共通である。なお、ここで#0101のような表記は、２進数をあらわすものとする。ラベル値は、好適には固定ビット数とする。というのは、後で説明するが、その方が、ビット回転、ＸＯＲ、基数ソートなどの計算に好都合だからである。
【００４０】
構成されたグラフ・データは、主記憶１０６上にロードされるか、または、ハードディスク１０８に、保存される。グラフ・データが非常に大きい場合、グラフ・データを先ずハードディスク１０８上に置き、計算に必要な箇所のデータだけを主記憶にロードするようにすることもできる。
【００４１】
グラフ探索モジュール２０６は、グラフを順次探索して、１つのグラフの全てのノードを訪問し、そのノードの隣接ノードを参照して、隣接ノードとのハッシュ計算モジュール２０８を呼び出しつつ、そのノードのラベル値を更新する処理を行う。
【００４２】
図３は、グラフ探索モジュール２０６の処理のフローチャートを示す図である。図３において、ステップ３０２では、グラフ探索モジュール２０６は、グラフのすべてのノードを訪問したかどうかの判断を行う。この判断は実際は、g.nodelistの末端に達したかどうかで行われる。
【００４３】
もしステップ３０２で、まだグラフのすべてのノードを訪問していないと判断されると、ステップ３０４で、g.nodelistに従い、グラフ探索モジュール２０６は、次のノードを訪問する。グラフ探索の最初の段階では、ステップ３０４では、先頭のノードを訪問することになる。
【００４４】
ステップ３０６では、グラフ探索モジュール２０６は、モジュール２０８を呼び出すことによって、今訪問している当該ノードの隣接ノードの情報を用いて、ハッシュによりラベル値の計算を行う。ここで隣接ノードとは、当該ノードにエッジを介して直接つながっているノードである。このような隣接関係は、g.adjacencymatrixに記録されている値を参照することによって、調べることができる。この計算には、当該ノードのラベル値と、隣接ノードのラベル値とが使用される。これらのラベル値は、g.labellistを参照することによって取得される。ラベル値の計算は、図５、図６及び図７のフローチャートを参照して、後でより詳細に説明する。
【００４５】
ステップ３０８では、グラフ探索モジュール２０６は、そのように計算されたラベル値で、当該ノードのラベル値を更新する。このときg.labellistに直接上書きしてもよいが、より好適には、g.labellistにではなく、g.labellistxに更新ラベルが書き込まれる。これは、g.labellistに直接上書きすると、ノードの探索順序に依存して、結果が変わってしまうからである。
【００４６】
次にステップ３０２での判断に戻り、全てのノードを訪問し終わるまで、ステップ３０４、３０６及び３０８が実行される。
【００４７】
全てのノードを訪問し終わると、g.labellistxの全てのノードが書き換えられている。そこで、g.labellistが、g.labellistxで置換される。このようなグラフの訪問によるラベル値の書き換えは、比較すべき２つのグラフ各々について行われる。その様子は、図４(c)に模式的に示されている。
【００４８】
このようなグラフの訪問によるラベル値の書き換え処理は、好適には、図４(d)などに示されるように、複数回行われる。それによって、グラフ比較の精度は一般的に高まるが、回数が増えるほど精度が高まるとは限らないで、自ずと最適な回数がある。
【００４９】
図２に戻って、グラフ類似度計算モジュール２１０は、書き換えられたラベル値に基づき、２つのグラフの類似度を計算する。一番素朴な類似度の計算方法は、２つのグラフの間の書き換えられたラベル値の一致比率を計算するものである。後に、もう少し複雑なグラフの類似度の計算についても説明する。
【００５０】
図５は、隣接ノードとのハッシュ計算モジュール２０８の処理をより詳細に説明する、概要フローチャートである。
【００５１】
図３のフローチャートで、ノードを訪問していくときに、今滞在しているノードを自ノードと呼ぶことにすると、自ノードのラベル５０２とは、今滞在しているノードに対応するラベル値であり、g.labellistから取得される。それを便宜上、ThisNodeLabelと書くことにする。
【００５２】
一方、今滞在しているノードに隣接するラベルの集合５０４は、g.adjacencymatrixに記録されている値を参照することによって、g.labellistから取得される。それは一般的に複数ありえるので、NeighboringNodeLabels[]と書くことにする。
【００５３】
そして、ハッシュ関数を、Hash()とし、新しいラベル５０８をNewLabelとすると、
NewLabel = Hash(ThisNodeLabel,NeighboringNodeLabels[])  と計算される。
【００５４】
このように計算されたNewLabelの値が、今滞在しているノードのラベル値として、g.labellistxに上書きされる。
【００５５】
図６は、図５の処理の一実施例を示す図である。すなわち、図６の処理において、自ノードのラベル６０２と、隣接ノードのラベル集合６０４とから、新しいラベル６０８を生成するために、ハッシュ計算ブロック６０６は、自ノードのラベル６０２を１ビット回転するブロック６１０と、隣接ノードのラベル集合６０４をＸＯＲするブロック６１２と、ブロック６１０の出力とブロック６１２の出力を新しいラベル６０８としてＸＯＲするブロック６１４を有する。
【００５６】
図８に、図６の処理の具体的な計算例を示す。図８において、自ノードのラベルが#1000、隣接ノードのラベルがそれぞれ、#1110と#1100であるとする。すると、ブロック６１２の出力は#1110と#1100のＸＯＲで#0010となり、一方、ブロック６１０の出力は、#1000の１ビット回転で#0001となり、それらのＸＯＲをとるブロック６１４の出力は#0011となって、これが自ノードの新ラベルとなる。
【００５７】
図７は、図５の処理のさらに別の実施例を示す図である。すなわち、図７の処理において、自ノードのラベル７０２と、隣接ノードのラベル集合７０４とから、新しいラベル７０８を生成するために、ハッシュ計算ブロック７０６は、自ノードのラベル７０２を１ビット回転するブロック７１０と、隣接ノードのラベル集合７０４をソートするブロック７１２と、ソートされた出力の重複をカウントするブロック７１４と、カウント値を加算するブロック７１６と、カウント分ビット回転するブロック７１８と、ビット回転された出力をＸＯＲするブロック７２０と、ブロック７１０の出力とブロック７２０の出力を新しいラベル７０８としてＸＯＲするブロック７２２を有する。
【００５８】
尚、好適な実施例では、ラベルは固定幅のビット列であるので、ブロック７１２でのソートは、基数(radix)ソートを使用するのが好都合である。
【００５９】
図９に、図７の処理の具体的な計算例を示す。図９において、自ノードのラベルが#1000、隣接ノードのラベルがそれぞれ、#0101、#1100、#0101であるとする。すると、ブロック７１２のソート出力は、#0101、#0101、#1100となる。すると、#0101は２つ続いてあらわれるので、ブロック７１４のカウント出力は、#0101について2、#1100について1となる。
【００６０】
次に、ブロック７１６が、元のラベルの値にカウント出力を加える。#0101には2が加えられて#0111、#1100には1が加えられて#1101になる。
【００６１】
すると、ブロック７１８が、カウント出力分だけビット回転させる。#0111は2ビット回転で#1101となり、#1101は1ビット回転で#1011となる。
【００６２】
次に、ブロック７２０が、ビット回転された値である#1101と#1011とのＸＯＲを計算し、#0110を出力する。
【００６３】
一方、ブロック７１０が、自ノードのラベルの#1000の1ビット回転である、#0001を出力する。するとブロック７２２が、ブロック７２０から出力された#0110と、ブロック７１０から出力された#0001のＸＯＲを計算し、その結果である#0111が、自ノードの新ラベルとなる。
【００６４】
尚、自ノードのラベル値をハッシュにより計算するためのアルゴリズムは、図６または図７に示すアルゴリズムに限定されず、妥当な計算量且つハッシュ衝突が起こりにくいものであれば、任意のハッシュ・アルゴリズムを使用することができる。
すなわち、ノードに隣接するラベルの集合をNeighboringNodeLabels[]とし、自ノードのラベルをThisNodeLabelとしたとき、
NewLabel = Hash(ThisNodeLabel,NeighboringNodeLabels[])のような引数をとる関数である。
【００６５】
すると、NeighboringNodeLabels[]をソートしてから並べてそれを１つの数と見なし、適当な素数P1で割った余りをNewLabelとする方法を行ってもよい。図９の例だと、
NeighboringNodeLabels[]は、#0101, #1100, #0101からなるので、それらをソートして並べることにより、#010101011100
よって、NewLabel = #010101011100 mod P1 と計算される。
【００６６】
次に、図１０及び図１１のフローチャートを参照して、２以上の複数のグラフどうしの類似度を一度に比較する処理について説明する。この処理を行うためのモジュールは、図２のグラフ類似度計算モジュール２１０に含まれている。
【００６７】
図１０において、ステップ１００２では、Γ = {Ｇ10,...,Ｇh0}と、互いに類似度を比較すべきh個のグラフが用意され、主記憶１０６またはハードディスク・ドライブ１０８にそれらのグラフのデータが格納される。このとき、グラフのノードには、既に説明した方法により、ラベルに応じた、所定ビット数の２進数のラベル値が付与されている。
【００６８】
h = |Γ|で、すなわち、グラフの個数である。rmaxは、ハッシュ計算のための繰り返し回数である。場合によるが、rmaxは、3から5程度に選ばれる。
【００６９】
ステップ１００４では、r = 1とセットされ、rに関するrmaxまでのループが開始される。
【００７０】
ステップ１００６では、r <= rmaxかどうかが判断され、もしそうなら、ステップ１００８で、Ｋr = Ｉとセットされる。ここでＩは、h×hの単位行列である。
【００７１】
ステップ１０１０では、i = 1とセットされ、ここからiに関するループに入る。ステップ１０１２では、i <= hかどうかが判断され、もしそうなら、ステップ１０１４で、次の式が実行される。
Ｇir = NH(Ｇir-1)
ここでＧirは、Ｇiのr乗ではなく、ハッシュ計算のr回目の結果のラベル値をもつグラフを表す。また、NH()は、図３のフローチャートの処理を行う関数またはサブルーチンである。この場合の隣接ノードとのハッシュ計算を行うアルゴリズムは、これには限定されないが、例えば、図７に示すアルゴリズムであるとする。
【００７２】
次のステップ１０１６でＶirとあるのは、Ｇirのノード・リストである。
ステップ１０１６では、ＶiSORT = RADIX_SORT(Ｖir)によって、Ｖirの成分が、ラベル値に基づき基数ソートされた並びでＶiSORTに格納される。ステップ１０１８では、iが1だけ増分されて、ステップ１０１２に戻る。すなわち、iがhに達するまで、ステップ１０１４、１０１６、及び１０１８が繰り返される。
【００７３】
ステップ１０１２で、iがhを超えたと判断されると、ステップ１０２０に行き、そこで、Ｇr-1が除去される。ここで、Ｇr-1とは、Ｇ1r-1,...,Ｇhr-1の総称的な記号であり、要するに、Ｇ1r-1,...,Ｇhr-1を保持していた主記憶の領域を開放する処理を行なう。
【００７４】
次にステップ１０２２で、iが1にセットされる。これは、iに関するループが始まることを意味する。ステップ１０２４では、i <= hかどうかが判断され、もしそうなら、ステップ１０２６で、jが1にセットされる。これは、jに関するループが始まることを意味する。
【００７５】
ステップ１０２８では、j <= hかどうかが判断される。もしそうなら、ステップ１０３０で、j < iであるかどうかが判断される。この判断は、次のステップ１０３２がiとｊで対称であるため、重複処理を避けるために行なわれる。
【００７６】
ステップ１０３０で、j < iと判断されると、ステップ１０３２に進み、そこで、
Ｋijr = Ｋjir = COMPARE_LABELS(Ｇir,Ｇjr)という計算がなされる。COMPARE_LABELS()は、その引数で指定した２つのグラフのラベルを比較して、その比較結果を実数で返す関数であり、その詳細な処理内容は、図１１のフローチャートを参照して、後で説明する。また、その具体的計算で、ステップ１０１６で計算されたＶiSORT、ＶjSORTを使用する。
【００７７】
ステップ１０３４では、ｊを1だけ増分してステップ１０２８に戻り、すなわち、jがhに達するまで、ステップ１０３０、１０３２及び１０３４を繰り返す。
【００７８】
こうして、ステップ１０２８で、jがhを超えたと判断されると、ステップ１０３６でiを1だけ増分して、ステップ１０２４に行く。ステップ１０２４で、iがhを超えたと判断されると、ステップ１０３８でrを1だけ増分して、ステップ１００６に戻る。
【００７９】
ステップ１００６で、rがrmaxを超えたと判断されると、下記の式で類似度行列Ｋが計算されて、処理が完了する。類似度行列Ｋは、そのij成分が、グラフＧi0と、グラフＧj0の類似度をあらわしている。
【数１】
2011001806.tif 000003
【００８０】
次に、図１１のフローチャートを参照して、ステップ１０３２で使用される関数COMPARE_LABELS()の処理の内容を説明する。
【００８１】
ステップ１１０２では、ＶaSORT、ＶbSORTを２つのグラフのソートされたノード・リストとし、ＶaSORTの次数をna、ＶbSORTの次数をnbとする。
【００８２】
ステップ１１０４では、以下で使用される変数を、c = 1, i = 1, j = 1とセットする。
【００８３】
ステップ１１０６では、i <= na且つj <= nbであるかどうかが判断され、もしそうなら、ステップ１１０８で、vi = ＶaSORT[i], vj = ＶaSORT[j]とセットされる。
【００８４】
ステップ１１１０では、la(vi) = lb(vj)かどうかが判断される。la(vi)は例えば、ＶiaSORTのi番目の成分のノードのラベル値を示す。
【００８５】
もしla(vi) = lb(vj)であると判断されたなら、ステップ１１１２で、c = c + 1, i = i + 1, j = j + 1とそれぞれ増分されて、ステップ１１０６に戻る。
【００８６】
ステップ１１１０で、la(vi) = lb(vj)でないと判断されると、ステップ１１１４に進み、そこで、la(vi) < lb(vj)かどうかが判断される。もしla(vi) < lb(vj)であるなら、ステップ１１１６でiが1だけ増分され、そうでなければ、ステップ１１１８でjが1だけ増分され、何れにしても、処理は、ステップ１１０６に戻る。
【００８７】
ステップ１１０６で、i > naまたはj > nbと判断されると、ステップ１１２０に行き、そこで、次の式により、類似度kが計算される。
【数２】
2011001806.tif 000004
【００８８】
ステップ１１２２では、そのように計算されたkの値がリターンされる。実際上、この値は、COMPARE_LABELS()の呼び出し側である、ステップ１０３２で使用される。
【００８９】
以上、本発明を実施の形態を用いて説明したが、上記実施の形態に、多様な変更または改良を加えることが可能であり、その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、この分野の当業者に明らかであろう。例えば、図５に示すラベル値のハッシュ計算として、図６あるいは図７に示す具体的な処理を示したが、これらはあくまでも実施例であり、妥当な計算量の任意のハッシュ関数を使用することができる。また、類似度計算のアルゴリズムとして、図１１に示す処理も一実施例であり、この分野の当業者であるなら、２つのグラフの一致するラベル値の数に基づき、様々な変形例を思いつくことができるはずである。
【００９０】
加えて、以下のように２つのノード間の類似度も、本発明によって計算することができる。すなわち、対象のノードをそれぞれＡ、Ｂとする。各ノードを含む２つの部分グラフを抽出して、本発明を適用することによってＡの更新ラベルとＢの更新ラベルの一致する割合を求め、それをＡとＢの類似度とすることができる。
【符号の説明】
【００９１】
２０２・・・グラフ・データ作成モジュール
２０４・・・グラフ・データ
２０６・・・グラフ探索モジュール
２０８・・・隣接ノードのハッシュ計算モジュール
【図１】
2011001806.tif 000005
【図２】
2011001806.tif 000006
【図３】
2011001806.tif 000007
【図４】
2011001806.tif 000008
【図５】
2011001806.tif 000009
【図６】
2011001806.tif 000010
【図７】
2011001806.tif 000011
【図８】
2011001806.tif 000012
【図９】
2011001806.tif 000013
【図１０】
2011001806.tif 000014
【図１１】
2011001806.tif 000015
【国際調査報告】
2011001806.tif 000016
2011001806.tif 000017
2011001806.tif 000018
2011001806.tif 000019