DEIM Forum 2014 D6-2

構造的類似度に基づくグラフクラスタリングの高速化
塩川 浩昭†

藤原 靖宏†

鬼塚真†† 日本電信電話株式会社 NTT ソフトウェアイノベーションセンタ
〒 180–8585 東京都武蔵野市緑町 3–9–11
E-mail: †{shiokawa.hiroaki,fujiwara.yasuhiro,onizuka.makoto}@lab.ntt.co.jp
あらましグラフクラスタ分析はグラフの中に存在するコミュニティ構造を理解する上で重要な要素技術である．その中でもノード間の構造的類似度を用いたクラスタリング手法 SCAN は，グラフ中のクラスタを抽出するだけでなく，ハブや外れ値などのノードも併せて抽出可能な手法として知られている．しかしながら，SCAN は全てのエッジに対する計算を行うため，グラフに含まれるエッジ数を |E| とした時に O(|E|) の計算量を要する．この SCAN の計算量は，グラフに含まれるノード数を |V | とした時に，最悪の場合 |E| ≈ |V |2 となることから最悪計算量が O(|V |2 ) とな
り，大規模なグラフへの適用が難しい．本稿では SCAN の高速化手法を提案する．提案手法では，最短ホップ数が 2となる様なノードに接続したエッジのみを計算対象としてクラスタリングを行う．これにより，提案手法は SCAN と同一の結果をより高速に抽出ことを可能にする．本稿では，実データに対する評価実験を行い，SCAN の計算時間を最大で約 70% 短縮することを示した．
キーワード

グラフ，クラスタリング，コミュニティ抽出

1. は じ め にやハブに対してノード単体で接続した構造を有し，多くの場合ノイズとして扱われる．この特性から，ハブや外れ値の抽出は，グラフ構造はデータをノードとエッジで表現した基本的なグラフ構造の理解やマーケティングや情報拡散分析，Web 検索

データ構造であり，情報推薦や情報検索，科学データ分析などなどグラフ構造に基づく幅広い応用に対し有効であることが知の様々な分野で利用されている．特に近年では，数億ノードかられている．そのため，これらの手法はクラスタのみを抽出すら構成される大規模なグラフ構造が登場し，このようなデータ

る従来の手法に対して，より細かな分析を可能にする手法としに対する高速な解析処理技術への需要が高まっている．例えば，て期待されている．

Facebook では 2012 年に 1ヶ月当たりのアクティブユーザ数がその中でも，Xu らによる SCAN [8] は，高速な構造的類似

10 億人，また Twitter では一日当たりの投稿数が 3 億 4000 万度に基づくグラフクラスタリング手法の一つである．SCAN はを突破したと報告されている [1]．このように，大規模グラフは多次元ベクトルデータに対する密度ベースのクラスタリング手

現実に存在し今後も規模をさらに増大させていくことが考えら

法として有名な DBSCAN [14] をグラフ構造に応用した手法でれ，大規模なグラフ構造に対する高速な解析手法は必要不可欠ある．SCAN では，事前に 2 つのパラメータを与えることでクな技術となってくると言える．

ラスタリングを実行する．1 つ目のパラメータはクラスタを構

グラフ構造解析のひとつとして，クラスタリングが挙げられ成する構造的類似度の閾値 ϵ である．2 つ目のパラメータはクる．グラフ構造にはクラスタと呼ばれる相互に密な接続を有すラスタを構成する最小ノード数を示す µ である．これら 2 つのる部分ノード集合が存在する．例えば，Web グラフではトピッ

パラメータ ϵ，µ を基にして，SCAN はグラフ構造からクラス

クの近いページ集合が互いにリンクすることで，トピックの類

タ，ハブ，外れ値の抽出を行う．まず，SCAN はグラフ構造に似したページ群がコミュニティを形成する傾向にある．グラフ

含まれる全てのエッジに対して，構造的類似度を計算する．こ構造中のクラスタは互いに共通した性質を持つことから，グラの構造的類似度は，隣接する 2 つのノード間で共通して隣接す

フ構造の理解や様々なアプリケーションに利用され，重要な要るノード集合の割合，言い換えると 2 つのノードの隣接ノード

素技術となっている．この背景からこれまで Modularity に基集合の積集合の割合を測る尺度として定義されている [8]．全づく手法 [2]，[3]，[4]，[5] や min-max cut による手法 [6]，[7] などてのエッジに対して構造的類似度を計算した後，事前に与えら様々なクラスタリング手法の研究が行われてきた．

れたパラメータ ϵ，µ を満たす，core と呼ばれるクラスタの核構造的類似度に基づいたグラフクラスタリング手法 [8]，[9]，となるノードを見つける．その後，ϵ，µ の制約の下，core を[10]，[11]，[12]，[13] は特に注目を集めているクラスタリング手

中心にクラスタサイズが収束するまでクラスタを拡張してい法である．これらの手法はグラフ構造からクラスタを抽出する

く．いずれのクラスタにも属さなかったノードに対してハブとのみではなく，ハブや外れ値といったノードも併せて抽出する

外れ値の判定を行い処理を終了する．これまでに述べたとおり，ことを可能にする．グラフ構造において，ハブは複数のクラス

SCAN は Modularity による手法や min-max cut による手法

タを橋渡しする構造を持ち，周辺のクラスタに影響力のあるとは異なり，パラメータ ϵ および µ を与えることでノードをクノードとして扱われることが多い．一方で外れ値は，クラスタ

ラスタ，ハブおよび外れ値に分類することができる．

表1

しかしながら，SCAN はその計算量の大きさから大規模なグラフ構造を対象としたクラスタリングは難しい．SCAN では，全てのエッジに対して構造的類似度を計算する．そのため，グ
ラフ構造中のエッジ数を |E| とした時に，O(|E|) の時間計算量が生じる．またグラフ構造中のノード数を |V | としたとき|E| ≈ |V |2 となるような場合，SCAN の時間計算量は最悪計算
量 O(|V |2 ) となる．したがって，近年増加する大規模なグラフ
構造のクラスタリングに膨大な処理時間を要することになる．

記号

|V |
|E|
ϵ
µ
Γ(u)
|Γ(u)|σ(u, v)Nϵ (u)|Nϵ (u)|Kϵ,µ (u)u 7→ϵ,µ v
u →ϵ,µ v

