Poor Quality Partitioning on SNAP Converted Undirected Graphs

Hi there,

So I'm using METIS to partition undirected graphs. I'm using SNAP graphs, and if they are directed I convert them to undirected using SNAPPy, and then into METIS format using Networkit 3.4 which produces correct graphs that pass graphchk.

I am however obtaining poor quality partitioning for these graphs, where most vertices in each partition don't even share a single edge with the other vertices in the partition. What is interesting is that when I convert the SNAP graphs to a directed METIS format (which gives me a large number of missing edges using graphchk), I am able to obtain a very good quality partitioning where I can get METIS to work without segfaulting for certain k.

Is there a way to avoid segmentation faults and null pointers for missing edges in METIS, so that I can continue to obtain good quality partitioning for directed graphs?

An example of these results is for the amazon0601 SNAP graph (http://snap.stanford.edu/data/amazon0601.html), when I convert to METIS format using Networkit 3.4 (such that it includes (u,v) when there exists (v,u)) then I obtain a poor quality partitioning with a high edge cut. However when I use my own conversion mechanism (http://pastebin.com/e1Q94N0n - which for each (u,v) in the SNAP edge list, it adds v to line u in the METIS file), I obtain a good quality partitioning (it works for k = 129, 256, 514, 1024 - after some random guessing).

Thanks,
Phil