A graph-theoretic clustering methodology based on vertex attack tolerance

Abstract

We consider a schema for graph-theoretic clustering of data using a node-based resilience measure called vertex attack tolerance (VAT). Resilience measures indicate worst case (critical) attack sets of edges or nodes in a network whose removal disconnects the graph into separate connected components: the resulting components form the basis for candidate clusters, and the critical sets of edges or nodes form the intercluster boundaries. Given a graph representation G of data, the vertex attack tolerance of G is τ (G) = minS⊂V /S/ /V -S-C (V -S)j+1 , where Cmax(V - S) is the largest component remaining in the graph upon the removal of critical node set S. We propose three principal variations of VAT-based clustering methodologies: hierarchical (hier-VAT-Clust), non-hierarchical (VAT-Clust) variations, and variation partial-VAT-Clust. The hierarchical implementation yielded the best results on both synthetic and real datasets. Partial-VAT-Clust is useful in data involving noise, as it attempts to remove the noise while clustering the actual data.We also explored possible graph representations options, such as geometric and k-nearest neighbors, and discuss it in context of clustering efficiency and accuracy. max

Department(s)

Engineering Program

Document Type

Conference Proceeding

Publication Date

1-1-2015

Journal Title

Proceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015

Citation-only

Share

COinS