Abstract
In many applications of computer vision and pattern recognition which use graph-based knowledge representation, it is of great interest to be able to extract the K largest cliques in a graph, but most methods are geared either towards extracting the single clique of maximum size, or enumerating all cliques, without following any particular order. In this paper we present a novel approach for partial clique enumeration, that is, the extraction of the K largest cliques of a graph. Our approach is based on a continuous formulation of the clique problem developed by Motzkin and Straus, and is able to avoid extracting the same clique multiple times. This is done by casting the problem into a game-theoretic framework and iteratively rendering unstable the solutions that have already been extracted.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P.: Automatic subspace clustering of high dimensional data for data mining applications. In: Proc. 1998 ACM-SIGMOD Int. Conf. Management of Data, Seattle, Washington (June 1998)
Barrow, H.G., Burstall, R.M.: Subgraph Isomorphism, Matching Relational Structures, and Maximal Cliques. Information Processing Letters 4(4), 83–84 (1976)
Battiti, R., Protasi, M.: Reactive local search for the maximum clique problem, Technical Report TR-95-052, International Computer Science Institute, Berkeley, CA (1995)
Bertoni, A., Campadelli, P., Grossi, G.: A neural algorithm for the maximum clique problem: analysis, experiments and circuit implementation. Algorithmica 33(1), 71–88 (2002)
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, Supplement, vol. A, pp. 1–74. Kluwer Academic Publishers, Boston, MA (1999)
Bomze, I.M., Pelillo, M., Giacomini, R.: volutionary approach to the maximum clique problem: Empirical evidence on a larger scale. In: Bomze, I.M., Csendes, T., Horst, R., Pardalos, P.M. (eds.) Developments in Global Optimization, pp. 95–108. Kluwer, Dordrecht, The Netherlands (1997)
Busygin, S.: A new trust region technique for the maximum weight clique problem (2002)
Cannings, C., Veckers, G.: Patterns of ess’s. J. Theor. Biol. p. 132
Dmitry, D., Ari, R.: Efficient Unsupervised Discovery of Word Categories Using Symmetric Patterns and High Frequency Words. In: Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, Association for Computational Linguistics, pp. 297–304 (2006)
Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22, 754–768 (1997)
Hammersley, J., Clifford, P.: Markov fields on finite graphs and lattices, unpublished manuscript (1971)
Hastad, J.: Clique is hard to approximate within n 1 − ε. In: Proc. 37th Ann. Symp. Found. Comput. Sci. pp. 627–636 (1996)
Horaud, R., Skordas, T.: Stereo correspondence through feature grouping and maximal cliques. IEEE Trans. Pattern Anal. Mach. Intell. 11(11), 1168–1180 (1989)
Kopf, R., Ruhe, G.: A computational study of the weighted independent set problem for general graphs. Found. Control Engin. 12, 167–180 (1987)
Losert, V., Akin, E.: Dynamics of games and genes: Discrete versus continuous time. J. Math. Biol. 17, 241–251 (1983)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math. 17, 533–540 (1965)
Nina, M., Dana, R., Ram, S.: A New Conceptual Clustering Framework. Machine Learning 56, 115–151 (2004)
Pavan, M., Pelillo, M.: Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(1), 167–172 (2007)
Pelillo, M.: Replicator equations, maximal cliques, and graph isomorphism. Neural Computation 11(8), 2023–2045 (1999)
Pelillo, M., Jagota, A.: Feasible and infeasible maxima in a quadratic program for maximum clique. J. Artif. Neural Networks 2, 411–420 (1995)
Pelillo, M., Torsello, A.: Payoff-Monotonic Game Dynamics and the Maximum Clique Problem. Neural Computation 18, 1215–1258 (2006)
Torsello, A., Bulò, S.R., Pelillo, M.: Grouping with asymmetric affinities: A game-theoretic perspective. In: CVPR 2006. Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 292–299. Los Alamitos, CA (2006)
Weibull, J.W.: Evolutionary Game Theory. MIT Press, Cambridge (1995)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bulò, S.R., Torsello, A., Pelillo, M. (2007). A Continuous-Based Approach for Partial Clique Enumeration. In: Escolano, F., Vento, M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2007. Lecture Notes in Computer Science, vol 4538. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72903-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-72903-7_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72902-0
Online ISBN: 978-3-540-72903-7
eBook Packages: Computer ScienceComputer Science (R0)