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.
Type de document :
Communication dans un congrès
DISCML - 3rd NIPS Workshop on Discrete Optimization in Machine Learning - 2011, Dec 2011, Sierra Nevada, Spain. 2011
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger
Contributeur : Romaric Gaudel <>
Soumis le : vendredi 26 octobre 2012 - 10:23:54
Dernière modification le : jeudi 11 janvier 2018 - 06:23:38
Document(s) archivé(s) le : dimanche 27 janvier 2013 - 03:39:26


  • HAL Id : hal-00745666, version 1


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. 2011. 〈hal-00745666〉



Consultations de la notice


Téléchargements de fichiers