Tolerance granulation based community detection algorithm

Shu Zhao, Ke Wang, Jie Chen, Feng Liu, Menghan Huang, Yanping Zhang, Jie TangTsinghua 2015 · DOI

Abstract

Community structure is a fundamental feature of real-world networks, revealing the internal organization of vertices. Accurately uncovering these structures is essential for understanding complex systems. This paper proposes the Tolerance Granulation based Community Detection Algorithm (TGCDA), which utilizes tolerance relations to granulate a network hierarchically. The algorithm first identifies an initial set of granules based on tolerance relations among vertices. These granules are then merged hierarchically using a granulation coefficient until a single granule remains. Finally, a partition is selected based on a maximum granulation criterion to resolve overlapping vertices. Experimental results on real-world and synthetic networks demonstrate that TGCDA identifies community structures more accurately than traditional methods, achieving a Normalized Mutual Information (NMI) accuracy 17.55% higher than the Newman Fast Algorithm (NFA) on average.

Introduction

In network science, a "community" consists of a group of nodes more densely connected to each other than to the rest of the network. Detecting these structures is vital for fields ranging from social dynamics to biological pathways. However, existing algorithms often struggle with the trade-off between computational efficiency and accuracy, particularly when dealing with overlapping communities or "fuzzy" boundaries. TGCDA addresses this gap by leveraging the local density of "tolerance relations"—where nodes share connections without necessarily forming a perfect transitive clique—to build a more accurate global partition.

The TGCDA Methodology

The core innovation of TGCDA is the application of Granular Computing to network topology. The process follows four main stages:

  1. Initial Granulation: The algorithm identifies Maximal Tolerance Granules (MTGs). In graph terms, these are subsets of vertices where every pair is connected by an edge. Unlike traditional clusters, these granules can overlap, reflecting the reality of complex networks.
Example of a network partitioned into maximal tolerance granules.
  1. Hierarchical Merging: A Granulation Coefficient (GC)—essentially a Jaccard similarity index for granules—is defined. The algorithm iteratively merges the pair of granules with the highest GC.
  2. Optimization via Extended Modularity: To determine the optimal stopping point, the algorithm calculates Extended Modularity (GQ) at each layer of the hierarchy. The layer with the maximum GQ value is selected as the optimal partition.
  3. Handling Overlaps: Remaining overlapping vertices are assigned to specific communities based on their "degree of affiliation," ensuring a clean final partition.

Experimental Evaluation

The authors evaluated TGCDA using both synthetic benchmarks and classic real-world networks:

  • Synthetic Random Networks: Generated using the GN-benchmark model (128 nodes in four communities). This tested performance as community clarity ($P_{in}$ vs $P_{out}$) varied.
  • Real-World Networks: Including Zachary’s Karate Club (34 members), the Bottlenose Dolphin Network (62 nodes), and American College Football (115 nodes).

Key Results and Discussion

TGCDA consistently outperformed the Newman Fast Algorithm (NFA) and the Clustering Granulation based Community Detection Algorithm (CGCDA). On real-world networks, it achieved an average NMI accuracy 17.55% higher than NFA.

NMI accuracy comparison on synthetic random networks showing TGCDA's superior performance as internal edge probability increases.

As shown in the synthetic tests, TGCDA is particularly effective when the community structure is well-defined (where $P_{in} \ge 0.7$). The algorithm's total time complexity is approximately $O(n^2)$, making it computationally competitive with other hierarchical clustering methods while providing superior accuracy.

Conclusion

By shifting from strict transitivity to tolerance relations, TGCDA acknowledges that local density is a superior indicator of community membership. While the algorithm shows strong results, future work will explore "multi-granularity" lenses to improve detection in extremely noisy networks and adapt the model for dynamic, time-varying systems.

Summary updated

Abstract

Community structure is one of the most important features in real networks and reveals the internal organization of the vertices. Uncovering accurate community structure is effective for understanding and exploiting networks. Tolerance Granulation based Community Detection Algorithm (TGCDA) is proposed in this paper, which uses tolerance relation (namely tolerance granulation) to granulate a network hierarchically. Firstly, TGCDA relies on the tolerance relation among vertices to form an initial granule set. Then granules in this set which satisfied granulation coefficient are hierarchically merged by tolerance granulation operation. The process is finished till the granule set includes one granule. Finally, select a granule set with maximum granulation criterion to handle overlapping vertices among some granules. The overlapping vertices are merged into corresponding granules based on their degrees of affiliation to realize the community partition of complex networks. The final granules are regarded as communities so that the granulation for a network is actually the community partition of the network. Experiments on several datasets show our algorithm is effective and it can identify the community structure more accurately. On real world networks, TGCDA achieves Normalized Mutual Information (NMI) accuracy 17.55% higher than NFA averagely and on synthetic random networks, the NMI accuracy is also improved. For some networks which have a clear community structure, TGCDA is more effective and can detect more accurate community structure than other algorithms.
BibTeX
@inproceedings{zhao2015tolerance,
  author = {Shu Zhao and Ke Wang and Jie Chen and Feng Liu and Menghan Huang and Yanping Zhang and Jie Tang},
  title = {{Tolerance granulation based community detection algorithm}},
  booktitle = {Tsinghua},
  year = {2015},
  doi = {10.1109/tst.2015.7350014},
}
Figure