記号の定義

定義
ノード数
エッジ数
クラスタを構成するための構造的類似度の閾値
クラスタに含まれる最小ノード数
ノード u の構造的隣接ノード集合
Γ(u) に含まれるノード数
エッジ (u, v) の構造的類似度
ノード u の ϵ − neighborhood
Nϵ に含まれるノード数
core であるノード u
ノード u からノード v への direct structure reachability
ノード u からノード v への structure reachability

1. 1 本研究の貢献
本稿では以下の問題について取り組む．
［問題定義 1］
（構造的類似度に基づく高速なクラスタリング）

Given: グラフ構造 G = (V, E)，構造的類似度の閾値 ϵ，およびクラスタを構成する最小ノード数 µ．

Find: グラフ構造 G から，クラスタ集合 C ，ハブ集合 H
および外れ値集合 O．
本稿では問題定義 1 を従来よりも大規模なグラフ構造に対し本稿で提案する手法は我々の知る限り，クラスタリングの高速性と正確性の両方を同時に満たす最初の手法である．従来手法である SCAN は高い計算コストを有するものの，クラスタだ
けでなくハブや外れ値を抽出できることから幅広いアプリケー
ションで利用されている．本稿で提案する手法は，既に従来技術が利用されているアプリケーションや将来的に利用が予測される分野において，その処理性能の向上に貢献する．

て適用可能にするため，SCAN と同一のクラスタ集合 C ，ハブ

本稿の構成は，次の通りである．2. 節で本稿の前提となる知集合 H ，外れ値集合 O を高速に抽出するクラスタリング手法

識について概説する．3. 節にて提案手法の詳細について説明し，を提案する．本稿では従来手法 SCAN の計算コストを削減す

4. 節において提案手法の評価と分析を行う．5. 節にて関連研究るために，現実のグラフ構造の高いクラスタ性に着目した．クについて述べ，6. 節にて，本稿をまとめ，今後の課題について

ラスタ性はあるノードの隣接ノード同士が互いエッジで接続し論ずる．

やすい傾向にあるという性質ある．現実のグラフ構造は高いク

2. 事 前 準 備

ラスタ性を持つことから，クラスタを形成しやすく密にエッジで接続した部分グラフ構造を内包していると考えられる．そこ

従来手法 SCAN [8] を基に，本稿の前提について述べる．本で本研究では，全てのエッジに対して構造的類似度の計算を必

稿では無向重みなしグラフ G = (V, E) に対して，クラスタ集要とした SCAN を高速化するために，高いクラスタ性により合 C ，ハブ集合 H および外れ値集合 O を抽出することを考え密なエッジの接続を有する部分グラフ構造の計算を可能な限り

る．表 1 にて本稿で用いる記号とその定義を示す．

回避するような手法を考える．提案手法では，最短ホップ数が従来手法では 2 つのノード間で共有される隣接ノード集合の2 となるような部分ノード集合を抽出し，抽出した部分ノード割合を評価することで構造類似度を計算していく．ここで用いに含まれるノードに接続したエッジについてのみ構造的類似度

る隣接ノード集合は以下のように定義される．

計算を行う．本稿では，本手法で抽出する最短ホップ数が 2 と［定義 1］（構造的隣接ノード集合） u ∈ V とするとき，隣接なる部分ノード集合を 2-hop away ノードと呼ぶ．2-hop away

ノード集合はノード u にエッジで接続するノードとノード u 自ノードに接続するエッジについてのみ構造的類似度の計算を行身から構成される集合 Γ(u) で与えられる．

うことで，高いクラスタ性により密なエッジの接続を有するサ

Γ(u) = {v ∈ V |{u, v} ∈ E} ∪ {u}.

ブグラフ構造を少ない計算回数でクラスタリングする．従来手法である SCAN では，全てのエッジについて構造的類似度計

また先に述べたように，クラスタリングで用いられる 2 ノード算を行う必要があったのに対し，提案手法は 2-hop away ノー間の構造的類似度は定義 1 に基づき以下のように定義される．

ドに接続したエッジのみ構造的類似度計算を行う．ゆえに，ク［定義 2］（構造的類似度） u, v ∈ V ，|Γ(u)| を隣接ノード集合

ラスタリング全体で計算されるエッジの本数を削減することがに含まれるノード数とするとき，ノード u，v 間の構造的類似できる．提案手法はグラフ中のノード数 |V | に対して O(|V |)度は σ(u, v) となる．

の時間計算量を示す．その結果として，提案手法は以下の特性
を有する．

•

高速性:

|Γ(u) ∩ Γ(v)|σ(u, v) = √.
|Γ(u)||Γ(v)|

先に述べた 2 つのアプローチにより，従来手

定義 2 に示したように，ノード u，v 間の σ(u, v) は共有され

法 SCAN に対して高速にクラスタリングを行うことができる．

るノードがない場合 σ(u, v) = 0，互いに全て共有する場合に

•

正確性:

提案手法で用いるアプローチは，SCAN におけるクラスタの定義を満たす． したがって，問題定義 1 において SCAN と同一のクラスタを得ることができる．

•

運用性:

は σ(u, v) = 1 となる．
構造的類似度に基づくクラスタリング手法 SCAN はクラス
タを構成するための類似度の閾値として ϵ を導入し，類似度 ϵ

提案手法は事前計算を必要とせず，グラフ構以上で接続する隣接ノード集合 ϵ-neighborhood を定義する．

造 G と 2 つのパラメータ ϵ，µ を与えることによりクラスタリ［定義 3］（ϵ-neighborhood） u ∈ V ，ϵ ∈ R とするとき，ϵ-ングを実行できる．

neighborhood Nϵ (u) は以下のように定義される．

Nϵ (u) = {v ∈ Γ(u)|σ(u, v) >= ϵ}.
ここで，クラスタを構成する最小ノード数としてパラメータ µを導入し，特別なノードのクラスとして core を定義する．
［定義 4］（Core） u ∈ V ，ϵ ∈ R，µ ∈ N および |Nϵ (u)| をノード u における ϵ-neighborhood のノード数とするとき，core は
以下のように定義される．

