Hi Hyunchul, On Tue, 03 Mar 2009 15:35:11 +0900, Hyunchul Kim <sun...@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 > -- http://mail.python.org/mailman/listinfo/python-list
