特許
J-GLOBAL ID：201203051852301044
グラフの類似度計算システム、方法及びプログラム
発明者：
,
出願人/特許権者：
代理人 (3件)：
上野 剛史
, 太佐 種一
, 市位 嘉宏
公報種別：再公表公報
出願番号（国際出願番号）：JP2010059795
公開番号（公開出願番号）：WO2011-001806
出願日： 2010年06月09日
公開日（公表日）： 2011年01月06日
要約：
SNSやWWWのリンクなどの極めて多数のノードをもつグラフ間の類似度を、妥当な計算時間で求めること。 グラフのノードに、そのノードのラベルに一意的な値が付与される。好適には、この値は、固定長ビット列である。このときのビット列の長さは、ラベルの種類を表現するに足りる桁数よりも十分大きい数に選ばれる。1つのグラフにつき、深さ優先探索、幅優先探索などの既存のグラフ探索技法により、そのグラフのノードを順次訪問する。その際、この発明のシステムは、1つのノードにあるとき、そのノードに隣接する全てのノードのビット列ラベル値と、そのノードのノードのビット列ラベル値とに計算を施して、ビット列値を計算する。この発明のシステムは、その計算されたビット列値と、もともとそのノードがもっているビット列ラベル値からハッシュ計算を施して、別のビット列ラベル値を計算し、それを、そのノードのラベル値とする。こうして、1つのグラフの全てのノードを訪問し終わったとき、全てのノードのラベル値は、書き換えられていることになる。グラフの類似度を比較したい別のグラフについても同様の処理を行なうと、別のグラフでも、全てのノードのラベル値が、書き換えられていることになる。すると、1つのグラフにおいて、全ノード数に対する、別のグラフと一致するラベル値の割合を計算することにより、類似度を求めることができる。
請求項（抜粋）：
コンピュータの処理によって、各ノードに離散ラベルが付与された、2つのグラフの間の類似度を計算する方法であって、
前記2つのグラフの各々に、所与のノードと、その隣接ノードに、異なる離散ラベルに異なる値が対応するように、ラベル値を付与するステップと、
前記2のグラフにおいて、順次ノードを辿るステップと、
前記ノードを辿る間に、訪問しているノードのラベル値と、該訪問しているノードに隣接しているノードのラベル値とのハッシュ計算により新たなラベル値を計算して、該新たなラベル値で、該訪問しているノードのラベル値を更新するステップと、
前記2つのグラフのノードに付与されている、一致するラベル列の個数に基づき、前記2つのグラフの間の類似度を計算するステップを有する、
方法。
IPC (1件)：
FI (3件)：
G06F17/30 419B
, G06F17/30 350C
, G06F17/30 412
