The Hyperspherical Geometry of Community Detection: Modularity as a Distance
Martijn Gösgens, Remco van der Hofstad, Nelly Litvak; 24(112):1−36, 2023.
Abstract
This article presents a metric space of clusterings, where clusterings are represented by a binary vector indexed by the vertex pairs. The authors extend this geometry to a hypersphere and demonstrate that maximizing modularity is equivalent to minimizing the angular distance to a modularity vector within the set of clustering vectors. Thus, modularity-based community detection methods can be seen as a subset of a broader class of projection methods. These projection methods involve a two-step procedure: first, mapping the network to a point on the hypersphere, and second, projecting this point onto the set of clustering vectors. The authors show that this class of projection methods encompasses various interesting community detection methods that cannot be described using null models and resolution parameters, as is customary for modularity-based methods. The paper introduces a new characterization of these methods in terms of meridians and latitudes of the hypersphere. Additionally, by relating the modularity resolution parameter to the latitude of the corresponding modularity vector, the authors provide a new interpretation of the resolution limit observed in modularity maximization.
[abs]