A re-coloring approach for graph b-coloring based clustering

摘要

This paper proposes a re-coloring approach for graph b-coloring based clustering. Based on the notion of graph b-coloring in graph theory, a b-coloring based clustering method was proposed. However, previous method did not explicitly consider the quality of clusters, and could not find out better clusters which satisfy the properties of b-coloring. Although a greedy re-coloring algorithm was proposed to reflect the quality of clusters, it was still restrictive in terms of the explored search space due to its greedy and sequential re-coloring process. We aim at overcoming the limitations by enlarging the search space for re-coloring, while guaranteeing the b-coloring properties. In our approach, the vertices in a graph are divided into two disjoint subsets based on the properties of b-coloring. A best first re-coloring algorithm is proposed to realize non-greedy search for the admissible colors of vertices. A color exchange algorithm is proposed to remedy the problem in sequential re-coloring. These algorithms are orthogonal to each other with respect to the re-colored vertices, and thus can be utilized in conjunction. The proposed approach was evaluated against several UCI benchmark datasets. The results are encouraging and indicate the effectiveness of the proposed method, especially with respect to the ground truth micro-averaged precision.