A framework for joint community detection across multiple related networks

Prakash Mandayam Comar, Pang-Ning Tan, Anil K. JainNeurocomputing 2012 · DOI

TL;DR

This paper introduces a novel framework for simultaneously detecting communities across multiple interconnected networks. By jointly analyzing these networks, the approach improves community detection accuracy compared to analyzing each network in isolation, particularly when networks are noisy or incomplete. This has significant implications for understanding complex social structures and information flow in interconnected digital environments.

What Problem Does This Paper Address?

Community detection, the task of identifying cohesive groups of nodes in a network, is a fundamental problem in data mining and machine learning with applications ranging from social network analysis to biological systems. Traditionally, research has focused on detecting communities within a single network. However, in today's digital landscape, users and entities often have a presence across multiple online platforms (e.g., social media, academic networks, Wikipedia). This creates a scenario where multiple related networks exist, and information from one network can potentially enhance the understanding of communities in another. The challenge is to effectively leverage the interconnectedness of these networks to achieve more robust and accurate community detection than is possible by analyzing each network independently. This is especially important when individual networks might be noisy, incomplete, or lack rich attributes for effective clustering.

Methods

The core of this paper is a novel framework for joint community detection across multiple related networks. The approach is based on non-negative matrix factorization (NMF). Instead of factorizing individual adjacency matrices, the framework jointly factorizes the adjacency matrices of multiple networks, including a matrix representing the links between networks.

Key aspects of the method include:

  • Joint Objective Function: A unified objective function is proposed that minimizes the reconstruction error across all networks simultaneously, incorporating terms for each individual network's adjacency matrix and a term for the inter-network adjacency matrix. This function is designed to learn cluster memberships for nodes in each network and the correspondences between these clusters.
  • Iterative Update Formulas: The framework derives iterative update rules for the cluster membership matrices (X and Y for two networks) and the correspondence matrix (V) using a gradient descent approach. These updates are designed to monotonically decrease the objective function, ensuring convergence.
  • Incorporating Prior Information: The framework allows for the incorporation of prior knowledge about the relationships between communities in different networks. This is achieved by adjusting the correspondence matrix (V) using a weighted combination of the learned correspondence and a user-defined prior matrix (P). This is particularly useful when external information can guide the clustering process.
  • Heuristics for Initialization and Optimization: The paper discusses the computational complexity and proposes heuristics for initializing the cluster membership matrices. These heuristics, inspired by label propagation, suggest prioritizing high-degree nodes and assigning them orthogonal cluster memberships to speed up convergence and improve accuracy.

Datasets

The paper evaluates its framework on both synthetic and real-world datasets:

  • Synthetic Data Set: A synthetic dataset was generated to systematically study the effect of noise within individual networks and between networks on clustering performance.
  • Wikipedia Data Set: This dataset consists of two interconnected networks: one representing articles and their categories/subcategories, and another representing Wikipedia editors and their contributions. The goal was to identify subcategories within articles and relate them to editor communities. This dataset is challenging due to editors contributing to multiple topics and noisy article links.
  • Digg Data Set: This dataset involves two networks: Digg users and Wikipedia editors. Links were established based on the similarity of bookmarked URLs (Digg) and edited articles (Wikipedia). The objective was to identify user communities based on shared interests.

Key Insights and Ideas

  • Synergy of Multiple Networks: The most significant insight is that jointly analyzing multiple related networks leads to demonstrably better community detection results than analyzing them in isolation. This highlights the power of leveraging cross-network information.
  • Noise Resilience: The framework shows improved performance even when one of the networks contains a significant amount of noise, suggesting that information from a cleaner network can help denoise and improve the clustering of a noisier one.
  • Prior Knowledge is Powerful: Incorporating prior knowledge about community correspondences can further boost performance, especially when the learned correspondences might be ambiguous or incomplete.
  • Initialization Matters: The paper strongly emphasizes the impact of initialization. Using heuristics that leverage high-degree nodes and their potential for orthogonal cluster memberships significantly speeds up convergence and improves accuracy, moving away from potentially suboptimal random initializations.
  • Label Propagation Analogy: Interpreting the iterative update formulas as a form of cluster membership propagation provides valuable intuition for understanding the algorithm's behavior and developing optimization strategies.

Key Results

  • Improved NMI: The proposed "Joint" and "Joint + Prior" algorithms consistently outperformed baseline methods like normalized cut (Ncut) and independent clustering (Ind) and co-clustering (CoC) on both synthetic and real-world datasets, as measured by Normalized Mutual Information (NMI). For example, on the Wikipedia article network, Joint+Prior achieved an NMI of 0.45, compared to 0.38 for CoC and 0.30 for Independent clustering.
  • Effect of Noise: On synthetic data, increasing noise in one network or between networks generally decreased NMI, but the Joint algorithm showed better resilience than some baselines.
  • Wikipedia Performance: The Joint algorithm successfully identified finer subcategories within the Wikipedia article network, outperforming Ncut which tended to group articles into broader categories. For the editor network, Joint+Prior also showed superior performance.
  • Initialization Speedup: Experiments on Wikipedia demonstrated that manual and automatic initialization heuristics significantly reduced the number of iterations required for convergence and improved the final NMI scores compared to random initialization.

Limitations and Future Work

  • Scalability: The authors acknowledge that the current framework has a computational complexity of O(n²T) (where n is the number of nodes and T is the number of iterations), which might be prohibitive for networks with millions of nodes. They suggest that scalability for very large networks will be pursued in future work.
  • Number of Clusters: The framework assumes the number of clusters (k) is known beforehand. Determining the optimal number of clusters is a common challenge in clustering and could be an area for future research.
  • Generalization to More Networks: The current formulation is presented for two networks, though it is noted that the approach can be extended to more than two networks. Further exploration of this generalization would be beneficial.
  • Exploration of Heuristics: While heuristics for initialization are proposed, further investigation into different seeding strategies and their impact on convergence and accuracy could be valuable.

Summary updated

BibTeX
@article{comar2012framework,
  author = {Prakash Mandayam Comar and Pang-Ning Tan and Anil K. Jain},
  title = {{A framework for joint community detection across multiple related networks}},
  journal = {Neurocomputing},
  year = {2012},
  doi = {10.1016/j.neucom.2011.04.035},
}
Figure