Kϵ,µ (u) ⇔ |Nϵ (u)| >= µ.
従来手法では定義 4 を満たす core ノード u をクラスタの中心として，Nϵ をクラスタのメンバとして同一のクラスタに所属させる．この手順により，パラメータ ϵ，µ を用いてクラスタの形を決定し，µ を用いてクラスタの最小サイズを定める．この考えは direct structure reachability として以下に定義される．
［定義 5］（Direct structure reachability） u, v ∈ V ，ϵ ∈ R お
よび µ ∈ N とするとき，ノード u とノード v における direct

structure reachability u 7→ϵ,µ v は以下のようになる．

［定義 8］（ハブ） クラスタ集合 C ，ハブ集合 H とすると，ノード h ∈ V がハブである (e.g. h ∈ H) 必要十分条件は (1)h∈/ ∀Ci ∈ C ，(2) u, v ∈ Γ(h) s.t u ∈ Ci , v ∈ Cj , i =| j．
［定義 9］（外れ値） クラスタ集合 C ，ハブ集合 H ，外れ値集
合 O とすると，ノード o ∈ V が外れ値 (e.g. o ∈ O) である必要十分条件は o ∈/ C ∧o∈/ H．

2. 1 SCAN のアルゴリズム
従 来 手 法 SCAN の ア ル ゴ リ ズ ム を Algorithm1 に 示 す．

SCAN はグラフ構造中の全てのエッジを全て走査することにより，与えられたパラメータに応じた全ての structure-connected
クラスタを抽出する．クラスタが決定しなかったノードに対してハブもしくは外れ値のいずれであるか判定を行う．

structure-connected クラスタの抽出アルゴリズムについて述べる．SCAN の開始時点において，全てのノードは unclassiﬁedというクラスタに所属させる．SCAN は unclassified となっている各ノードに対して，そのノードが core の条件を満たすかどうか判定を行う．この際に，SCAN が選択した unclassified な

u 7→ϵ,µ v ⇔ Kϵ,µ (u) ∧ v ∈ Nϵ (u).

ノードの構造的隣接ノード集合に含まれる全てのノードに対し

定義 5 はノード u，v が core である場合対称であるが，どちらて，構造的類似度を計算する必要がある．SCAN が判定を行ったか一方が core でない場合には非対称となる．ゆえに，u 7→ϵ,µ v

ノードが core の時，このノードを中心に structure-connected

かつノード v が core でない場合，ノード v は Kϵ,µ (u) が構築

クラスタの探索を実行し，ノードが core で無かった場合には，するクラスタの境界に面したノードとなる．本稿ではこのようそのノードを non-member というクラスタに所属させる．

なノード v を border と呼ぶ．定義 5 をより一般的な形に拡張

SCAN は core と判定されたノードを中心にクラスタを探索すした structure reachability を示す．

るために，新たなクラスタ ID として clusterID を生成する．以［定義 6］（Structure reachability） u, v ∈ V ，ϵ ∈ R および後の処理では，core と判定されたノードから structure reacha-µ ∈ N とすると，ノード u とノード v における structure

bility で到達可能な全てのノードの所属クラスタを clusterID とreachability u →ϵ,µ v は以下に定義される．

していく．まず，SCAN はキュー Q へ core と判定されたノー

u →ϵ,µ v s.t. (ui 7→ϵ,µ ui+1 ) ∧ (u1 = u) ∧ (un = v).

ドの ϵ-neighborhood に含まれる全てのノードを挿入する．そして，キュー Q に入力された全てのノードに対して，direct

ここで定義された structure reachability は推移律を満たし，

structure reachable となるノード集合 R を計算する．R を求め

非対称である．この structure reachability は direct structure

るために SCAN はキュー Q に含まれる全てのノードの全ての

reachability の推移閉包であるり，定義 5 の対称性から，推移閉

構造的隣接ノードに対して構造的類似度を計算する．最後に R

包の構成要素である u1 , . . . , un−1 は core ノードである必要がに含まれるノードの所属クラスタが unclassified の場合，新たある．core 同士が direct structure reachability を示す時，そにキュー Q へと挿入する．R に含まれるノードが unclassified

れらの ϵ-neighbor は同一クラスタに属することになる．この考もしくは non-member の場合，先に生成した clusterID を割り

えは structure connected クラスタとして以下に定義される．

当てる．この処理をキュー Q に含まれるノードがなくなるまで［定義 7］（Structure-Connected クラスタ） ノ ー ド u ∈ V ，

継続し，structure-connected クラスタの抽出を行う．

ϵ ∈ R および µ ∈ N とすると，Kϵ,µ (u) から求まるクラス

次に，ハブと外れ値の判定アルゴリズムについて述べる．全て

タ C[u] ∈ C が structure-connected クラスタである必要十分のノードに対する structure-connected クラスタの抽出処理が条件は (1) u ∈ C[u]; (2) ∀v ∈ V , u →ϵ,µ v ⇔ v ∈ C[u]．

終了した後，SCAN は全ての non-member となったノードを走

この定義より，structure-connected クラスタはその中に含まれ査しハブと外れ値の判定を行う．このとき，ある non-member

る core により一意に決めることができることがわかる．ここで，のノードが 2 つ以上の異なるクラスタに隣接している場合は，border ノードは，複数のクラスタの core から direct structure

このノードをハブと判定し，1 つ以下のクラスタにのみ隣接しreachability となる可能性があることに注意されたい．この場ている場合には外れ値と判定する．

合，border ノードは border ノード自身が core でない限り，複数のクラスタに属する．

SCAN は全てのノードの構造的隣接ノード集合に含まれるノードに対して，構造的類似度計算を行う必要がある．したがっパラメータ ϵ, µ に対するクラスタリング結果が C で与えらて，SCAN の時間計算量は O(|E|) となり，|E| ≈ |V |2 に近づれる時，ノード集合 V にはいずれのクラスタ集合 C にも属さく場合，最悪計算量として O(|V |2 ) の計算量を必要とする．

ないノードが存在する場合がある．これらのノードはハブもし
くは外れ値に分類される．

Algorithm 1 SCAN

なるノード集合に接続したエッジに対する構造的類似度計算を

