On the External Validity of Average-Case Analyses of Graph Algorithms (Data, Docker, and Code)

Here you find supplemental material for our paper On the External Validity of Average-Case Analyses of Graph Algorithms. Code The source code and a description of how to use it can be found at github.com/thobl/external-validity. Additionally external-validity-main.zip contains a snapshot. Docker Image The easiest way to reproduce the experiments is to use the docker image ext_val.zip. Refer to github.com/thobl/external-validity for instructions how to use it. Input Data: Networks from Network Repository We use a set of 3006 networks from networkrepository.com [1]. Refer to our paper for more details on the data set. [1] Ryan A. Rossi and Nesreen K. Ahmed, The Network Data Repository with Interactive Graph Analytics and Visualization (AAAI 2015) Here we provide this data set in two formats. Use the first for reproducing our experiments. If you want to do your own experiments on the same networks, we recommend using the second. input_data.zip contains the original graph as edge list (one edge per line) with no guarantees on where node indices start (usually at 0 or 1) or whether they are consecutive. The graphs might consist of multiple connected components. edge_lists_real.zip contains the graphs reduced to their largest connected component. Node indices are consecutive starting at 0 and every edge is contained only for one direction. Output Data: Generated Networks The generated networks are provided as edge lists (one connected component, consecutive node indices starting at 0, every edge is contained only in one direction). They are grouped into different categories. For more details on the generated networks, refer to our paper. cl stands for Chung-Lu graphs er stands for Erdős-Rényi graphs deg_20 indicates that the average degree is 20, otherwise it is 10 girg stands for geometric inhomogeneous random graphs girg_square means that a square was used as ground space, otherwise a torus was used girg_deg_scaling contains girgs with various average degrees Output Data: Computation Results The raw data computed by our experiments is contained in output_data.zip. Additionally, there are three csv files summarizing all computed statistics for the networks. graph_stats.csv contains the stats for all graphs graph_stats_real.csv contains the same stats but only for the graphs from Network Repository graph_stats_gen.csv contains stats for the generated networks, including the parameters used to generate the