A Scheme to Design Community Detection Algorithms in Various Networks

Haoye Lu, Amiya Nayak

TL;DR

This paper proposes a general, unified scheme for designing community detection algorithms applicable to diverse network types, moving beyond the current trend of developing specialized algorithms. By abstracting transmission and similarity networks into a common graph model, they offer a systematic approach to defining and detecting communities, demonstrated to yield reasonable results.

What Problem Does This Paper Address?

Community detection, the task of identifying groups of nodes with dense internal connections and sparse external connections, is crucial for understanding and managing complex systems like social networks, transportation systems, and biological networks. However, existing community detection algorithms are often developed independently for specific network types or purposes. This leads to a proliferation of algorithms, making it difficult to choose the most appropriate one and suggesting that a truly general-purpose algorithm might not exist. The authors argue that while a single algorithm for all scenarios may be elusive, a general design procedure for deriving effective algorithms is feasible. They aim to provide such a systematic scheme.

Methods

The core of the paper is a proposed general scheme for designing community detection algorithms. This scheme involves:

  • Network Abstraction: The authors first identify two primary types of real-world networks: transmission networks (e.g., material or information flow) and similarity networks (based on attribute similarities). They then propose methods to abstract these into a unified graph model.
  • Unified Graph Model: Both transmission and similarity networks are reduced to a weighted graph representation. For transmission networks, a "relation strength measurement" (RSMFTN) is defined, generalizing direct measurements. For similarity networks, a "relation strength measurement for similarity network" (RSMFSN) is developed, often based on weighted similarity functions. Crucially, they show that both types can be reduced to a common graph model.
  • Community Definition: Based on this unified graph model, they formally define a community as a subset of nodes where the relation strength between any pair of nodes (in both directions) is above a certain threshold, termed the "community parameter" (CP).
  • Detection Algorithm: The scheme leads to an algorithm that, given a chosen Relation Strength Measurement (RSM) and Community Parameter (CP), identifies maximal communities. This involves transforming the weighted graph into an "effective edge graph" and then finding maximal cliques within this graph, which is equivalent to finding maximal communities. They leverage the Bron-Kerbosch algorithm for finding maximal cliques.

Datasets

The paper uses the following datasets:

  • Zachary's Karate Club Network: Used for demonstrating the proposed scheme and algorithm.
  • LFR Benchmark Networks: Used for comparing the performance of their algorithm against other popular community detection methods.

Key Insights and Ideas

  • Unification of Network Types: The paper successfully demonstrates that diverse network types (transmission and similarity) can be abstracted into a common graph model, simplifying the design of general community detection strategies.
  • Systematic Algorithm Design: Instead of ad-hoc algorithm development, the paper proposes a structured approach that can guide the creation of new community detection algorithms tailored to specific problems.
  • Community Parameter (CP) as a Global Property: The definition of a community based on a CP highlights its role as a global threshold for internal relation strength, simplifying the community structure analysis.
  • Equivalence of Maximal Communities and Maximal Cliques: A key theoretical result establishes that finding maximal communities in their framework is equivalent to finding maximal cliques in the derived effective edge graph, allowing the application of established clique-finding algorithms.

Key Results

  • The proposed scheme provides a general framework for designing community detection algorithms.
  • An algorithm derived from this scheme was demonstrated on Zachary's Karate Club network, producing three maximal communities with a CP of 1.5.
  • When tested on LFR benchmark networks, the proposed algorithm showed competitive performance in terms of Normalized Mutual Information (NMI), precision, recall, and F-Score, often outperforming other methods, especially as the number of shared communities increased. For instance, when the number of shared communities ($N_c$) was 2, the average F-score was around 0.9.

Limitations and Future Work

  • Algorithm Complexity: The paper acknowledges that the Bron-Kerbosch algorithm, used for finding maximal cliques, has exponential complexity in the worst case, which can limit its scalability for very large networks. However, they note that for sparse effective edge graphs, linear complexity might be achievable.
  • Choice of RSM and CP: The effectiveness of the proposed scheme relies on choosing appropriate Relation Strength Measurements (RSMs) and Community Parameters (CPs), which are problem-dependent and require careful consideration by the user.
  • Future Work: The authors suggest that their work facilitates the development of new algorithms and that readers need to derive algorithms according to their practical problems, implying further research into specific RSMs and CPs for various applications.

Summary updated

Abstract

Network structures, consisting of nodes and edges, have applications in almost all subjects. A set of nodes is called a community if the nodes have strong interrelations. Industries (including cell phone carriers and online social media companies) need community structures to allocate network resources and provide proper and accurate services. However, most detection algorithms are derived independently, which is arduous and even unnecessary. Although recent research shows that a general detection method that serves all purposes does not exist, we believe that there is some general procedure of deriving detection algorithms. In this paper, we represent such a general scheme. We mainly focus on two types of networks: transmission networks and similarity networks. We reduce them to a unified graph model, based on which we propose a method to define and detect community structures. Finally, we also give a demonstration to show how our design scheme works.
BibTeX
@article{lu2019scheme,
  author = {Haoye Lu and Amiya Nayak},
  title = {{A Scheme to Design Community Detection Algorithms in Various Networks}},
  journal = {Future Internet},
  year = {2019},
  doi = {10.3390/fi11020041},
}
Figure