DEIM Forum 2017 E2-1

ノードが複数の属性を持つグラフにおけるコミュニティ検出
伊藤

寛祥†

駒水

孝裕††

天笠 俊之††

北川 博之††† 筑波大学大学院システム情報工学研究科 〒 305-8573 茨城県つくば市天王台１丁目１−１†† 筑波大学計算科学研究センター 〒 305-8573 茨城県つくば市天王台１丁目１−１
E-mail: †hiro.3188@kde.cs.tsukuba.ac.jp, ††taka-coma@acm.org, {amagasa,kitagawa}@cs.tsukuba.ac.jp
あらましコミュニティ検出は，グラフデータの分析における重要な技術である．実世界に存在するグラフデータは

多くの場合，ノードを特徴づける複数種類の属性を保持している．この属性を用いることで，コミュニティ検出に加え，そのコミュニティの性質を検出できると考えられる．また，属性値にも，類似性に基いたクラスタが存在すると考えられる．コミュニティと属性値のクラスタは相互に関連すると考えられ，また，これらを同時に検出することで，コミュニティ検出と属性値のクラスタの検出が相補的に行われ，精度が向上することが期待されるが，複数の属性のクラスタを考慮したコミュニティ検出手法は存在しない．そこで，本研究では，コミュニティ検出と属性値のクラスタの検出，コミュニティと属性値のクラスタの間の関連性を同時に検出する手法を提案する．実データを用いた，ベースライン手法との比較実験により，コミュニティ検出の精度が 11%，属性値のクラスタ検出の精度が 7∼22%程度向上
することを確認した．
キーワード コミュニティ検出，非負値行列分解

1. は じ め に究者ネットワークにおいては，研究者をノードとすると，参加したことがある研究会議や，過去に投稿した論文，そこに含まコミュニティ検出とは，グラフにおいてノード間が密に接続れる単語などがノードの属性に対応する．Twitter においては，しているノードの部分集合を発見する問題である．コミュニ

ユーザをノードとすると，ユーザが発信したツイートに含まれティに属するノードは同様の性質をもつことが多く，この特性る単語やハッシュタグ，居住地などがノードの属性に対応する．

から，コミュニティ検出はノードの性質の推定 [5], [7], [18] や，

このような属性は，ノードと属性値との関係における偏りか

コミュニティへの情報の推薦 [8]，ノードの相互関係の分析 [2]ら，属性値のクラスタが存在すると考えられ，また，属性値のなど，さまざまなアプリケーションに応用されている．

クラスタは特定のコミュニティと関連すると考えられる．研究

コミュニティ検出をアプリケーションに応用する際には，コ

者ネットワークにおける属性のひとつである研究会議を例に挙ミュニティがどのような性質をもつかを検出することが重要でげると，ある研究者コミュニティは特定の分野の研究を行うたあり，近年よく研究されている．ノードのテキスト情報を用いめ，特定の分野の研究会議に参加し，また，その偏りから，研てコミュニティの性質を検出する手法として，グラフ中のコミュ究会議にもクラスタが存在する．このような，ノードの属性値

ニティと，そのコミュニティがどのようなトピックに関心をものクラスタの情報は，テキスト情報と同様に，コミュニティのつかを検出する手法が多く提案されている [13], [14], [17], [19]．

性質や関心を推定する際に有用な情報になると考えられる．

上に挙げた研究は，コミュニティとトピックが一対一対応といこれに対応し，ノードとエッジの種類が複数存在するグラフ

うモデリングをしている．しかしながら，コミュニティは複数をクラスタリングする手法が提案された [12], [16]．これらの研のトピックに関連があり，また，トピックは複数のコミュニティ

究はいずれも，すべてのノードのクラスタ数が同じという仮から関連付けられるという性質がある．学術研究を例にすると，定を置いている．しかしながら，各種属性はそれぞれ異なる粒ある研究者コミュニティは “データベース” と “データマイニン

度のクラスタをもち，コミュニティは複数のクラスタに関連をグ” の 2 つの研究分野に取り組むことがあり，また，“データもつ．たとえば，データベースに関連する研究会議は，データベース” の研究分野は複数の研究者コミュニティから研究されベースシステムや，データマイニングといったトピックを取りる．これに対し，Yin らはコミュニティとトピックを確率モデ扱うことから，単語のクラスタより研究会議のクラスタの方がルで同時にモデリングし，その間の関連性を検出する手法を提粒度が大きいと考えられる．また，研究者コミュニティは多く案した [20]．この研究では，コミュニティは複数のトピックにの場合複数の研究テーマに取り組み，研究会議には複数の研究関心を持ち，トピックは複数のコミュニティと関連するという者コミュニティの研究者が出席する．

モデリングを行っている．

そこで，本研究では，ノードが複数の属性をもつグラフか

ここで，実世界に存在するグラフデータの多くはノードが複ら，コミュニティ，属性値のクラスタ，コミュニティと属性値

数種類の属性を保持する．このようなグラフの例として，共著のクラスタとの関連性を検出する手法を提案する（図 1）．属に基づく研究者ネットワークや，Twitter などのソーシャルメ

性値のクラスタとは，ノードがもつ各種属性において，関連

ディアにおけるソーシャルネットワークがそれに該当する．研性の強い属性値の集合のことを指す．単語の属性を例にする

と，“database” と “query” など，よく共起する単語の集合がdatabase

query

xml

searchoptimize

learn

model

probabilistic

NIPS

ECML

単語の属性値のクラスタとなる．会議の属性を例にすると，“SIGMOD” や “VLDB” など，分野が近い会議の集合が会議の属性値のクラスタとなる．コミュニティと属性クラスタ，その間の関連性を検出することで，コミュニティがどのような事柄に関心があるかを知ることができ，さらに，コミュニティ間が

