An empirical study of graph nodes clustering with the p-resistance

Details

Supervisors

Saerens, Marco ; Courtain, Sylvain

Faculty

Louvain School of Management

Degree label

Master [120] : ingénieur de gestion, à finalité spécialisée

Abstract

The rise of technology and the wide availability of data have supported the private sector to leverage machine learning solutions in order to boost their profitability. Among these solutions, clustering algorithms are of particular interest to companies as it allows them to better understand their customers and operations through the aggregations of data into clusters. In the present thesis, clustering of networks will be studied through the lenses of a new distance called the p-resistance. This distance has the quality of providing local and global information, however, this desirable behaviour comes at the price of heavy computations which are mostly unfeasible even for small graphs. Therefore, two new implementations using improved techniques are explored, namely, an iterative reweighted least square (IRLS) and a column by column computation of the original definition of the p-resistance as defined by Herbster and Lever. In view of these challenges and mitigating solutions, the conducted experiments have shown promising results when benchmarked with existing clustering algorithms.