Require: G = (V, E), ϵ ∈ R, µ ∈ N;
Ensure: clusters C, hubs H, and outliers O;
1: for each unclassified node u ∈ V do2:
if Kϵ,µ (u) then3:
generate new clusterID;
4:
insert ∀x ∈ Nϵ (u) into queue Q;
5:while Q =| ∅ do6:y ∈ Q;
7:
R = {x ∈ V |y 7→ϵ,µ x};
8:
for each x ∈ R do
if x is unclassified then9:10:
insert x to queue Q;
11:
end ifif x is unclassified or non-member then
12:
13:
assign current clusterID to x;
14:
end if15:
end forremove y from Q;
16:
17:
end while
18:
else
19:
assign non-member to u;
20:
end if
21: end for
22: for each non-member node u do23:
if ∃x, y ∈ Γ(u), x.clusterID =| y.clusterID then24:label u as hub;
25:
else
26:
label u as outlier ;27:
end if
28: end for

削減することができる．
提案手法は 2 つの利点を有する．1 つ目は，現実世界に数多く存在する複雑ネットワークに対して，従来手法 SCAN よりも高速にクラスタリングできるという点である．複雑ネットワー
クは，先に述べた様に高いクラスタ性を有することが知られている．このような特性をもつ現実のグラフデータに提案手法を用いることで，数多くのエッジに対する構造的類似度計算を少数のエッジに対する構造的類似度計算により補完し，計算量を削減することができる．具体的には，ノード数が |V | となるグ
ラフ構造に対して O(|V |) の時間計算量でクラスタリングを実行することができる．

2 つ目は，クラスタリング結果の正確性である．提案手法
は，従来手法の SCAN と異なり，一部のエッジに対してのみ
構造的類似度の計算を行うが，出力されるクラスタ，ハブ，および外れ値は同一のパラメータに対して同一の結果を出力す

3. 提 案 手 法る．その理由として 2-hop away ノード集合のクラスタ包含性という特性が挙げられる．提案手法は，計算量削減のため，

本節では提案手法について概説する．提案手法は従来手法と2-hop away ノード集合を逐次的に選択していくが，選択した同一のクラスタリング結果をより高速に抽出することができる．

ノード集合とその隣接ノードから構成されるサブグラフ構造内

最初に提案手法を構成する基本的なアイデアについて述べ，そに structure-connected クラスタが完全に包含される特性を有の詳細について 3. 2 節以降で説明する．

する．言い換えると，提案手法で選択した 2-hop away ノード

3. 1 基本アイデア

集合で到達不可能なノードは structure-connected クラスタに従来手法である SCAN ではグラフ構造中の全てのエッジ E に含まれないということが保証されている．ゆえに，クラスタの対し類似度計算を行うことから，従来手法は最悪の場合 O(|V |2 )正確性が保証されている．2-hop away ノード集合のクラスタの時間計算量を要する．ゆえに，クラスタリングにかかる時間

包含性の詳細については 3. 3 節で述べる．

を短縮するためには，構造的類似度が計算されるエッジの数を

3. 2 2-hop away ノードによるクラスタリング

減らすことが重要である．

提案手法は，任意のノード u を選択し，そのノード u に接続

そこでまず本稿ではグラフのクラスタ性に着目した．グラフ

した全てのエッジに対して構造的類似度を計算する．類似度計のクラスタ性とは，エッジで接続する 2 つのノード u，v と，算後，ノード u を起点に 2-hop away ノード集合を取得する．

同じくエッジで接続する 2 つのノード v ，w が存在するときに，起点とされるノード u を本稿では pivot と呼び，ノード u を

ノード u，w がエッジで接続している割合を表したものである．

pivot とする 2-hop away ノード集合の定義を以下に示す．

一般的に現実のグラフ構造では高いクラスタ性を示すことが知［定義 10］（2-hop away ノード集合） ノード u ∈ V を pivot，

られており，本研究でクラスタリングの対称とするグラフ構造

ノード w を w ∈ Nϵ (u)\{u} とするとき，ノード u に対するも例外ではない．このことから，グラフ構造中の多くのノード

2-hop away ノード集合 H(u) は，は高い確率でその隣接ノード同士がエッジで接続されていると考えられる．また同様に，エッジで接続した隣接ノード同士はH(u) = {v ∈ V |(u, v) ∈/ E ∧ (v, w) ∈ E},

他のノードから共に接続されている確率も高い．すなわち，あで与えられるノード集合である．

るノードの隣接ノード集合は他のノードの隣接ノード集合であ

定義 10 で与えられる，ノード u の 2-hop away ノード集合は，る可能性が高く，パラメータ µ が適切に設定されている状態を

Nϵ (u) に含まれるノードに隣接し，ノード u からの最短ホップ仮定すると，隣接ノード集合に隣接するノードについてのみ構

数が 2 となるノードの集合である．ここで従来手法 SCAN で造的類似度を計算することで，隣接ノード集合に対する構造的はノード u の隣接ノード集合 Γ(u) に含まれる全てのノードに類似度計算を補完することができると考えられる．

接続したエッジについて構造的類似度を計算した．これに対し，

そこで提案手法では，時間計算量 O(|V |2 ) を削減するため

提案手法は Γ(u) に含まれるノードに接続したエッジについてはに，最短ホップ数が 2 となるような部分ノード集合を抽出し，構造的類似度を計算せず，定義 10 により取得した 2-hop away

抽出した部分ノード集合に含まれるノードに接続したエッジにノードに含まれるノードに接続したエッジに対してのみ構造的ついてのみ構造的類似度計算を行う．本稿では最短ホップ数が類似度を計算する．これにより，提案手法は pivot であるノー2 となるような部分ノード集合を 2-hop away ノード集合と呼ド u にに関する構造的類似度計算を削減する．

び，その詳細については 3. 2 節で定義する．このような方式を

その後，H(u) に含まれる全てのノードを pivot とし，新た採ることで，2-hop away ノード集合から最短ホップ数が 1 とに選択された pivot に基づき 2-hop away ノード集合を拡張す

る．この際に，2-hop away ノード集合を拡張する時点までに選

Algorithm 2 Proposed method