VLDB

SIGMOD

ICDT

EDBT

ICML

databasesearchminingmachine

query

query

frequent

learn

どのような事柄で共通しているかを検出することができる．
本研究では，非負値行列分解 (Non-negative Matrix Factor-

ization，以降 NMF と表記する) に基づき，コミュニティ検出，
属性値のクラスタ検出，コミュニティと属性値のクラスタ間の関係の検出を行う．ここで，これらをひとつの損失関数で表現することで，コミュニティの検出，属性値のクラスタの検出を

SIGMOD

連携させ，精度向上を狙う．すなわち，グラフ中のエッジ情報が欠損している場合でも，どの属性値のクラスタに関連するかに基づき，情報を補うことができ，また，属性値にノイズが存在する場合でも，どのコミュニティの属性値であるかを考慮す

VLDB

EDBT

PAKDD

ECML
SDM

ICML

KDD

NIPS

図 1 本研究の目的．本研究では，ノードが複数種類の属性を持つグラ
フから，コミュニティ，属性値のクラスタ，その間の関連性を検出することを目的とする．

ることで，属性値のクラスタリングの精度が向上することが期待される．
実験では論文データベース DBLP [1] を用い，手法の有用性の検証を行った．実験より，本手法で，研究者コミュニティ，属性値のクラスタ，その間の関係性の検出できることを示した．
また，既存の手法と比較して，コミュニティの検出精度が 11%，
属性クラスタの検出精度が 7∼22%程度向上することを示した．
本研究の貢献は以下である．

•

コミュニティと複数種類の属性の属性クラスタ，その間の関連性の検出という新しい問題を定義し，その検出に成功した．

•

非負値行列分解に基づく，上記の問題に対応した手法を提案し，効率的な最適化アルゴリズムを導出した．

•

既存のコミュニティ検出手法，属性クラスタの検出手法と比較し，コミュニティの検出精度を約 11%，属性値のクラス
タの検出精度を 7∼22%向上させた．
本論文の構成は以下である．2. 節で本研究と関連する研究に関して述べる．3. 節で本研究で取り組む問題の定義を行い，4.
節で本論文の提案手法に関して述べる．5. 節で，本研究で行った実験に関して述べ，6. 節で結論を述べる．

2. 関 連 研 究
コミュニティ検出に関する手法はさまざまなアプローチが存在
し，グラフの分割に基づく手法 [7], [15]，確率モデルに基づく手法 [21]，NMF に基づく手法 [9], [18] などが存在する．グラフの分割に基づく手法としては Newman-Girvan 法 [7]，n-cut [15]などが主要な手法として挙げられる．確率モデルに基づく手法としては Zhang らの SSN-LDA [21] が挙げられ，LDA [3]に基づきグラフ中のコミュニティを潜在確率変数としてモデリングし，ノードの多項分布としてコミュニティを検出した．

NMF に基づく手法として，Gegick らはグラフの隣接行列に対して NMF を適用することで，グラフ中のコミュニティを検出する Symmetric-NMF [9] を提案した．Yang らは，オーバーラップしたコミュニティを高速に検出する NMF に基づく手法

BigCLAM [18] を提案した．これらの手法は，グラフ中のノードの属性を考慮せず，グラフのエッジ情報のみに基づいたコミュニティ検出手法である．このような研究は，[4] によくまとめられているため，そちらも参照されたい．
近年では，コミュニティの検出に加え，コミュニティがもつ性質を検出する手法が提案されている．Yang らは，コミュ
ニティの検出に対し，ユーザが生成した情報を付与する手法

CESNA [19] を提案した．Wang らは，NMF に基づき，グラ
フにおけるコミュニティと，そのコミュニティに属するノードの属性のクラスタを同時に検出する手法 SCI [17] を提案した．Michael らは，トピックモデルに基づきコミュニティの検出と，コミュニティのトピックを検出する手法 Author-Topic

model [14] を提案した．本研究はテキストデータのみなど，ひとつの属性ではなく，複数種類の属性を用いる点でこれらの研究と異なる．
ノードとエッジの種類が複数種類存在するグラフデータに対するクラスタリング手法も近年よく研究されている．Yin らは，

NMF に基づいて，複数種類存在するノードをクラスタリング
する手法を提案した [12]．Sun らは，ランキングが上位のノードはクラスタにおける影響力も大きいという観点から，ノードのクラスタリングとノードのランキングを同時に行う手法を提案した [16]．これらの手法は各種ノードを単一のクラスタにク
ラスタリングする手法であるが，本研究の手法は，各種ノードをそれぞれ別種類とみなしてクラスタリングし，かつ，コミュ
ニティと属性クラスタとの関係性を明示的に得られるという点で，これらの研究と異なる．
本研究の立ち位置は，表 1 にまとめられる．本研究は，ノードがもつ複数種類の属性を考慮し，コミュニティと属性値のク
ラスタ，その間の関連性を検出する初の手法である．

3. 問 題 定 義
本研究では，複数種類の属性をもつグラフデータを対象に分表 1 コミュニティ検出に関連する研究との比較
コミュニティと属性値のクラスタとの関連性

エッジ情報のみ得られない[7], [9], [15], [18], [21]

得られる

–

テキスト情報を利用

複数種類の属性情報を利用[14], [17], [19][12], [16]

[20]

本研究

析を行い，コミュニティ，属性値のクラスタ，およびコミュニb ) 属性値のクラスタ

ティと属性値のクラスタとの関連性を検出する．本節では，提ノードが複数種類の属性をもつグラフ G が与えられた時，属案手法の入力である，ノードが複数種類の属性をもつグラフ

性 t ∈ T において，属性値同士がよく関連している属性値の集

