An Effective Multi-level Immune Algorithm for Graph Bipartitionin

An important application of graph partitioning is data clustering using a graph model--- the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information for clustering. An effective multi-level algorithm based on AIS (artificial immune systems) for graph bipartitioning is proposed. During its coarsening phase, we adopt an improved matching approach based on the global information of the graph core to develop its guidance function. During its refinement phase, we exploit the hybrid immune refinement algorithm inspired in the CSA (clonal selection algorithm) and affinity maturation of the AIS. The algorithm is verified to be capable of finding the global approximate bipartitioning which incorporate early-exit FM (FM-EE) local improvement heuristic into CSA. The success of our algorithm relies on exploiting both the CSA and the concept of the graph core. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS that is a state-of-the-art partitioner in the literature. Our experimental evaluations show that it performs well and produces encouraging solutions on 18 graphs benchmarks.