Unable to partition a very large graph (vertices=167276, #Hedges: 4718221)

Dea Sir/Madam:

I'm currently trying to partition a large unweighted simple graph with "shmetis". The OS is Windows XP with a Pentium 3.6GHz CPU and 2G RAM. After running for a while, the program caused the OS to terminate it, saying: "shmetis.exe has encountered a problem and needs to close". I tried the program with a smaller graph (part of the larger graph) and it worked well.

Following is the output of the program. Is it related to out-of-memory problem or other issues? Is there a maximum number of edges that it can deal with?

C:\_zDOWNLOAD\hmetis-1.5.3-WIN32>shmetis ..\data\p_locpairs_new.csv 64 25
HMETIS 1.5.3 Copyright 1998, Regents of the University of Minnesota

HyperGraph Information -----------------------------------------------------
Name: ..\data\p_locpairs_new.csv, #Vtxs: 167276, #Hedges: 4718221, #Parts: 64,
UBfactor: 0.25
Options: HFC, FM, Reconst-False, V-cycles @ End, No Fixed Vertices

Recursive Partitioning... --------------------------------------------------

Bisecting a hgraph of size [vertices=167276, hedges=4718221, balance=0.50]

(Windows terminates the program at this point)


University of South Carolina

RE: Diansheng, This is probably


This is probably due to out of memory. Can you run it on a Linux box to see if you get an error message to that regard.


RE: Thanks. Another question ...


Thanks for the reply. I reduced the graph to a Delaunay Triangulation (DT). The data points are geographic locations. So, a DT is a spatially contiguous mesh graph over the geographic space. shmetis and khmetis all worked fine except that I later found out a problem in the result (which is a major problem for my application). Is it possible that a subgraph (one part of the partitioned graph) is not connected?

For example, I expect that the partitioning of the Delaunay Triangluation (DT) into 256 parts would give me 256 geographic regions, each of which is spatially contiguous. This is not the case in the result. Although most parts are spatially contiguous, I found out that there are several parts contain regions that are spatially far away. I don't know how this is possible because the DT only connects spatial neighbors.


RE: BTW, I plotted the degree

BTW, I plotted the degree distribution and it is a power-law curve. Probably this is the reason that hmetis does not work well.