19434526 nodes, 38059692 edges. Use gpmetis 5.0.1, run 956 minutes, doesn't finish!?
I have a graph with 19434526 nodes, 38059692 edges. I thought metis can give a quick partition of this graph, but it still runs on our powerful server. I don't know why, I see the introduction of metis that it can partition a graph with 1 million in seconds. Why this graph take days cannot finish partitioning?
Could you tell me how to use metis to get fast partitioning? I can put up with hours, but take days is too much. I think this graph is not that large for metis when I saw the performance report of metis.
Could you tell me why and suggestions?
Thank you! Looking forward to your quick reply!
Submitted by ray on Mon, 2011-10-17 15:19
»
- Login to post comments
RE: Try the 5.0.2 version of
Try the 5.0.2 version of Metis that has just been posted. This should address the issues with these types of graphs.
RE: Can you compute the degree
Can you compute the degree distribution of the graph and email it to me?
RE: This is graph file link
Sorry, I don't know what the k you want for computing this degree distribution. So I give you this link, you can download with:
wget 128.226.118.167:8080/graph. This graph file follows metis graph format.
Also when I try metis-4.0.3, I found that graphchk reports it has less number of edges than registered. I don't know why. I also check the edges number by printing it out and check by sum-up in program. I believe the edges number is all right. So I think maybe metis-4.0.3 cannot work on unconnected graph. Am I right? If I am wrong, please help to point it out.
Also you can help me to choose which metis I should use for partitioning such kind of graph.
Thank you.
RE: Your graph has vertices whose
Your graph has vertices whose degree is as high as 3.7M. What you need is the version of Metis for graphs with power law degree distribution (which is not public yet). For now, I suggest you try hMetis and see what happens. In hMetis, use the first-choice coarsening scheme.
george
RE: Thank you for your suggestions and help
When I have the result, I will get back to you to see if it is a good partition.
Thanks again.
RE: forget to say, partition this graph to 100 parts
forget to say, partition this graph to 100 parts
RE: How much memory do you have
How much memory do you have in your system?
What is the degree distribution of the graph? If the graph has only a few nodes with very high degree, Metis will not be fast. For such graph, at this point you can only partition it using hmetis.
RE: memory is 100G, 24 cpu cores
Thank you for your reply.
For this unconnected graph, it is composed of several separated graphs. And indeed it has a few nodes with very high degree.
So I don't know if your metis (k, par, h) can partition such kind of graph into number of partition I wish with minimum edge-cut?
Can hmetis partition this graph and satisfy my requirements? Or other suggestions.
Looking forward to your reply. Thank you in advance.
RE: If the graph is such that
If the graph is such that most of the edges connect to a single node, then metis will not work. Hmetis is a better choice. However, if your graph consists of many unconnected components, then why don't you just use hmetis to partition the largest(s) connected components. Those algorithms are designed to primarily handle connected graphs.
george
RE: Because the graph is generated automatically
Thank you for your reply.
Because the graph is generated automatically, as a result from another processing. So I don't know if the graph is unconnected one or connected one. Also don't know how many connected components there. I think I can program to pick up connected components from the graph first, though it would take additionally effort.
If Hmetis can do this work no matter unconnected or connect graph, that will save me a lot of effort.
Or another question: do you have any software to pick up connected components from an unconnected graph?
Thanks a lot for your help.