Incremental Spectral Clustering with the Normalised Laplacian

Charanpal Dhanjal 1 Romaric Gaudel 2, 3 Stéphan Clémençon 1
3 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : Partitioning a graph into groups of vertices such that those within each group are more densely connected than vertices assigned to different groups, known as graph clustering, is often used to gain insight into the organization of large scale networks and for visualization purposes. Whereas a large number of dedicated techniques have been recently proposed for static graphs, the design of on-line graph clustering methods tailored for evolving networks is a challenging problem, and much less documented in the literature. Motivated by the broad variety of applications concerned, ranging from the study of biological networks to graphs of scientific references through to the exploration of communications networks such as the World Wide Web, it is the main purpose of this paper to introduce a novel, computationally efficient, approach to graph clustering in the evolutionary context. Namely, the method promoted in this article is an incremental eigenvalue solution for the spectral clustering method described by Ng. et al. (2001). Be- yond a precise description of its practical implementation and an evaluation of its complexity, its performance is illustrated through numerical experiments, based on datasets modelling the evolution of a HIV epidemic and the purchase history graph of an e-commerce website.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-00745666
Contributor : Romaric Gaudel <>
Submitted on : Friday, October 26, 2012 - 10:23:54 AM
Last modification on : Tuesday, April 23, 2019 - 5:02:52 PM
Long-term archiving on : Sunday, January 27, 2013 - 3:39:26 AM

Identifiers

  • HAL Id : hal-00745666, version 1

Citation

Charanpal Dhanjal, Romaric Gaudel, Stéphan Clémençon. Incremental Spectral Clustering with the Normalised Laplacian. DISCML - 3rd NIPS Workshop on Discrete Optimization in Machine Learning - 2011, Dec 2011, Sierra Nevada, Spain. ⟨hal-00745666⟩

Share

Metrics

Record views

721

Files downloads

549