Source-linked AI summary
Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
Manlio De Domenico, Andrea Lancichinetti, Alex Arenas, Martin Rosvall
TL;DR
Single-layer aggregation can lose information in systems with multiple interaction layers. The paper introduces a flow-compression generalization of the map equation for multilayer networks, which identifies communities that conventional analyses miss and reveals smaller, more overlapping modules in collaboration networks.
Problem
Aggregating multiple interaction layers into one network can lose structural information, while conventional community methods generally assume a single link type.
Method
The authors introduce a multilayer flow-compression method that generalizes the map equation by modeling flows with memory of the present layer.
Results
Multiplex Infomap accurately identifies benchmark communities across up to 5-6 layers per mode network, whereas standard Infomap succeeds for only one layer per mode network.
Takeaways & Limitations
Compared with conventional network analysis, the multilayer method reveals smaller modules with more overlap that better capture the actual organization.
Takeaways & Limitations
Without empirical inter-layer link weights, the relax rate must be chosen appropriately for the system under study.
Abstract
from arXiv · showhide
Unveiling the community structure of networks is a powerful methodology to comprehend interconnected systems across the social and natural sciences. To identify different types of functional modules in interaction data aggregated in a single network layer, researchers have developed many powerful methods. For example, flow-based methods have proven useful for identifying modular dynamics in weighted and directed networks that capture constraints on flow in the systems they represent. However, many networked systems consist of agents or components that exhibit multiple layers of interactions. Inevitably, representing this intricate network of networks as a single aggregated network leads to information loss and may obscure the actual organization. Here we propose a method based on compression of network flows that can identify modular flows in non-aggregated multilayer networks. Our numerical experiments on synthetic networks show that the method can accurately identify modules that cannot be identified in aggregated networks or by analyzing the layers separately. We capitalize on our findings and reveal the community structure of two multilayer collaboration networks: scientists affiliated to the Pierre Auger Observatory and scientists publishing works on networks on the arXiv. Compared to conventional aggregated methods, the multilayer method reveals smaller modules with more overlap that better capture the actual organization.
Introduction
Multilayer networks preserve distinct interaction modes and the flow constraints they impose, while aggregation can distort topology and dynamics. The paper introduces a flow-compression framework that generalizes the map equation to identify overlapping modules across layers.
- Introduction: Aggregating multiple relationship types into one weighted, directed network can distort network topology and dynamics.The distortion matters because social interactions may depend on location, time, or communication medium.
- Modules in multilayer networks: a flow-approach: The method generalizes the map equation by modeling multilayer flows while retaining a modular code structure with unique names for important structures.Its flow model retains memory of the present layer rather than the previous step.
- Flow dynamics on multilayer networks: Multilayer networks represent agents interacting in different roles, times, or means, with each layer imposing distinct flow constraints.Physical nodes represent agents, while node-layer tuples represent state nodes in specific layers.
- Flow dynamics on multilayer networks: Relax rate r interpolates between movement constrained to the current layer and movement along any link of the physical node.At r = 0, layer constraints are retained; at r = 1, movement follows the fully aggregated network’s freedom.
- The multiplex map equation: The multiplex generalization assigns a common code word to state nodes representing the same physical object when they belong to the same module, allowing natural overlap.This extends the map equation beyond the single-module membership constraint of hard partitions.
Results and Discussion
The study validates Multiplex Infomap on synthetic multilayer benchmarks and applies it to two collaboration networks. Across these analyses, preserving multilayer structure identifies communities that conventional aggregation, separate-layer analysis, or generalized modularity fail to recover.
- Performance tests: The benchmark construction samples L dependent layers from each of T independently generated LFR mode networks, without providing the algorithm the mode count or sampling order.Each benchmark contains T × L layers, with T sets of L dependent layers.
- Performance tests: In the illustrative two-mode benchmark, generalized modularity recovers layer communities but misses the original mode communities, while the multiplex map equation recovers both.The multiplex result uses relax rate r = 0.15.
- Performance tests: Multiplex Infomap accurately identifies planted communities across up to 5–6 layers per mode network, whereas separate-layer and expanded-network Infomap succeed only for one layer.Performance is evaluated using NMI between planted and obtained state-node partitions at relax rate r = 0.15.
- Performance tests: Generalized modularity fails to identify planted cross-layer communities because its null model covers intra-layer links and treats inter-layer coupling only through a parameter.The resulting modularity score favors merging different communities across layers.
- Collaboration networks: In the Pierre Auger and arXiv collaboration networks, multilayer analysis reveals smaller, more overlapping modules, with multilayer scientists concentrated in the network core.The Auger visualization includes more than 90% of scientists in its largest connected component.
- Collaboration networks: Restricting cross-layer movement to roughly one step in six increases within-module persistence by 25% in Auger and 13% in arXiv networks.These persistence gains indicate longer random-walker residence within modules under r = 0.15 than under r = 1.0.
Methods
The method minimizes a multiplex map-equation description length for random-walker dynamics across multilayer networks. It models inter-layer movement through empirical weights or a relaxation parameter and accounts for physical nodes represented across layers.
- Multiplex map equation: The multiplex map equation encodes random-walker trajectories between physical nodes while the walker navigates state nodes across layers.Its information-theoretic machinery is the map equation, with the flow model incorporating the current layer.
- Flow dynamics: Inter-layer movement uses empirical transition probabilities when weights exist, or a relaxation rate r that controls how freely walkers follow links across layers.For directed networks, low-rate teleportation ensures a unique ergodic solution; τ = 0.15 is used throughout, with robustness to variation.
- Partitioning: The optimal partition assigns state nodes to modules by minimizing the map-equation description length of movements within and between modules.Module codebooks describe node visits and exits, while an index codebook describes module entries.
- Codebooks: Module codebooks use codewords for physical nodes and exits, with lengths derived from visit and exit rates; the index codebook uses module-entry rates.The map equation weights average codeword lengths by their rates of use.
- Multiplex representation: State nodes belonging to the same module share a common codeword derived from their total visit rate, while state nodes of one physical node may occupy multiple modules.This is the key multiplex-specific difference from the standard map equation.
OUTLINE
The supporting information adds benchmark-graph analyses, multilayer NMI details, and further information about the real datasets.
- Supporting information: The supporting information examines synthetic benchmark graphs, including how relax rate r affects networks with overlapping communities across layers.It also provides additional information about multilayer Normalized Mutual Information and the real datasets.
Community structure of synthetic multilayer networks
Synthetic benchmarks examine how multilayer community detection and NMI vary with layer overlap and relax rate, showing when multilayer, averaged, and aggregated analyses recover planted structure.
- Benchmark design: Synthetic benchmarks use multilayer networks with planted communities and evaluate partitions using Normalized Mutual Information (NMI) for node-layer assignments.The supplementary analysis also describes LFR benchmark networks with controlled degree, community-size, and mixing parameters.
- Benchmark results: For small overlap fractions and relax rates, 16 modules are detected because flow remains preferentially within cliques in separate layers.Below roughly 50–60% relax rate, the layers remain weakly coupled and the multiplex NMI captures this multilayer behavior.
- Benchmark results: Beyond the weak-coupling region, 8 modules are detected, while for overlap above 50% the multiplex NMI is 1 nearly regardless of relax rate.Average NMI can indicate that per-layer partitions are correct even when the multilayer partition differs.
- Benchmark results: Aggregated analysis always reveals 8 modules regardless of underlying overlap, accurately proxying the multilayer structure only when layer partitions highly overlap.The supplementary text identifies aggregation as a source of information loss and potentially misleading partitioning.
- Relax-rate effects: The optimal relax rate depends on the number of mode networks: high rates suit one mode, whereas too-high or too-low rates distort multilayer constraints when modes exceed one.Without empirical inter-layer weights, the relax rate must be selected for the system under study.
- Comparison with modularity: Generalized modularity identifies layer-wise communities in this benchmark but fails to identify which layers correspond to which mode networks.For inter-layer coupling DX > 1, performance drops further because inter-layer weights dominate intra-layer weights.
Comparing the aggregated and multilayer networks of Auger and ArXiv
Supplementary analyses compare multilayer and aggregated community structures in two collaboration datasets: the Pierre Auger Observatory and the ArXiv network.
- Empirical comparisons: At relax rate r = 1, the random walker moves freely between layers, but multilayer and aggregated partitions need not coincide because multilayer solutions allow overlap.The aggregated optimization used for comparison does not identify overlapping communities by construction.
- Empirical comparisons: In both datasets, increasing the relax rate produces bigger modules and fewer community assignments per physical node, reducing overlap.Module size is defined using the effective number of modules, which is based on the Shannon entropy of the partition.
- Pierre Auger Collaboration: The Pierre Auger dataset contains 514 authors, 9,209 collaborations, and 16 task-defined layers built from technical reports submitted between 2010 and 2012.The dataset uses manually disambiguated authors and assigns reports to one or more tasks.
- Detailed community structure: Detailed maps are provided for multilayer and aggregated Pierre Auger community structures to complement the main-text comparisons.The supplementary figures show the multilayer partition at r = 0.15 and an aggregated-network view at r = 1.0.
- ArXiv collaboration network: The ArXiv dataset contains 12,019 articles and 14,488 authors across 13 categories, using papers containing “network” in the title or abstract through May 2014.The categories define layers of the multilayer co-authorship network.