Message Boards Message Boards

2
|
3390 Views
|
2 Replies
|
4 Total Likes
View groups...
Share
Share this post:

What does FindGraphPartitions do?

Posted 8 years ago

What does the function FindGraphPartitions do?

The documentation doesn't explain this function clearly. I can see that this is the key:

FindGraphPartition[g,k] gives a partition of vertices into k approximately equal-size parts.

FindGraphPartition finds a partition of vertices such that the number of edges having endpoints in different parts is minimized.

But that's not a precise definition. What is "approximately equal-size"? What is the quantity being optimized here? If that's not easy to explain, then what algorithm does it use?

I have asked support about this more than once and received no useful response. I know others have asked too and they also received no response.

A function like this is not useful except as a toy because I don't even know what it does (not only how it does it).

The same can be said about FindGraphCommunities too. The description is extremely vague. In that case however, I am familiar enough with the topic that I can guess what the different methods actually do. However, this is only a guess (even if it's a confident one), so no one can use the result form these functions in a peer-reviewed publication where reproducibility is required. The fix would be so easy: just put in references for each community detection method. E.g. Method -> "Centrality" is probably based on this paper. Why does't Wolfram do it then?


I know that many people complain that Mathematica is not open source and we can't know how it computes e.g. integrals (and oh the horror, it even gives wrong results sometimes!). I hope it's clear enough that what I am talking about here is something entirely different and much more serious. I don't have to know how to compute an integral to know what an integral is. But what FindGraphCommunity does is defined by the algorithm (i.e. how it does it) and without a proper description the function is simply useless. In the case of FindGraphPartitions I literally cannot even figure out what it actually does!

POSTED BY: Szabolcs Horvát
2 Replies

FindGraphPartitions is very useful if one is doing large-scale linear algebra on sparse matrices and underlying methods need (or at least eprform better with) something close to block diagonal. It can also be useful for plotting graphs in two or three dimensions since it helps to cut down on edge intersections. A consequence is that a graph corresponding to a FEM-like mesh (for example) can be plotted in a way that might actually recover the original shape.

A good reference for this technology is the METIS site.

For the graph drawing aspect I think there is some mention in this TMJ article by Yifan Hu. And related.

POSTED BY: Daniel Lichtblau

Thank you for the links Daniel. They are useful.

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract