An efficient block model for clustering sparse graphs

Author: 

Gyenge, A
Sinkkonen, J
Benczúr, A

Publication Date: 

8 September 2010

Journal: 

Proceedings of the 8th Workshop on Mining and Learning with Graphs, MLG'10

Last Updated: 

2020-09-10T09:19:57.837+01:00

DOI: 

10.1145/1830252.1830261

page: 

62-69

abstract: 

Models for large, sparse graphs are found in many applications and are an active topic in machine learning research. We develop a new generative model that combines rich block structure and simple, efficient estimation by collapsed Gibbs sampling. Novel in our method is that we may learn the strength of assortative and disassortative mixing schemes of communities. Most earlier approaches, both based on low-dimensional projections and Latent Dirichlet Allocation implicitely rely on one of the two assumptions: some algorithms define similarity based solely on connectedness while others solely on the similarity of the neighborhood, leading to undesired results for example in near-bipartite subgraphs. In our experiments we cluster both small and large graphs, involving real and generated graphs that are known to be hard to partition. Our method outperforms earlier Latent Dirichlet Allocation based models as well as spectral heuristics. © 2010 ACM.

Symplectic id: 

974411

Submitted to ORA: 

Not Submitted

Publication Type: 

Conference Paper

ISBN-13: 

9781450302142