Constant community identification in million-scale networks.

Area of Science:

• Network Science
• Graph Theory
• Machine Learning

Background:

• Community detection in complex networks is inherently stochastic, making accuracy assessment challenging.
• Identifying constant communities, vertex groups consistently clustered across algorithms, is crucial for reliable analysis.
• Existing methods for finding constant communities are computationally expensive and do not scale to large networks.

Purpose of the Study:

• To develop efficient and scalable methods for detecting constant communities in large-scale complex networks.
• To overcome the limitations of current expensive and non-scalable approaches for constant community identification.

Main Methods:

• Utilized binary edge classification to identify constant communities, classifying edges based on their participation in stable groups.
• Introduced a GCN-based semi-supervised approach (Line-GCN) and an unsupervised approach based on image thresholding.
• The proposed methods do not require explicit community detection, enabling scalability to networks with millions of vertices.

Main Results:

• Both semi-supervised and unsupervised methods achieved higher F1-scores and comparable or superior NMI scores on real-world graphs compared to state-of-the-art baselines.
• The unsupervised algorithm demonstrated a 10x speed improvement over baseline methods, with all proposed algorithms scaling effectively to large networks.
• The methods proved robust under noisy conditions, maintaining stability across three different well-studied noise models.

Conclusions:

• The developed binary edge classification methods offer a significant advancement in scalable and accurate constant community detection.
• These approaches provide a robust and efficient alternative for analyzing large and potentially noisy complex networks.
• The findings pave the way for more reliable community detection and network analysis in various scientific domains.