データの定義，および，本研究の目的である，コミュニティ検合を属性 t ∈ T の属性値のクラスタとする．ここで，本研究で出，属性値のクラスタ検出，その間の関連性の検出のそれぞれは，各属性値は複数のクラスタに属するものとする．具体的にの問題定義を与える．

は，属性 t ∈ T の属性値のクラスタ数 k (t) が与えられた時，属ノードの集合とそれら間の関係性は，以下で定義される重み性値のクラスタ st ∈ St に属する属性値 x は確率分布 p(x | st )で与えられるものとする (|St | = k (t) )．

付きグラフで表現される．

c ) コミュニティと属性値のクラスタとの関連性
G ′ = ⟨V, E, W⟩ を重み付きグラフ

コミュニティc と属性 t ∈ T の属性値のクラスタ st が与えらとし，V をグラフ中のノード集合，E をグラフ中のエッジ集合，れた時，c が st と関連する確率をコミュニティと属性値のクラ定義 3.1 (重み付きグラフ)

W : E → R+ をエッジの重みとし，e ∈ E から実数 w ∈ R+ へ

スタとの関連性とする．ここで，コミュニティは複数の属性値の写像とする．□のクラスタに関連するものとする．具体的には，コミュニティ

さらに，グラフ中の各ノードは複数の属性で特徴づけられる．
ここで，本研究では属性値は数値ではなく，集合で与えられるものとする．ノードと属性値との間の関係性は二部グラフで表現される．これを属性グラフとし，以下に定義する．

c と属性 t ∈ T の属性値のクラスタの集合 St が与えられた時，
コミュニティc と属性 t ∈ T のクラスタ st ∈ St との関連性は確率分布 p(st | c) で与えられるものとする．
以上を踏まえ，本研究の目的である，コミュニティ検出，属性値のクラスタ検出，コミュニティと属性値のクラスタとの関

定義 3.2 (属性グラフ) 属性 t ∈ T の属性値集合を Xt とし，ノードと Xt との 2 部グラフを属性グラフ Gt = ⟨V ∪ Xt , Et , Wt ⟩とする．Et はエッジ集合であり，Wt : Et → R+ はエッジの重みで，エッジ e ∈ Et から実数 w ∈ R+ への写像とする．□

連性の検出を以下に定義する．
定義 3.4 (本研究の目的)

ラフ G が与えられた時，以下の３つを検出することである．

•

コミュニティ：∀n ∈ V, ∀c ∈ C, p(n | c) (ここで，|C| = l)

本研究では，ノードは複数の属性 T で特徴づけられるものとする．ノードが複数種類の属性をもつグラフの定義は以下でノードが複数種類の属性をもつグ•

属性値のクラスタ：∀t ∈ T , ∀x ∈ Xt , ∀st ∈ St , p(x | st ) (ここで，|St | = k(t) )ある．

•
定義 3.3 (ノードが複数種類の属性をもつグラフ)

重み付き∀c ∈ C, ∀t ∈ T , ∀st ∈ St , p(st | c)

グラフ G ′ = ⟨V, E, W⟩ と，複数の属性グラフ {Gt }t∈T （ここで，Gt = ⟨V ∪ Xt , Et , Wt ⟩ である）が与えられたとき，これらによっ⟨⟩て構成されるグラフ G = G ′ , {Gt }T
t=1 をノードが複数種類の属性をもつグラフとする．□

コミュニティと属性値のクラスタとの関連性：□

4. 提 案 手 法
本節では，NMF にもとづき，複数種類の属性をもつグラフ
から，コミュニティ，属性値のクラスタ，その間の関連性を検

本研究では，ノードが複数種類の属性をもつグラフから，コ出する手法を提案する．具体的には，コミュニティと属性値のミュニティ，属性値のクラスタ，コミュニティと属性値のクラクラスタを NMF に基づきモデリングし，コミュニティと属性

スタとの関連性の３つを検出することを目的とする．はじめに，値のクラスタを関連付ける行列を新たに設定し，それらを同時

それぞれの問題に関する本研究での仮定を述べる．

に行列分解することで，3. 節で挙げた情報を検出することを目a ) コミュニティ
ノードが複数種類の属性をもつグラフ G において，以下の２

指す．

4. 1 損 失 関 数つの性質をもつノード集合をコミュニティとする．(1) コミュ

ここでは，本研究で設定する損失関数に関して記述する．はニティに属するノード間はコミュニティ外と比較して密にエッ

じめに，入力となる行列の構成，コミュニティ検出，属性値のジが接続されている．(2) コミュニティに属するノードは似たクラスタの検出，その間の関連性の検出に関する損失関数の設性質をもつ．ここで，本研究では，各ノードは複数のコミュニ定に関して記述する．つづいて，それらを統合した損失関数にティに属するものとする．具体的には，コミュニティ数 l が与関して詳細を記述する．

えられた時，コミュニティc ∈ C に属するノード n ∈ V は確率分布 p(n | c) で与えられるものとする (|C| = l)．

入力行列の構成: 本手法では，ノードが複数種類の属性を持つグラフを，グラフの隣接行列 A ∈ R|V |×|V | と，ノードと 属性

t ∈ T の属性値との関係を表現する行列 X (t) ∈ R|V|×|X
現する．行列 A の各要素は Au,v = wu,v /

(t)

∑

|

で表

u,v wu,v とする．こarg minU (t) − U ∗ R(t)2(3)

こで，wu,v = W(eu,v ) はノード u とノード v の間のエッジの重U (t) ,U ∗ ,R(t) >=0

みを指し，Au,v は複数種類の属性をもつグラフ G においてノー(t)s.t. ∀1 <=r<= k , ∀0 <
=p<
= l,

ド u, v が接続される確率 p(u, v) を表す．行列 X
(t)

