(57)【特許請求の範囲】
【請求項１】
記憶部と協働してグラフデータのノードのクラスタリング処理を実行する制御部を有するクラスタリング装置であって、
前記制御部は、
入力されたグラフデータから、いずれのクラスタにも未所属の第１ノードを選択し、
前記第１ノードおよび該ノードとエッジで接続されるノードの集合である、前記第１ノードの隣接ノード集合を前記グラフデータから取得し、
前記第１ノードの隣接ノード集合に所属する、前記第１ノードとは異なる各第２ノードの隣接ノード集合を前記グラフデータから取得し、
前記第１ノードの隣接ノード集合および前記各第２ノードの隣接ノード集合の類似度を算出し、
前記第１ノードに対して、前記類似度が第１閾値以上となる前記第２ノードの集合である第１近接ノード集合を生成し、
前記第１近接ノード集合の要素数が第２閾値以上となる場合に前記第１ノードが第１条件を満たすと判定し、前記第１近接ノード集合の要素数が第２閾値未満となる場合に前記第１ノードが前記第１条件を満たさないと判定し、
前記第１ノードが前記第１条件を満たすと判定した場合に、前記第１近接ノード集合を新たなインデックスが付与されたクラスタとし、
前記第１近接ノード集合に所属する各ノードの隣接ノード集合の和集合である第２近接ノード集合を生成し、
前記第２近接ノード集合から前記新たなインデックスが付与されたクラスタを差し引いた第１差集合に所属するノードのなかから、前記新たなインデックスが付与されたクラスタに追加所属させるノードを決定し、
前記第１ノードが前記第１条件を満たさないと判定した場合に、前記第１ノードを未分類クラスタに所属させる
一連の処理を、前記グラフデータの全ノードの所属クラスタが決定するまで繰り返す
ことを特徴とするクラスタリング装置。
【請求項２】
前記第１差集合に所属するノードのなかから、前記新たなインデックスが付与されたクラスタに追加所属させるノードを決定する処理において、
前記制御部は、
前記第１差集合から第３ノードを選択し、
前記第３ノードの隣接ノード集合を前記グラフデータから取得し、
前記第３ノードの隣接ノード集合に所属する、前記第３ノードとは異なる第４ノードの隣接ノード集合を前記グラフデータから取得し、
前記第３ノードの隣接ノード集合および各前記第４ノードの隣接ノード集合の前記類似度を算出し、
前記第３ノードに対して、前記類似度が前記第１閾値以上となる前記第４ノードの集合である第３近接ノード集合を生成し、
前記第３近接ノード集合の要素数が前記第２閾値以上となる場合に前記第３ノードが前記第１条件を満たすと判定し、前記第３近接ノード集合の要素数が前記第２閾値未満となる場合に前記第３ノードが前記第１条件を満たさないと判定し、
前記第３ノードが前記第１条件を満たすと判定した場合に、前記新たなインデックスが付与されたクラスタと前記第３近接ノード集合との和集合で前記新たなインデックスが付与されたクラスタを更新し、前記第３近接ノード集合に所属する各ノードの隣接ノード集合の和集合である第４隣接ノード集合を生成し、前記第１差集合と前記第４隣接ノード集合との和集合から前記新たなインデックスが付与されたクラスタを差し引いた第２差集合で前記第１差集合を更新し、
前記第３ノードが前記第１条件を満たさないと判定した場合に、前記第３ノードを前記未分類クラスタに所属させるとともに、前記第１差集合と、前記新たなインデックスが付与されたクラスタに所属するノードのうち該ノードの隣接ノード集合および前記第３ノードの隣接ノード集合の前記類似度が前記第１閾値以上であるノードの集合との和集合で前記第１差集合を更新する
一連の処理を、前記第１差集合が空集合になるまで繰り返して前記新たなインデックスが付与されたクラスタを構成する
ことを特徴とする請求項１記載のクラスタリング装置。
【請求項３】
前記制御部は、さらに、
前記第１差集合を１ノードに集約した集約ノードを生成し、
前記第１差集合に所属する各ノードの隣接ノード集合および前記集約ノードの隣接ノード集合の前記類似度の上限値ならびに下限値の各推定値を算出し、
前記類似度の上限値ならびに下限値の各推定値に基づく第２条件が満たされると判定した場合に、前記各ノードを前記第１条件を満たすか否かの判定対象とし、前記類似度の上限値ならびに下限値の各推定値に基づく前記第２条件が満たされないと判定した場合に、前記各ノードを前記第１条件を満たすか否かの判定対象から除外して、前記未分類クラスタへ所属させる
ことを特徴とする請求項１または２記載のクラスタリング装置。
【請求項４】
前記制御部は、さらに、
前記未分類クラスタに所属するノードを、前記グラフデータにおけるクラスタ同士を接続させるハブノードもしくはクラスタに所属する１つのノードのみと接続するアウトレイヤノードのいずれかに分類する
ことを特徴とする請求項１、２または３記載のクラスタリング装置。
【請求項５】
コンピュータが、
入力されたグラフデータから、いずれのクラスタにも未所属の第１ノードを選択し、
前記第１ノードおよび該ノードとエッジで接続されるノードの集合である、前記第１ノードの隣接ノード集合を前記グラフデータから取得し、
前記第１ノードの隣接ノード集合に所属する、前記第１ノードとは異なる各第２ノードの隣接ノード集合を前記グラフデータから取得し、
前記第１ノードの隣接ノード集合および前記各第２ノードの隣接ノード集合の類似度を算出し、
前記第１ノードに対して、前記類似度が第１閾値以上となる前記第２ノードの集合である第１近接ノード集合を生成し、
前記第１近接ノード集合の要素数が第２閾値以上となる場合に前記第１ノードが第１条件を満たすと判定し、前記第１近接ノード集合の要素数が第２閾値未満となる場合に前記第１ノードが前記第１条件を満たさないと判定し、
前記第１ノードが前記第１条件を満たすと判定した場合に、前記第１近接ノード集合を新たなインデックスが付与されたクラスタとし、
前記第１近接ノード集合に所属する各ノードおよび該各ノードとエッジで接続されるノードの集合である該各ノードの隣接ノード集合の和集合である第２近接ノード集合を生成し、
前記第２近接ノード集合から前記新たなインデックスが付与されたクラスタを差し引いた第１差集合に所属するノードのなかから、前記新たなインデックスが付与されたクラスタに追加所属させるノードを決定し、
前記第１ノードが前記第１条件を満たさないと判定した場合に、前記第１ノードを未分類クラスタに所属させる
一連の処理を、前記グラフデータの全ノードの所属クラスタが決定するまで繰り返すこと
を含むこと特徴とするクラスタリング方法。
【請求項６】
コンピュータに、
入力されたグラフデータから、いずれのクラスタにも未所属の第１ノードを選択し、
前記第１ノードおよび該ノードとエッジで接続されるノードの集合である、前記第１ノードの隣接ノード集合を前記グラフデータから取得し、
前記第１ノードの隣接ノード集合に所属する、前記第１ノードとは異なる各第２ノードの隣接ノード集合を前記グラフデータから取得し、
前記第１ノードの隣接ノード集合および前記各第２ノードの隣接ノード集合の類似度を算出し、
前記第１ノードに対して、前記類似度が第１閾値以上となる前記第２ノードの集合である第１近接ノード集合を生成し、
前記第１近接ノード集合の要素数が第２閾値以上となる場合に前記第１ノードが第１条件を満たすと判定し、前記第１近接ノード集合の要素数が第２閾値未満となる場合に前記第１ノードが前記第１条件を満たさないと判定し、
前記第１ノードが前記第１条件を満たすと判定した場合に、前記第１近接ノード集合を新たなインデックスが付与されたクラスタとし、
前記第１近接ノード集合に所属する各ノードおよび該各ノードとエッジで接続されるノードの集合である該各ノードの隣接ノード集合の和集合である第２近接ノード集合を生成し、
前記第２近接ノード集合から前記新たなインデックスが付与されたクラスタを差し引いた第１差集合に所属するノードのなかから、前記新たなインデックスが付与されたクラスタに追加所属させるノードを決定し、
前記第１ノードが前記第１条件を満たさないと判定した場合に、前記第１ノードを未分類クラスタに所属させる
一連の処理を、前記グラフデータの全ノードの所属クラスタが決定するまで繰り返して実行させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置などに関する。
【背景技術】
【０００２】
近年、例えば、インターネット上で提供されるソーシャルメディアが普及してきている。ソーシャルメディアの一例としてソーシャルネットワーキングサービスが挙げられる。ソーシャルネットワーキングサービスにおいて、個々のユーザが、他のユーザとの関係を築いていくことを繰り返すにより、各ユーザをエッジ、各ユーザ間の関係をノードと見なしうるグラフデータが構築される。
【０００３】
このようにして構築されたグラフデータは、ユーザ数、ユーザ間の関係がきわめて膨大な数である、いわゆるビッグデータである。このため、グラフ構造のビッグデータを高速にクラスタ解析することが、例えばソーシャルネットワーキングサービスの利便性に資する。そして、ソーシャルネットワーキングサービスに限らず、グラフ構造のビッグデータを高速にクラスタ解析することが求められる局面が多いため、高速クラスタ解析の手法が提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Xiaowei  Xu,  Nurcan  Yuruk,  Zhidan  Feng,  Thomas  A.  J.  Schweiger,  “SCAN:  A  Structural  Clustering  Algorithm  for  Networks,”  SIGKDD’07,  August  12-15,  2007,  San  Jose,  CA,  US.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述の従来技術では、計算量が多く、グラフデータがより大規模化するにしたがい、クラスタ解析の処理時間が膨大になってしまう。
【０００６】
本願が開示する実施形態は、上記に鑑みてなされたものであって、グラフデータのクラスタ解析を高速化することを目的とする。
【課題を解決するための手段】
【０００７】
本願が開示する実施形態の一例は、記憶部と協働してグラフデータのノードのクラスタリング処理を実行する制御部を有するクラスタリング装置であって、前記制御部は、入力されたグラフデータから、いずれのクラスタにも未所属の第１ノードを選択し、前記第１ノードおよび該ノードとエッジで接続されるノードの集合である、前記第１ノードの隣接ノード集合を前記グラフデータから取得し、前記第１ノードの隣接ノード集合に所属する、前記第１ノードとは異なる各第２ノードの隣接ノード集合を前記グラフデータから取得し、前記第１ノードの隣接ノード集合および前記各第２ノードの隣接ノード集合の類似度を算出し、前記第１ノードに対して、前記類似度が第１閾値以上となる前記第２ノードの集合である第１近接ノード集合を生成し、前記第１近接ノード集合の要素数が第２閾値以上となる場合に前記第１ノードが第１条件を満たすと判定し、前記第１近接ノード集合の要素数が第２閾値未満となる場合に前記第１ノードが前記第１条件を満たさないと判定し、前記第１ノードが前記第１条件を満たすと判定した場合に、前記第１近接ノード集合を新たなインデックスが付与されたクラスタとし、前記第１近接ノード集合に所属する各ノードの隣接ノード集合の和集合である第２近接ノード集合を生成し、前記第２近接ノード集合から前記新たなインデックスが付与されたクラスタを差し引いた第１差集合に所属するノードのなかから、前記新たなインデックスが付与されたクラスタに追加所属させるノードを決定し、前記第１ノードが前記第１条件を満たさないと判定した場合に、前記第１ノードを未分類クラスタに所属させる一連の処理を、前記グラフデータの全ノードの所属クラスタが決定するまで繰り返すことを特徴とする。
【発明の効果】
【０００８】
本願が開示する実施形態によれば、例えば、グラフデータのクラスタ解析を高速化することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施形態１のクラスタリング装置の構成を示す機能ブロック図である。
【図２−１】図２−１は、実施形態１のクラスタリング処理における入力グラフデータの一例を示すフローチャートである。
【図２−２】図２−２は、実施形態１のクラスタリング処理におけるクラスタリング結果の一例を示す図である。
【図３】図３は、実施形態１のクラスタリング処理を示すフローチャートである。
【図４】図４は、ステップＳ２６０のサブルーチンを詳細に示すフローチャートである。
【図５−１】図５−１は、実施形態１のクラスタリング処理の具体例を示す図である。
【図５−２】図５−２は、実施形態１のクラスタリング処理の具体例を示す図である。
【図５−３】図５−３は、実施形態１のクラスタリング処理の具体例を示す図である。
【図５−４】図５−４は、実施形態１のクラスタリング処理の具体例を示す図である。
【図６】図６は、実施形態２のクラスタリング処理を示すフローチャートである。
【図７】図７は、ステップＳ３６０のサブルーチンを詳細に示すフローチャートである。
【図８−１】図８−１は、実施形態２のクラスタリング処理の具体例を示す図である。
【図８−２】図８−２は、実施形態２のクラスタリング処理の具体例を示す図である。
【図８−３】図８−３は、実施形態２のクラスタリング処理の具体例を示す図である。
【図８−４】図８−４は、実施形態２のクラスタリング処理の具体例を示す図である。
【図９】図９は、従来技術のクラスタリング処理を示すフローチャートである。
【図１０】図１０は、ステップＳ１５０のサブルーチンを詳細に示すフローチャートである。
【図１１】図１１は、ステップＳ１７０のサブルーチンを詳細に示すフローチャートである。
【図１２】図１２は、実施形態１および実施形態２のクラスタリング処理を実行するコンピュータの構成を示す機能ブロック図である。
【発明を実施するための形態】
【００１０】
以下に、本願が開示するクラスタリング装置などの実施形態を図面に基づいて説明する。なお、以下に複数の実施形態を例示するが、同一の開示事項について、後述の際には説明を省略する。また、以下に示す複数の実施形態は、一例を示すに過ぎず、本願が開示する技術を限定するものではない。また、以下に示す複数の実施形態は、適宜組合せてもよい。
【００１１】
［実施形態１］
（実施形態１のクラスタリング装置の構成）
図１は、実施形態１のクラスタリング装置の構成を示す機能ブロック図である。図１に示す実施形態１のクラスタリング装置２００は、入力部２０１、制御部２０２、出力部２０３を有する。また、クラスタリング装置２００は、グラフデータ記憶部１１０、クラスタリング結果記憶部１２０と接続される。
【００１２】
入力部２０１は、グラフデータ記憶部１１０から、図２−１に例示する入力グラフデータを読み込み、制御部２０２へ出力する。図２−１に例示すように、グラフデータＧは、例えば、ノード集合Ｖ＝｛０，１，・・・，１２，１３｝と、各ノード間を接続するエッジ集合Ｅを含む。すなわち、Ｇ＝｛Ｖ，Ｅ｝である。
【００１３】
制御部２０２は、主記憶装置および処理装置を有する。制御部２０２は、グラフデータ記憶部１１０から入力されたグラフデータを主記憶装置に展開する。そして、制御部２０２は、主記憶装置に展開したグラフデータに対して、後述するクラスタリング処理を実行する。
【００１４】
制御部２０２が実行するクラスタリング処理は、グラフデータのノード集合Ｖを次の（１）−（３）の３つの集合のいずれかへ分類する処理である。
（１）エッジで密に接続されたノード集合Ｃｋからなる集合Ｃ（以降、「Cluster」と呼ぶ）：
Ｃ＝｛Ｃ１，Ｃ２，・・・，Ｃｐ｝（for  ∃ｐ）
（２）Ｃｌｕｓｔｅｒ間を接続するノードの集合Ｈ（以降、「Hub」と呼ぶ）：
Ｈ＝｛Ｈ１，Ｈ２，・・・，Ｈｑ｝（for  ∃ｑ）
（３）ＣｌｕｓｔｅｒでもＨｕｂでもないノードの集合Ｏ（以降、「Outlier」と呼ぶ）：
Ｏ＝｛Ｏ１，Ｏ２，・・・，Ｏｒ｝（for  ∃ｒ）
【００１５】
そして、制御部２０２は、図２−２に例示する、グラフデータをクラスタリング処理したクラスタリング結果を出力部２０３へ出力する。図２−２の例示では、ノード集合｛０，１，２，３，４，５｝がClusterＣ１であり、ノード集合｛７，８，９，１０，１１，１２｝がClusterＣ２であり、ノード集合｛６｝がClusterＣ１とClusterＣ２を接続するHubＨ１であり、ノード集合｛１３｝が、OutlierＯ１である。
【００１６】
出力部２０３は、制御部２０２から出力された処理結果を、クラスタリング結果記憶部１２０へ出力する。なお、図２−１、図２−２に示すグラフデータは、あくまで一例を示すに過ぎない。
【００１７】
（実施形態１のクラスタリング処理）
図３は、実施形態１のクラスタリング処理を示すフローチャートである。制御部２０２は、クラスタリング処理開始に先立ち、図２−１に例示するようなグラフデータＧ＝｛Ｖ，Ｅ｝と、パラメータε，μを入力とする。グラフデータＧは、入力部２０１から入力され、パラメータε，μは、図示しない入力装置もしくは設定ファイルなどから入力される。
【００１８】
制御部２０２は、グラフデータＧおよびパラメータε，μの入力後、グラフデータＧのノードのうち、いずれのクラスタにも未所属の１つのノードｖを、ランダムに選択する（ステップＳ２００）。なお、ステップＳ２００におけるノードｖの選択方法は、ランダムに選択することに限らず、最小次数で選択もしくは最大次数で選択のいずれかの方法であってもよい。ここで、次数とは、ノードに接続されるエッジの数をいう。
【００１９】
次に、制御部２０２は、Γ（ｖ）に含まれる全てのノードｕに対してのみStructural  similarity  σ（ｕ，ｖ）を計算する（ステップＳ２１０）。なお、Γ（ｘ）およびStructural  similarity  σ（ｕ，ｖ）は、以下の［定義１］で定義される。なお、Γ（ｘ）は、ノードｘの隣接ノード集合の一例である。また、σ（ｕ，ｖ）は、ノードｕの隣接ノード集合およびノードｖの隣接ノード集合の類似度の一例である。
【００２０】
【数１】
0006039595.tif 000002
【００２１】
次に、制御部２０２は、Structural  similarity  σ（ｕ，ｖ）の計算結果を元に、ノードｖがパラメータε，μに対してCOREであるか否かを判定する（ステップＳ２２０）。なお、ノードｖ（ｖ∈Ｖ）がCOREであるとは、パラメータε，μに対して、以下の［定義２］で定義されるε-neighborhood  Ｎε（ｖ）が、以下の［定義３］で定義される所定条件を満たすことである。ノードｖがパラメータε，μに関してCOREであることを、COREε，μ（ｖ）と表す。なお、ε-neighborhood  Ｎε（ｖ）は、第１近接ノード集合の一例である。また、εは、最小クラスタサイズを示す、第１閾値の一例である。また、μは第２閾値の一例である。
【００２２】
【数２】
0006039595.tif 000003
【００２３】
【数３】
0006039595.tif 000004
【００２４】
制御部２０２は、ステップＳ２２０で、ノードｖがCOREであると判定した場合（ステップＳ２２０Ｙｅｓ）には、新たなクラスタＩＤとしてＣｉを生成する（ステップＳ２３０）。なお、COREであるとは第１条件を満たすことの一例であり、COREでないとは第１条件を満たさないことの一例である。また、“ｉ”は、０を初期値として、ステップＳ２３０の実行の都度、１インクリメントされるインデックスである。次に、制御部２０２は、次に∀ｕ∈Ｎε（ｖ）のクラスタをクラスタＣｉに決定する（ステップＳ２４０）。
【００２５】
次に、制御部２０２は、ステップＳ２４０で決定したクラスタＣｉを基に、クラスタＣｉの隣接ノード集合であるＲ＝Ｎ（Ｎε（ｖ））＼Ｃｉを取得する（ステップＳ２５０）。なお、Ｎ（Ｎε（ｖ））は、2-hop  neighborhoodと呼び、以下の［定義４］で定義される。2-hop  neighborhood  Ｎ（Ｎε（ｖ））は、第２近接ノード集合の一例である。また、Ｎ（Ｎε（ｖ））＼Ｃｉは、第１差集合の一例である。
【００２６】
【数４】
0006039595.tif 000005
【００２７】
次に、制御部２０２は、2-hop  neighborhoodである集合Ｒを取得後、集合Ｒから派生して取得できるクラスタを抽出し、クラスタＣｉに組み入れて、クラスタＣｉに所属するノードを決定する（ステップＳ２６０）。なお、ステップＳ２６０の処理は、後に詳述する。制御部２０２は、ステップＳ２６０の終了後、ステップＳ２８０へ処理を移す。
【００２８】
一方、制御部２０２は、ステップＳ２２０で、ノードｖがCOREでないと判定した場合（ステップＳ２２０Ｎｏ）には、ノードｖをクラスタnon-memberの所属とし（ステップＳ２７０）、ステップＳ２８０へ処理を移す。なお、non-memberは、COREでないノードが所属するクラスタであり、未分類クラスタの一例である。
【００２９】
ステップＳ２８０では、制御部２０２は、入力されたグラフデータＧの全ノードの所属クラスタが決定したか否かを判定する（ステップＳ２８０）。制御部２０２は、ステップＳ２８０で、入力されたグラフデータＧの全ノードの所属クラスタが決定したと判定した場合（ステップＳ２８０Ｙｅｓ）には、ステップＳ２９０へ処理を移す。
【００３０】
ステップＳ２９０では、制御部２０２は、全てのノードのクラスタが決定された後、non-memberとされたノードをHubまたはOutlierへ分類する処理をおこなう。なお、ステップＳ２９０の処理は、後述する図９のステップＳ１７０と同一である。
【００３１】
一方、制御部２０２は、ステップＳ２８０で、入力されたグラフデータＧの全ノードの所属クラスタが決定されていない、すなわち、クラスタに未所属のノードがあると判定した場合（ステップＳ２８０Ｎｏ）には、ステップＳ２００へ処理を移す。そして、制御部２０２は、ステップＳ２００で、クラスタに未所属のノードｖ∈Ｖを、ランダムに選択する。
【００３２】
（ステップＳ２６０の詳細）
図４は、ステップＳ２６０のサブルーチンを詳細に示すフローチャートである。まず、制御部２０２は、集合Ｒが空集合φであるか否かを判定する（ステップＳ２６１）。制御部２０２は、集合Ｒが空集合φであると判定した場合（ステップＳ２６１Ｙｅｓ）には、図３のステップＳ２８０へ処理を移す。
【００３３】
一方、制御部２０２は、集合Ｒが空集合φでないと判定した場合（ステップＳ２６１Ｎｏ）には、集合Ｒから１つのノードｕを、ランダムに選択する（ステップＳ２６２）。なお、ステップＳ２６２におけるノードｕの選択方法は、ランダムに選択することに限らず、最小次数で選択もしくは最大次数で選択のいずれかの方法であってもよい。
【００３４】
次に、制御部２０２は、Γ（ｕ）に含まれる全てのノードｖに対してのみStructural  similarity  σ（ｕ，ｖ）を計算する（ステップＳ２６３）。なお、Γ（ｘ）（ｘ＝ｕ，ｖ∈Ｖ）およびStructural  similarity  σ（ｕ，ｖ）（ｕ，ｖ∈Ｖ）は、上述の［定義１］と同様である。
【００３５】
次に、制御部２０２は、ノードｕがパラメータε，μに対してCOREであるか否かを判定する（ステップＳ２６４）。制御部２０２は、ステップＳ２６４で、ノードｕがCOREであると判定した場合（ステップＳ２６４Ｙｅｓ）には、クラスタＣｉとＮε（ｕ）の和集合を新たなクラスタＣｉとして更新する（ステップＳ２６５）。なお、Ｎε（ｕ）は、第３近接ノード集合の一例である。
【００３６】
次に、制御部２０２は、ステップＳ２６５でクラスタＣｉを更新したことに応じて、2-hop  neighborhood  ＲをＲ＝｛Ｒ∪Ｎ（Ｎε（ｕ））｝＼Ｃｉとして更新する（ステップＳ２６６）。制御部２０２は、ステップＳ２６６の処理が終了すると、ステップＳ２６１へ処理を移す。なお、Ｎ（Ｎε（ｕ））は、第４近接ノード集合の一例である。また、｛Ｒ∪Ｎ（Ｎε（ｕ））｝＼Ｃｉは、第２差集合の一例である。
【００３７】
一方、制御部２０２は、ステップＳ２６４で、ノードｕがCOREでないと判定した場合（ステップＳ２６４Ｎｏ）には、ノードｕをクラスタnon-memberの所属とし（ステップＳ２６７）、2-hop  neighborhood  ＲをＲ＝Ｒ∪｛ｗ|σ（ｗ，ｕ）≧ε∧Ｃ［ｗ］＝Ｃｉ｝として更新する（ステップＳ２６８）。ただし、Ｃ［ｗ］はノードｗが所属するクラスタを表す。そして、制御部２０２は、ステップＳ２６８の処理が終了すると、ステップＳ２６１へ処理を移す。なお、Ｒ∪｛ｗ|σ（ｗ，ｕ）≧ε∧Ｃ［ｗ］＝Ｃｉ｝は、前記第１差集合と、前記新たなインデックスが付与されたクラスタに所属するノードのうち該ノードの隣接ノード集合および前記第３ノードの隣接ノード集合の前記類似度が前記第１閾値以上であるノードの集合との和集合の一例である。
【００３８】
（実施形態１のクラスタリング処理の具体例）
図５−１、図５−２、図５−３、図５−４は、実施形態１のクラスタリング処理の具体例を示す図である。まず、図５−１を参照し、ノード０に着目すると、ノード０の隣接ノードは、ノード１、ノード４、ノード５、ノード６だが、COREであるノード１、ノード４、ノード５が所属するクラスタＣ１が形成される（図３のステップＳ２００−ステップＳ２４０に対応）。
【００３９】
そして、図５−２を参照し、未選択のノード２に着目すると、ノード２のε-neighborhoodＮε（２）は、ノード１、ノード３、ノード５なので、ノード１、ノード３、ノード５が所属するε-neighborhoodＮε（２）とクラスタＣ１の和集合を、新たなクラスタＣ１として更新する（図３のステップＳ２５０−ステップＳ２６０に対応）。その結果、図５−３に示すようなクラスタＣ１が形成される。
【００４０】
また、図５−３を参照し、未選択のノード６に着目すると、ノード６は、パラメータε，μに対してCOREでないので、non-memberに分類される（図３のステップＳ２２０、ステップＳ２７０に対応）。
【００４１】
同様にして、図５−４に示すように、ノード７、ノード８、ノード９、ノード１０、ノード１１、ノード１２が所属するクラスタＣ２が形成される（図３のステップＳ２００−ステップＳ２４０に対応）。また、図５−４において、未選択のノード１３に着目すると、ノード１３は、パラメータε，μに対してCOREでないので、non-memberに分類される（図３のステップＳ２２０、ステップＳ２７０に対応）。
【００４２】
そして、図５−４において、non-memberに分類されたノード６はHubＨ１と分類され、ノード１３はOutlierＯ１と分類される（図３のステップＳ２８０−ステップＳ２９０に対応）。以上のようにして、Ｇ＝｛Ｖ，Ｅ｝が、クラスタリングされる。
【００４３】
［実施形態２］
（実施形態２のクラスタリング装置の構成）
実施形態２のクラスタリング装置３００は、図１に示すように、実施形態１のクラスタリング装置２００の構成と同様である。クラスタリング装置３００は、クラスタリング装置２００の入力部２０１に対応する入力部３０１、制御部２０２に対応する制御部３０２、出力部２０３に対応する出力部３０３を有する。また、クラスタリング装置３００は、グラフデータ記憶部１１０、クラスタリング結果記憶部１２０と接続される。
【００４４】
（実施形態２のクラスタリング処理）
図６は、実施形態２のクラスタリング処理を示すフローチャートである。図６の実施形態２のクラスタリング処理におけるステップＳ３００−ステップＳ３４０、ステップＳ３７０−ステップＳ３９０は、図３の実施形態１のクラスタリング処理におけるステップＳ２００−ステップＳ２４０、ステップＳ２７０−ステップＳ２９０と同一である。
【００４５】
実施形態２のクラスタリング処理では、ステップＳ３４０に続くステップＳ３５０、ステップＳ３６０が、実施形態１のクラスタリング処理におけるステップＳ２４０に続くステップＳ２５０、ステップＳ２６０と異なる。
【００４６】
ステップＳ３５０では、制御部３０２は、同一のクラスタと既に判定されたＮε（ｖ）および｛∀（ｕ，ｗ）∈Ｅ｜ｕ∈｛Ｖ＼Ｎε（ｖ）｝∧ｗ∈Ｎε（ｖ）｝をそれぞれ１つのノードおよび１本のエッジに集約する。エッジの集約において、クラスタ外のノードをノードｕとすると、weight（ｕ，Ｃｉ）＝｜｛（ｕ，ｗ）∈Ｅ｜∀ｗ∈Ｃｉ｝｜となる重みをノードｕとクラスタＣｉ間を接続するエッジの重みとして付与する。なお、エッジの付与方法の具体例は、後述する。
【００４７】
次に、制御部３０２は、ステップＳ３５０で集約したノードに対してStructural  similarityの上限値および下限値を推定し、Structural  similarityの計算対象を除外しつつ、集合Ｒから派生して取得可能なクラスタＣｉを抽出する（ステップＳ３６０）。なお、ステップＳ３６０の処理は、後に詳述する。制御部３０２は、ステップＳ３６０の終了後、ステップＳ３８０へ処理を移す。
【００４８】
（ステップＳ３６０の詳細）
図７は、ステップＳ３６０のサブルーチンを詳細に示すフローチャートである。図７のステップＳ３６０のサブルーチンにおけるステップＳ３６１、ステップＳ３６２、ステップＳ３６５、ステップＳ３６７−ステップＳ３７０は、図３のステップＳ２６０のサブルーチンにおけるにおけるステップＳ２６１、ステップＳ２６２、ステップＳ２６３、ステップＳ２６５−ステップＳ２６８と同一である。
【００４９】
実施形態２のステップＳ３６０のサブルーチンでは、ステップＳ３６２に続いてステップＳ３６３、ステップＳ３６４が、実施形態２のステップＳ２６０のサブルーチンと比較して追加になる。
【００５０】
ステップＳ３６３では、制御部３０２は、ステップＳ３６２で選択したノードｕと集約されたクラスタｖ間のエッジ（ｕ，ｖ）に対して、以下の［定義５］に基づきStructural  similarityの上限値の推定値を算出し、［定義６］に基づきStructural  similarityの下限値の推定値を算出する。
【００５１】
【数５】
0006039595.tif 000006
【００５２】
【数６】
0006039595.tif 000007
【００５３】
次に、制御部３０２は、σ（ｕ，ｖ）ｍａｘ、σ（ｕ，ｖ）ｍｉｎを用いて、ノードｕがCOREであるか否かの判定対象から除外するか否かを判定する（ステップＳ３６４）。具体的には、制御部３０２は、σ（ｕ，ｖ）ｍａｘ＜εの場合で｜Γ（ｕ）｜−weight（ｕ，ｖ）＜μのとき、ノードｕをクラスタのメンバからの除外対象と判定し（ステップＳ３６４Ｙｅｓ）、ノードｕをクラスタnon-memberの所属とする（ステップＳ３６９）。
【００５４】
また、制御部３０２は、σ（ｕ，ｖ）ｍａｘ＜εの場合で｜Γ（ｕ）｜−weight（ｕ，ｖ）≧μのとき、ノードｕをCOREであるか否かの判定対象と判定し（ステップＳ３６４Ｎｏ）、Γ（ｕ）＼｛ｖ｝に含まれる全てのノードｔに対してのみStructural  similarity  σ（ｔ，ｕ）を計算する（ステップＳ３６５）。そして、制御部３０２は、ノードｕがパラメータε，μに対してCOREか否かを判定する（ステップＳ３６６）。なお、制御部３０２は、σ（ｔ，ｕ）ｍｉｎ≦ε≦σ（ｔ，ｕ）ｍａｘのときは、ノードｕをCOREであるか否かの判定対象から除外しない（ステップＳ３６４Ｎｏ）。
【００５５】
（実施形態２のクラスタリング処理の具体例）
図８−１、図８−２、図８−３、図８−４は、実施形態２のクラスタリング処理の具体例を示す図である。まず、図８−１を参照し、ノード０に着目すると、ノード０の隣接ノードは、ノード１、ノード４、ノード５、ノード６だが、COREであるノード１、ノード４、ノード５が所属するクラスタＣ１が形成される（図６のステップＳ３００−ステップＳ３４０に対応）。
【００５６】
そして、図８−２を参照すると、ノード０、ノード１、ノード４、ノード５が、ノード０に集約される。その際、クラスタＣ１外へのエッジ（２，０）、（３，０）、（６，０）に対して、weight（２，０）＝｜｛（２，１），（２，５）｝｜＝２、weight（３，０）＝｜｛（３，４）,（３，５）｝｜＝２、weight（６，０）＝｜｛（６，０），（６，４）｝｜＝２の重みがそれぞれ与えられる。この際、集約されたノードごとに、Structural  similarityの上限値および下限値の推定値が算出される。
【００５７】
また、図８−３を参照すると、クラスタＣ１は、ノード２、ノード３は、ノード０に集約されている。その際、クラスタＣ１外へのエッジ（６，０）、（６，３）に対して、weight（６，０）＝｜｛（６，０），（６，３）｝｜であるが、（６，０）に対しては既にweight（６，０）＝２の重みが与えられているので、weight（６，０）＝３となる。このようにして、ノード０、ノード１、ノード２、ノード３、ノード４、ノード６は、ノード０に集約される。
【００５８】
この際、集約されたノードのStructural  similarityの上限値および下限値の推定値が算出される。そして、集約されたノードは、Structural  similarityの上限値および下限値の推定値に基づき、COREであるか否かの判定対象に含められる、もしくはCOREであるか否かの判定対象から除外される。
【００５９】
そして、図８−３において、未選択のノード６に着目すると、ノード６は、パラメータε，μに対してCOREでないので、non-memberに分類される（図６のステップＳ３２０、ステップＳ３７０に対応）。
【００６０】
同様にして、図８−４に示すように、ノード７、ノード８、ノード９、ノード１０、ノード１１、ノード１２がノード１２に集約されて所属するクラスタＣ２が形成される（図６のステップＳ３００−ステップＳ３４０に対応）。この際、集約されたノードのStructural  similarityの上限値および下限値の推定値が算出される。そして、集約されたノードは、Structural  similarityの上限値および下限値の推定値に基づき、COREであるか否かの判定対象に含められる、もしくはCOREであるか否かの判定対象から除外される。
【００６１】
また、図８−４において、未選択のノード１３に着目すると、ノード１３は、パラメータε，μに対してCOREでないので、non-memberに分類される（図６のステップＳ３２０、ステップＳ３７０に対応）。
【００６２】
そして、図８−４において、non-memberに分類されたノード６はHubＨ１と分類され、ノード１３はOutlierＯ１と分類される（図６のステップＳ３８０−ステップＳ３９０に対応）。以上のようにして、Ｇ＝｛Ｖ，Ｅ｝が、クラスタリングされる。
【００６３】
［比較例としての従来技術］
（従来技術のクラスタリング装置の構成）
従来技術のクラスタリング装置１００は、図１に示すように、実施形態１のクラスタリング装置２００の構成と同様である。クラスタリング装置１００は、クラスタリング装置２００の入力部２０１に対応する入力部１０１、制御部２０２に対応する制御部１０２、出力部２０３に対応する出力部１０３を有する。また、クラスタリング装置１００は、グラフデータ記憶部１１０、クラスタリング結果記憶部１２０と接続される。
【００６４】
（従来技術のクラスタリング処理）
図９は、従来技術のクラスタリング処理を示すフローチャートである。まず、制御部１０２は、グラフデータＧ＝｛Ｖ，Ｅ｝およびパラメータε，μを入力とする。制御部１０２は、これらのデータが入力されると、全てのグラフのエッジについて、上述したStructural  similarity  σ（ｕ，ｖ）を計算する（ステップＳ１００）。
【００６５】
次に、制御部１０２は、全てのエッジに対してStructural  similarity  σ（ｕ，ｖ）を計算した後、乱数などを用いて任意のノードｖ∈Ｖを選択する（ステップＳ１１０）。次に、制御部１０２は、ノードｖに対してパラメータε，μを用いて、ノードｖがCOREであるかどうかの判定を行う（ステップＳ１２０）。
【００６６】
制御部１０２は、ノードｖがCOREと判定されなかった場合は（ステップＳ１２０Ｎｏ）、ノードｖをクラスタnon-memberの所属とする（ステップＳ１８０）。一方、制御部１０２は、ノードｖがCOREと判定された場合は（ステップＳ１２０Ｙｅｓ）、ノードｖを起点としたクラスタの抽出処理に移行する。まず、新たなクラスタＩＤとして、Ｃｉを生成する（ステップＳ１３０）。
【００６７】
次に、制御部１０２は、ｖ∈Ｎε（ｖ）を待ち行列Queue  Ｑに挿入し（ステップＳ１４０）、待ち行列Ｑに挿入されたノードに対してＣｉに所属するノードの抽出処理を実行する（ステップＳ１５０）。ステップＳ１５０の詳細は、後述する。制御部１０２は、ステップＳ１１０−ステップＳ１６０の処理を全てのノードの所属クラスタが決定するまで継続し（ステップＳ１６０）、全てのノードのクラスタが決定された後（ステップＳ１６０Ｙｅｓ）、クラスタnon-memberの所属ノードをHubまたはOutlierへ分類する処理をおこなう（ステップＳ１７０）。
【００６８】
（ステップＳ１５０の詳細）
図１０は、ステップＳ１５０のサブルーチンを詳細に示すフローチャートである。まず、制御部１０２は、待ち行列Ｑが空集合φか否かを判定する（ステップＳ１５１）。制御部１０２は、待ち行列Ｑが空集合φでない場合（ステップＳ１５１Ｎｏ）に、待ち行列Ｑの先頭にあるノードｙを取り出し（ステップＳ１５２）、ノードｙからDirREACHε，μ（ｙ，ｘ）で定義されるノード集合Ｒを取得する（ステップＳ１５３）。ここで用いるDirREACHε，μ（ｙ，ｘ）は、以下の［定義７］で定義される。
【００６９】
【数７】
0006039595.tif 000008
【００７０】
次に、制御部１０２は、集合Ｒ：Ｒ＝｛ｘ∈Ｖ｜DirREACHε，μ（ｙ，ｘ）｝を取得する（ステップＳ１５３）。次に、制御部１０２は、集合Ｒが空集合φでない場合（ステップＳ１５４Ｎｏ）、集合Ｒから任意のノードｘを選択する（ステップＳ１５５）。一方、制御部１０２は、集合Ｒが空集合φである場合（ステップＳ１５４Ｙｅｓ）、ステップＳ１５１へ処理を移す。そして、制御部１０２は、ステップＳ１５６において、ノードｘの所属クラスタが未決定の場合（ステップＳ１５６Ｙｅｓ）、ノードｘを待ち行列Queue  Ｑへ挿入する（ステップＳ１５７）。一方、制御部１０２は、ステップＳ１５６において、ノードｘの所属クラスタが決定済の場合（ステップＳ１５６Ｎｏ）、ステップＳ１５８へ処理を移す。
【００７１】
次に、制御部１０２は、ノードｘの所属クラスタが未決定もしくはnon-memberの所属とされている場合（ステップＳ１５８Ｙｅｓ）、ノードｘのクラスタをＣｉと決定する（ステップＳ１５９）。一方、制御部１０２は、ノードｘの所属クラスタが決定かつnon-memberの所属とされていない場合（ステップＳ１５８Ｎｏ）、ステップＳ１５４へ処理を移す。集合Ｒと待ち行列Queue  Ｑに含まれる全てのノードに対してこれらの処理が終了した後、すなわち待ち行列Queue  Ｑが空集合φになったとき（ステップＳ１５１Ｙｅｓ）、ステップＳ１６０へ処理を移す。
【００７２】
なお、制御部１０２は、待ち行列Queue  Ｑが空集合φである場合（ステップＳ１５１Ｙｅｓ）に、ステップＳ１６０へ処理を移す。
【００７３】
（ステップＳ１７０の詳細）
図１１は、ステップＳ１７０のサブルーチンを詳細に示すフローチャートである。先ず、制御部１０２は、クラスタnon-memberに、未分類のノードｖが存在するか否かを判定する（ステップＳ１７１）。制御部１０２は、クラスタnon-memberに、未分類のノードが存在場合に（ステップＳ１７１Ｙｅｓ）、クラスタnon-memberから任意のノードｖを一つ選択し、二つ以上のクラスタとエッジで接続しているか判定する（ステップＳ１７２）。制御部１０２は、クラスタnon-memberに、未分類のノードが存在しない場合に（ステップＳ１７１Ｎｏ）、処理を終了する。
【００７４】
制御部１０２は、ノードｖが二つ以上のクラスタと接続している場合（ステップＳ１７２Ｙｅｓ）には、新たなHubのＩＤとしてＨｉを生成し（ステップＳ１７３）、ノードｖをＨｉに分類する（ステップＳ１７４）。なお、“ｉ”は、０を初期値として、ステップＳ１７３の実行の都度、１インクリメントされるインデックスである。
【００７５】
一方、ノードｖが一つ以下のクラスタにしか接続していない場合（ステップＳ１７２Ｎｏ）、新たなOutlierのＩＤとしてＯｉを生成し（ステップＳ１７５）、ノードｖをＯｉに分類する（ステップＳ１７６）。なお、“ｉ”は、０を初期値として、ステップＳ１７５の実行の都度、１インクリメントされるインデックスである。制御部１０２は、以上の処理により、全ノードをCluster、Hub、Outlierのいずれかに分類し、処理を終了する。
【００７６】
上述の従来技術は、計算されたStructural  similarityに基づいてCoreノードの選出およびクラスタリングを行うことから、事前に全てのエッジに対してStructural  similarityを計算する必要がある。Structural  similarityは、最大計算量となる完全グラフの場合、ノード数をＶとするとエッジ数が｜Ｖ｜２であることから、分母の計算量はＯ（｜Ｖ｜２）のオーダとなる。さらに、Structural  similarityは、最大計算量となる完全グラフの場合、ノード数をＶとするとエッジ数が｜Ｖ｜２であることから、分子は２つの集合の積集合を取得する処理が含まれるため計算量Ｏ（｜Ｖ｜２）のオーダの比較計算処理が発生する。
【００７７】
よって、従来技術では、Structural  similarity全体の計算量はＯ（｜Ｖ｜４）のオーダになる。すなわち、従来技術はグラフデータの規模がおおきくなるに伴い計算時間が急激に増加し、クラスタリング処理に膨大な時間を必要とする。
【００７８】
（実施形態１および２の効果）
以上から、実施形態１および２は、Structural  similarityの計算を一部のエッジに対してのみおこなうが、従来技術と同様にクラスタ構造を抽出することができる。そして、実施形態１およびでは、部分的なノードのみを計算対象とすることで、ノード間で共有される隣接ノードの数に比例してStructural  similarityの計算を削減することが可能になる。すなわち、実施形態１および２では、計算対象とするノードの一部のみを効率的に選択することで、エッジに対するStructural  similarityの計算回数を大幅に削減する。このため、クラスタリング処理時間の大幅な短縮を実現する。
【００７９】
さらに、実施形態２では、エッジの集約と、Structural  similarityの推定によるエッジの計算除外により、Structural  similarityの計算回数をさらに削減するができる。すなわち、実施形態２では、ノードの逐次集約と、Structural  similarityの推定手法を用いたエッジの計算対象除外により、Structural  similarityの計算回数をさらに削減し、処理時間の短縮を図ることができる。
【００８０】
以上の実施形態１および２は、Structural  similarityに基づく従来の様々な技術に対して適用可能であり、いずれの技術に対しても結果として得られるクラスタの質を劣化させずにクラスタリングの処理時間を削減させることができる。
【００８１】
（クラスタリング処理を実行するコンピュータの構成）
図１２は、実施形態１および実施形態２のクラスタリング処理を実行するコンピュータの構成を示す機能ブロック図である。図１２示すように、コンピュータ１０００は，ＣＰＵ（Central  Processing  Unit）１１００、内部記憶装置である主記憶装置１２００、外部記憶装置である二次記憶装置１３００、入出力装置１４００、バス１５００を有する。バス１５００は、ＣＰＵ（Central  Processing  Unit）１１００、内部記憶装置である主記憶装置１２００、外部記憶装置である二次記憶装置１３００、入出力装置１４００を接続する。
【００８２】
上述の実施形態１または実施形態２のクラスタリングの処理手順を規定するクラスタリングプログラムが、入出力装置１４００を経由して二次記憶装置１３００に展開され、ＣＰＵ１１００により実行される。これにより、実施形態１および２のクラスタリング装置２００および３００が実現される。クラスタリング装置２００および３００は、二次記憶装置１３００に格納されたグラフデータを入力とし、主記憶装置１２００に展開し、ＣＰＵ１１００により、入力されたグラフデータのクラスタリング処理を実行する。ＣＰＵ１１００は、並列処理命令により、入力されたグラフデータのクラスタリング処理を実行してもよい。
【００８３】
なお、グラフデータは、二次記憶装置１３００に格納されるものに限られない。すなわち、グラフデータは、クラスタリング装置２００または３００としてのコンピュータ１０００に所定のインターフェースを介して接続された記憶装置あるいは通信回線を介して通信可能な遠隔の記憶装置から入力されてもよい。例えば、クラスタリング装置２００または３００としてのコンピュータ１０００は、図１に示すグラフデータ記憶部１１０またはクラスタリング結果記憶部１２０が、外部装置としてネットワーク経由で接続されてもよい。
【００８４】
以上、複数の実施形態を説明したが、本願が開示する技術はこれらの実施形態に限定されるものではない。すなわち、これらの実施形態は、その他の様々な形態で実施されることが可能であり、種々の省略、置き換え、変更を行うことができる。例えば、各装置の分散もしくは統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合することができる。
【００８５】
また、実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。
【００８６】
実施形態１および２ならびにその変形は、本願が開示する技術に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【００８７】
２００、３００  クラスタリング装置
２０１、３０１  入力部
２０２、３０２  制御部
２０３、３０３  出力部
１１０  グラフデータ記憶部
１２０  クラスタリング結果記憶部
【図１】
0006039595.tif 000009
【図２−１】
0006039595.tif 000010
【図２−２】
0006039595.tif 000011
【図３】
0006039595.tif 000012
【図４】
0006039595.tif 000013
【図５−１】
0006039595.tif 000014
【図５−２】
0006039595.tif 000015
【図５−３】
0006039595.tif 000016
【図５−４】
0006039595.tif 000017
【図６】
0006039595.tif 000018
【図７】
0006039595.tif 000019
【図８−１】
0006039595.tif 000020
【図８−２】
0006039595.tif 000021
【図８−３】
0006039595.tif 000022
【図８−４】
0006039595.tif 000023
【図９】
0006039595.tif 000024
【図１０】
0006039595.tif 000025
【図１１】
0006039595.tif 000026
【図１２】
0006039595.tif 000027