An IEEE-TNN paper on Max-Weight-Clique

[Marcello Pelillo]

Dear all,
 
the following paper, accepted for publication in the
IEEE Transactions on Neural Networks, is accessible at the
following www site:

      http://www.dsi.unive.it/~pelillo/papers/ieee-tnn-mwcp.ps.gz

Comments and suggestions are welcome!

Best regards,
Marcello Pelillo


*********************

Approximating the Maximum Weight Clique Using Replicator Dynamics

I. M. Bomze (University of Vienna, Austria) 
M. Pelillo  (University of Venice, Italy)
V. Stix     (University of Vienna, Austria)


Abstract

Given an undirected graph with weights on the vertices, the maximum weight
clique problem (MWCP) is to find a subset of mutually adjacent vertices
(i.e., a clique) having largest total weight. This is a generalization of
the classical problem of finding the maximum cardinality clique of an
unweighted graph, which arises as a special case of the MWCP when all the
weights associated to the vertices are equal. The problem is known to be
NP-hard for arbitrary graphs and, according to recent theoretical
results, so is the problem of approximating it within a constant factor.

Although there has recently been much interest around neural network
algorithms for the unweighted maximum clique problem, no effort has been
directed so far towards its weighted counterpart. In this paper, we
present a parallel, distributed heuristic for approximating the MWCP based
on dynamics principles developed and studied in various branches of
mathematical biology. The proposed framework centers around a recently
introduced continuous characterization of the MWCP which generalizes an
earlier remarkable result by Motzkin and Straus. This allows us to
formulate the MWCP (a purely combinatorial problem) in terms of a
continuous quadratic programming problem. One drawback associated with
this formulation, however, is the presence of "spurious" solutions, and
we present characterizations of these solutions. To avoid them we
introduce a new regularized continuous formulation of the MWCP inspired by
previous works on the unweighted problem, and show how this approach
completely solves the problem.

The continuous formulation of the MWCP naturally maps onto a parallel,
distributed computational network whose dynamical behavior is governed by
the so-called replicator equations. These are dynamical systems
introduced in evolutionary game theory and population genetics to model
evolutionary processes on a macroscopic scale. We present theoretical
results which guarantee that the solutions provided by our clique finding
replicator network are actually the ones being sought. Extensive
experiments on both randomly generated and standard benchmark graphs have
been conducted, and the results obtained confirm the effectiveness of the
proposed approach.


Key words: Maximum weight clique, replicator equations, evolutionary game
theory, dynamical systems, quadratic programming.

*********************


________________________________________________________________________
                                                        Marcello Pelillo
                                             Dipartimento di Informatica
                                      Universita' Ca' Foscari di Venezia
                             Via Torino 155, 30172 Venezia Mestre, Italy

                                                  Tel: (39) 041 2908.440
                                                  Fax: (39) 041 2908.419
                                            E-mail: pelillo at dsi.unive.it
                                   URL: http://www.dsi.unive.it/~pelillo