(t)

Xu,x = wu,x /

∑

(t)

(t)

の各要素は

(t)

(t)

U·,r

(t)

u,x wu,x とする．ここで，wu,x = Wt (eu,x ) は

ノード u と属性 t における属性値 x とのエッジの重みを指し，(t)∗= 1, U·,p= 1, Rp,·
1

F

(t)

1

=1
1

また，この項は，ノードと属性値のクラスタとの関連を表す

Xu,x は複数種類の属性をもつグラフ G においてノード u が属

行列を，ノードがどのコミュニティに属するかを表現する行列性値 x をもつ確率 p(u, x) を表す．

と，コミュニティと属性値のクラスタの行列に分解する，非負

コミュニティ検出の損失関数：グラフ中のコミュニティを行∗
列 U ∗ ∈ R|V|×l で表現し，各要素 Uu,cをノード u がコミュニ

値行列分解と解釈することができる．すなわち，この項を最適化することで，著者がどの属性値のクラスタに関連するかといティc に属する確率 p(u | c) とする．ここで l はコミュニティ

う情報を，グラフ構造に基づくコミュニティの検出に対して付数である．ノード u と v がコミュニティc においてエッジが存与することを意味している．

∗∗
在する確率は Uu,cUv,cで表現され，複数種類の属性をもつグ

ラフにおいてノード u と v でエッジが存在する確率 p(u, v) は統合した損失関数：本手法では，コミュニティ検出，属性値∑のクラスタの検出，その間の関連性をひとつの損失関数でモデ構造を最もよく表現する U は以下の損失関数を最小化する U

ラスタの検出がそれぞれの情報を補い合うことを狙いとする．

である．

コミュニティ検出に関する損失関数，属性値のクラスタの検出∗∗c∈C Uu,c Uv,c で表現される．すなわち，グラフ中のエッジの
∗
∗

∗

∗ T

arg min A − U (U )U ∗>=0s.t. ∀1 <
=p<
= l,

2

リングする．こうすることで，コミュニティ検出，属性値のクに関する損失関数，コミュニティと属性値のクラスタの関連性(1)
Fの検出に関する損失関数をすべて合わせると，以下の損失関数

∗
U·,p
=1
1

が得られる．

属性値のクラスタの検出に関する損失関数：属性 t の属性値のクラスタを表す行列を V (t) ∈ R|X(t)|×k(t)

で表現し，各要素

L=arg minT
U ∗ , {U (t) , V (t) , R(t) }t=1 >=0(t)Vx,st は属性値 x がクラスタ st に属する確率 p(x | st ) とする．
ここで k (t) は属性 t のクラスタ数である．本研究では V (t) を，+グラフのノードと属性値との関係から検出する．グラフのノードと属性値のクラスタとの関連を行列 U (t) ∈ R|V|×k

(t)

T {
∑

X (t) − U (t) (V (t) )T

t=1

で表現

+λt U (t) − U ∗ R(t)(t)

し，各要素 Uu,st は，ノード u が属性値のクラスタ st に属する確率 p(u | st ) とする．ノード u が属性 t の属性値のクラスタ
(t)

(t)

st において属性値 x に関連する確率 p(u, c | st ) は Uu,st Vx,stで表現され，グラフにおいてノード u と属性値 x にエッジが存在する確率 p(u, x) は

∑

(t)
(t)
st ∈St Uu,st Vx,st で表現される．すな(t)

わち，グラフ中のエッジの構造を最もよく表現する行列 U

V

(t)

，

は以下の損失関数を最小化する行列である．

2

2

A − U ∗ (U ∗ )T

F

2
F

}
(4)

F

(t)
s.t. ∀1 <= T,=r<= k , ∀1 <=p<
= l, ∀1 <
=t<
∗
U·,p
= 1, U·,r
1

(t)

(t)

(t)
1

= 1, V·,r1= 1, Rp,·=1
1

ここで λt はユーザが与えるパラメータであり，属性 i の属
性値のクラスタがコミュニティの検出に対して与える影響力の大きさとなる．この λt が大きくなるほど，属性値のクラスタ

arg min2

X (t) − U (t) (V (t) )T

(2)

(t)

< k(t) , U·,rs.t. ∀1 <
=r=

(t)

1

= 1, V·,r=1
1

コミュニティと属性値のクラスタの関連性の検出に関する損失関数：本研究では，ノードのコミュニティと属性値のクラス
タ t との間の関連を示す行列を R(t) ∈ Rl×k(t)がコミュニティの検出に対して与える影響力が大きくなる．

4. 2 最 適 化

FU (t) ,V (t) >=0式 4 はすべての変数に関して同時に凸にならない．本研究では [11] に基づいて各変数に関して更新式を導出し，それを繰り返し実行することで最適化を行う．KKT 条件は以下で表される．

で表現し，各要(t)

素 Rst ,c をコミュニティc が属性値のクラスタ st に関連する確率 p(st | c) とする．本研究では，ノードがどのコミュニティに属するかを表現する行列 U ∗ に対して R(t) で線形写像することで，ノードがどの属性値のクラスタに属するかを表現する行
列 U (t) に変換することを考える．すなわち，以下の損失関数を最小化するような R(t) を求めることで，コミュニティと属性値のクラスタとの関係を得ることができる．

(t)
(t) >
(t) >
U∗ >
0
= 0, U >= 0, V= 0, R =∇U ∗ L >=0= 0, ∇U (t) L >= 0, ∇V (t) L >= 0, ∇R(t) L >∗U ⊙ ∇U ∗ L = 0, U
V

(t)

(t)

⊙ ∇V (t) L = 0, R

(5)
(6)

⊙ ∇U (t) L = 0,(t)

