License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.779
URN: urn:nbn:de:0030-drops-47384
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4738/
Go to the corresponding LIPIcs Volume Portal

Kanade, Varun ; Mossel, Elchanan ; Schramm, Tselil

Global and Local Information in Clustering Labeled Block Models

pdf-format:
55.pdf (0.6 MB)

Abstract

The stochastic block model is a classical cluster-exhibiting random graph model that has been widely studied in statistics, physics and computer science. In its simplest form, the model is a random graph with two equal-sized clusters, with intra-cluster edge probability p, and inter-cluster edge probability q. We focus on the sparse case, i.e. p, q = O(1/n), which is practically more relevant and also mathematically more challenging. A conjecture of Decelle, Krzakala, Moore and Zdeborova, based on ideas from statistical physics, predicted a specific threshold for clustering. The negative direction
of the conjecture was proved by Mossel, Neeman and Sly (2012), and more recently the positive direction was proven independently by Massoulie and Mossel, Neeman, and Sly.

In many real network clustering problems, nodes contain information as well. We study the interplay between node and network information in clustering by studying a labeled block model, where in addition to the edge information, the true cluster labels of a small fraction of the nodes are revealed. In the case of two clusters, we show that below the threshold, a small amount of node information does not affect recovery. On the other hand, we show that for any small amount of information efficient local clustering is achievable as long as the number of clusters is sufficiently large (as a function of the amount of revealed information).

BibTeX - Entry

@InProceedings{kanade_et_al:LIPIcs:2014:4738,
  author =	{Varun Kanade and Elchanan Mossel and Tselil Schramm},
  title =	{{Global and Local Information in Clustering Labeled Block Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{779--792},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4738},
  URN =		{urn:nbn:de:0030-drops-47384},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.779},
  annote =	{Keywords: stochastic block models, information flow on trees}
}

Keywords: stochastic block models, information flow on trees
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI