Graph500 Generation
I used this adaption of the standard Graph500 Kronecker generator to synthesize the graph kron_18_e4 discussed below with 2^18 (262144) nodes and approximately 1.31 x 10^8 edges. The average degree of this graph is approximately 10^3 and consumes 1.7 GB of space. I avoided using the Graph500 reference implementation directly because of the edge packing optimization of the edge-list file.
For comparison, I also determined the degree distribution of our current generator using a graph with a factor ten fewer edges called erdos_renyi_18_e3.
Note that I chose the above parameters according to David's minimum requirements for an ideal graph to run our algorithm on, but I have also generated much larger graphs (including one with 2^19 nodes and with approx. avg. degree of 10^4) which can be found on the new lab machine. This larger graph consumes 35 GB of space in edge-list format, and was the largest I could generate within the 64 GB of memory of the new lab machine.
The diameter of the graph was computed using teexgraph to be 5. This is line with the "small-world phenomena" and low diameters observed in real world graphs
With a best-fit curve, the graph clearly follows the power law distribution. The comb-like distribution observed below is an interesting limitation of the way that R-MAT-based generators recursively distribute edges. More details of the issue and a solution can be found here. This article also links to an implementation of the proposed fix to Kronecker generation called Smooth Kronecker generation. The only reason why I didn't opt for Smooth Kronecker generation was because it is less standard than the classical Kronecker generation of Graph500.