⊙ ∇R(t) L = 0

続いて各変数に関する勾配は，以下で表される．

(7)

Algorithm 1 Optimization Algorithm
Require: A, {X (t) }t∈T , {λt }t∈T , ϵ∇U ∗ L = − 2AT RU ∗ + 2U ∗ (U ∗ )T U ∗+T∑

Ensure: U ∗ , {U (t) , V (t) , R(t) }t∈T
1: U ∗ , {U (t) , V (t) , R(t) }t∈T ← random non-negative init

λt (−U (t) (R(t) )T + U ∗ R(t) (R(t) )T )′(8)

2: ϵ′ ← maxInt, ϵ ← ϵ2

t=1

∇U (t) L = − X

(t)

(t)

V

+U

(t)

(t) T

(V

) V

3: while abs(ϵ′ − ϵ) >= ϵ do(t)+ λt (U (t) − U ∗ R(t) )∇Ri L = − (U ) U

(t)

∗ T

∗

+ (U ) U R

(t)

5:
6:

for t ∈ T do

(11)

7:

U (t) ← U (t) ⊙8:V (t) ← V (t) ⊙9:U (t) ← U (t) Q

AT U ∗ +∑T(t)(R(t) )Ti=1 λt U∑
T
2U ∗ (U ∗ )T U ∗ + i=1 U ∗ R(t) (R(t) )T
X (t) V (t) + λt U ∗ R(t)U (t) ← U (t) ⊙ (t) (t)U (V )T V (t) + λt U (t)V (t) ← V (t) ⊙R(t) ← R(t) ⊙

(12)

(13)

U ∗ U (t)

(t)

(t)

U·,r

(t)

V·,r

= 1,
1

=
1

1

化の際に適用する．

U∗ ← U

Q

(

(

(16)

)−1
(18)

(t)

)−1
(19)

i=1

|X (t) |Q(t) = Diag 

∑
i=1

13:

end for14:

ϵ′ ← ϵ15:

ϵ ← L U ∗ , {U (t) , V (t) , R(t) }t∈T()

るためである．行列の正規化を行わない状態では，各行列の要素の値域が異なる場合が想定され，行列を更新する際に値域が大きい行列の影響が大きくなる可能性がある．このため，本研
究では，Algorithm1 で示した手順で最適化を行う．

5. 実

験

実験に使用したデータセットと提案手法の適用方法に関して述
ラスタ，コミュニティと属性値のクラスタとの関係を掲載する．

5. 3 節で，コミュニティ検出，属性値のクラスタ検出の精度に関して，本手法と関連する手法とを比較する．最後に，5. 4 節
で，パラメータの変化で，出力にどのような影響を与えるか議

本研究では論文データベース DBLP を用い，手法の検証，評

i=1|X (t) |(t)

Ui,1 ,∑

価を行った．Digital Bibliography Project (DBLP) [1] はコン|X (t) |(t)Ui,2 , · · · ,i=1∑

ピュータサイエンス分野の論文データベースである．本研究では，４つの研究分野 (データベース，データマイニング，情報検

(t)

i=1

i,l

i=1

(20)

Ui,k(t) 

 (t)

k
k(t)
k(t)
∑
∑
∑
(t)
(t)
(t)
(t)
QR = Diag 
Ri,1 ,
Ri,2 , · · · ,
R 
i=1

)

5. 1 データセット



|V|
|V|
|V|
∑
∑
∑
∗
∗
∗ 
Q∗ = Diag 
Ui,1
,
Ui,2
,··· ,
Ui,l

R(t) ← R(t)論する．

ここで，Q∗ , Q(t) , QR は

i=1

12:

U ∗ U (t)(U ∗ )T U ∗ R(t)
−1
(t)
QR

べる．5. 2 節で，実際に検出されたコミュニティ，属性値のク(17)

V (t) ← V (t) Q(t)R(t) ← R(t) QR

R(t) ← R(t) ⊙本節では，提案手法の有用性に関して議論する．5. 1 節で，)∗ −1

U (t) ← U (t) Q(t)V (t) ← V (t) Q(t)11:)

