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:
- 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.
- 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.
- 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.
- 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.
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