Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling - MathOverflow

Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling

2011-12-26T10:35:26Z

I encountered a problem which roughly translates to the following in mathematical terms:

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?

Answer by Chad Musick for Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling

2011-12-26T21:54:28Z

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 Noack, many variants of this problem are NP-hard, but there are reasonable approximation methods.

There is a nice piece of open-source software, Gephi, that automates clustering in visually beautiful ways. The graphviz project (originally from AT&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.

Answer by Suresh Venkat for Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling

2011-12-27T04:49:39Z

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 (see the references here)