Comparing ways to find communities in layered networks
Explicit objective functions in modularity-based community detection on multiplex networks
Social and Information Networks
Summary
Detecting groups within networks that have multiple layers, like social or data layers, can be done by combining these layers in different ways. The authors compare three common strategies: combining layers first, combining during group-finding, or combining results afterward. They provide clear math showing how these methods relate and differ, and run tests on fake and real data. Their work helps clarify how these approaches work and when one might be better than another.
What this means in practice
- •For network analysts: Choose appropriate fusion strategies for detecting communities in complex layered networks in social or biological data.
- •For data engineers: Improve multiplex network analysis pipelines by understanding and implementing explicit objective functions for community detection.
Authors
Elizaveta Evmenova, Petr Chunaev
Abstract
Modularity-based community detection in multiplex networks is commonly approached through one of three strategies: early fusion (EF), which first aggregates the layers into a single network and then applies community detection; simultaneous fusion (SF), which combines information from the layers during modularity optimization; and late fusion (LF), which combines the community assignments obtained by detecting communities separately in each layer. Although recent taxonomies and surveys distinguish these strategies conceptually, their objective functions have rarely been compared analytically. We provide such a comparison for shared-node multiplex networks with normalized non-negative edge and layer weights, a common resolution parameter, and no interlayer edges. Node-attributed networks are represented by topology and attribute-similarity layers. We use a common notation for the three formulations and derive explicit relationships between their objective functions. In particular, we show that the EF objective equals the SF objective plus a non-negative heterogeneity term. We prove that the SF objective admits an optimal layer-weight vector at a simplex vertex, although nonvertex optima may also occur under ties, whereas the EF objective is concave with respect to the layer parameter for each fixed partition, and its joint optimum may occur in the interior of the simplex. For LF methods, the resulting objective and conclusions depend heavily on how the transient graph is constructed. In this study, we focus only on one of such LF methods. We complement the analytical results with brute-force experiments on synthetic multiplexes and heuristic experiments on real-world networks, including node-attributed networks represented as multiplexes. The experiments illustrate the analytical results and the influence of heuristic optimizers on the observed comparisons.