Welcome to MathOverflow

Question

3

2

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?

flag	asked Dec 26 2011 at 10:35 reddoc 31●1

	`to maximize the edges'' = `to maximize the number of the edges''? – Boris Novikov Dec 26 2011 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 2011 at 19:55

Chad Musick · Answer 1 · 2011-12-27 01:07:40Z UTC

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.

edited Dec 27 2011 at 1:07

answered Dec 26 2011 at 21:54

Chad Musick
165●1●9

	Facebook has their friend graph, which they must use something like this to lay out... – Igor Rivin Dec 26 2011 at 22:02
	Is this what's described here? en.wikipedia.org/wiki/… 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 2011 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 2011 at 0:40

Suresh Venkat · Answer 2 · 2011-12-27 04:49:39Z UTC

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)

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.