Median Graph Shift: A New Clustering Algorithm for Graph Domain

Salim Jouili (1) , Salvatore Tabbone (1) , Vinciane Lacroix (2)

1 QGAR - Querying Graphics through Analysis and Recognition
2 SIC - Signal and Image Centre

n the context of unsupervised clustering, a new algorithm for the domain of graphs is introduced. In this paper, the key idea is to adapt the mean-shift clustering and its variants proposed for the domain of feature vectors to graph clustering. These algorithms have been applied successfully in image analysis and computer vision domains. The proposed algorithm works in an iterative manner by shifting each graph towards the median graph in a neighborhood. Both the set median graph and the generalized median graph are tested for the shifting procedure. In the experiment part, a set of cluster validation indices are used to evaluate our clustering algorithm and a comparison with the well-known Kmeans algorithm is provided.

Mots clés: Graph clustering; Graph median-shift; Graph matching

Domaines: Traitement du texte et du document

Salim Jouili, Salvatore Tabbone, Vinciane Lacroix. Median Graph Shift: A New Clustering Algorithm for Graph Domain. 20th International Conference on Pattern Recognition - ICPR 2010, Aug 2010, Istanbul, Turkey. pp.1051-4651, ⟨10.1109/ICPR.2010.238⟩. ⟨inria-00526991⟩