how to find all completely connected sub-graphs?

[wwwayne]

Hi Hyunchul,

On Tue, 03 Mar 2009 15:35:11 +0900, Hyunchul Kim
<sundol at sfc.keio.ac.jp> wrote:

>Hi, all,
>
>How can I find all "completely connected subgraphs" in a graph when node 
>and edge data are available?
>
>"completely connected subgraph" is a group, all members of which are 
>connected to each other.

Since you're asking here I suspect you want (to develop) a python
solution, but I have seen only solutions for a few special cases.

This is the well-known graph theoretic "maximal cliques" problem (dual
to the maximal independent sets problem) which is NP-complete so
heuristics are in order for large examples.

The most commonly used algorithm was (and perhaps still is, though I
haven't kept up with this area) Bierstone's Algorithm, which I believe
was unpublished so available only in discussion papers and the like. I
compared it and two other common (at the time) algorithms, implemented
in FORTRAN (as it was then), for a MSc project a U. Waterloo in 1970,
and probably still have a copy somewhere...

It may well also be in the update (ACM membership or site access
trough a univeristy library or similar is required to get the full
text of most of these):

Corrections to Bierstone's Algorithm for Generating Cliques
http://portal.acm.org/citation.cfm?id=321694.321698

and:

Algorithm 457: finding all cliques of an undirected graph
http://portal.acm.org/citation.cfm?doid=362342.362367

The classic reference for such clustering techniques is:

An Analysis of Some Graph Theoretical Cluster Techniques
http://portal.acm.org/citation.cfm?id=321608&dl=GUIDE&coll=GUIDE&CFID=25034057&CFTOKEN=54219245

If you want to find all cliques of a fixed size, then there are more
efficient algorithms, and there's a very recent paper on these:

Virginia Vassilevska, Efficient algorithms for clique problems,
Information Processing Letters, v.109 n.4, p.254-257, January, 2009 
http://portal.acm.org/citation.cfm?id=1480733&dl=GUIDE&coll=GUIDE&CFID=25034057&CFTOKEN=54219245

I hope these leads help!

wwwayne

>Thanks,
>
>Hyunchul
>