択された pivot から direct structure reachable とされたノーRequire: G = (V, E), ϵ ∈ R, µ ∈ N;
Ensure: clusters C, hubs H, and outliers O;
1: for each unclassified node u ∈ V do
2:
P = {u};3:
if Kϵ,µ (u) then4:
generate new clusterID id;
5:
assign id to ∀v ∈ Nϵ (u);
6:
else
7:
label u as non-member ;8:
end if ∪while { ∀u∈P H(u)}\P =| ∅ do9:∪10:for v ∈ { ∀u∈P H(u)}\P do

ド集合は拡張された 2-hop away ノード集合から除外する．本
稿では拡張された 2-hop away ノード集合を拡張 2-hop away
ノード集合と呼び，以下に定義する．
［定義 11］（拡張 2-hop away ノード集合） ノード un を新たに選択した pivot，ノード u1 , u2 , . . . , un−1 ∈ V をノード un
が pivot として選択される以前に選択された pivot とする．ただし，ノード ui−1 と ui に対して，ノード ui−1 が先に選択されたものとする．また，ノード w を w ∈ Γ(un ) とする．このとき，un が pivot として選択された際に得られる拡張 2-hop

11:
12:
13:
14:
15:
16:
17:
18:

if Kϵ,µ (v) thengenerate new clusterID id;
assign id to ∀v ∈ Nϵ (v);elselabel v as non-member ;end ifend for ∪for u ∈ { ∀u∈P H(u)}\P do

19:
P = P ∪ H(u);20:
end for21:
end while
22: end for
23: while each node u which labeled as several id do∪n−1
24:number of ids < µ thenH(un)={v ∈ V |(u, v) ∈/ E∧(v, w) ∈ E∧v ∈/ i=0 Nϵ (ui )∪H(ui )}, 25: if thecompute structural similarities for non-evaluated edges
26:
end if27:
if Kϵ,µ (u) then
で与えられるノード集合である．
28:
u is core;29:
refine cluster ids
提 案 手 法 は 選 択 し た pivot の 集 合 を P と す る と き ， 30: end if
31:
end
while
∪
32: for each non-member node u do
{ n
i=0 H(ui )}\P = ∅ となるまで，拡張 2-hop away ノード
33:
if ∃x, y ∈ Γ(u), x.clusterID =| y.clusterID then34:label u as hub;
集合を取得し，取得したノード集合に接続するエッジに対して
35:
else
∪
36:
label u as outlier ;構造的類似度を計算する．ノード集合 { n37:
end ifi=0 H(ui )}\P が収束
38: end foraway ノード集合 H(un ) は，する条件は (1) 提案手法が全てのノードを走査し終えた場合，∪
もしくは，(2) ni=0 Nϵ (ui ) が収束した場合の 2 通りである．
我々の検証では，事前に与えられるパラメータ ϵ および µ は極よるものである．文献 [8] では，“an ϵ value between 0.5 andめて小さい場合を除き，提案手法は (2) の理由で収束する．

0.8 is normally suﬃcient to achieve a good clustering result.

提案手法では，グラフ中に未計算のノードが存在する限り定We recommend a value for µ, of 2.” と示されている．この知義 10 および定義 11 で定義される（拡張）2-hop away ノード

見に従い，よいクラスタが得られる µ = 2 をパラメータとして集合の取得と構造的類似度の計算を繰り返す．提案手法のアル与えた場合，複数のクラスタに属するノードは自明に core とな

ゴリズムの詳細については Algorithm2 を参照されたい．

る．以上の理由から現実のグラフ構造に対しては計算量の増加

3. 2. 1 非計算対象ノードの後処理が回避されている．実際に我々の評価実験では，未計算のエッ提案手法では定義 7 で与えられた structure-connected クラジに対する構造的類似度計算の計算は一度も発生せず，かつ，スタと同一のクラスタを抽出するために，2 つ以上のクラスタ

core の判定に要する時間もクラスタリング全体にかかる計算時に属する未計算のノードに対して後処理を行う．

間に対して無視できる程度に小さいという結果が得られている．

2 つ以上のクラスタに属するノードは，そのノードが core で

3. 3 提案手法の正確性ある場合，定義 6 により隣接するクラスタが同一の structure-

提案手法により抽出されるクラスタの正確性について証明すconnected クラスタとなる．ゆえに，2 つ以上のクラスタに属る．本稿でいう正確性とは同一のグラフ構造およびパラメータするノードが存在する場合，そのノードが core となるかを判定を与えた際に，従来手法である SCAN と同一のクラスタリンする必要がある．提案手法では所属クラスタ数の多いノードかグ結果を出力することである．

ら順に選択し，所属クラスタ数がパラメータ µ 以上の場合には，クラスタの正確性を示すためには，2-hop away ノード集合

類似度計算を必要とせずに core と判定し，関連するクラスタ

によって計算されるノード集合が 2-hop away ノード集合に含のクラスタラベルを更新する．上記の処理が終了した後，依然まれる core ノードが構築する structure-connected クラスタをとして複数のクラスタに属しているノードについてのみ，未計全て含んでいる必要がある．これは 2-hop away ノード集合の算のエッジに関して構造的類似度を計算し core の判定を行う．

クラスタ包含性により証明できる．まず本節ではクラスタ包含

この後処理は，一見すると提案手法の計算量を従来手法 SCAN性を示すために，2-hop away ノード集合の non-direct struc-と同等のものに近づけてしまう手法にみえる．しかしながら，

tural reachability を補題 1 で示す．補題 1 では，拡張 2-hop

2 つの理由により計算量の増加が回避されている．第 1 の理由

away ノード集合の抽出が収束した際に得られた pivot 集合をは，複数クラスタに属する全てのノードを後処理する必要がcore に隣接するノードは複数存在することが示唆される．このP ，pivot 集合に含まれるノードの ϵ-neighborhood の和集合を∪∀u∈P Nϵ (u) とする．また，2-hop away ノード集合抽出時に∪得られるノード集合を VH = { ∀u∈P Nϵ } ∪ P とする．

ような場合，複数存在するノードのうち，どれか一つでも core

［補題 1］（non-direct structural reachability） 拡張 2-hop away

