Graph node clustering base on attraction/repulsion matrices: An experimental comparison.

Details

Supervisors

Courtain, Sylvain ; Saerens, Marco

Faculty

Louvain School of Management

Degree label

Master [120] en ingénieur de gestion

Abstract

This thesis is an experimental comparison of two clustering algorithms injected with different attraction/repulsion matrices. Clustering or community detection on a graph is assigning the objects constituting a network into different groups. A network is a collection of interconnected objects. To detect those communities and ultimately create our groups, clusters, we are using attraction/repulsion matrices. The attraction/repulsion matrices we tested are based upon different similarity and dissimilarity matrices. An example of an attraction/repulsion matrix is the correlation matrix. We plugged our various attraction/repulsion matrices into two different clustering algorithms, the well-known kernel k-means, and the attraction repulsion soft clustering. We answer the three following questions: • Which attraction/repulsion matrix achieves the most competitive results with the attraction repulsion soft clustering algorithm? • Which attraction/repulsion matrix achieves the most competitive results with the kernel k-means algorithm? • Which of the two algorithms, ARSC and KKM, is the most competitive when plugged with attraction/repulsion matrices? And are they competing against well-established algorithms? To answer those questions, we will run a series of clustering experiments with the attraction repulsion soft clustering, and the kernel k-means injected with divers attraction/repulsion matrices. The algorithms plugged with different attraction/repulsion matrices will run onto various datasets. For each of those datasets, we not only know the number of clusters they contain, but we also know each object true class, i.e. the cluster for which an object belongs. Knowing this, we can use performance metrics to assess the efficiency of each algorithm against one another.