Spectral clustering for multiclass Erdös-Rényi graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this article, we study the properties of the spectral analysis of multiclass Erdös-Rényi graphs. With a view towards using the embedding afforded by the decomposition of the graph Laplacian for subsequent processing, we analyze two basic geometric properties, namely interclass intersection and interclass distance. We will first study the dyadic two-class case in details and observe the existence of a phase transition for the interclass intersection. We then focus on the general multiclass case, where we introduce an appropriate notion of diagonal concentration and derive a statistical model that allows sampling graphs whose expected diagonal concentration is fixed. The simulations provided yield useful guidelines for practitioners to choose appropriately parameters in the context of spectral clustering.

Original languageEnglish (US)
Title of host publication2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings
Pages5422-5425
Number of pages4
DOIs
StatePublished - Nov 8 2010
Externally publishedYes
Event2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Dallas, TX, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010
Country/TerritoryUnited States
CityDallas, TX
Period3/14/103/19/10

Keywords

  • Community detection
  • Non-Euclidean datasets
  • Random graph models
  • Spectral graph theory

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Spectral clustering for multiclass Erdös-Rényi graphs'. Together they form a unique fingerprint.

Cite this