であることが判明すれば，その他のノードについては後処理すノード集合抽出時に走査されるノードの部分集合を VH ，それる必要がない．第 2 の理由は，先行研究 [8] に示された知見にに含まれない全てのノード集合を V H = V \VH とするとき，ない点である．グラフ構造のクラスタ性に着目すると，同一の

{∪ni=0 H(ui )}\P = ∅ ならば，{∀(u, v) ∈ E|u ∈ VH ∧v ∈ V H }106に対して σ(u, v) < ϵ が成立する．

105

ド u は自明にノード v の ϵ-neighborhood に含まれる．ノード v∪
は VH に含まれることから，v ∈ P もしくは，v ∈ ∀u∈P Nϵ (u)∪である．v ∈ P のとき，u ∈ ∀u∈P Nϵ (u) となることから，∪n∪{ i=0 H(ui )}\P = ∅ に矛盾する．v ∈ ∀u∈P Nϵ (u) のとき∪
u ∈ P となることから，同様に { ni=0 H(ui )}\P = ∅ に矛盾∪nする．ゆえに { i=0 H(ui )}\P = ∅ ならば，{∀(u, v) ∈ E|u ∈VH ∧ v ∈ V H } に対して σ(u, v) < ϵ となる．

□

Wall clock time [s]証明 背理法により証明する．まず，u ∈ VH ，v ∈ V H に対して

σ(u, v) >= ϵ となるエッジが存在すると仮定する．仮定より，ノー

SCAN
Proposal

104

103

102

101

100

CondMat

図1

HepPh

Email

DBLP

GoogleWikipedia

クラスタリング実行時間の比較

補題 1 より，拡張 2-hop away ノード集合の抽出が収束した際の部分ノード集合 VH は構造的類似度が ϵ よりも小さなエッ|−kの計算量は O( |Vβk
βk + k + C) = O(|V | + C) = O(|V |)． □ジでのみ V H と接続する．これにより，補題 2 に示す（拡張）一般にグラフ構造において |V | ≪ |E| であるため，提案手法は2-hop away ノード集合によって得られる部分ノード集合 VH

従来手法 SCAN よりも少ない計算量でクラスタリングを実行のクラスタ包含性が証明できる．

することができる．

［補題 2］（VH のクラスタ包含性） ノード u ∈ {u ∈ V |u ∈VH ∧ Kϵ,µ (u)} とし，ノード u による structure-connected ク
ラスタを C[u] とした時，∀v ∈ C[u] ⇒ v ∈ VH が成立する．
証明

4. 評 価 実 験
提案手法の有効性を評価するために，我々の提案したその高

補 題 1 よ り，VH は 構 造 的 類 似 度 が ϵ よ り 小 さ な エ

速化手法および Xu らによる SCAN [8] に対し，処理の高速性

ッジ に の み 接 続 し て い る ．定 義 6，定義 7 より，structure-

およびクラスタリング結果の正確性の観点から比較評価を行

connected クラスタは direct structure-connected である必要う．本実験には CPU が Intel Xeon Quad–Core L5640，メモがあるため，構造的類似度が ϵ より小さなエッジで接続した

リが 144GB の Linux サーバを利用する．また，提案手法およ

ノードは strcuture-connected クラスタに含まれない．従って，

び SCAN は gcc–g++ 4.1.2 を用いて実装した．

∀v ∈ C[u] ⇒ v ∈ VH が成立する．

□

4. 1 高 速 性

補題 2 により，2-hop away ノード集合に基づくクラスタリン

本実験では，グラフ構造とパラメータ ϵ および µ を与えた後，グ手法がクラスタの精度に影響を与えないことを示した．このクラスタリング処理が終了するまで処理を行った際の処理時間ことから正確なクラスタを抽出するためには，2-hop away ノーを示し比較を行う．本実験で用いたパラメータは文献 [8] で用ド集合に基づくアプローチにより構造的類似度計算が削減されいられているものと同一のものを利用し，いずれのデータセッ

たノードに対する core 判定を行う必要があるが，ここで述べトに対しても ϵ = 0.7，µ = 3 とした．本実験に用いたデータ

た core 判定は前節で述べた非計算対象ノードへの後処理によっセットは Stanford Large Network Analysis Project （注 1）からて対応される．ゆえに，提案手法は定義 7 と同一のクラスタを

以下のデータセットを使用した．またデータセットの統計情報抽出することが可能となる．

を表 2 に示す．

3. 4 計算量分析
最後に本節で提案手法の計算量を分析する．ノード数 |V |，実験結果を図 1 に示す．縦軸が対数表示となっていることに注意されたい．図 1 に示したように，いずれのデータセットに

エッジ数 |E| のグラフ構造に対する計算量を定理 1 に示す．

対しても提案手法は従来手法 SCAN に対して約 40% から 約

［定理 1］（提案手法の計算量） 2-hop away ノード集合に基づ70% 計算時間を短縮している．特にクラスタ係数の大きなデー

く提案手法は O(|V |) の計算量を要する．
証明 各ノードの平均次数を k ，クラスタ係数を c とした時に

β = 1 − c と仮定する．これらの仮定から，各 pivot に対する計算量を考える．2-hop away ノード集合を求める際に与えられタセットである Google では計算時間を 69.9% 短縮しており，最も大きく計算時間を短縮できている．これに対し，クラスタ
係数の極めて小さな Wikipedia では，計算時間の短縮率が最も小さく 37% という結果を得た．

る最初に pivot に対しては，次数全てに対して構造的類似度を

この結果から，提案手法は従来手法に対してより高速に構造計算することから O(k)．それ以外の pivot については，平均的的類似度に基づくクラスタの抽出ができることを示した．またに ck 本のエッジが他の pivot と共有されているとかんがえら

特に，クラスタ係数の大きな複雑ネットワークに対して提案手れるため，構造的類似度を必要とする計算量は O(βk)．さらに

法は有効であることを示した．

2-hop away ノード集合に含まれる pivot ノードの数は，pivotの隣接ノードになったノードが pivot にならない点から，最大|−k
で |Vβk．非計算対象ノードに対する後処理を O(C)，ただしC ≈ 0，とおくと，各 pivot 辺りの計算量と pivot 数から全体

4. 2 正 確 性
提案手法と従来手法 SCAN の出力するクラスタリング結果の正確性について評価を行う．クラスタリング結果の比較には（注 1）：http://snap.stanford.edu/index.html

