Each graph in this benchmark represents a star-like structure of diﬀerent graphs S0 , . . . , St. Graphs S1 , . . . , St are weakly connected to the center S0 by random edges. The total number of edges between each Si and S0 was less than 3% out of the total number of edges in Si . The graphs are mixtures of the following structures: social networks, ﬁnite-element graphs, VLSI chips, peer-to-peer networks, and matrices from optimization solvers.
More info can be found in the paper I. Safro, P. Sanders, C. Schulz: Advanced Coarsening Schemes for Graph Partitioning, SEA 2012.
Communicated by Christian Schulz, uploaded on March 30, 2012.
The 15 compressed graph files (bzip2) are all in a subdirectory called archive/data/star-mixtures. They can be downloaded from there with a tool like wget. Alternatively, you can download a tar file of all these graphs (16 MB).