A graph-theoretic clustering methodology based on vertex attack tolerance


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


Engineering Program

Document Type

Conference Proceeding

Publication Date


Journal Title

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