The Projection Method: a Geometric Framework for Community Detection

Link to Join MS Teams Talk

This talk will be broadcast at 13:30 BST 31st July on MS Teams only.

Meeting ID: 393 527 089 878
Passcode: dsm7py

Abstract

We present the class of projection methods for community detection that generalizes many popular community detection methods. In this framework, we represent each clustering (partition) by a vector on a high-dimensional hypersphere. To detect communities, we map the network as a whole to a point on this same hypersphere and find the clustering vector that is nearest to it. We show that several existing community detection methods fit this framework. In addition, we show that these different methods suffer from the same granularity problem: they have parameters that control the granularity of the resulting clustering, but choosing these to obtain clusterings of the desired granularity is nontrivial. We provide a general heuristic to address this granularity problem, which can be applied to any projection method. Finally, we show how, given a generator of graphs with community structure, we can optimize a projection method for this generator in order to obtain a community detection method that performs well on this generator.

About Martijn

Martijn very recently received his PhD at TU Eindhoven under the supervision of Remco van der Hofstad and Nelly Litvak. His research focuses on detecting communities in complex networks. Communities are groups of nodes that are better connected internally than externally. Such communities could, for example, correspond to groups of friends on social media or fields of study in citation networks. Another branch of his research concerns validating validation measure. For many machine learning tasks, there exist many measures to quantify the similarity between two outcomes. These measures are used to validate the performance of a machine learning algorithm by measuring the similarity between the outcome of the algorithm and the desired (‘true’) outcome. An important task is then to validate these measures.