Abstract
Networks have been a general tool for representing, analyzing, and modeling relational data arising in several domains. One of the most important aspects of network analysis is community detection or network clustering. Until recently, the major focus has been on discovering community structure in single (i.e., monoplex) networks. However, with the advent of relational data with multiple modalities, multiplex networks—networks composed of multiple layers representing different aspects of relations—have emerged. Consequently, community detection in multiplex networks, i.e., detecting clusters of nodes shared by all layers, has become a new challenge. In this paper, we propose Network Fusion for Composite Community Extraction (NF-CCE), a new class of algorithms based on four different non-negative matrix factorization models capable of extracting composite communities in multiplex networks. Each algorithm works in two steps: first, it finds a non-negative, low-dimensional feature representation of each network layer; then, it fuses the feature representations of layers into a common non-negative, low-dimensional feature representation via collective factorization. The composite clusters are extracted from the common feature representation. We demonstrate the superior performance of our algorithms over state-of-the-art methods on various types of multiplex networks, including biological, social, economic, citation, phone communication, and brain multiplex networks.
Introduction: The Challenge of Multiplex Networks
Most traditional network analysis focuses on "monoplex" networks, where only one type of interaction exists between nodes (e.g., a simple list of friends). However, real-world data is increasingly multiplex: a social network might have distinct layers for "friendship," "professional advice," and "co-working."
The fundamental challenge is "composite community detection": identifying groups of nodes that belong together across all these modalities. Previous approaches often relied on simple averaging of adjacency matrices, which unfortunately averages noise alongside signal, leading to degraded results. Other state-of-the-art methods struggle to effectively balance complementary information—what one layer adds to another—with the inherent noise present in specific layers.
Methodology: The NF-CCE Framework
To address these limitations, we introduce the NF-CCE (Network Fusion for Composite Community Extraction) framework. NF-CCE operates through a robust "denoise-then-fuse" philosophy in two distinct steps:
- Denoising (Step 1): Each network layer is factorized individually using Non-negative Matrix Factorization (NMF). This produces a low-dimensional feature representation for each layer, effectively filtering out local noise and irrelevant connections.
- Fusion (Step 2): These individual representations are fused into a single consensus representation ($H$) via collective factorization.
To achieve this consensus, we treat the low-dimensional subspaces of each layer as points on a Grassmann manifold. We minimize the projection distance between these individual layer subspaces and the shared consensus subspace. This geometric approach ensures that the final fusion is stable and captures the most significant shared structures.
Algorithmic Variants
We developed four specific algorithmic variants based on different NMF techniques to handle various network characteristics:
- CSNMF: Collective Symmetric NMF.
- CPNMF: Collective Projective NMF.
- CSNMTF: Collective Symmetric Non-negative Matrix Tri-Factorization.
- CSsemi-NMTF: A "semi" version allowing for some negative entries in factor matrices to increase flexibility.
These algorithms utilize natural gradients during optimization to ensure the resulting matrices remain orthonormal, which significantly improves the interpretability of the resulting clusters.
Experimental Evaluation
Our methods were evaluated against a massive variety of datasets to ensure generalizability:
- Synthetic Networks: Tested for robustness against noise (SYNTH-N) and ability to capture complementary information (SYNTH-C).
- Bibliographic Data: CiteSeer and CoRA, utilizing citation and word-similarity layers.
- Social/Communication Data: MIT Mobile Phone Data and Law Partnership networks.
- Biological Networks: Protein-protein interaction and co-expression networks for Humans, Yeast, and Mice.
- Economic and Brain Data: World Trade Networks and Worm Brain synapse networks.
Key Insights and Results
- Superior Accuracy: NF-CCE variants consistently outperformed state-of-the-art methods like PMM, SC-ML, and SNF across nearly all real-world datasets in terms of Purity, Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI).
- Robustness to Noise: Synthetic tests revealed that while other methods' performance plummeted as noise increased, NF-CCE (particularly CSNMF and CSNMTF) maintained high accuracy.
- Biological Consistency: In the Human Biological Network (HBN), the communities found by NF-CCE showed significantly higher functional consistency (based on Gene Ontology) than those found in any single layer. This demonstrates that integrating layers reveals biological truths invisible in isolation.
- Geometry over Averaging: Our results confirm that simple matrix averaging is often detrimental. By using Grassmann manifolds, we move toward a geometric understanding of how different network layers relate.
Conclusion and Future Work
NF-CCE provides a powerful framework for extracting robust, informative communities from complex multiplex data. While highly effective, current limitations include the requirement for a pre-specified number of clusters ($k$) and the assumption of perfect node alignment across layers. Future research will focus on automatically determining $k$ and extending the model to "multilayer" networks where nodes may only exist in a subset of layers. Additionally, further optimization of natural gradient calculations will be explored to scale the framework for truly massive networks with billions of edges.
Summary updated