Gradient flow-based modularity maximization for community detection in multiplex networks

Kai Bergermann, Martin Stoll

Introduction

In network science, identifying "communities"—groups of nodes more densely connected to each other than to the rest of the network—is a fundamental task. While well-established for single-layer graphs, real-world systems are often multiplex, consisting of multiple layers that represent different types of relationships between the same set of entities. For instance, a social network might have layers for Facebook, Twitter, and LinkedIn connections.

Detecting communities in these networks typically involves maximizing multiplex modularity, a quality metric that measures the strength of division into groups. However, modularity maximization is an NP-complete combinatorial problem. Existing heuristic solvers, such as GenLouvain, often struggle with scalability as the number of nodes ($n$) and layers ($L$) increases.

Proposed Methods: MPBTV and DGFM3

This research introduces two novel methods that transform the discrete optimization problem into a continuous "gradient flow"—a mathematical path that moves toward the optimal value of a function. These methods are solved using a graph-based Merriman–Bence–Osher (MBO) scheme.

  1. MPBTV (Multiplex Balanced Total Variation): This approach leverages a theoretical equivalence: maximizing multiplex modularity is mathematically identical to minimizing a "balanced total variation" functional. By using a Ginzburg–Landau-type energy functional, the authors derive an Allen–Cahn-type differential equation to find the optimal community structure.
  2. DGFM3 (Direct Gradient Flow Multiplex Modularity Maximization): This method directly formulates a gradient flow to maximize the modularity functional without the intermediate TV step.

The efficiency of these methods stems from two key components:

  • Diffusion Step: A linear step solved using truncated eigendecompositions. Instead of computing the full matrix exponential, the algorithm uses only the top $k$ eigenvalues and eigenvectors, capturing the essential structural information.
  • Thresholding Step: A non-linear step that "snaps" nodes into discrete community assignments.

Performance and Scalability

The most significant advantage of MPBTV and DGFM3 is their computational efficiency. Traditional methods often exhibit quadratic time scaling or hit memory limits with large networks. In contrast, the proposed gradient flow methods scale almost linearly with the number of node-layer pairs ($nL$).

Runtime comparison showing that MPBTV and DGFM3 scale linearly with network size, significantly outperforming traditional matrix-based methods.

In numerical experiments, these methods achieved runtimes up to five orders of magnitude faster than the standard GenLouvain solver on large-scale networks. For a multiplex network derived from an image with approximately 300,000 node-layer pairs, the proposed methods were roughly 100,000 times faster.

Applications: Image Segmentation

The researchers demonstrated the versatility of their methods by applying them to image segmentation. In this context, an image is treated as a multiplex network where layers represent different data sources, such as RGB color channels and spatial (xy) coordinates.

Qualitative results on a test image: (a) original image, (b) ground truth, (c) and (d) community detection results for the RGB and xy layers using MPBTV.

On a custom-labeled test image, MPBTV achieved a classification accuracy of 0.976 and a Normalized Mutual Information (NMI) score of 0.909, outperforming several established competitors while maintaining superior speed.

Conclusion and Future Work

By bridging the gap between image processing (Total Variation) and network science (Modularity), this work provides a mathematically elegant framework for large-scale community detection. While the methods occasionally struggle with very small communities—a known trade-off of spectral approximations—the massive gains in speed and scalability make them highly practical for modern big-data applications. Future research aims to extend these techniques to semi-supervised learning and higher-dimensional data like hyperspectral imaging.

Summary updated

Abstract

We propose two methods for the unsupervised detection of communities in undirected multiplex networks. These networks consist of multiple layers that record different relationships between the same entities or incorporate data from different sources. Both methods are formulated as gradient flows of suitable energy functionals: the first (MPBTV) builds on the minimization of a balanced total variation functional, which we show to be equivalent to multiplex modularity maximization, while the second (DGFM3) directly maximizes multiplex modularity. The resulting non-linear matrix-valued ordinary differential equations (ODEs) are solved efficiently by a graph Merriman--Bence--Osher (MBO) scheme. Key to the efficiency is the approximate integration of the discrete linear differential operators by truncated eigendecompositions in the matrix exponential function. Numerical experiments on several real-world multiplex networks show that our methods are competitive with the state of the art with respect to various metrics. Their major benefit is a significant reduction of computational complexity leading to runtimes that are orders of magnitude faster for large multiplex networks.
BibTeX
@inproceedings{bergermann2025gradient,
  author = {Kai Bergermann and Martin Stoll},
  title = {{Gradient flow-based modularity maximization for community detection in multiplex networks}},
  booktitle = {Philosophical},
  year = {2025},
  doi = {10.1098/rsta.2024.0244},
}
Figure