Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimal cluster recovery in the labeled stochastic block model
KTH, School of Electrical Engineering (EES), Automatic Control.
2016 (English)In: Advances in Neural Information Processing Systems, Neural information processing systems foundation , 2016, p. 973-981Conference paper (Refereed)
Abstract [en]

We consider the problem of community detection or clustering in the labeled Stochastic Block Model (LSBM) with a finite number K of clusters of sizes linearly growing with the global population of items n. Every pair of items is labeled independently at random, and label ℓ appears with probability p(i, j, ℓ) between two items in clusters indexed by i and j, respectively. The objective is to reconstruct the clusters from the observation of these random labels. Clustering under the SBM and their extensions has attracted much attention recently. Most existing work aimed at characterizing the set of parameters such that it is possible to infer clusters either positively correlated with the true clusters, or with a vanishing proportion of misclassified items, or exactly matching the true clusters. We find the set of parameters such that there exists a clustering algorithm with at most s misclassified items in average under the general LSBM and for any s = o(n), which solves one open problem raised in [2]. We further develop an algorithm, based on simple spectral methods, that achieves this fundamental performance limit within O(npolylog(n)) computations and without the a-priori knowledge of the model parameters.

Place, publisher, year, edition, pages
Neural information processing systems foundation , 2016. p. 973-981
Keywords [en]
Clustering algorithms, Parameter estimation, Stochastic systems, Cluster recovery, Community detection, Fundamental performance limits, Global population, Model parameters, Priori knowledge, Spectral methods, Stochastic block models, Stochastic models
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-216847Scopus ID: 2-s2.0-85019210642OAI: oai:DiVA.org:kth-216847DiVA, id: diva2:1160857
Conference
30th Annual Conference on Neural Information Processing Systems, NIPS 2016, 5 December 2016 through 10 December 2016
Note

Conference code: 127462; Export Date: 24 October 2017; Conference Paper. QC 20171128

Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2017-11-28Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records BETA

Proutiere, Alexandre

Search in DiVA

By author/editor
Proutiere, Alexandre
By organisation
Automatic Control
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 34 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf