Please use this identifier to cite or link to this item:
|Title:||Clustering sparse graphs|
|Citation:||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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 15, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.