DBSJ Japanese Journal

一般論文

Vol. 14-J, Article No. 4, March 2016

1 はじめに動的グラフに対する密度ベースク
ラスタリング

グラフ構造はデータをノードとエッジで表現した基本的なデータ構造であり，情報推薦や情報検索，科学データ分析などの様々な分野で利用されている．とりわけ近年では，時間経過とともに構造を大きく変化させる動的グラフが数多く登場しており，動的グラフに対する高速かつ高精度なデータ分析技術は大規模なデータに隠れた構造や特性，相互作用を理解する上で重要な要素技術となっている．例えば，マイクロブログサービス Twitter では 2015 年
現在で１日あたり約 5 億件の投稿があることが報告されている 1 ．
これは 1 秒間あたりに約 6,000 件の投稿がされていることを示しており，時間経過とともに Twitter のもつグラフ構造が極めて大きく変化していることを確認できる．このような動的グラフはTwitter のみに限定されず，例えば道路ネットワークや通信ネッ
トワーク，文書の引用関係，ソーシャルネットワーク，マイクロア
レイデータなど様々存在しており，動的グラフに対する高速かつ高精度な分析技術への要求が大きなものであることが認識できる．

Density-based Clustering for Dynamic
Graphs塩川 浩昭♡ 藤原 靖宏♢
飯田 恭弘♢ 鬼塚 真♠
Hiroaki SHIOKAWA Yasuhiro FUJIWARA
Yasuhiro IIDA Makoto ONIZUKA
グラフはエンティティ同士の関連性を表現する最も基本的なデー

大規模なグラフ構造の分析技術のひとつとしてクラスタリングが挙げられる．グラフ構造にはクラスタと呼ばれる相互に密な接続を有する部分ノード集合が存在する．例えば，Web グラフではト
ピックや関心の近いページ集合が互いにリンクすることで，トピッ
クや関心の類似したページ群がコミュニティを形成する傾向にある．グラフ構造中のクラスタは互いに共通した性質を持つことか
ら，グラフ構造の理解や様々なアプリケーションに利用され，非常に重要な要素技術となっている．そのため，これまで Modularityに基づく手法 [1, 2] や最小カットに基づく手法 [3, 4] など様々なクラスタリング手法の研究が行われてきた．

タ構造であり，我々の身の回りに数多く存在している．特に近年では，短期間に構造を大きく変化させる動的グラフが登場しており，動的グラフに対する高速かつ高精度なクラスタ分析は重要な要素技術となっている．本稿では，動的に構造が変化するグラフに対する密度ベースのクラスタリング手法を提案する．提案手法
は，(1) ある時刻 t に入力されたグラフ構造から，グラフ構造に含まれるクラスタ構造を要約した cluster skeleton を抽出し，(2) 時刻 t + 1 におけるグラフ構造の変化に併せて，事前に構築した cluster skeleton を逐次更新する．その後，(3) cluster
skeleton から時刻 t + 1 におけるクラスタ構造を復元する．提案
手法を用いることで，動的なグラフからパラメータの設定を介さず高速かつ高精度にクラスタを抽出することが可能になる．本稿では提案手法の詳細と実験結果について述べる．

その中でも構造的類似度を用いた密度ベースのクラスタリング
手法 [5, 6] は特に注目を集めているクラスタリング手法である．
この手法はグラフ構造からクラスタに加えて，グラフ構造中において複数のクラスタに接続するようなハブとなるノードや，クラスタに接続したノイズとして扱われる外れ値となるノードを合わせて抽出することが可能である．このことから，クラスタのみを抽出する従来手法に対して，密度ベースクラスタリング手法はより細やかな分析を可能にする手法として期待されている．しかしながら，既存の密度ベースクラスタリング手法の多くはグラフのもつ構造が変化しない静的なグラフを前提としており，本稿で述
べた動的なグラフのクラスタリングは対象とはしていない．

Graphs are one of the most fundamental data structures that represent relationships among entities, andmany large-scale graphs are recently available. In thispaper, we present a novel density-based graph clustering algorithm for dynamic graphs. We employed
three key approach for efficient dynamic graph clustering. First, we extract cluster skeleton that summarizes cluster structures at timestamp t. Second,
we incrementally update the cluster skeleton when
the graph dynamically changed its topology as timestamp t + 1. Last, we conduct new cluster structurefrom the updated cluster skeleton. By following theabove approaches, our proposed method extract clusters from dynamic graphs without setting any userspecified parameters. As a result, this paper experimentally confirmed that our proposed method simultaneously achieves efficient and highly accurate clustering for the dynamic graphs.

この背景から，動的グラフを対象としたクラスタリング手法[7, 8, 9, 10] がこれまで提案されてきたが，これらの既存手法は依然として下記に示す課題を有する．

• 高速性: 動的グラフは単位時間あたりにその構造を大きく変化させる．ところが既存の密度ベースクラスタリングは，グラフに含まれる全てのノードとエッジに対して計算を行う必要があり，クラスタリングに要する時間的コストが大きい．
• 高精度性: 大規模な動的グラフにおいて，高速なクラスタリ
ングを実現するために計算対象をサンプリングする手法などが考えられる．ところが，文献 [11] で報告されている通り，
サンプリングによる手法は出力結果の精度を劣化させる．
• パラメータ設定: 文献 [5, 6] で報告されている通り，パラメー
タ設定は出力結果の精度に大きく影響を与える．また，動的グラフではグラフの構造が大きく変化していくため，時間経
過とともに最適なパラメータ設定が異なってくる．
理想的には，逐次的に変化するグラフ構造に追従するために，動的グラフに対するクラスタリング手法は高速かつ高精度であることが望ましい．さらに，大規模なグラフ構造に対するパラメータ
チューニングは多くの時間的コストを要することから，ユーザによるパラメータ設定を介さない手法が望ましい．

♡ 正会員

筑波大学計算科学研究センター
shiokawa@cs.tsukuba.ac.jp♢ 正会員 NTT ソフトウェアイノベーションセンタ
{fujiwara.yasuhiro, iida.yasuhiro}@lab.ntt.co.jp♠ 正会員 大阪大学大学院情報科学研究科
onizuka@ist.osaka-u.ac.jp

1 https://about.twitter.com/company

1

日本データベース学会和文論文誌

Vol. 14-J, Article No. 4, 2016 年 3 月

DBSJ Japanese Journal

一般論文

