×

zbMATH — the first resource for mathematics

Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation. (English) Zbl 1380.65100
A continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix is presented. A one-to-one correspondence between stationary points of the authors’ formulation and cliques of a given graph is built. It is shown that the local (resp. global) minima of the continuous problem correspond to the maximal (resp. maximum) cliques of the given graph. A new clique finding algorithm based on the continuous formulation is presented. The efficiency of the new algorithm is tested on the DIMACS data sets to show that it outperforms other existing algorithms based on the Motzkin-Straus formulation and that it can compete with a sophisticated combinatorial heuristic.

MSC:
65K05 Numerical mathematical programming methods
15A23 Factorization of matrices
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
Software:
CLIP; DIMACS; TRON
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979) · Zbl 0411.68039
[2] Luce, RD; Perry, AD, A method for matrix analysis of group structure, Psychometrika, 14, 94-114, (1949)
[3] Ben-Dor, A; Shamir, R; Yakhini, Z, Clustering gene expression patterns, J. Comput. Biol., 6, 281-297, (1999)
[4] Sugihara, G, Graph theory, homology and food webs, Proc. Symp. Appl. Math., 30, 83-101, (1984)
[5] Prihar, Z.: Topological properties of telecommunication networks. Proc. IRE 44, 927-933 (1956) · Zbl 1305.90349
[6] Rhodes, N; Willett, P; Calvet, A; Dunbar, JB; Humblet, C, CLIP: similarity searching of 3D databases using clique detection, J. Chem. Inf. Comput. Sci., 43, 443-448, (2003)
[7] Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos P.M. (eds.) Handbook of Combinatorial Optimization, pp. 1-74. Springer, New York (1999). doi:10.1007/978-1-4757-3023-4 · Zbl 1253.90188
[8] Wu, Q; Hao, J-K, A review on algorithms for maximum clique problems, Eur. J. Oper. Res., 242, 693-709, (2015) · Zbl 1341.05241
[9] Grosso, A; Locatelli, M; Pullan, W, Simple ingredients leading to very efficient heuristics for the maximum clique problem, J. Heuristics, 14, 587-612, (2008) · Zbl 1173.90565
[10] Motzkin, TS; Straus, EG, Maxima for graphs and a new proof of a theorem of turan, Can. J. Math., 17, 533-540, (1965) · Zbl 0129.39902
[11] Bomze, IM, Evolution towards the maximum clique, J. Glob. Optim., 10, 143-164, (1997) · Zbl 0880.90110
[12] Ding, C; Li, T; Jordan, MI, Non-negative matrix factorization for combinatorial optimization: spectral clustering, graph matching and clique finding, IEEE Int. Conf. Data Mining, 44, 183-192, (2008)
[13] Gibbons, LE; Hearn, DW; Pardalos, PM; Ramana, MV, Continuous characterization of the maximum clique problem, Math. Oper. Res., 22, 754-768, (1997) · Zbl 0883.90098
[14] Pardalos, PM; Phillips, AT, A global optimization approach for solving the maximum clique problem, Int. J. Comput. Math., 17, 533-540, (1990) · Zbl 0825.68488
[15] Pelillo, M, Relaxation labeling networks for the maximum clique problem, J. Artif. Neural Netw., 2, 313-328, (1995)
[16] Du, G., Gu, J., Pardalos, P.M.: Satisfiability Problem: Theory and Applications, DIMACS Series, vol. 35. American Mathematical Society, Providence (1997) · Zbl 0881.00041
[17] Horst, R., Pardalos, P.M., Van Thoai, N.: Introduction to Global Optimization. Springer, Berlin (2000) · Zbl 0966.90073
[18] Pardalos, PM; Xue, J, The maximum clique problem, J. Glob. Optim., 4, 301-328, (1992) · Zbl 0797.90108
[19] Gillis, N; Glineur, F, Continuous characterization of the maximum-edge biclique problem, J. Glob. Optim., 58, 439-464, (2014) · Zbl 1305.90349
[20] Belachew, M.T., Gillis N.: Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation. arXiv:1505.07077 (2015) · Zbl 1380.65100
[21] Ho, N.D.: Non-negative Matrix Factorization Algorithms and Applications. Doctoral dissertation, Université catholique de Louvain (2008) · Zbl 0797.90108
[22] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[23] Calamai, PH; Moré, JJ, Projected gradient methods for linearly constrained problems, Math. Prog., 39, 93-116, (1987) · Zbl 0634.90064
[24] Lin, C-J; Moré, JJ, Newton’s method for large bound-constrained optimization problems, SIAM J. Optim., 9, 1100-1127, (1999) · Zbl 0957.65064
[25] Golub, G.H., Loan, C.F.V.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[26] Vandaele, A; Gillis, N; Glineur, F; Tuyttens, D, Heuristics for exact non-negative matrix factorization, J. Glob. Optim., 65, 369-400, (2016) · Zbl 1341.65057
[27] Berman, A., Plemmons, R.J.: Non-negative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994) · Zbl 0815.15016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.