  Finding complete subgraphs in a graph, that is, cliques, is a key problem and
has many real-world applications, e.g., finding communities in social networks,
clustering gene expression data, modeling ecological niches in food webs, and
describing chemicals in a substance. The problem of finding the largest clique
in a graph is a well-known NP-hard problem and is called the maximum clique
problem (MCP). In this paper, we formulate a very convenient continuous
characterization of the MCP based on the symmetric rank-one nonnegative
approximation of a given matrix, and build a one-to-one correspondence between
stationary points of our formulation and cliques of a given graph. In
particular, we show that the local (resp. global) minima of the continuous
problem corresponds to the maximal (resp. maximum) cliques of the given graph.
We also propose a new and efficient clique finding algorithm based on our
continuous formulation and test it on various synthetic and real data sets to
show that the new algorithm outperforms other existing algorithms based on the
Motzkin-Straus formulation, and can compete with a sophisticated combinatorial
heuristic.
