Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T19:19:54Z http://mathoverflow.net/feeds/question/84305 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84305/finding-optimal-vertex-partitioning-of-graphs-to-maximize-cohesion-and-minimize-c Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling reddoc 2011-12-26T10:35:26Z 2011-12-27T04:49:39Z <p>I encountered a problem which roughly translates to the following in mathematical terms:</p> <p>Given a directed graph, find an optimal vertex partitioning to maximize the edges inside partitions (strong cohesion) and minimize them between partitions (loose coupling). I've yet to find the exact metric to optimize for but is there an algorithm that can do something like this?</p> http://mathoverflow.net/questions/84305/finding-optimal-vertex-partitioning-of-graphs-to-maximize-cohesion-and-minimize-c/84339#84339 Answer by Chad Musick for Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling Chad Musick 2011-12-26T21:54:28Z 2011-12-27T01:07:40Z <p>This is a variant of graph clustering. The primary method of solving this problem is to decide on desirable parameters for the outcome and apply an energy (or force) model to approximate these. According to <a href="http://www.springerlink.com/content/bnkwtl1vanl222ln/" rel="nofollow">Noack</a>, many variants of this problem are NP-hard, but there are reasonable approximation methods.</p> <p>There is a nice piece of open-source software, <a href="https://gephi.org/features/" rel="nofollow">Gephi</a>, that automates clustering in visually beautiful ways. The graphviz project (originally from AT&amp;T) also implements some of these methods, but its focus is not on clustering and so it lacks some of the versatility in clustering that Gephi has. </p> http://mathoverflow.net/questions/84305/finding-optimal-vertex-partitioning-of-graphs-to-maximize-cohesion-and-minimize-c/84362#84362 Answer by Suresh Venkat for Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling Suresh Venkat 2011-12-27T04:49:39Z 2011-12-27T04:49:39Z <p>I'm not sure where in your formulation you use the directed nature of the graphs. However, if that's not a critical point, correlation clustering is a clean formulation that captures this: You're given a weighted graph and the goal is to find a partitioning so that you maximize (the sum of weights for intra0cluster edges - sum of weights of intercluster edges). There are simple approximation algorithms for this problem (<a href="http://www.cs.yale.edu/homes/el327/papers/CorrelationClusteringRevisited.pdf" rel="nofollow">see the references here</a>)</p>