Evolutionary approach to obtain graph covering by densely connected subgraphs

• Autorzy: Stańczak J. , Potrzebowski H. , Sęp K.
• Języki publikacji: EN

Abstrakty

EN

This article describes two evolutionary methods for dividing a graph into densely connected structures. The first method deals with the clustering problem, where the element order plays an important role. This formulation is very useful for a wide range of Decision Support System (DSS) applications. The proposed clustering method consists of two stages. The first is the stage of data matrix reorganization, using a specialized evolutionary algorithm. The second stage is the final clustering step and is performed using a simple clustering method (SCM). The second described method deals with a completely new partitioning algorithm, based on the subgraph structure we call α-clique. The α-clique is a generalization of the clique concept with the introduction of parameter α, which imposes for all vertices of the subgraph the minimal percentage (α*100%) of vertices of this subgraph that must be connected with vertices of this α-clique. Traditional clique is an instance of α-clique with α = 1. Application of this parameter makes it possible to control the degree (or strength) of connections among vertices (nodes) of this subgraph structure. The evolutionary approach is proposed as a method that enables finding separate α-cliques that cover the set of graph vertices.

Słowa kluczowe

EN

graph; clique; graph clustering; evolutionary algorithms

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2011
• Tom: Vol. 40, no 3
• Strony: 849--875
• Opis fizyczny: Bibliogr. 35 poz., il.

Twórcy

autor

Stańczak J.

autor

Potrzebowski H.

autor

Sęp K.

• Systems Research Institute Polish Academy of Science, Newelska 6, Warsaw 01-447, Poland,

Bibliografia

• Aho, A.V., Hopcroft, J.E. and Ullman, J.D. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley.
• Altus, S.S., Kroo, I.M. and Gage, P.J. (1996) A Genetic Algorithm for Scheduling and Decomposition of Multidisciplinary Design Problems. J. of Mechanical Design, 118(4), 486-489.
• Aussiello,G., Crescenzi, P., Gambosi,G., Kann,V., Marchetti-Spaccamela, A. and Protasi, M. (1999) Complexity and Approximation. Springer.
• Bagirov, A.M. and Yearwood, J. (2006) A new non-smooth optimization algorithm for minimum sum-of-squares clustering problems. EJOR 170, 578-595.
• Benson, S.J. and Ye, Y. (2000) Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation. In: M. Ferris and J. Pang, eds., Applications and Algorithms of complementarity. Kluwer Academic Publishers, 1-18.
• Beineke, L. and Wilson, R. (1978) Selected Topics in Graph Theory. Academic Press.
• Browning, T.R. (2001) Applying the Design Structure Matrix to System Decomposition and Integration Problems: A Review and New Directions. IEEE Transactions on Engineering Management, 48(3), 292-306.
• Chen, Z.-Q., Wang, R.-L. and Okazaki, K.(2008) An Efficient Genetic AlgorithmBased Approach for the Minimum Graph Bisection Problem. IJCSNS International Journal of Computer Science and Network Security, 8(6), 118-124.
• Cichosz, P. (2000) Systemy uczce się (Learning systems, in Polish). WNT, Warszawa.
• Cowen, L. (1998) Approximation Algorithms. John Hopkins University.
• Falkner, J., Rendl, F. and Wolkowicz, H. (1994) A computational study of graph partitioning. Mathematical Programming, 66 (2), 211-239.
• Hansen, P., Mladenovic, N. and Urosevic, D. (2004) Variable neighborhood search for the maximum clique. The Fourth International Colloquium on Graphs and Optimisation (GO-IV), 145 (1), 117-125.
• Hassin, R. and Khuller, S. (1986) z-Approximation. Journal of Algorithms, 41 (2), 429-442.
• Hochbaum, D.S., ed. (1997) Approximation Algorithms for NP.-hard Problems PWS Publishing Company.
• Hromkovic, J. (2001) Algorithmics for Hard Problems. Springer.
• Jain, A.K. and Dubes, R.C. (1988) Algorithms for Clustering Data. Eaglewood Cliffs, NJ, Prentice-Hall.
• Jukna, S. (2001) Extremal Combinatorics. Springer-Verlag, Berlin-Heidelberg.
• Korte, B. and Vygen, J. (2000) Combinatorial Optimization, Theory and Algorithms. Springer.
• Kumlander, D. (2007) An Approach for the Maximum Clique Finding Problem, Test Tool Software Engineering. Software Engineering, Innsbruck, Austria.
• Lenstra, J.K. (1977) Sequencing by enumerative methods. Mathematical Centre Tracts, Amsterdam.
• Marchiori, E. (1998) A Simple Heuristic Based Genetic Algorithm for the Maximum Clique Problem. Proceedings of the 1998 ACM Symposium on Applied Computing. ACM, 366-373.
• McCulley, C. and Bloebaum, C.A. (1996) Genetic Tool for Optimal Design Sequencing in Complex Engineering Systems. Structural Optimization, 12 (2-3), 186-201.
• McCormick, W.T., Schweitzer, P.J. and White, T.W. (1972) Problem decomposition and data reorganization by a clustering technique. Operations Res. 20, 993-1009.
• Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin-Heidelberg
• Mulawka, J. and Stańczak, J. (1999) Genetic Algorithms with Adaptive Probabilities of Operators Selection. Proceedings of ICCIMA’99, New Delhi, India. World Scientific, 464-468.
• Potrzebowski, H., Stańczak, J. and Sęp, K. (2004) Evolutionary metod in grouping of units with argument reduction. Proceedings of the 15th International Conference on Systems Science vol. 3. Oficyna Wydawnicza Politechniki Wrocławskiej, 29-3-6.
• Potrzebowski, H., Stańczak, J. and Sęp, K. (2006) Evolutionary Algorithm to Find Graph Covering Subsets Using -Cliques, In: J. Arabas, ed., Evolutionary Computation and Global Optimization, Prace Naukowe Politechniki Warszawskiej, 351-358.
• Protasi, M. (2001) Reactive local search for the maximum clique problem. Algorithmica, 29(4), 610-637.
• Rogers, J.L. (1997) Reducing Design Cycle Time and Cost Through Process Resequencing. International Conference on Engineering Design ICED 1997, Tampere, Finland, Estonian Academy Publishers.
• Stańczak, J. (2003) Biologically inspired methods for control of evolutionary algorithms, Control and Cybernetics. 32(2), 411-433.
• Sysło, M.M., Deo, N. and Kowalik, J.S. (1983) Algorithms of Discrete Optimization. Prentice-Hall.
• Talbi, E.-G. and Bessiere, P. (1991) A parallel genetic algorithm for the graph partitioning problem. Proc. of the 5th International conference on Supercomputing. ACM, New York, 312-320.
• Williamson, D. (1999) Lecture Notes on Approximation Algorithms. IBM Research Report RC 21409 02 17.
• Wilson, R.J. (1996) Introduction to Graph Theory. Addison Wesley Longman.
• Yu, T.L., Goldberg, D.E., Yassine, A. and Yassine, C. (2003) A Genetic Algorithm Design Inspired by Organizational Theory. Genetic and Evolutionary Computation Conference (GECCO) 2003, Chicago, Illinois. Springer-Verlag, Heidelberg, LNCS 2724, 1620-1621.