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

A graph density-based strategy for features fusion from different peak extract software to achieve more metabolites in metabolic profiling from high-resolution mass spectrometry.

In metabolomics study, it is not easy to extract the metabolites from data of ultra high-performance liquid chromatography-high-resolution mass spectrometry, especially for those with low abundance. Different software for peak recognition and matching use different algorithms, leading to different extract results. Therefore, integration of results from different software can obtain richer metabolome information, but the redundant features should be removed. In this study, an integrated strategy of fusing features and removing redundancy based on graph density (FRRGD) was proposed. A graph is used to cover the ion features generated by two open access software (XCMS, MZmine 2) and a software (SIEVE) from an instrument vendor, and redundant features were removed by searching the maximal complete sub-graphs. A standard mixture containing 41 metabolites and a spontaneous urine were utilized to develop the method and demonstrate its usefulness. For the standard mixture, 19, 19 and 27 metabolites were extracted by XCMS, MZmine 2 and SIEVE, respectively. After fusion by FRRGD, 37 metabolites were obtained. For the diluted spontaneous urine sample, 1103, 1500 and 387 metabolites were extracted by XCMS, MZmine 2 and SIEVE, respectively, FRRGD produced 1619 metabolites which were much more than individual software, significantly increasing metabolome coverage. The proposed FRRGD shows a great prospect as a new data processing strategy for metabolomics study.

Lower Bounds on Paraclique Density.

The scientific literature teems with clique-centric clustering strategies. In this paper we analyze one such method, the paraclique algorithm. Paraclique has found practical utility in a variety of application domains, and has been successfully employed to reduce the effects of noise. Nevertheless, its formal analysis and worst-case guarantees have remained elusive. We address this issue by deriving a series of lower bounds on paraclique densities.