Vol. 14-J, Article No. 4, March 2016

定義 3 (構造的隣接ノード集合) u ∈ V とするとき，隣接ノード集
合はノード u にエッジで接続するノードとノード u 自身から構成される集合 N[u] で与えられる．

1.1 本研究の貢献
本稿では動的グラフに対してパラメータ設定を必要としない高速かつ高精度な密度ベースクラスタリング手法を提案する．具体的には，(1) 時刻 t に入力されたグラフ構造に含まれるクラスタ構造を要約した cluster skeleton を抽出し，(2) 時刻 t + 1 におけるグラフ構造の変化に併せた cluster skeleton の逐次更新手法を提供する．その後，(3) cluster skeleton から時刻 t + 1 におけるクラスタ構造を復元する．さらに重要な点としてこれらの処理は，(4)
ユーザによるパラメータ設定を必要とせず，既存の密度ベースク
ラスタリング手法に対して高速かつ精度を劣化させずに行う．その結果として，提案手法は以下の特性を有する．
• 高速性: 提案手法は動的グラフに対する既存の密度ベースク
ラスタリング手法に対して高速である．
• 高精度性: 提案手法は動的グラフに対する既存の密度ベース
クラスタリング手法に対して高精度である．
• パラメータフリー: 提案手法はユーザによるパラメータ設定を必要としない．
本稿で提案する手法は我々の知る限り，動的グラフに対する密度ベースクラスタリングにおいて，高速性，高精度性およびパラ
メータフリーの全てを同時に満たす最初の手法である．既存手法は高い計算コストを有するものの，クラスタだけでなくハブや外れ値を抽出できることから既に幅広いアプリケーションで利用されている．本稿で提案するグラフクラスタリング手法は，既に従来技術が利用されているアプリケーションや将来的に利用が予測される分野において，その処理性能の向上に貢献する．

2

N[u] = {v ∈ V : {u, v} ∈ E} ∪ {u}.

また，クラスタリングで用いる 2 ノード間の構造的類似度は定義
3 に基づき以下のように定義される．
定義 4 (構造的類似度) u, v ∈ V ，|N[u]| を N[u] のノード数とする
とき，ノード u，v 間の構造的類似度は σ(u, v) となる．

|N[u] ∩ N[v]|σ(u, v) = √.
|N[u]||N[v]|(2)

ノード u，v 間の σ(u, v) は共有されるノードがない場合 σ(u, v) = 0，
互いに全て共有する場合には σ(u, v) = 1 となる．
構造的類似度に基づくクラスタリング手法はクラスタを構成するための類似度の閾値として ϵ を導入し，類似度 ϵ 以上で接続する隣接ノード集合 ϵ-neighborhood を定義する．
定義 5 (ϵ-neighborhood) u ∈ V，ϵ ∈ R とするとき，ϵneighborhood Nϵ [u] は以下のように定義される．

Nϵ [u] = {v ∈ N[u] : σ(u, v) ≥ ϵ}.

(3)

ここで，クラスタを構成する最小ノード数としてパラメータ µ を導入し，特別なノードのクラスとして core を定義する．

問題定義

定義 6 (core) u ∈ V，|Nϵ [u]| を Nϵ のノード数とするとき，core
は |Nϵ [u]| ≥ µ となるノード u である．本稿では core となるノード u を Kϵ,µ (u) と記述する．

ここでは本論文で対象とする問題を定義する．
動的グラフとは時刻経過とともにノードとエッジが更新される
グラフ構造である．本稿では，Gt = {Vt , Et } を時刻 t における動的グラフのスナップショットとし，Vt および Et はそれぞれ時刻 t における Gt のもつノード集合およびエッジ集合とする．このとき，動的グラフを下記のように定義する．

従来手法では定義 6 を満たす core ノード u をクラスタの中心として，Nϵ [u] をクラスタのメンバとして同一のクラスタに所属させる．この手順により，パラメータ ϵ ，µ を用いてクラスタの形を決定し，µ を用いてクラスタの最小サイズを定める．この考えは direct structure reachability として以下に定義される．

定義 1 (動的グラフ Gi j ) 時刻 i から時刻 j までの動的グラフを
Gi j = (Gi ; △Gi+1 , . . . , △G j ) とする．ただし，時刻 (i ≤ t < j) における △Gt+1 = {△Vt+1 , △Et+1 } は時刻 t + 1 で更新される部分グラフである．△Vt+1 と △Et+1 はそれぞれ時刻 t + 1 において追加/削
除されたノードおよびエッジ集合を表す．

定義 7 (direct structure reachability) ノード v が u に対して direct structure reachability を満たすとき，ノード u と v はKϵ,µ (u) ∧ v ∈ Nϵ [u] を満たす．本稿ではこれを u 7→ϵ,µ v と記述する．
定義 7 はノード u と v が core である場合対称となるが，どちらか一方が core でない場合には非対称となる．ゆえに，u 7→ϵ,µ v かつ
ノード v が core でない場合，ノード v は Kϵ,µ (u) が構築するクラスタの境界に面したノードとなる．本稿ではこのようなノード v
を border と呼ぶ．定義 7 をより一般的な形に拡張した structure
reachability を下記に示す．

本稿では説明の簡単化のため動的グラフ G，および時刻 t におけるグラフ Gt は無向重みなしグラフとする．定義 1 で与えた動的グラフに対して，動的クラスタを以下に定義する．
定義 2 (動的クラスタ) 時刻 t におけるグラフ Gt に含まれるクラスタ集合を Ct とするとき，動的グラフ Gi j = (Gi ; △Gi+1 , . . . , △G j )に対する動的クラスタを Ci j = (Ci ; △Ci+1 , . . . , △C j ) とする．ただし，時刻 (i ≤ t < j) において Ct + △Ct+1 = Ct+1 である．

定義 8 (structure reachability) ノード v が u に対して structure reachability を満たすとき，ノード u と v は ∃u1 , . . . , un ∈ Vに対して u1 = u ∧ un = v ∧ ui 7→ϵ,µ ui+1 を満たす．本稿ではこれを
u →ϵ,µ v と記述する．

定義 1,2 より，本稿で取り組む問題は，動的グラフ Gi j が与えられた時に，動的クラスタ Ci j を獲得することである．本稿ではユーザによるパラメータ設定を介さず，精度の高いクラスタリン
グ結果を求めるための手法を提案する．

3(1)

