Ant colony opimization algorithms for clustering problems

Krzysztof Schiff


The clustering problem is one of the main problems which can be encountered in a data analysis. This problem can be modelled by means of a graph; finding clusters means finding cliques in the graph. Often there is a need to find clusters (cliques) in a graph in different ways and to construct a list of clusters. This paper describes two such ways, these can be stated as the cluster minimum covering problem and the vertex cluster minimum partitioning problem. This paper describes new ant algorithms which were used in order to make a list of clusters in both presented problems, and also discusses the results of their comparison.

Słowa kluczowe: clustering, clique covering problem, clique vertex partitioning problem, ant algorithms

Garey M., Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York 1979.

Ponce J., Ponce E., Padilla F., Padilla A., Ant Colony Algorithm for Clustering through of Cliques, 2006.

Ponce J., Ponce E., Padilla F., Padilla A., Ochoa A., Algoritmo De Colonia De Hormigas Para El Problema Del Clique Máximo Con Un Optimizador Local K-Opt, Hífen, Uruguaiana, Vol. 30, No. 58, Brasil 2006.

Fenet S., Solnon C., Searching for Maximum Cliques with Ant Colony Optimization EvoWorkshops 2003, LNCS 2611, 2003, 236-245.

Xu X., Ma J., Lee J., An Improved Ant Colony Optimization for the Maximum Clique Problem, IEEE Third International Conference on Natural Computation, 2007.

Bron C., Kerbosh J., Finding all cliques of an undirected graph, Association of Computer Machine, 16, 1973, 575-577.

Wang J., Xu X., Tsng Z., Bi W., Chen X., Li Y., A New Neural Network Algorithm for Clique Vertex-Partition Problem, Yin F., Wang J., Guo C. (Ed.): ISNN 2004, LNCS 3173, Springer-Verlag, Berlin 2004, 425-29.

Kellerman E., Determination of keyword conflict, IBM Technical Disclosure Bulletin 16, 1973, 544-546.

Behrisch M., Taraz A., Efficiently covering complex networks with cliques of similar vertices, TCS: Theory of Computer Science 355, 2006, 37-47.

Cazals F., Karnade C., An algorithm for reporting maximal c-cliques, Theory of Computer Science 349, 2005, 484-490.

Gramm J., Guo J., Huffner F., Niedermeier R., Data reduction and exact algorithms for clique cover, ACM J. Exp. Algorith. 13, 2.2–2.15, 2009.

Tseng C., Siewiorek D., IEEE Trans. CAD 5, 379 (1986).

Harmanani H., A Parallel Neural Networks Algorithm for the Clique Partitioning Problem, IJCA, Vol. 9, No. 2, 2002

Little P., Rylander B., Problem Partitioning in Hybrid Genetic Algorithms, Proceedings of the 5th WSEAS Int. Conf. on circuits, systems, electronics, control and signal processing, Dallas, USA, November 1–3, 2006

Rizzo J., An Ant System Algorithm for Maximum Clique, The Pennsylvania State University, Master Thesis, 2003.

Orlin J., Contentment in graph theory: covering graphs with cliques, Mathematics 39, 1977, 406-424.

Snyers D., Clique Partitioning Problem and Genetic Algorithms in Albrecht R.F.(eds.), Artificial Neural Nets and Genetic Algorithms Springer-Verlag, 1993.

Tseng C., Sieworek D., Facet: A Procedure for the Automated Synthesis of Digital Systems, Proceeding of the 20th ACM/IEEE Design Automated Conf., 1983, 490-496.