Robust Graph-Theoretic Clustering Approaches using Node-Based Resilience Measures
Abstract
This paper examines a schema for graph-theoretic clustering using node-based resilience measures. Node-based resilience measures optimize an objective based on a critical set of nodes whose removal causes some severity of disconnection in the network. Beyond presenting a general framework for the usage of node based resilience measures for variations of clustering problems, we emphasize the unique potential of such methods to accomplish the following properties: (i) clustering a graph in one step without knowing the number of clusters a priori, and (ii) removing noise from noisy data. We first present results of clustering experiments using a β-parametrized generalization of vertex attack tolerance, showing high clustering accuracy for both real datasets and equal density synthetic data sets, as well as successful removal of noise nodes. It is shown that arbitrarily increasing β increases the number of noise nodes removed in some cases, and that internal validation measures can be used to determine the correct number of clusters in a class of datasets. Further results are presented using five different resilience measures with a general node-based resilience clustering technique. In a subset of cases a resilience measure, such as integrity, is able to cluster to high accuracy in one step, giving the correct clustering while also determining the correct number of clusters. Integrity is also shown to be promising with respect to noise removal, removing up to 80% of noise on some datasets.
Recommended Citation
J. Matta et al., "Robust Graph-Theoretic Clustering Approaches using Node-Based Resilience Measures," Proceedings of the IEEE 16th International Conference on Data Mining(2016, Barcelona, Spain), Institute of Electrical and Electronics Engineers (IEEE), Dec 2016.
The definitive version is available at https://doi.org/10.1109/ICDM.2016.0043
Meeting Name
IEEE 16th International Conference on Data Mining (2016: Dec. 12-15, Barcelona, Spain)
Department(s)
Electrical and Computer Engineering
Research Center/Lab(s)
Center for High Performance Computing Research
Second Research Center/Lab
Intelligent Systems Center
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Dec 2016