ここで定義された structure reachability は推移律を満たし非対称となる．structure reachability は direct structure reachability の推移閉包であり，定義 7 の対称性から，推移閉包の構
成要素である u1 , . . . , un−1 は core ノードである必要がある．すな
わち core 同士が direct structure reachability を示すとき coreの ϵ-neighborhood は同一クラスタに属することになる．これはstructure-connected クラスタとして以下に定義される．

クラスタモデル

本節では本稿で求める密度ベースクラスタについて定義する．
本稿で求める密度ベースクラスタは，静的なグラフ構造に対する密度ベースクラスタリング手法 SCAN[5] で求めるクラスタである．従来手法では 2 つのノード間で共有される隣接ノード集合の割合を評価することで構造類似度を計算していく．ここで用いる
隣接ノード集合は以下のように定義される．

定義 9 (structure-connected クラスタ) core であるノード uから求まる structure-connected クラスタ Cu は u →ϵ,µ v を満たす全てのノードから構成されるノード集合である．

2

日本データベース学会和文論文誌
Vol. 14-J, Article No. 4, 2016 年 3 月

DBSJ Japanese Journal

一般論文

Vol. 14-J, Article No. 4, March 2016

この定義より，structure-connected クラスタはその中に含まれる
core により一意に決めることができることがわかる．従来手法では structure-connected クラスタの取得のために全てのエッジを走査するため，クラスタリングの計算量が O(|V|2 ) となる．ここで，border ノードは，複数のクラスタの core から direct structure
reachability となる可能性があることに注意されたい．この場合，border ノードは複数のクラスタに属する．
パラメータ ϵ, µ から求まるクラスタ集合を C とするとき，ノード集合 V にはいずれのクラスタ集合 C にも属さないノードが存在する場合がある．これらのノードはハブもしくは外れ値に分類される．ハブと外れ値は下記のように定義する．

定義 12 に示した様に，structure core-similarity とは core となるノードが持つ最大の ϵ の値を示している．この値を基に隣接する core 同士が同一クラスタになりやすさを定義 13 に示す
reachability-similarity を用いて，定義 14 に示す 2 つの core 間の core-connectivity similarity を計算することで求める．
定義 13 (reachability-similarity) ノード u, v ∈ Gt とするとき，ノード u に対するノード v の reachability-similarity RS(u, v)
を以下に定義する．

RS(u, v) = min{CS(u), σ(u, v)}.

定義 14 (core-connectivity similarity) ノード u, v ∈ Vt か
つ (u, v) ∈ Et とするとき，ノード u, v 間の core-connectivity similarity CCS(u, v) は以下のように定義する．

定義 10 (ハブ) クラスタ集合 C，ハブ集合 H とすると，ノードh ∈ V がハブである (e.g. h ∈ H) 必要十分条件は (1) h < ∀Ci ∈ C，
(2) u, v ∈ N[h] s.t u ∈ Ci , v ∈ C j , i , j．

CCS(u, v)

定義 11 (外れ値) クラスタ集合 C，ハブ集合 H，外れ値集合 O とすると，ノード o ∈ V が外れ値 (e.g. o ∈ O) である必要十分条件
は o < C ∧ o < H．

4

(5)

=

min{RS(u, v), RS(v, u)}=min{CS(u), CS(v), σ(u, v)}.

(6)

定義 14 に示した CCS に基いて，提案手法で構築する CCMSTは以下のように与えられる．

動的グラフに対するクラスタリング

定義 15 (CCMST) 時刻 t のグラフ構造 Gt に含まれるエッジ e ∈Et に対して，CCS の値が ω(e) で与えられるとき，ω(e) で重み付けされたグラフを G′t = (Vt , Et , ω) とするとき，CCMST は G′t のMaximum Spaning Tree である．

本節では提案手法について述べる．まず最初に提案手法の基本
アイデアについて述べた後，その詳細を 4.2 節以降で述べる．

4.1 基本アイデア
提案手法は 2 つのアイデアに基づき動的グラフに対するクラスタ
リングの高速化と高精度化を行う．具体的には，動的グラフに対するクラスタ抽出を行う際に必要な計算コストを削減するため，クラスタ構造を要約する cluster skeleton の導入と，cluster skeletonの差分更新手法を提案する．

定義 15 で与えられる CCMST は以下の性質を持つことが文献 [6] において知られている．
補題 1 (クラスタの正当性) G′ t に 対 す る CCMST に お い て ，ω(e) > ϵ̂ で接続するノードは，Gt = (Vt , Et ) で与えられる時刻
t のグラフに対して，ϵ̂ ≥ ϵ となるパラメータ ϵ で SCAN[5] を実行した際に必ず同じクラスタに含まれる．

cluster skeleton の導入 従来手法ではグラフ構造に含まれる全てのエッジ E に対して計算を行う．この全網羅的な類似度計
算は，動的グラフが構造を変化させる毎に高い計算コストを要求
し，クラスタリングに膨大な時間を必要とする．そこで本稿では，
従来手法とは異なり，前の時刻のクラスタリング結果を要約する
cluster skeleton を構築し，cluster skeleton に対してのみ類似度計算を行うことで動的グラフに対するクラスタリングの計算コストを削減する．具体的には，前の時刻のクラスタリング結果から獲得されるグラフ構造の構造的類似度に基づく最大全域木を cluster
skeleton として用いる．

補題 1 の証明については，文献 [6] を参照されたい．本稿では，G′ から CCMST を構築するために Prim 法 [13] を用いる．
提案手法では CCMST を Cluster Skeleton として構築し，
CCMST を差分更新していくことにより，動的グラフに対するパラメータを必要としない密度ベースクラスタリングを実現する．
CCMST の差分更新方式の詳細は 4.3 節，クラスタ抽出手順の詳
細は 4.4 節で述べる．

4.3 cluster skeleton の差分更新手法
提案手法は CCMST を更新していくことで動的グラフに対する密度ベースクラスタリングを実現する．本節では CCMST の差分更新手法について述べる．
時刻が t から t + 1 に推移しグラフ構造が変化した際に，時刻t + 1 における CCMST を構築するためには，構造的類似度を計算しそこから定義 14 で与えた core-connectivity similarity を求める必要がある．時刻が t から t + 1 に推移した際のグラフ構造の変化は大きく分けて，(1) エッジの追加と (2) エッジの削除の 2 つに分類できる．そこで本稿では，時刻 t + 1 において (u, v) ∈ Et+1 となるエッジが追加される場合および (u, v) ∈ Et が削除される場合について構造的類似度の差分更新方式を与える．

