Automatic Quasi-Clique Merger Algorithm - a Hierarchical Clustering Based on Subgraph-Density.
Automatic Quasi-Clique Merger Algorithm - a Hierarchical Clustering Based on Subgraph-Density.
复制标题
DOI：
10.1016/j.physa.2021.126442
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Scott Payne;Edgar Fuller;G. Spirou;Cun-Quan Zhang
中科院分区：
文献类型：
--
作者：
Scott Payne;Edgar Fuller;G. Spirou;Cun-Quan Zhang
自动准团合并算法是一种新的算法，改编自以QCM名称发表的早期工作（由Ou和Zhang（2007）介绍）。AQCM算法在任何数据集中执行分层聚类，其中存在量化任何数据i和数据j的相似性的相关相似性度量。重要的是，该方法表现出两个有价值的性能属性：（1）根据数据的固有属性而不是参数自动返回更大或更小数量的聚类的能力。(2)在数据集中合理地定义了大量相对较小的聚类时，自动返回这些聚类的能力。在这项工作中，我们提出了一个准集团凝聚的方法的一般思想，提供完整的细节的数学步骤的AQCM算法，并解释一些背后的新方法的动机。新方法的主要成就是凝聚过程现在根据给定数据集特有的固有结构自适应地展开，并且这种情况不会发生驱动先前QCM算法的时间昂贵的参数调整。出于这个原因，我们称新算法为自动算法。我们提供了一个演示的算法的性能在社会媒体网络的22,900个节点的社区检测任务。
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 algorithmautomatic. We provide a demonstration of the algorithm’s performance at the task of community detection in a social media network of 22,900 nodes.