# 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

- Login to post comments