cluster skeleton の差分更新手法 cluster skeleton に基づき動的グラフに対応するための差分更新手法を提案する．本稿
で提案する差分更新手法では，既存研究である Lee らによる知見 [12] に基づき，密度ベースクラスタリングにおける差分更新
ノード集合を獲得する．その後，獲得したノード集合に対してのみ，structural similarity の計算と全域木の再計算を行い cluster
skeleton を更新する．

4.2 cluster skeleton の導入

時刻 t におけるグラフ Gt に含まれるクラスタ構造を要約する cluster skeleton を導入する．本節では cluster skeleton として，Sunらによって提案された core-connected maximal spanning tree
(CCMST) [6] を用いる．CCMST とは互いに同一のクラスタとなる可能性の高い core 同士を接続した Maximal Spanning Tree である．CCMST を獲得するためには，まず structure core-similarityとよばれる指標を各ノードに対して計算する必要がある．

4.3.1 時刻 t + 1 で (u, v) ∈ Et+1 が追加される場合
時刻 t + 1 においてエッジ (u, v) ∈ Et+1 が追加される場合について考える．時刻変化とともにエッジが追加される場合，エッジ(u, v) に対する構造的類似度計算のみならず，エッジの端点である
ノード u および v に接続するエッジが持つ構造的類似度が更新されることになる．このとき，ノード u（またはノード v）の時刻 t における隣接ノード集合を Nt [u]（Nt [v]）とし w ∈ Nt [u]（w ∈ Nt [v]）とおくと，時刻 t + 1 におけるエッジ (u, w) に対する構造的類似度
σt+1 (u, w) について以下の補題が成り立つ．

