Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/73252
Title: Clustering sparse graphs
Authors: Chen, Y.
Sanghavi, S.
Xu, H. 
Issue Date: 2012
Source: Chen, Y.,Sanghavi, S.,Xu, H. (2012). Clustering sparse graphs. Advances in Neural Information Processing Systems 3 : 2204-2212. ScholarBank@NUS Repository.
Abstract: We develop a new algorithm to cluster sparse unweighted graphs - i.e. partition the nodes into disjoint clusters so that there is higher density within clusters, and low across clusters. By sparsity we mean the setting where both the in-cluster and across cluster edge densities are very small, possibly vanishing in the size of the graph. Sparsity makes the problem noisier, and hence more difficult to solve. Any clustering involves a tradeoff between minimizing two kinds of errors: missing edges within clusters and present edges across clusters. Our insight is that in the sparse case, these must be penalized differently. We analyze our algorithm's performance on the natural, classical and widely studied "planted partition" model (also called the stochastic block model); we show that our algorithm can cluster sparser graphs, and with smaller clusters, than all previous methods. This is seen empirically as well.
Source Title: Advances in Neural Information Processing Systems
URI: http://scholarbank.nus.edu.sg/handle/10635/73252
ISBN: 9781627480031
ISSN: 10495258
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

22
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.