Incremental spectral clustering with application to monitoring of evolving blog communities

Huazhong Ning, Wei Xu, Yun Chi, Yihong Gong, Thomas Huang

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


In recent years, spectral clustering method has gained attentions because of its superior performance compared to other traditional clustering algorithms such as K-means algorithm. The existing spectral clusteririg algorithms are all off-line algorithms, i.e., they can not incrementally update the clustering result given a small change of the data set. However, the capability of incrementally updating is essential to some applications such as real time monitoring of the evolving communities of websphere or blogsphere. Unlike traditional stream data, these applications require incremental algorithms to handle not only insertion/deletion of data points but also similarity changes between existing items. This paper extends the standard spectral clustering to such evolving data by introducing the incidence vector/matrix to represent two kinds of dynamics in the same framework and by incrementally updating the eigenvalue system. Our incremental algorithm, initialized by a standard spectral clustering, continuously and efficiently updates the eigenvalue system and generates instant cluster labels, as the data set is evolving. The algorithm is applied to a blog data set. Compared with recomputation of the solution by standard spectral clustering, it achieves similar accuracy but with much lower computational cost. Close inspection into the blog content shows that the incremental approach can discover not only the stable blog communities but also the evolution of the individual multi-topic blogs.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th SIAM International Conference on Data Mining
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages12
ISBN (Print)9780898716306
StatePublished - 2007
Externally publishedYes
Event7th SIAM International Conference on Data Mining - Minneapolis, MN, United States
Duration: Apr 26 2007Apr 28 2007

Publication series

NameProceedings of the 7th SIAM International Conference on Data Mining


Other7th SIAM International Conference on Data Mining
Country/TerritoryUnited States
CityMinneapolis, MN


  • Incidence vector/matrix
  • Incremental clustering
  • Spectral clustering
  • Web-blogs

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Incremental spectral clustering with application to monitoring of evolving blog communities'. Together they form a unique fingerprint.

Cite this