定義 12 (structure core-similarity) ノード u ∈ Vt の structure core-similarity CS(u) を以下に定義する．
{
max{ϵ ∈ R : |Nϵ [u]| ≥ µ} |N[u]| ≥ µ(4)CS(u) =
0otherwise3

日本データベース学会和文論文誌
Vol. 14-J, Article No. 4, 2016 年 3 月

DBSJ Japanese Journal

一般論文

Vol. 14-J, Article No. 4, March 2016

補題 2 (エッジ追加による差分更新) エッジ (u, v) を時刻 t + 1 で追加されたエッジとし，ノード w を w ∈ Nt [u] とするとき，時刻
t + 1 におけるエッジ (u, w) の構造的類似度 σt+1 (u, v) には以下が成立する．

 σ (u,w) √|N [u]||N [w]|+1
t √
t
t



(|N√
t [u]|+1)|Nt [w]|σt+1 (u, w) = 
σ
(u,w)
|N
[u]||Nttt [w]|
 √(|Nt [u]|+1)|Nt [w]|(w ∈ Nt [u] ∩ Nt [v])(Otherwise)

4.4 Cluster Skeleton からのクラスタ抽出
本節では，これまで述べた CCMST からクラスタ抽出を行う手法について述べる．クラスタを抽出するに際して重要となるのが，適切なクラスタリング結果を与えるパラメータ ϵ の自動決定である．
本節では，文献 [6, 14] に基づく ϵ の決定方法とクラスタ抽出手法について述べる．
まず提案手法では，4.2 節で与えた CCMST から，CCMST のエッジに付与されている全ての重み (ϵ) を列挙する．その後列挙した値をソートし，ひとつずつ ϵ の候補を選択する．選択した ϵの候補に対して，まず補題 1 に基づくクラスタの抽出を行う．その後，クラスタに含まれなかったノードに関して以下に定義される attachability-similarity を求める．

(7)

ただし，σt (u, w) は時刻 t における (u, w) の構造的類似度である．
証明 1 w∈ Nt [u] ∩ Nt [v] の と き ，定 義 4 よ りσt+1 (u, w)= √|Nt+1 [u]∩Nt+1 [w]| ．こ の と き ，時 刻 t + 1 に お い て|Nt+1 [u]||Nt+1 [w]|

定義 16 (attachability-similarity) ノ ー ドvのattachability-similarity AS(v) は以下のように定義される．

(u, v) ∈ Et+1 が追加となるため，ノード u, v, w はクリークをつ く り，|Nt+1 [u] ∩ Nt+1 [w]|=|Nt [u] ∩ Nt [w]| √+ 1 と な る ．こ こで 定 義 4 か ら ，|Nt [u] ∩ Nt [w]|=σ√t (u, w) |Nt [u]||Nt [w]| で あ
る た め ，|Nt+1 [u] ∩ Nt+1 [w]|=σt (u, w) |Nt [u]||Nt [w]| + 1．ま た ，
時刻 t + 1 において，(u, v) ∈ Et+1 が追加されるため，自明に |Nt+1 [u]||Nt+1 [w]|=(|Nt [u]| + 1)|Nt [w]| で あ る ．し た がって ，w ∈ Nt [u] ∩ Nt [v] のとき，補題 2 は成立する．
w < Nt [u] √∩ Nt [v] に つ い て も 同 様 に ，|Nt+1 [u] ∩Nt+1 [w]|=σt (u, w) |Nt [u]||Nt [w]|，かつ，|Nt+1 [u]||Nt+1 [w]|=(|Nt [u]| +1)|Nt [w]| であるため，補題 2 は成立する．
□

AS(v) = max{RS(u, v) : u ∈ N[v]\{v}}.

すなわち，attachability-similarity とは各ノードとその隣接ノードに対する最大の reachability-similarity を示したものである．
attachability-similarity を計算後，クラスタに含まれないノード
を attachability-similarity で与えられる隣接ノードと同一のクラスタに割り当てる．以上の処理により，選択した ϵ 候補に対するクラスタリングを終了する．
提案手法では，選択した ϵ 候補から獲得したクラスタリング結果に対して，以下に示した構造的類似度に基づく modularity の値を計算する．

補題 2 において計算が必要となる Nt [u] ∩ Nt [v] は σt+1 (u, v) の計算結果から獲得することができる．また，|Nt [u]| および |Nt [v]| は
時刻 t における構造的類似度の計算結果から獲得可能である．したがって，エッジの追加に伴う構造的類似度の差分更新を少ない
計算コストで実行することができる．

4.3.2

定義 17 (構造的類似度に基づく modularity) 時刻 t のクラスタt|を Ct = {C1t , . . . , C|Ct } とし，|Ct | を時刻 t におけるクラスタ数とするとき，構造的類似度に基づく modularityQ s は以下に定義さ
れる．

(
)2 
|Ct | 
∑
 ISi

DSi 


Qs =
−
(10)
.




 TS

T
S
i=1
∑
∑
ただし，ISi =u∈Cit ,v∈Vt σ(u, v)，TS =u,v∈Cit σ(u, v)，DSi =
∑
σ(u,
v)
である．
u,v∈Vt

時刻 t + 1 で (u, v) ∈ Et が削除される場合

本節ではエッジが削除される場合について述べる．前節と同様に，エッジ (u, v) が削除されることにより，その端点であるノード
u および v に接続するエッジに関して構造的類似度の更新が必要となる．ここで w ∈ Nt [u]（もしくは，w ∈ Nt [v]）とするとき，時
刻 t + 1 におけるエッジ (u, w) に対する構造的類似度 σt+1 (u, w) について以下が成立する．

その後，選択した ϵ 候補に対する Q s を保存し，次の ϵ 候補を選択する．上記の処理を Q s を最大化する ϵ 候補が決定するまで実行
し，クラスタリング精度を最も向上させる ϵ を自動決定する．以上により，提案手法はパラメータフリーな動的グラフに対する密度ベースクラスタリングを実現する．

補題 3 (エッジ削除による差分更新) エッジ (u, v) を時刻 t + 1 で削除されたエッジとし，ノード w を w ∈ Nt [u] とするとき，時刻
t + 1 におけるエッジ (u, w) の構造的類似度 σt+1 (u, v) には以下の通りとなる．

 σ (u,w) √|N [u]||N [w]|−1
t √
t
t



(|N√
t [u]|−1)|Nt [w]|σt+1 (u, w) = |N[u]||Nσ(u,w)
tt [w]|t √(|Nt [u]|−1)|Nt [w]|(w ∈ Nt [u] ∩ Nt [v])(Otherwise)(9)

5 評価実験
提案手法の有効性を評価するために，我々の提案手法およびKim らによる手法 (Kim-Han09)[8] および Lee らによる手法(eTrack)[12] に対し，処理の高速性とクラスタリングの質の観点から比較実験を行う．本評価で比較に用いる Kim-Han09[8] はKim らにより 2009 年に提案された動的グラフに対する密度ベースのクラスタリング手法である．Kim-Han09 はクラスタリング
結果の時間変化に対する類似度と各時刻におけるクラスタリングの質の両方を最適化する手法である．また，提案手法と同様にパラメータ ϵ をヒューリスティックスを用いて最適化する手法も導入している．eTrack は Lee らにより 2014 年に提案された動的グ
ラフに対する密度ベースクラスタリング手法である [12]．eTrack
では，動的グラフの構造変化の影響を受けるノード集合およびエッジ集合を定義しており，そのノード集合とエッジ集合に対しての
み SCAN に基づくクラスタリングを実行しなおす差分更新型のク
ラスタリング手法である．eTrack は，提案手法で導入しているパ
ラメータ ϵ の最適化は行わず，一度設定した epsilon の値を使い続ける手法である．これらの手法の詳細については 6 節で述べる．

(8)

ただし，σt (u, w) は時刻 t における (u, w) の構造的類似度である．
補題 3 は証明 1 と同様の手順で証明できるため，本稿では割愛する．前節と同様に，補題 3 において計算が必要となる Nt [u] ∩ Nt [v]は σt+1 (u, v) の計算結果から獲得することができる．また，|Nt [u]|および |Nt [v]| は時刻 t における構造的類似度の計算結果から獲得可能である．したがって，エッジの追加に伴う構造的類似度の差
分更新を少ない計算コストで実行することができる．
提案手法では，補題 2 および補題 3 を用いて，時刻 t における構造的類似度計算結果から時刻 t + 1 における構造的類似度計算結果を差分更新により求める．その後，差分更新の結果に対して改めて Prim 法により時刻 t + 1 の CCMST を構築する．

4

日本データベース学会和文論文誌
Vol. 14-J, Article No. 4, 2016 年 3 月

DBSJ Japanese Journal

一般論文

Vol. 14-J, Article No. 4, March 2016

60

50

80
Kim-Han09
eTrack
Proposed70

60
Kim-Han09
eTrack
Proposed50

80
Kim-Han09
eTrack
Proposed

70

20

50
40
30

40

Wall clock time [s]3060Wall clock time [s]Wall clock time [s]Wall clock time [s]

60
40

30

20

20
10

0

t2

t3

t4

(a) Graph(1%, Inner)

t5

0

50
40
30
20

10

10

t1

Kim-Han09
eTrack
Proposed

t1

t2

t3

t4

0

t5

(b) Graph(5%, Inner)

10

t1

t2

t3

t4

t5

(c) Graph(1%, Outer)

0

t1

t2

t3

t4

t5

(d) Graph(5%, Outer)

図 1: 実行速度の比較
本稿では，LFR benchmark[15] を用いてノード数 10 万，エッ
ジ数 200 万のグラフを生成した．上記のグラフを初期状態とし，エッジの追加を行う 4 パターンの動的グラフを作成し評価を行った．データセットの詳細は以下のとおりである．
• Graph(1%, Inner): 初期グラフに存在するノードについて
のみ，初期グラフの持つエッジ数の 1%に相当する 2 万エッジを各時刻毎に追加した動的グラフ．ただし，エッジを追加するノード対はランダムに選択するものとする．
• Graph(5%, Inner): 初期グラフに存在するノードについて
のみ，初期グラフの持つエッジ数の 5%に相当する 10 万エッ
ジを各時刻毎に追加した動的グラフ．ただし，エッジを追加するノード対はランダムに選択するものとする．
• Graph(1%, Outer): 初期グラフの持つエッジ数の 1%に相当する 2 万エッジを各時刻毎に追加した動的グラフ．ただし，エッジの追加に伴い，初期グラフに含まれないノードに接続するエッジも追加されるものとする．また，エッジを追加するノードはランダムに選択するものとする．
• Graph(5%, Outer): 初期グラフの持つエッジ数の 5%に相当する 10 万エッジを各時刻毎に追加した動的グラフ．ただし，エッジの追加に伴い，初期グラフに含まれないノードに接続するエッジも追加されるものとする．また，エッジを追加するノードはランダムに選択するものとする．
また，本実験では上記 4 パターンに併せてエッジの削除を行う動的グラフについても評価を行ったが，上記 4 パターンと同様の実験結果の傾向が得られたため本稿からは除外した．
本実験ではこれらのデータセットに対して各タイムスタンプに対するクラスタリング処理が終了するまで処理を行った際の処理時間および Q s を評価した．本実験には CPU が Intel Core i7
1.8GHz，メモリが 4GB の計算機を利用した．また，提案手法および Kim-Han09，eTrack は gcc–g++ 4.1.2 を用いて実装した．

刻変化に伴い計算時間が増加している．また，同様に提案手法は
eTrack と比較しても高速であることが確認できる．eTrack は提案手法と同様にグラフクラスタの差分更新手法であるが，差分更新を行う際に，追加・削除されたエッジや追加削除に伴い類似度を変化させるエッジの構造的類似度を全て再計算し直す必要がある．これに対して，提案手法は構造的類似度の再計算を必要とせず，前時刻の計算結果から現在時刻の類似度の値を差分計算により求めることができる．ゆえに，各エッジに対する類似度計算にかかるコストが小さくなることから，提案手法は eTrack よりも高速に動作していると考えられる．

5.2 クラスタリングの質の比較
本節では提案手法のクラスタリングの質を評価する．本研究では質の評価も定義 17 で与えた，構造的類似度に基づく Modularityを用いる．なお，本実験で用いた各種パラメータの設定は前節と同様である．
本研究で用いた 4 種類の動的グラフに対するクラスタリングの質の評価結果を図 2 に示す．図 2 に示したように，提案手法はいずれのデータセットにおいても Q s の値が大きく良いクラスタリン
グ結果を示していることが確認できる．一方で，Kim-Han09 や
eTrack は提案手法よりも Q s の値が小さくなっていることがわかる．特に，eTrack は時刻経過とともに Q s の値が次第に低下している．
この理由は，各手法のパラメータ ϵ の決定方式にある．まず，提案手法と Kim-Han09 のクラスタリングの質の違いについて議論する．提案手法および Kim-Han09 はパラメータ ϵ を自動決定する手法である．提案手法は，Cluster Skeleton を構築すること
で，入力されたグラフがクラスタを作ることができる全ての ϵ を列挙し，構造的類似度に基づく ModulaityQ s を最大化する ϵ を決定している．これにより Q s の値が高くなるクラスタリングを実現している．これに対して，Kim-Han09 ではパラメータ ϵ の最適化を行うものの，全ての ϵ を列挙しないため局所最適な ϵ を用いる．ゆえに，両手法とも動的グラフの構造変化に追従した ϵの自動選択を行うものの，提案手法のほうが高い質を示す結果となっている．次に，提案手法と eTrack のクラスタリングの質に関して議論する．eTrack はパラメータを自動調整することが出来ない手法である．したがって，初期グラフにおいて高い Q s の値を示していたとしても，時間経過とともに ϵ の値が最適ではなくなる可能性がある．その結果として，図 2 に示したように，eTrackの Q s の値は時間経過にしたがって低下していると考えられる．

5.1 実行時間の比較
本節では提案手法の実行速度を評価する．本実験では全ての評価において µ = 2 を用いた．また，eTrack ではパラメータ ϵ の値として，初期グラフに対して提案手法が自動検出した ϵ の値をそれ
ぞれのデータセットで用いるものとした．
本研究で用いた 4 種類の動的グラフに対する実行速度の評価結果を図 1 に示す．図 1 に示したように，いずれのデータセットに対しても提案手法は従来手法と比較して高速に処理できている．
具体的には，Kim-Han09 に対しては約 20 倍，eTrack に対しては約 6 倍の高速化に成功している．特に，Kim-Han09 は t5 に近づくにつれて処理時間が増加しているのに対し，提案手法はほぼ一定の処理時間でクラスタリングができていることが確認できる．
この理由は，提案手法の差分更新方式にあると考えられる．提案
手法は追加されたエッジと，エッジの追加により類似度が変化する周辺エッジについてのみ計算を行う．ゆえに，提案手法は構造が変化した部分に対してのみ計算を行えばクラスタリング結果を獲得することができる．これに対して，Kim-Han09 は各 t1 , . . . , t5
においてグラフ構造全てを再計算する必要がある．したがって，時6 関連研究
グラフ構造中からクラスタを抽出するグラフクラスタリング
はデータマイニング分野において重要な技術であり，これまで
min-max cut[3] や normalized cut[4]，Modularity に基づく手法 [1, 2, 16, 17] など，数多く研究されてきた．本節ではこれらの中でも，本稿の議論の対象である構造的類似度に基づく密度ベー
スクラスタリング手法 [5, 18, 19, 6, 14, 20] は近年注目を集めている手法のひとつである．

5

日本データベース学会和文論文誌
Vol. 14-J, Article No. 4, 2016 年 3 月

DBSJ Japanese Journal

一般論文

0.8

Qs score

0.6

0.4

1

Kim-Han09
eTrack
Proposed

0.8

0.6

0.4

0.4

0.2

0.2

0

0

0

t2

t3

t4

(a) Graph(1%, Inner)

t5

t1

t2

t3

t4

t5

(b) Graph(5%, Inner)

Kim-Han09
eTrack
Proposed

0.8

0.6

0.2

t1

1

Kim-Han09
eTrack
ProposedQs score

0.8

Qs score

1

Kim-Han09
eTrack
ProposedQs score

1Vol. 14-J, Article No. 4, March 2016

0.6

0.4

0.2

t1

t2

t3

t4

t5

(c) Graph(1%, Outer)

0

t1

t2

t3

t4

t5

(d) Graph(5%, Outer)

図 2: クラスタリングの質 Q s の比較

6.1 静的なグラフ構造に対する手法

プローチである．snapshot quality は，各時刻におけるグラフ構
造を静的なグラフ構造とみなして，密度ベースクラスタリングを適用した結果との類似度であり，history quality は直前の時刻におけるクラスタリング結果と現時刻におけるクラスタリング結果の類似度を示したものである．この両指標を満たすクラスタリン
グ結果を各時刻に対して求めることで，動的グラフのクラスタリ
ングを実現する．
この概念に基づくクラスタリング手法として代表的な手法は Lin
らによる手法 [7] や Kim らによる手法 [8] が挙げられる．ところ
がこれらの手法では，各時刻に対して都度，密度ベースクラスタリ
ング (e.g. SCAN) を実行する必要があり，各時刻において O(|V|4 )程度の計算量が必要となる．また，密度ベースクラスタリング手法および temporal smoothing のために複数のパラメータ設定を必要とすることから，大規模な動的なグラフ構造に対する適用が難しい．近年，temporal smoothing におけるパラメータ設定を除去するために Folino らが遺伝的アルゴリズムによる手法 [10]も提案しているが，その計算量は既存手法 [7, 8] よりも極めて大きく依然として大規模なグラフへの適用が難しい．
temporal smoothing とは異なるもうひとつの動的グラフクラスタリングアプローチとして，クラスタの差分更新による手法がある．Lee らは動的に変化するクラスタから SCAN に基づく
core ノードのみを Skeleton として獲得し，グラフの時系列変化に併せて Skeleton を更新していく手法 eTrack を提案した [9]．
Skeleton を構築し，それを差分更新するという点において，提案手法と同様のアプローチであるが，Lee らによる手法は密度ベース
クラスタリング実行の際に複数のパラメータ設定を要求する．これに対して，提案手法では Skeleton の構築方法に Core-Connected
Similarity による Maximum Spanning Tree を用いている．これにより，密度ベースクラスタリングに必要なパラメータの候補をリストアップし，構造的類似度に基づく modularity を用いたパラメータフリーな動的クラスタリングを実現している．

静的なグラフ構造を対象とした，構造的類似度に基づく密度ベー
スクラスタリング手法 [5, 18, 19, 6, 14, 20] は，データマイニン
グ分野において近年利用され始めているグラフクラスタリング手法である．4 節で述べたとおり，この手法では事前にクラスタを構成するための類似度の閾値 ϵ とクラスタを構成する最小ノード数 µ をパラメータとして与える．これにより任意の大きさ，形状のクラスタを抽出できるだけではなく，クラスタに併せてハブや
外れ値といったノードを抽出することが可能である．
代表的な手法として Xu らによる SCAN[5] が挙げられる．
SCAN は多次元ベクトルデータに対する密度ベースのクラスタリング手法としてよく知られている DBSCAN[21] の概念をグラフ構造に適用した手法である．1 節で述べたように，事前に全てのエッジに対して構造的類似度を計算し，パラメータ ϵ ，µ に従い，クラスタの核となる core と定義されるノードを見つける．その後 SCAN は検出された core を中心にクラスタを拡張し，最終的にクラスタに属するノード集合とそれ以外の集合にノードを分類する．クラスタに属さなかったノード集合のうち，2 つ以上のクラスタに接続しているノードについてはハブ，それ以外のノードは外れ値と判定される．SCAN では 1 つのエッジに対する構造的類似度の計算に O(|V|2 )，グラフ構造全体で O(|V|4 ) の計算量が必要となる．さらにクラスタリング自体にかかる計算量も踏まえると，SCAN 全体で O(|V|4 ) から O(|V|4 + |V|2 ) 程度の計算コストが必要となる．この理由から，大規模な動的グラフに対し SCAN
を適用することは難しい．
ま た ，SCAN の 拡 張 手 法 と し て Bortner ら に よ る
SCOT+HintClus[19] および Huang らによる gSkeletonClu[14]が挙げられる．これらの手法では，SCAN の問題点としてパラメータ ϵ 決定の難しさを指摘し，ϵ-free なクラスタリング手法をそれぞれ提案している．SCOT+HintClus では DBSCAN の拡張手法として知られる OPTICS[22] の概念を用いて，構造的類
似度に基づくノードの走査順を与えることで準最適な ϵ を見つけ出す．gSkeletonClu では，構造的類似度をエッジの重みとして与えた最小全域木を構築し，この全域木の上でパラメータ µ の制約を満たすようなパラメータ ϵ の候補を抽出する．いずれの手法
も SCAN と同様に，事前に全てのエッジに対して構造的類似度が計算されていることを前提としている．そのため，従来手法である SCAN と同程度かそれ以上の計算時間を必要とする．

7 おわりに本稿では，既存のクラスタリング手法のアプローチを融合し，大規模な動的グラフ構造に対する高速，正確かつパラメータフリー
な密度ベースグラフクラスタリングの実現に向けた手法を提案した．提案手法では (1) ある時刻 t に入力されたグラフ構造から，グラフ構造に含まれるクラスタ構造を要約した cluster skeleton を抽出し，(2) 時刻 t + 1 におけるグラフ構造の変化に併せて，事前に構築した cluster skeleton を逐次更新する．その後，(3) cluster
skeleton から時刻 t + 1 におけるクラスタ構造を復元する．さら
に重要な点としてこれらの処理は，(4) ユーザによるパラメータ設定を必要とせず，既存の密度ベースクラスタリング手法に対して
高速かつ精度を劣化させずに行う．
その結果として，提案手法は以下の特性を有する．
• 高速性: 提案手法は動的グラフに対する既存の密度ベースク
ラスタリング手法に対して高速である．
• 高精度性: 提案手法は動的グラフに対する既存の密度ベース

6.2 動的なグラフ構造に対する手法
時間変化とともに構造を動的に変化させるグラフ構造に対する密度ベースクラスタリング手法 [7, 8, 9, 10] が近年提案されつつある．動的グラフに対する密度ベースクラスタリング手法は大きく
分けて 2 種類に分類される．
ひ と つ は ，Chakrabarti ら に よって 提 案 さ れ た temporalsmoothing [23] を用いる手法である．temporal smoothing とは，(1)snapshot quality と (2)history quality と呼ばれる 2 つの指標を動的グラフの各時刻毎に評価し，両指標を極大化させる
解を各スナップショットのクラスタリング結果として獲得するア6

日本データベース学会和文論文誌
Vol. 14-J, Article No. 4, 2016 年 3 月

DBSJ Japanese Journal

一般論文

Vol. 14-J, Article No. 4, March 2016[15] Andrea Lancichinetti and Santo Fortunato. Community
Detection Algorithms: A Comparative Analysis. Phys.
Rev. E, 80:056117, Nov 2009.
[16] M. E. J. Newman. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E - PHYS
REV E, 69:066133, Jun 2004.
[17] Aaron Clauset, M. E. J. Newman, and Cristopher
Moore. Finding Community Structure in Very Large
Networks. Phys. Rev. E, 70:066111, Dec 2004.

クラスタリング手法に対して高精度である．
• パラメータフリー: 提案手法はユーザによるパラメータ設定を必要としない．
上記の特性により，提案手法はこれまでグラフクラスタリングを用いていたアプリケーションにおける分析の幅や処理性能の向上に本手法は貢献できる．

[文献][1] Vincent D. Blondel, Jean-Loup Guillaume, Renaud
Lambiotte, and Etienne Lefebvre. Fast Unfolding ofCommunities in Large Networks. Journal of Statistical Mechanics: Theory and Experiment, 2008:P10008,
October 2008.
[2] Hiroaki Shiokawa, Yasuhiro Fujiwara, and Makoto
Onizuka. Fast Algorithm for Modularity-based Graph
Clustering. In AAAI, pages 1170–1176, 2013.
[3] Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming
Gu, and Horst D. Simon. A Min-max Cut Algorithm
for Graph Partitioning and Data Clustering. In ICDM,
pages 107–114, 2001.
[4] Jianbo Shi and Jitendra Malik. Normalized Cuts andImage Segmentation. IEEE TPAMI, 22(8):888–905,
2000.
[5] Xiaowei Xu, Nurcan Yuruk, Zhidan Geng, and Thomas
A. J. Schweiger. SCAN: A Structural Clustering Algorithm for Networks. In KDD, pages 824–833, 2007.
[6] Heli Sun, Jianbin Huang, Jiawei Han, Hongbo Deng,
Peixiang Zhao, and Boqin Feng. gSkeletonClu: DensityBased Network Clustering via Structure-Connected
Tree Division or Agglomeration. In Proc. ICDM, pages
481–490, 2010.
[7] Yu-Ru Lin, Yun Chi, Shenghou Zhu, Hari Sundaram,
and Belle L. Tseng. FacetNet: A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks. In Proceedings of 17th International World Wide
Web Conference (WWW 2008), pages 685–694, 2008.
[8] Min-Soo Kim and Jiawei Han. A Particle-and-density
Based Evolutionary Clustering Method for Dynamic
Networks. Proceedings of VLDB Endowment, 2(1):622–
633, August 2009.
[9] Pei Lee, Laks V.S. Lakshmanan, and Evangelos E.
Milios. Incremental Cluster Evolution Tracking from
Highly Dynamic Network Data. In Proceedings of the
30th IEEE International Conference on Data Engineering (ICDE 2011), pages 3–14, 2014.
[10] Francesco Folino and Clara Pizzuti. An Evolutionary
Multiobjective Approach for Community Discovery in
Dynamic Networks. IEEE Transactions on Knowledge
and Data Engineering, 26(8):1838–1852, 2014.
[11] Sungsu Lim, Seungwoo Ryu, Sejeong Kwon, KyominJung, and Jae-Gil Lee. LinkSCAN∗ : Overlapping Community Detection Using the Link-space Transformation. In ICDE, pages 292–303, 2014.
[12] Pei Lee, Laks V. S. Lakshmanan, and Evangelos E.
Milios. Incremental Cluster Evolution Tracking from
Highly Dynamic Detwork Data. In Isabel F. Cruz,
Elena Ferrari, Yufei Tao, Elisa Bertino, and Goce Trajcevski, editors, Proceedings of the 30th IEEE International Conference on Data Engineering (ICDE2011),
pages 3–14, 2014.
[13] R. C. Prim. Shortest connection networks and some generalizations. Bell System Technology Journal, 36:1389–
1401, 1957.
[14] Jianbin Huang, Heli Sun, Qinbao Song, Hongbo Deng,and Jiawei Han. Revealing Density-Based Clustering
Structure from the Core-Connected tree of a network.
IEEE TKDE, 25(8):1876–1889, 2013.

[18] Nurcan Yuruk, Mutlu Mete, Xiaowei Xu, and Thomas
A. J. Schweiger. Ahscan: Agglomerative hierarchical structural clustering algorithm for networks. In
ASONAM, pages 72–77, 2009.
[19] Dustin Bortner and Jiawei Han. Progressive Clustering of Networks using Structure-Connected Order ofTraversal. In ICDE, pages 653–656, 2010.
[20] Weizhong Zhao, Venkata Swamy Martha, and Xiaowei
Xu. Pscan: A parallel structural clustering algorithm
for big networks in mapreduce. In AINA, pages 862–
869, 2013.
[21] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A Density-Based Algorithm for Discovering
Clusters in Large Spatial Databases with Noise. In
KDD, pages 226–231, 1996.
[22] Mihael Ankerst, Markus M. Breunig, Hans-Peter
Kriegel, and Jörg Sander. Optics: Ordering points to
identify the clustering structure. In SIGMOD Conference, pages 49–60, 1999.
[23] Deepayan Chakrabarti, Ravi Kumar, and Andrew
Tomkins. Evolutionary Clustering. In Proceedings of
12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2006), pages
554–560, 2006.

