Spectral clustering of large-scale communities via random sketching and validation

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

2 Scopus citations

Abstract

In our era of data deluge, clustering algorithms that do not scale well with the dramatically increasing number of data have to be reconsidered. Spectral clustering, while powerful, is computationally and memory demanding, even for high performance computers. Capitalizing on the relationship between spectral clustering and kernel k-means, the present paper introduces a randomized algorithm for identifying communities in large-scale graphs based on a random sketching and validation approach, that enjoys reduced complexity compared to the clairvoyant spectral clustering. Numerical tests on synthetic and real data demonstrate the potential of the proposed approach.

Original languageEnglish (US)
Title of host publication2015 49th Annual Conference on Information Sciences and Systems, CISS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781479984282
DOIs
StatePublished - Apr 15 2015
Event2015 49th Annual Conference on Information Sciences and Systems, CISS 2015 - Baltimore, United States
Duration: Mar 18 2015Mar 20 2015

Publication series

Name2015 49th Annual Conference on Information Sciences and Systems, CISS 2015

Other

Other2015 49th Annual Conference on Information Sciences and Systems, CISS 2015
CountryUnited States
CityBaltimore
Period3/18/153/20/15

Keywords

  • Sketch and validate
  • Spectral clustering
  • community identification

Fingerprint Dive into the research topics of 'Spectral clustering of large-scale communities via random sketching and validation'. Together they form a unique fingerprint.

Cite this