UMass Machine Learning and Friends Lunch | Main / Graph Clustering With Network Structure Indices

Graph clustering has become ubiquitous in the study of relational data sets. We examine two simple algorithms: A graphical adaptation of the k-means algorithm and the Girvan-Newman method based on edge betweenness centrality. We show that they can be effective at discovering the latent groups or communities that are defined by the link structure of a graph. However, both approaches rely on prohibitively expensive computations given the size of modern relational data sets. Network structure indices (NSIs) are a proven technique for indexing network structure and efficiently finding short paths. By incorporating NSIs into these graph clustering algorithms, we can overcome these complexity limitations. We also present promising quantitative and qualitative evaluations of the modified algorithms on synthetic and real data sets.

Presented by Matthew Rattigan