塩川 浩昭 Hiroaki SHIOKAWA
筑波大学計算科学研究センター助教．2015 年筑波大学大学院シス
テム情報工学研究科博士後期課程修了．博士（工学）．データベー
ス，データマイニング，特に大規模グラフに対する分析アルゴリ
ズムの高速化に関する研究に従事．日本データベース学会，情報処理学会，ACM，AAAI 各会員．

藤原 靖宏 Yasuhiro FUJIWARA
日本電信電話株式会社 NTT ソフトウェアイノベーションセンタ
特別研究員．2003 年早稲田大学大学院理工学研究科電気工学専攻
修士課程修了．2011 年東京大学大学院情報理工学系研究科電子情報学専攻博士課程修了．博士（情報理工学）．データマイニングの研究開発に従事．情報処理学会，電子情報通信学会，日本デー
タベース学会各会員．

飯田 恭弘 Yasuhiro IIDA
日本電信電話株式会社 NTT ソフトウェアイノベーションセンタ
主任研究員．2000 年東京大学工学系研究科物理工学専攻修了．修士（工学）．データベース，データマイニング等の研究に従事．日
本データベース学会，ACM 各会員．

鬼塚 真 Makoto ONIZUKA
大阪大学大学院情報科学研究科教授．博士（工学）．ビッグデー
タ工学の研究に従事．日本データベース学会，情報処理学会，電子情報通信学会，ACM 各会員．

7

日本データベース学会和文論文誌
Vol. 14-J, Article No. 4, 2016 年 3 月