表 2 データセットの詳細
DatasetAcronym|V |ca-ComdMat

CondMat23,133cit-HepPh

HepPh

34,546

email-Enron

Email36,692

com-DBLP

DBLP

web-Google
wiki-Talk|E|

Average cluster coeﬃcient

Diameter90-percentile eﬀective diameter

Source93,497

0.6334

14

6.5

[15]

421,5780.2848

12

5

[16]

367,6620.4970

11

4.8

[17]

317,080

1,049,866

0.6324

21

8

[18]

Google875,713

5,105,039

0.5143

21

8.1

[17]

Wikipedia

2,394,385

5,021,410

0.05269

4[19]

表 3 ARI の比較結果
Dataset

SCAN

Proposal

5. 1 Modularity に基づく手法

College football (ϵ = 0.5, µ = 2)

1.0

1.0

Modularity とは Newman らにより提案されたクラスタの質

Political books (ϵ = 0.35, µ = 2)

0.708

0.708

を評価する指標である [21]．Modularity は与えられたクラス
タ構造がランダムグラフの構造から離れているほど良いスコア

調整ランド指数 (ARI: Adjusted Rand Index) [20] を用いた．

を示す．言い換えると，クラスタ内部のエッジ接続が密であり，

ARI はクラスタの正解ラベルに対してするクラスタリング結

クラスタ間のエッジ接続が疎であるようなクラスタ程良いスコ

果の一致度を評価する指数であり，1 に近づくほどよい高い一アを示す．このことから Modularity に基づくクラスタリング

致度があることを示す．ARI の詳細については文献 [20] を参照

手法 [2]，[3]，[4]，[5] では Modualrity の値を最適化することでクされたい．本稿では正解クラスタラベルが与えられている以下

ラスタを抽出する．

のデータセットに対して，クラスタリング結果の ARI を比較した．

•

Modularity に基づくこれらのクラスタリング手法は比較的大規模なグラフ構造に対しても高速にクラスタを抽出できる

College football [21]： 2006 年の NCAA フットボー

手法として知られている．特に，Blondel らによる手法 [4] やル (Division 1-A) の対戦スケジュールを基に作成したグラフ構

Shiokawa らによる手法 [5] では，数億ノード規模以上のグラフ造である．ノード数 180，エッジ数 787 であり，ノードがフッ構造をそれぞれ数時間から数分で処理可能としている．しかしトボールチームの所属校，エッジが対戦スケジュールを表す．

ながら，Modularity に基づくこれらの手法では，グラフ構造

このデータセットでは，所属校が 11 のグループに分割されて中からハブや外れ値などの役割をもつノードを抽出できない．

いる．本稿では文献 [8] に基づき ϵ = 0.5, µ = 2 とし，提案手

5. 2 構造的類似度に基づく手法

法と従来手法 SCAN を適用した．

本稿の対象である構造的類似度に基づくグラフクラスタリン•（注 2）（注 3）：Aamazon.com で販売され

グ手法 [8]，[9]，[10]，[11]，[12]，[13] は，データマイニング分野にるアメリカの政治学に関する本の購買履歴を基に作成されたグ

おいて近年利用され始めているグラフクラスタリング手法であラフ構造である．ノード数は 105，エッジ数は 441 であり，ノーる．この手法では事前にクラスタを構成するための類似度の閾

ドが本，エッジが同一の消費者によって購入された事実を表す．

値 ϵ とクラスタを構成する最小ノード数 µ をパラメータとしてこのデータセットでは，各本は liberal ，neutral ，conservative

与える．これにより任意の大きさ，形状のクラスタを抽出できの 3 グループに分割されている．本稿では文献 [8] に基づきるだけではなく，クラスタに併せてハブや外れ値といったノー

ϵ = 0.35, µ = 2 とし，提案手法と従来手法 SCAN を適用した．

ドを抽出することが可能である．

Political books

各データセットに対する ARI の比較結果を表 3 に示す．表

代表的な手法として Xu らによる SCAN [8] が挙げられる．

3 に示すように，同一のデータセットに対して同一のパラメー

SCAN は多次元ベクトルデータに対する密度ベースのクラスタタが与えられる時，提案手法の ARI は従来手法 SCAN の示すリング手法としてよく知られている DBSCAN [14] の概念をグ

ARI と一致する．すなわち，提案手法は正解ラベルに対して従ラフ構造に適用した手法である．1. 節で述べたように，事前に来手法 SCAN と同等の ARI を示すクラスタリング結果を出力

全てのエッジに対して構造的類似度を計算し，パラメータ ϵ，µ

していることがわかる．

に従い，クラスタの核となる core と定義されるノードを見つ

5. 関 連 研 究ける．その後 SCAN は検出された core を中心にクラスタを拡張し，最終的にクラスタに属するノード集合とそれ以外の集合

グラフ構造中からクラスタを抽出するグラフクラスタリンにノードを分類する．クラスタに属さなかったノード集合のう

グはデータマイニング分野において重要な技術であり，これまち，2 つ以上のクラスタに接続しているノードについてはハブ，

で min-max cut [6] や normalized cut [7]，Modularity に基づ

それ以外のノードは外れ値と判定される．

く手法 [2]，[3]，[4]，[5] など，数多く研究されてきた．本節ではSCAN では全てのエッジに対して構造的類似度の計算を行う

これらの中でも特に，一般的によく利用される Modularity にことでクラスタリングを実行する．したがって，クラスタリン

基づく手法および，本稿の議論の対象である構造的類似度に基グに対して O(|E|) の時間計算量が必要となる．この計算量はづく手法 [8]，[9]，[10]，[11]，[12]，[13] の 2 つについて述べる．

最悪の場合 O(|V |2 ) に達する．これらの理由から，大規模なグラフ構造に対し SCAN を適用することは難しい．

（注 2）：http://www-personal.umich.edu/~mejn/netdata/（注 3）：http://www.orgnet.com/

