Modularity in Multilayer Networks Using Redundancy-Based Resolution and Projection-Based Inter-Layer Coupling

Alessia Amelio, Giuseppe Mangioni, Andrea Tagarelli

TL;DR

This paper introduces a more principled, parameter-free approach to measuring modularity in multilayer networks. By replacing arbitrary global constants with data-driven factors—specifically a redundancy-based resolution and projection-based inter-layer coupling—the authors provide a more expressive metric that naturally accounts for community-specific structures and temporal layer orderings.

What Problem Does This Paper Address?

In network science, "modularity" is the standard yardstick for measuring the strength of a network’s division into communities. While well-defined for simple graphs, multilayer networks (where nodes are connected via multiple types of relations, like "friendship" on one layer and "co-authorship" on another) present a challenge.

The existing standard, multislice modularity ($Q_{ms}$), relies on two crucial parameters: a resolution factor ($\gamma$) and an inter-layer coupling factor ($\omega$). Traditionally, these are set as arbitrary constants. This is problematic because it ignores the unique topological characteristics of different layers and communities. Furthermore, $Q_{ms}$ doesn't inherently handle "ordered" layers, such as those representing a network evolving over time, where a node's state in one time-step should primarily be coupled with its state in the next.

Methods

The authors propose a new formulation of multilayer modularity ($Q$) that eliminates the need for manual parameter tuning:

  1. Redundancy-based Resolution ($\gamma$): Instead of a fixed value, $\gamma$ is calculated for each community-layer pair. It uses the concept of "redundancy"—the variety of link types between node pairs. If a community has high information content (many redundant links across layers), the resolution factor is lowered to reflect that layer's high contribution to the community's internal structure.
  2. Projection-based Inter-Layer Coupling ($IC$): Instead of a constant $\omega$, the coupling strength is determined by how much a community’s "projection" (the set of nodes it contains) overlaps between two layers.
  3. Asymmetry and Ordering: The model introduces asymmetric coupling, recognizing that a community's relevance might differ when projecting from a "source" layer to a "destination" layer. It also supports partial order relations, allowing researchers to specify if layers are adjacent (only coupling $L_i$ to $L_{i+1}$) or succeeding (coupling $L_i$ to all $L_j$ where $j > i$).
  4. Time-Awareness: For temporal networks, they include a smoothing factor that penalizes the coupling strength as the distance between layers (time-steps) increases.

Datasets

The authors validated their approach using a mix of synthetic and real-world data:

  • Synthetic: They generated networks using Erdős-Rényi (ER) and Lancichinetti-Fortunato-Radicchi (LFR) benchmarks, creating various multilayer configurations (e.g., ER-ER, LFR-ER) to test how the metric responds to known community structures.
  • Real-World: 10 diverse datasets were used, including:
  • AUCS: University employee relationships (work, lunch, Facebook, etc.).
  • EU-Air: European airport connections across different airlines.
  • Social/Digital Networks: FriendFeed-Twitter-YouTube (FF-TW-YT), Flickr, GitHub-StackOverflow-Twitter (GH-SO-TW), and Higgs-Twitter.
  • Transport/Other: London transport network, Obama’s 2013 Israel visit (Twitter interactions), and a classroom social network (7thGraders).

Key Insights and Ideas

  • Context Matters: Modularity shouldn't be a "one-size-fits-all" global constant. By making $\gamma$ and $IC$ community-specific, the metric becomes much more sensitive to the actual "meaningfulness" of a group of nodes.
  • The "Surprise" of Projections: The asymmetric coupling idea is particularly clever. It captures the intuition that a small, tightly-knit community in one layer projecting perfectly onto a larger layer is more "surprising" (and thus indicates stronger coupling) than a giant community projecting onto a subset of itself.
  • Temporal Logic: By integrating layer ordering directly into the modularity equation, the authors move away from the "all-to-all" coupling of previous models, which often led to overestimating community stability in time-evolving networks.

Key Results

  • Higher Expressiveness: The proposed $Q$ consistently showed higher values and better differentiation than the standard $Q_{ms}$ across synthetic benchmarks.
  • Redundancy Gains: Using the redundancy-based $\gamma$ led to modularity gains of up to 0.12 compared to fixing $\gamma=1$, proving that data-driven resolution captures more structural information.
  • Asymmetry Wins: Asymmetric coupling ($IC_a$) generally resulted in higher modularity scores than symmetric versions, supporting the idea that directional relevance is a key feature of multilayer systems.
  • Structural Correlation: The authors found a strong positive correlation between their modularity measure and key topological features like edge-set coverage, suggesting the metric is a reliable proxy for "true" community quality.

Limitations and Future Work

  • Computational Overhead: The authors note that calculating variable $\gamma$ and $IC$ factors increases computation time (roughly a 50% increase in their LFR tests). While still efficient for medium networks, very large-scale multiplex graphs might require optimization.
  • Crisp vs. Overlapping: The current model focuses on "crisp" community memberships (a node is either in or out). The authors suggest that extending this to overlapping communities (soft memberships) is a vital next step.
  • Optimization Algorithms: This paper defines the measure of modularity. The next logical phase is developing new community detection algorithms specifically designed to maximize this new version of $Q$.

Reference: Amelio, A., Mangioni, G., & Tagarelli, A. (2019). Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling. IEEE Transactions on Network Science and Engineering. DOI: 10.1109/TNSE.2019.2913325.

Summary updated

Abstract

The generalized version of modularity for multilayer networks, a.k.a. multislice modularity, is characterized by two model parameters, namely resolution factor and inter-layer coupling factor. The former corresponds to a notion of layer-specific relevance, whereas the inter-layer coupling factor represents the strength of node connections across the network layers. Despite the potential of this approach, the setting of both parameters can be arbitrarily selected, without considering specific characteristics from the topology of the multilayer network as well as from an available community structure. Also, the multislice modularity is not designed to explicitly model order relations over the layers, which is of prior importance for dynamic networks. This paper aims to overcome the main limitations of the multislice modularity by introducing a new formulation of modularity for multilayer networks. We revise the role and semantics of both the resolution and inter-layer coupling factors based on information available from the within-layer and inter-layer structures of the multilayer communities. Also, our proposed multilayer modularity is general enough to consider orderings of network layers and their constraints on layer coupling. Experiments were carried out on synthetic and real-world multilayer networks using state-of-the-art approaches for multilayer community detection. The obtained results have shown the meaningfulness of the proposed modularity, revealing the effects of different combinations of the resolution and inter-layer coupling functions. This paper also represents a starting point for the development of new optimization methods for community detection in multilayer networks.
BibTeX
@article{amelio2020modularity,
  author = {Alessia Amelio and Giuseppe Mangioni and Andrea Tagarelli},
  title = {{Modularity in Multilayer Networks Using Redundancy-Based Resolution and Projection-Based Inter-Layer Coupling}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2020},
  url = {https://openreview.net/forum?id=Z2VIvCDsDnW},
}

Loading related content...

Figure