3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ to maximize the edges'' = to maximize the number of the edges''? $\endgroup$
    – Boris Novikov
    Dec 26, 2011 at 18:36
  • $\begingroup$ 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. $\endgroup$
    – reddoc
    Dec 28, 2011 at 19:55
  • $\begingroup$ en.wikipedia.org/wiki/Modularity_(networks) $\endgroup$
    – RobPratt
    Sep 30, 2022 at 13:51

2 Answers 2

Reset to default
2
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – reddoc
    Dec 28, 2011 at 22:07
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Facebook has their friend graph, which they must use something like this to lay out... $\endgroup$
    – Igor Rivin
    Dec 26, 2011 at 22:02
  • $\begingroup$ 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"? $\endgroup$
    – reddoc
    Dec 28, 2011 at 21:03
  • $\begingroup$ 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. $\endgroup$
    – Chad Musick
    Dec 29, 2011 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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