Scalable Algorithm for Probabilistic
Overlapping Community Detection

Kento Nozawa, Kei Wakabayashi
University of Tsukuba
WSDM 2017 workshop on SWM

Large Graph
It’s hard to analyze a large graph.
Examples:••••Citation networks
Co-author relationships
Social networks
Hyperlinks on web pages

Needs: Decomposition a large graphinto some smaller subgraphs
2Community Structures in Graph
In the same community,• nodes are densely connected internally• nodes resemble the others– Same affiliation– Same interest– Related research area3Overlapping CommunityEach node belongs to multiple communities.
Many graphs have overlapping communities– Ex. Related Research areas in co-author graph

EBxyA• Blue : Data mining• Red : Machine learning

A has published in both areas

C4w

Dz

Bag-of-nodes Representation
Bag-of-words for graph• A node corresponds to one document• The node and its adjacency list correspond to words in thedocument

EBw

xAyC
D
5Graphz

Node as doc

Nodes as words

A

A, B, C, D,E, x, y, z

B

B, A, E

CC, D, E, ADD, E, C, A

E

E, B, A, C, Dx

x, y, A, w

yy, A, x, zzz, y, A

w

w, x

Bag-of-nodes

Latent Dirichlet Allocation (LDA) [Blei+, 2003]• Probabilistic generative model for bag-of-words• Find topics from words co-occurrence• Each topic defines a distribution over all words

Coffee shop
drink drink
coffee coffee
coffee coffee
beans beans
espresso cafe
6Documents (bag-of-words)

coffeedrinkbeanscafe
…

0.15
0.15
0.14
0.13

author
citecitation
review…

0.14
0.12
0.110.11

Topics (distribution over all words)

LDA for Graph
A topic represents an overlapping community.
Each community is an affiliation probability distribution over nodes.
Node as doc

Nodes as words

A

A, B, C, D,E, x, y, z

B

B, A, E

CC, D, E, A

D

D, E, C, A

E

E, B, A, C, Dx

x, y, A, w

yy, A, x, z

zz, y, Aww, x7Graph as documents

E, C, D, B and A belong tothe community with high probabilityECDB
Axyzw

0.20
0.20
0.18
0.18
0.120.04
0.03
0.03
0.02

xyz
Aw
CD
B
E

0.22
0.22
0.20
0.15
0.07
0.05
0.04
0.04
0.01

Communities (distributions over nodes)

Stochastic Variational Inference [Mimno+, 2012]
Inference algorithms based on stochastic gradient descent––Update parameters based on sampling nodes in each iteration
mini-batch size : # sampling nodes as document
Node as doc

Nodes as words

A

A, B, C, D,E, x, y, z

B

B, A, E

Nodeas doc

Nodesas words

B

B, A, EC

C, D, E, AC

C, D, E, ADD, E, C, A

zz, y, A

EE, B, A, C, Dw

w, xxx, y, A, w

yy, A, x, zzz, y, Aw

w, x

When mini-batch size is 4

8sampling

Graph as documents

Experiment
Evaluation of scalability for the graph size
• Runtime for overlapping community detection

Quality metrics for overlapping communities• Triangle participation ratio (TPR)– Ratio of #nodes that belong to a triangle– Higher is better• Conductance– Ratio of #edges that link to an outer node– Lower is better9

Experimental Datasets
NameDBLP
OrkutFriendster#nodes317,080
3,072,441
65,608,366#edges1,049,866
117,185,083
1,806,067,135
From SNAP Datasets

Only Friendster:• Store into MySQL• Sample mini-batch size records from the table

10Comparison of Runtime

2hours7 min.

11#communities: 4,000#iterations: 1,000
Mini-batch size: 2,000

The Metrics of DBLP Communities
TPR: the median of SVBLDA is the third best
Conductance: the median of SVBLDA is the third worst

12#communities: 4,000#iterations: 1,000
Mini-batch size: 2,000

Parameter Sensitivity in DBLP
• Varying mini-batch size or # iterations
when fixing the other parameter• No significantly improvement of TPR/Conductancewhen mini-batch size > 3000 or # iterations > 2000

13

#iterations: 1,000

Mini-batch size: 2,000

Conclusion• Scalable community detection algorithm based on LDA
for large graph• About 2 hours to detect communities from the large graph• It’s unnecessary to set large mini-batch size and #iteration
for DBLP datasets

14