# Guidelines for Experimental Algorithmics:
## 4 Guidelines for the Experimental Design
### Scale of Experiments  
Clearly, we cannot test all possible instances, even if they are small [33]. On the other hand, we want to draw significant conclusions about our new algorithm (and here not about a particular data set). This means that our experimental results should justify the later conclusions and allow to clearly distinguish between hypotheses. While Section 4.2 discusses _which_ instances to select, we proceed with the question _\"how many?\"_. In addition, if the results are affected by randomness, how many repeated runs should we make for each? Too few instances may be insufficient to support a conclusion. Plots then look sparse, hypothesis tests (Section 7.3.1) are inconclusive and inferred parameters are highly uncertain, which is reflected in unusably wide confidence and credible intervals (Sections 7.3.2 and 7.4). More instances are always better, but as a very rough rule of thumb reflecting community custom, we recommend at least 12-15 real-world instances for an experimental paper. When using synthetically generated graphs, use different generators and varying parameters to avoid a set of overly similar instances. If you want to support specific conclusions about algorithmic behavior within a subclass of instances, make sure to have that many instances _in that subclass_. Yet, the noisier the measurements and the stronger the differences of output between instances, the more experiments are needed for a meaningful (statistical) analysis. More formally, the uncertainty of many test statistics and inferred parameters (Most importantly the t-statistic used in confidence intervals and t-tests. In Bayesian statistics, the marginal posterior distribution of a parameter with a Gaussian likelihood also follows a t-distribution, at least when using a conjugate prior [34].) scales with \(\sqrt{\frac{\beta^{2}}{n}}\), where \(n\) is the number of \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Network Name** & \# of Nodes & \# of Edges & Diameter & Class \\ \hline moreno\_blogs & 1 224 & 16 715 & 8 & Hyperlink \\ petster-hamster & 2 426 & 16 631 & 10 & Social \\ ego-facebook & 2 888 & 2 981 & 9 & Social \\ openflights & 3 425 & 19 256 & 13 & Infrastructure \\ opsahl-powergrid & 4 941 & 6 594 & 46 & Infrastructure \\ p2p-Gnutella08 & 6 301 & 20 777 & 9 & Peer-to-peer \\ advogato & 6 539 & 39 285 & 9 & Social \\ wiki-Vote & 7 115 & 100 762 & 7 & Social \\ p2p-Gnutella05 & 8 846 & 31 839 & 9 & Peer-to-peer \\ p2p-Gnutella04 & 10 876 & 39 994 & 10 & Peer-to-peer \\ foldoc & 13 356 & 91 471 & 8 & Hyperlink \\ twin & 14 274 & 20 573 & 25 & Intl. Relations \\ cfinder-google & 15 763 & 148 585 & 7 & Hyperlink \\ ca-AstroPh & 18 771 & 198 050 & 14 & Coauthorship \\ ca-cit-HepTh & 22 908 & 2 444 798 & 9 & Coauthorship \\ subelj\_cora & 23 166 & 89 157 & 20 & Citation \\ ego-twitter & 23 370 & 32 831 & 15 & Social \\ ego-gpilus & 23 628 & 39 194 & 8 & Social \\ p2p-Gnutella24 & 26 518 & 65 369 & 11 & Peer-to-peer \\ ca-cit-HepPh & 28 093 & 3148 447 & 9 & Citation \\ cit-HepPh & 34 546 & 420 877 & 14 & Citation \\ facebook-wosn-wall & 46 952 & 183 412 & 18 & Social \\ edit-frwikibooks & 47 905 & 139 141 & 8 & Authorship \\ dblp-cite & 49 789 & 49 759 & 2 & Citation \\ loc-brightkite\_edges & 58 228 & 214 078 & 18 & Social \\ edit-frwikinews & 59 546 & 157 970 & 7 & Authorship \\ dimmseq-BAY & 321 270 & 397 415 & 837 & Road \\ dimmseq9-COL & 435 666 & 521 200 & 1 255 & Road \\ roadNet-PA & 1 088 092 & 1 541 898 & 794 & Road \\ roadNet-TX & 1 379 917 & 1 921 660 & 1 064 & Road \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Graphs (taken from KONECT) for our evaluation of the betweenness approximation algorithms. samples and \(s^{2}\) is the sample variance. Generally speaking, if we want a result that is twice as precise, we need to quadruple the number of measurements. The same applies for the number of repetitions for each instance. When plotting results affected by randomness, it is often recommended to average over the results of multiple runs.