Automatic Quasi-Clique Merger Algorithm — A hierarchical clustering based on subgraph-density

The Automatic Quasi-Clique Merger algorithm is a new algorithm adapted from early work published under the name QCM (introduced by Ou and Zhang (2007)). The AQCM algorithm performs hierarchical clustering in any data set for which there is an associated similarity measure quantifying the similarity of any data i and data j. Importantly, the method exhibits two valuable performance properties: (1) the ability to automatically return either a larger or smaller number of clusters depending on the inherent properties of the data rather than on a parameter. (2) the ability to return a very large number of relatively small clusters automatically when such clusters are reasonably well defined in a data set. In this work we present the general idea of a quasi-clique agglomerative approach, provide the full details of the mathematical steps of the AQCM algorithm, and explain some of the motivation behind the new methodology. The main achievement of the new methodology is that the agglomerative process now unfolds adaptively according to the inherent structure unique to a given data set, and this happens without the time-costly parameter adjustment that drove the previous QCM algorithm. For this reason we call the new algorithm automatic. We provide a demonstration of the algorithm’s performance at the task of community detection in a social media network of 22,900 nodes.