Automatic Quasi-Clique Merger Algorithm - a Hierarchical Clustering Based on Subgraph-Density

Area of Science:

• Data Science
• Network Analysis
• Machine Learning

Background:

• Traditional clustering algorithms often require manual parameter selection, which can be time-consuming and suboptimal.
• Existing methods like Quasi-clique Merger (QCM) lack adaptivity to inherent data structures.
• Hierarchical clustering is a powerful technique but can be sensitive to parameter choices.

Purpose of the Study:

• Introduce the Automatic Quasi-clique Merger (AQCM) algorithm, an advancement over the QCM algorithm.
• Detail the mathematical steps and adaptive agglomerative approach of AQCM.
• Demonstrate AQCM's effectiveness in community detection within large-scale networks.

Main Methods:

• AQCM performs hierarchical clustering using a similarity measure between data points.
• The algorithm adaptively merges quasi-cliques based on data's inherent structure.
• No parameter adjustment is required, unlike the previous QCM algorithm.

Main Results:

• AQCM automatically determines the number of clusters based on data properties.
• The algorithm effectively identifies a large number of small, well-defined clusters when present.
• Demonstrated successful community detection in a social media network with 22,900 nodes.

Conclusions:

• AQCM provides an automatic and adaptive hierarchical clustering solution.
• The method overcomes the parameter-tuning limitations of prior algorithms.
• AQCM shows promise for efficient community detection in complex networks.