Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
to maximize the edges'' = to maximize the number of the edges''? –  Boris Novikov Dec 26 '11 at 18:36
    
I deliberately didn't write "number of edges" because as I said I've yet to find the exact metric to optimize for. The number of edges is definitely not a good metric because it would always lead to a trivial partitioning (with a single partition containing all the vertices). I think the "density" of the edges (=number of edges over maximal possible edges in the partition squared) may be a better metric. –  reddoc Dec 28 '11 at 19:55

2 Answers 2

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.

share|improve this answer
    
Facebook has their friend graph, which they must use something like this to lay out... –  Igor Rivin Dec 26 '11 at 22:02
    
Is this what's described here? en.wikipedia.org/wiki/Force-ased_algorithms_%28graph_drawing%29 It's a brilliant approach but my problem is that it doesn't give me a partitioning. Or do you mean something else by "force model"? –  reddoc Dec 28 '11 at 21:03
    
Yes, that's the one. It does give you a partition if you use the found clusters as your partition. The paper I linked to (Noack, "An Energy Model for Visual Graph Clustering") gives an algorithm for separating clusters. Once you've done this, the partition places each node in the cluster that it's part of. If you're using this for actual software, you might want to weight the edges based on what type of connection they have; if you are only doing static analysis where all links are of the same type, this might not matter, but for things like ipc, it can make a significant impact. –  Chad Musick Dec 29 '11 at 0:40

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)

share|improve this answer
    
Yes, this looks a lot like what I need. My domain problem does imply directed edges but I'm not sure I need consider this in the solution. –  reddoc Dec 28 '11 at 22:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.