Efficient Detecting Overlapping Communities by Seeding and Semi-Supervised Learning

Changxing Shang, Shengzhong Feng, Zhongying Zhao, Jianping FanarXiv 2014 · DOI · arXiv · OpenReview

TL;DR

This paper introduces ITEM, a novel algorithm for detecting overlapping communities in networks. ITEM transforms network edges into documents and nodes into terms, then uses a principled semi-supervised learning approach for community detection. It achieves state-of-the-art performance and linear time complexity, making it highly scalable.

What Problem Does This Paper Address?

Detecting communities in complex networks is a fundamental problem. Many existing methods rely on a "seeding then expanding" strategy. However, current seeding methods are often too complex for large networks or select low-quality seeds, while expansion methods can be heuristic and perform poorly on diverse network types. This leads to inaccurate community detection, especially in networks with overlapping communities where nodes can belong to multiple groups. The paper aims to address these limitations by proposing a more efficient and effective seeding and expansion process.

Methods

ITEM introduces a novel approach by treating network edges as documents and nodes as terms, creating a "corpus" from the network. This allows it to leverage text mining techniques.

  • Seeding: ITEM employs a two-step seeding process:
  • Local Ranking (RSS): A novel "Reputation, Strength, Specificity" (RSS) method ranks edges based on local network information, avoiding the computational burden and limitations of global ranking methods.
  • Global Information Gain (MGIG): Candidate seeds from RSS are then refined using the Maximizing Global Information Gain (MGIG) method, which selects distinctive and representative seeds from a global perspective.
  • Expanding: The core of ITEM's expansion is a principled semi-supervised learning approach using a Naïve Bayes classifier.
  • The selected seeds form a training set.
  • An Expectation-Maximization (EM) algorithm iteratively classifies edges into communities.
  • This approach leverages both labeled (seed) and unlabeled edge information, and incorporates Bayesian inference for more robust community assignment.
  • The method aims to infer community belonging by minimizing a global objective function, introducing a form of competition between communities.

Datasets

The paper evaluates ITEM on two types of datasets:

  • Synthetic Networks: Lancichinetti-Fortunato-Radicchi (LFR) benchmark networks are used to generate synthetic graphs with controlled parameters (network size, degree distribution, community size, mixing parameter, number of memberships, overlapping nodes).
  • Empirical Networks: The Facebook100 dataset, consisting of 100 friendship networks with meta-data like year and dorm, is used. For these networks, ground truth communities are unknown, and performance is evaluated using a classifier-based approach.

Key Insights and Ideas

  • Network-as-Corpus Analogy: The core insight is that network edges can be effectively treated as documents and nodes as terms, enabling the application of powerful text mining and information retrieval techniques to community detection.
  • Principled Semi-Supervised Learning: Moving beyond heuristic expansion functions, ITEM's use of semi-supervised learning with Bayesian inference offers a more robust and principled way to assign edges to communities, especially in the presence of unlabeled data.
  • Local-to-Global Seeding: The two-stage seeding process (RSS for local ranking, MGIG for global refinement) effectively balances computational efficiency with the selection of high-quality, representative seeds.
  • Scalability through Linearity: The algorithm's linear time complexity with respect to the number of edges is a significant advantage, enabling its application to very large networks where other methods struggle.

Key Results

  • Improved Clustering Performance: Experimental results on a wide range of synthetic and empirical networks show that ITEM significantly improves clustering performance compared to other state-of-the-art algorithms like GCE, SLPA, CPM, and PM.
  • Statistical Significance: Statistical analysis (Friedman test, Wilcoxon test) confirms that ITEM's performance is significantly better than most compared algorithms, often improving Normalized Mutual Information (NMI) by a substantial margin.
  • Scalability: ITEM exhibits linear time complexity with respect to the number of edges, making it highly scalable. For instance, it processed the Dblp network in 12 minutes on a multi-core workstation.
  • Versatility: ITEM demonstrates wide applicability across diverse network structures and parameter settings, consistently providing decent performance.

Limitations and Future Work

  • Unweighted and Undirected Networks: Currently, ITEM is designed to work only on unweighted and undirected networks.
  • Future Extensions: The authors propose extending ITEM to handle weighted and directed networks. They also suggest its potential use as a preparatory step for tasks like link prediction and key point detection, and its application to incremental or dynamic networks.
  • Parameter Sensitivity: While ITEM generally performs well, the paper notes that the effectiveness of some parameters (like th for MGIG) can be network-specific.

Summary updated

Abstract

Seeding then expanding is a commonly used scheme to discover overlapping communities in a network. Most seeding methods are either too complex to scale to large networks or too simple to select high-quality seeds, and the non-principled functions used by most expanding methods lead to poor performance when applied to diverse networks. This paper proposes a new method that transforms a network into a corpus where each edge is treated as a document, and all nodes of the network are treated as terms of the corpus. An effective seeding method is also proposed that selects seeds as a training set, then a principled expanding method based on semi-supervised learning is applied to classify edges. We compare our new algorithm with four other community detection algorithms on a wide range of synthetic and empirical networks. Experimental results show that the new algorithm can significantly improve clustering performance in most cases. Furthermore, the time complexity of the new algorithm is linear to the number of edges, and this low complexity makes the new algorithm scalable to large networks.
BibTeX
@misc{shang2014efficient,
  author = {Changxing Shang and Shengzhong Feng and Zhongying Zhao and Jianping Fan},
  title = {{Efficient Detecting Overlapping Communities by Seeding and Semi-Supervised Learning}},
  year = {2014},
  eprint = {1401.5888},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.5888},
}
Figure