これは，行列を更新した際，各列の和が 1 になることを保証す= 1 を満たすため，以下に示す正規化の式を，最適(∗(X (t) )T U (t)(U (t) )T U (t) (V (t) )T(t) −1

示される．ここで，行列の正規化は次の行列の更新の前に行う．

(15)(U ∗ )T U ∗ R(t)単調減少し，ある程度収束したところで行列分解が完了する．

Rp,·

U ∗ R(t) (R(t) )T

X (t) V (t) +λt U ∗ R(t)U (t) (V (t) )T V (t) +λt U (t)

10:

(

t∈T

(14)

式 12，13，14，15 を繰り返し適用することで，損失関数は1,(λt U (t) (R(t) )T

16: end while(X (t) )T U (t)(U (t) )T U (t) (V (t) )T∗
式 4 における条件， U·,p
= 1,
1

∑

t∈T

2U ∗ (U ∗ )T U ∗ +(10)を導出した．

∑

AT U ∗ +U ∗ ← U ∗ (Q∗ )−1

式 7 に対して勾配を代入することで，各変数に関して更新式

U∗ ← U∗ ⊙U∗ ← U∗ ⊙(9)∇V (t) L = − (X (t) )T U (t) + (U (t) )T U (t) (V (t) )T∗ T

4:索，機械学習) に [6] で人手で分類された著者 4019 名が，人手で４つの分野に分類された特定の 20 の会議 (1 分野あたり 5 つの会議) で 2009 年までに発表した論文 10491 件をデータセッ(21)

トとして用いる．
本研究では論文の著者をグラフのノードとし，共著関係をグ

(22)

i=1

である．
以上をまとめると，最適化のアルゴリズムは Algorithm1 でラフのエッジ，共著で論文を発表した回数をグラフの重みとする．また，ノードがもつ属性としては，“単語” と “論文”，“会議” とする．各属性に関して以下に詳細を記載する．

•

単語 : 単語の集合を，この属性の属性値集合とする．著という結果が出力されたことがわかる．図 2(c) は本手法で検出者がこれまでに発表した論文に含まれる単語に対してエッジがされた，“michael i. jordan” が所属する研究コミュニティと，そ存在するものとし，エッジの重みは著者がこれまで発表した論

れに関連する属性値のクラスタを記述したものである．図 2(c) を文に含まれる各単語の出現回数とする．ここで，本研究ではス

見ると，このコミュニティは “NIPS,ICML,UAI,COLT,ECML”

トップワードの除去と，ステミング処理を行った．属性値としという機械学習に関係する会議によく参加し，“learn, model,て使用する単語数は 1367 とした．

network”, “expert model”, “predict process” という研究テー•

論文 : 論文の集合を，この属性の属性値集合とする．著

マに関連するという結果が出力されたことがわかる．

者がこれまでに発表した論文に対してエッジが存在するものと

5. 3 関連手法との検出精度の比較

し，エッジの重みは常に 1 とする．属性値として使用する論文

本節では，コミュニティの検出精度，属性値のクラスタの検出精度に関して，関連手法と比較を行う．本研究では，以下の数は上記の項目で述べたとおりである．

•

会議 : 会議の集合を，この属性の属性値集合とする．著者が発表した論文がこれまでに掲載されたことのある会議に対手法と比較を行った．

•

NMF: 通常の NMF．著者-単語 (A-T)，著者-論文 (A-してエッジが存在するものとし，エッジの重みは著者が発表しP)，著者-会議 (A-C)，単語-論文 (T-P)，単語-会議 (T-C) の関た論文が各会議に掲載された回数とする．属性値として使用す（注 1）
係で作成される行列に対して，それぞれ NMF を適用する．

•

る会議数は上記の項目で述べたとおりである．

LCTA [20]: コミュニティとトピックを同時にモデリン

5. 2 実際に検出された出力

グした確率的生成モデル．コミュニティとトピック，その間の本節では，本手法をデータセットに対して適用し，検出され関係性を検出することができる．

たコミュニティと属性値のクラスタ，その間の関係性に関して•

HINMF [12]: 複数種類の属性をもつデータを対象とし，議論する．ここでは，コミュニティ数と単語の属性値のクラス

属性とデータとを同時にクラスタリングする NMF に基づく

タ数を 50，会議のクラスタ数を 4 に設定して実験を行った．図手法．

2(a)， 図 2(b)， 図 2(c) は，それぞれ本手法で検出された出力である．図中の赤い四角形がコミュニティを表し，中に列挙

本研究では Accuracy で定量的に精度の評価を行う．Accu-

racy の定義は以下である．

されている名前が，コミュニティに属するメンバーである．名
前の脇の数値は，研究者 u が研究コミュニティc に属する確率

定義 5.1 (Accuracy) ある集合中の要素 n ∈ S ，その要素の∗p(u | c) = Uu,cを表す．ここではコミュニティに属する確率がラベル Sn ，ある手法から得られたラベル rn が与えられた時，0.01 以上の研究者を記載している．図中の灰色の四角形が研

Accuracy は以下で定義される．

∑

究会議の属性値のクラスタ，青色の四角形が単語の属性値のクラスタを表現しており，四角形の中に，クラスタを構成する属
性値が記述されている．属性値の脇の数値は，属性 t の，ある(t)

属性値 x が属性値のクラスタ st に属する確率 p(x | st ) = Vx,stを表し，確率の大きい属性値から上位 5 つを記載している．コミュニティと属性値のクラスタを結ぶ線は，コミュニティと属性値のクラスタが関連していることを表しており，線の脇の数
値はコミュニティc が，属性 t の，ある属性値のクラスタ st と(t)

Accuracy =n∈S δ(sn , map(rn ))

|S|

(23)

ここで，|S| 集合 S 全体の大きさ，δ(x, y) はデルタ関数で，x = yのときに 1，それ以外のときに 0 をとる関数である．map(rn )は著者 n が対応するラベル rn をデータセット中のラベルにマッピングする関数である．最良のマッピングは Kuhn-Munkres ア
ルゴリズム [10] によって発見する．□

関連する確率 p(st | c) = Rst ,c を表している．また，ここでは

ここでは，コミュニティ数を 4，各属性のクラスタ数を 4 に研究コミュニティと関連度が大きい上位 3 つの属性値のクラス

それぞれ設定し，本手法と関連手法との Accuracy の比較をタを記載している．

行った．正解セットは，“著者” と “研究会議” に関しては人手

図 2(a) は 本 手 法 で 検 出 さ れ た ，“jiawei han” が 所 属 すによるラベル，“論文” に関しては人手によるラベリングされたる研究コミュニティと ，それに関連する属性値 のクラス タ

会議群から発表された論文，“単語” は各会議群から発表されを 記 載 し た も の で あ る ．図 2(a) を 見 る と ，“jiawei han”

た論文に含まれる単語のうち最も出現する単語上位 10 件とし，は 多 く の 中 国 人 の 研 究 者 と 研 究 コ ミュニ ティを 形 成 し ，Precision@10で評価する．

“KDD,ICDM,SDM,PAKDD,VLDB” というデータマイニン

表 2 は各手法で検出された各クラスタに関する Accuracy

グに関係する会議によく参加し，“cluster”，“graph classif ” との値をまとめたものである．それぞれの手法で検出できない

いった研究テーマに関連しているという結果が出力されたこ

タスクは N/A となっている．表 2 をみると，コミュニティのとがわかる．図 2(b) は本手法で検出された，“michael stone-

検出精度 (Author) に関しては，本手法が関連研究と比較してbraker” が所属する研究コミュニティと，それに関連する属性

11% Accuracy が改善していることがわかる．また，属性値の値のクラスタを記述したものである．図 2(b) を見ると，こクラスタの検出精度に関しては，Paper（論文）のクラスタ検のコミュニティは “SIGMOD,VLDB,PODS,EDBT,ICDT ” というデータベースに関係する会議によく参加し，“system up-date”,“algorithm”,“query” といった研究テーマに関連している（注 1）：NMF は共起関係に基づいたクラスタリング手法であるが，論文-会議
は 1 対 1 の関係であるため，共起関係を得られず，クラスタリングを行うことができない．このため，ここでは論文-会議 (P-C) の行列は除外する．

cluster
0.123
data
0.063
base
0.056
eﬃci
0.047
dimension 0.047

0.044

KDD
0.304
ICDM
0.202
SDM
0.096
PAKDD 0.094
VLDB
0.073

0.999

jiawei han
0.223
xifeng yan 0.049
hong cheng 0.026
ke wang
0.018
xiaoxin yin 0.011
feida zhu
0.010
chen chen 0.010

larg

0.037

0.046

graph
scale
attribut

0.092
0.085
0.079
0.067
0.051

approachmethodsupportstructurselect

0.244
0.116
0.097
0.074
0.051

0.039 classif

systemview
updat
maintenmanag

SIGMOD 0.420
VLDB
0.391
PODS
0.103
EDBT
0.064
ICDT
0.020

0.999

michael stonebraker
0.123
samuel madden
0.018
lawrence a. rowe
0.014

0.064

algorithm 0.176
process 0.097
0.074
metric0.0385
control
0.0367NIPS
0.478
ICML 0.217
UAI
0.210
COLT 0.078
ECML 0.017

0.041 distanc

0.040(a) コミュニティ; “Jiawei Han”

0.104
0.062
0.061
0.05450.0488

queri
evalu
web
integrdistribut

0.999

0.116
0.051
0.039
0.03690.0348michael i. jordan
0.216
satinder p. singh
0.020
lawrence k. saul
0.017
xuanlong nguyen
0.011
jiawei han
0.011

model
expertterriernonneg

0.079
0.057
0.051
0.042
0.037

process
predict
dynam
state
gener

0.117
0.080
0.068
0.048
0.030

0.044 glasgow

0.042(b) コミュニティ; “Michael Stonebraker”

learn
0.113
model
0.049
network 0.042
bayesian 0.025
decis
0.0234(a) コミュニティ; “Michael I. Jordan”

図 2 研究者コミュニティのメンバーと，コミュニティに関連する属性値のクラスタ
表 2 コミュニティ検出，属性値のクラスタ検出の Accuracy ，P recision@10

Algorithm

Author

Term

Paper

Conference

NMF (A-T)

64.02 ± 5.73

72.50 ± 0.00

N/A

N/A

NMF (A-P)

43.12 ± 5.17

N/A

44.58 ± 5.89

N/A

NMF (A-C)

75.35 ± 6.85

N/A

N/A

87.60 ± 1.73

NMF (T-P)

N/A

52.50 ± 8.91

50.02 ± 7.93

N/A

NMF (T-C)

N/A

68.38 ± 5.88

N/A

69.88 ± 6.68

LCTA

42.47 ± 4.77

67.19 ± 5.65

N/A

N/A

HINMF

68.90 ± 9.08

70.38 ± 4.05

56.46 ± 3.08

90.10 ± 12.63

Proposed

86.34 ± 2.39

69.10 ± 6.34

78.19 ± 9.87 97.20 ± 5.21

20
0
10-4

10-1
λt

100

101

(a) Accuracy; Author

102

Document

100

80
60
40
20
0
10-4

NMF(A-T)
NMF(T-P)
NMF(T-C)LCTA
HINMF
Proposed

10-3

20
10-2

10-1
λt

100

101

102

(b) Accuracy; Term

80

60
40

0
10-4

Conference

100

80
Accuracy(%)

40

NMF(A-T)
NMF(A-P)
NMF(A-C)LCTA
HINMF
Proposed
10-3 10-2

Precision@10(%)

Accuracy(%)

80
60

Term

100

Accuracy(%)

Author100

NMF(A-P)
NMF(T-P)
HINMF
Proposed
10-3 10-2

60
40
20

10-1
λt

100

101

102

(a) Accuracy; Paper

0
10-4

NMF(A-C)
NMF(T-C)
HINMF
Proposed
10-3 10-2

10-1
λt

100

101

102

(b) Accuracy; Conference

図 3 パラメータ λt を変化させた際の Accuracy の変化

出に関して 22%，Conference（会議）のクラスタ検出に関して

図 3(a), 図 3(b), 図 3(c), 図 3(d) はパラメータ λt を変動さ

7% Accuracy が改善したことが分かる．これは，コミュニティ

せた際の精度の変動をプロットしたものである．本手法の精度

検出と属性値のクラスタの検出を同時行い，その間の関係性をに加え，比較手法の精度を同時にプロットしている．本研究で同時にモデリングすることで，それぞれの検出精度が向上した

は，各パラメータをすべて同じ値に設定して実験を行った．図ことを示している．

を見ると，どのタスクにおいても λt = 0.005, 0.01 のときに最5. 4 パラメータ設定
本節では，提案手法に存在するパラメータ λt を変動させた
ときに，出力結果がどのように変化するかを議論する．本手法

も高い精度でクラスタリングが行われることが分かる．

6. 結

論

では，属性 t の属性値のクラスタがコミュニティの形成にどれ

本研究では，ノードがもつ複数種類の属性に着目し，グラフだけの影響力を与えるかを，パラメータ λt で調節する．λt が中のコミュニティと属性のクラスタ，その間の関係性を検出す大きいほど，属性 t の属性値のクラスタがコミュニティ形成にる手法を提案した．実験より，本手法によって，コミュニティ

与える影響力が大きくなり，小さいほどコミュニティ形成に与と属性のクラスタ，その間の関係性が検出できることを示し，える影響力が小さくなる．このため，パラメータの値が小さす

また，既存手法と比較して，コミュニティと属性値のクラスタ

ぎると，属性値のクラスタがノード間のエッジの情報を補い，の検出精度が向上したことを示した．

精度を向上させる効果が得られないと考えられる．また逆に，今後の展望としては，コミュニティ，属性値のクラスタの時パラメータの値が大きすぎると，属性値のクラスタがコミュニ

間的な変遷を検出する手法への拡張や，情報の伝播を推定する

ティの形成に与える影響力が大きすぎて，ノード間のエッジの手法への拡張などが考えられる．

情報を無視する結果になり，精度が低下すると考えられる．

謝

辞本研究の一部は，JSPS 科研費 JP25240014，NICT 高度通
信・放送研究開発委託研究「欧州との連携による公共ビッグデー
タの利活用基盤に関する研究開発」の助成を受けたものです．

文

献[1] DBLP. http://www.informatik.uni-trier.de/˜ley/db/.
[2] Edoardo M Airoldi, David M Blei, Stephen E Fienberg, andEric P Xing. Mixed membership stochastic blockmodels.
Journal of Machine Learning Research, Vol. 9, No. Sep,
pp. 1981–2014, 2008.
[3] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent dirichlet allocation. Journal of Machine Learning Research, Vol. 3, pp. 993–1022, 2003.
[4] Santo Fortunato. Community detection in graphs. Physics
reports, Vol. 486, No. 3, pp. 75–174, 2010.
[5] Mario Frank, Andreas P Streich, David Basin, andJoachim M Buhmann. Multi-assignment clustering forboolean data. Journal of Machine Learning Research,
Vol. 13, No. Feb, pp. 459–489, 2012.
[6] Jing Gao, Feng Liang, Wei Fan, Yizhou Sun, and Jiawei
Han. Graph-based consensus maximization among multiple
supervised and unsupervised models. In Advances in Neural
Information Processing Systems, pp. 585–593, 2009.
[7] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of thenational academy of sciences, Vol. 99, No. 12, pp. 7821–
7826, 2002.
[8] Junzo Kamahara, Tomofumi Asakawa, Shinji Shimojo, andHideo Miyahara. A community-based recommendation system to reveal unexpected interests. In Multimedia Modelling
Conference, 2005. MMM 2005. Proceedings of the 11th International, pp. 433–438. IEEE, 2005.
[9] Da Kuang, Chris Ding, and Haesun Park. Symmetric nonnegative matrix factorization for graph clustering. In Proceedings of the 2012 SIAM International Conference on
Data Mining, pp. 106–117. SIAM, 2012.
[10] Harold W Kuhn. The hungarian method for the assignment
problem. Naval research logistics quarterly, Vol. 2, No. 1-2,
pp. 83–97, 1955.
[11] Daniel D Lee and H Sebastian Seung. Learning the parts ofobjects by non-negative matrix factorization. Vol. 401, pp.
788–791. Nature Publishing Group, 1999.
[12] Jialu Liu and Jiawei Han. Hinmf: A matrix factorization method for clustering in heterogeneous information networks. In Proceedings of the international joint conference
on artificial intelligence workshop, 2003.
[13] Yan Liu, Alexandru Niculescu-Mizil, and Wojciech Gryc.
Topic-link lda: joint models of topic and author community.
In proceedings of the 26th annual international conferenceon machine learning, pp. 665–672, 2009.
[14] Michal Rosen-Zvi, Thomas Griﬃths, Mark Steyvers, andPadhraic Smyth. The author-topic model for authors anddocuments. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pp. 487–494. AUAI Press,
2004.
[15] Jianbo Shi and Jitendra Malik. Normalized cuts and image
segmentation. IEEE Transactions on pattern analysis andmachine intelligence, Vol. 22, No. 8, pp. 888–905, 2000.
[16] Yizhou Sun, Yintao Yu, and Jiawei Han. Ranking-based
clustering of heterogeneous information networks with star
network schema. In Proceedings of the 15th ACM SIGKDD
international conference on Knowledge discovery and data
mining, pp. 797–806. ACM, 2009.

[17] Xiao Wang, Di Jin, Xiaochun Cao, Liang Yang, and Weixiong Zhang. Semantic community identification in large attribute networks. In AAAI, pp. 265–271, 2016.
[18] Jaewon Yang and Jure Leskovec. Overlapping community
detection at scale: a nonnegative matrix factorization approach. In Proceedings of the sixth ACM international conference on Web search and data mining, pp. 587–596. ACM,
2013.
[19] Jaewon Yang, Julian McAuley, and Jure Leskovec. Community detection in networks with node attributes. In 2013
IEEE 13th International Conference on Data Mining, pp.
1151–1156. IEEE, 2013.
[20] Zhijun Yin, Liangliang Cao, Quanquan Gu, and Jiawei Han.
Latent community topic analysis: integration of community
discovery with topic modeling. ACM Transactions on Intelligent Systems and Technology (TIST), Vol. 3, No. 4, p. 63,
2012.
[21] Haizheng Zhang, Baojun Qiu, C Lee Giles, Henry C Foley,
and John Yen. An lda-based community structure discovery approach for large-scale social networks. ISI, Vol. 200,
, 2007.