ま た ，SCAN の 拡 張 手 法 と し て Bortner ら に よ るSCOT+HintClus [10] および Huang らによる gSkeletonClu[12] が挙げられる．これらの手法では，SCAN の問題点としてパラメータ ϵ 決定の難しさを指摘し，ϵ-free なクラスタリング手法をそれぞれ提案している．SCOT+HintClus では DBSCANの拡張手法として知られる OPTICS [22] の概念を用いて，構造的類似度に基づくノードの走査順を与えることで準最適な ϵ を見つけ出す．gSkeletonClu では，構造的類似度をエッジの重みとして与えた最小全域木を構築し，この全域木の上でパラメー
タ µ の制約を満たすようなパラメータ ϵ の候補を抽出する．いずれの手法も SCAN と同様に，事前に全てのエッジに対して構造的類似度が計算されていることを前提としている．そのため，従来手法である SCAN と同程度かそれ以上の計算時間を必要とする．本稿は SCAN に基づく高速なクラスタリング手法について論ずるため，これらの手法で議論されている ϵ-free
なクラスタリング手法について本稿では議論の対象としない．
本稿で提案する高速化手法は，本節で述べた関連研究とはことなり，グラフ構造の中からクラスタ集合，ハブ集合，外れ値集合を最高で O(|V |) で抽出する手法である．

6. お わ り に
本稿では，大規模なグラフ構造に対する高速かつ正確な構造的類似度に基づくグラフクラスタリングの実現に向けた手法を提案し，その概要について示した．提案手法では，最短ホップ
数が 2 となる様なノードに接続したエッジのみを計算対象としてクラスタリングを行うことで，構造的類似度の計算が発生するエッジ数を削減した．提案手法は従来手法のクラスタの定義を満たすことから，提案手法は従来手法の SCAN で生成されるクラスタリング結果と同様の処理結果をより高速に抽出可能とする．本稿で示した計算量分析により，提案手法は O(|V |)の時間計算量で動作する．また実験結果で示したように，提案
手法はクラスタ係数が大きな現実のグラフ構造に対してより有効に計算時間を削減するとが可能である．これにより，これまでグラフクラスタリングを用いていたアプリケーションにおける分析の幅や処理性能の向上に本手法は貢献できる．
文

献[1] Christopher Sibona and Jae Hoon Choi. Factors Aﬀecting
End–User Satisfaction on Facebook. In Proceedings of the
6th International AAAI Conference on Weblogs and Social
Media (ICWSM 2012). AAAI Press, 2012.
[2] M. E. J. Newman. Fast Algorithm for Detecting Community
Structure in Networks. Physical Review E - PHYS REV E,
Vol. 69, p. 066133, Jun 2004.
[3] Aaron Clauset, M. E. J. Newman, and Cristopher Moore.
Finding Community Structure in Very Large Networks.
Physical Review E - PHYS REV E, Vol. 70, p. 066111, Dec
2004.
[4] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics: Theory and Experiment, Vol. 2008, p. P10008, October
2008.
[5] Hiroaki Shiokawa, Yasuhiro Fujiwara, and Makoto Onizuka.
Fast algorithm for modularity-based graph clustering. In
AAAI, 2013.

[6] Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu,
and Horst D. Simon. A min-max cut algorithm for graphpartitioning and data clustering. In ICDM, pp. 107–114,
2001.
[7] Jianbo Shi and Jitendra Malik. Normalized cuts and image
segmentation. IEEE Trans. Pattern Anal. Mach. Intell.,Vol. 22, No. 8, pp. 888–905, 2000.
[8] Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J.
Schweiger. Scan: a structural clustering algorithm for networks. In KDD, pp. 824–833, 2007.
[9] Nurcan Yuruk, Mutlu Mete, Xiaowei Xu, and Thomas A. J.
Schweiger. Ahscan: Agglomerative hierarchical structuralclustering algorithm for networks. In ASONAM, pp. 72–77,
2009.
[10] Dustin Bortner and Jiawei Han. Progressive clustering of
networks using structure-connected order of traversal. In
ICDE, pp. 653–656, 2010.
[11] Heli Sun, Jianbin Huang, Jiawei Han, Hongbo Deng, Peixiang Zhao, and Boqin Feng. gskeletonclu: Density-based
network clustering via structure-connected tree division or
agglomeration. In ICDM, pp. 481–490, 2010.
[12] Jianbin Huang, Heli Sun, Qinbao Song, Hongbo Deng, andJiawei Han. Revealing density-based clustering structurefrom the core-connected tree of a network. IEEE Trans.
Knowl. Data Eng., Vol. 25, No. 8, pp. 1876–1889, 2013.
[13] Weizhong Zhao, Venkata Swamy Martha, and Xiaowei Xu.
Pscan: A parallel structural clustering algorithm for big
networks in mapreduce. In AINA, pp. 862–869, 2013.
[14] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei
Xu. A density-based algorithm for discovering clusters inlarge spatial databases with noise. In KDD, pp. 226–231,
1996.
[15] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.
Graph evolution: Densiﬁcation and shrinking diameters.
ACM Trans. Knowl. Discov. Data, Vol. 1, No. 1, March
2007.
[16] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.
Graphs over time: Densiﬁcation laws, shrinking diametersand possible explanations. In Proceedings of the Eleventh
ACM SIGKDD International Conference on Knowledge
Discovery in Data Mining, KDD ’05, pp. 177–187, New
York, NY, USA, 2005. ACM.
[17] Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, andMichael W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large welldeﬁned clusters. CoRR, Vol. abs/0810.1355, , 2008.
[18] Jaewon Yang and Jure Leskovec. Deﬁning and evaluating
network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12, pp. 3:1–3:8, New York, NY, USA, 2012.
ACM.
[19] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg.
Signed networks in social media. In Proceedings of the
SIGCHI Conference on Human Factors in Computing Systems, CHI ’10, pp. 1361–1370, New York, NY, USA, 2010.
ACM.
[20] L. Hubert and P. Arabie. Comparing partitions. Journal ofclassification, Vol. 2, No. 1, pp. 193–218, 1985.
[21] M. E. J. Newman and M. Girvan. Finding and Evaluating
Community Structure in Networks. Physical Review E PHYS REV E, Vol. 69, p. 026113, Feb 2004.
[22] Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel,and Jörg Sander. Optics: Ordering points to identify theclustering structure. In SIGMOD Conference, pp. 49–60,
1999.