2f:T44e,TODO: - ~~exclude papers marked "EXCLUDE"~~ - ~~Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm appears twice in the literature~~ - ~~benchmark_datasets has "first character detmines node or edge (n/e)" (spelling error)~~ - ~~there are two empty rows in literature, or now five?~~ - ~~benchmark_datasets has two empty rows~~ Questions to answer: - Has the type of benchmark dataset used changed through the years? - Do papers include supplemental material more frequently compared to previous years? - Include a navigable analysis of the contents of the Datasets - Include a table with dataset -> paper, split by graph feature - ~~Classification of the datasets~~ - ~~Which venues were these papers published in?~~ - How these datasets evolved (child collections). - Count of available datasets, recreated datasets, non-copyable datasets, and lost data - year dataset appeared in origin paper vs. when it was used Points of discussion: - ~~random generation: the Barabasi method and the Erdos-Renyi one~~ - ~~what kind of details about a graph should you take into account?~~30:T658,# Abstract ## Introduction Computational evaluations are crucial for standardized and objective evaluation of graph layout algorithms. Standard benchmark datasets facilitate comparison with prior work, and reliable access to datasets is fundamental for replicability. However, there is no comprehensive repository of benchmark datasets for Graph Drawing, and many datasets have been lost. ## Data collection We collected 196 papers from Graph Drawing, IEEE venues, and Eurographics venues that include computational evaluations of graph layout algorithms. We searched for the datasets used. ## Data analysis We archived datasets we found and re-created ones that were lost but had sufficient replication instructions. We classified graphs by their features and statistics. We also found text and images from papers using those graphs. ## Implementation We implemented graph creation, data analysis, and website code. ## Materials We provide a [Graph Benchmark Datasets](https://visdunneright.github.io/gd_benchmark_sets/) website; a [repository](https://github.com/visdunneright/gd_benchmark_sets/) with code for the website and metadata on the benchmark datasets; a [long-term archive](https://osf.io/j7ucv/) of this repository and the benchmark datasets. ## Conclusion We provide a resource for the Graph Drawing and visualization communities to use to find datasets for computational evaluations of graph layout algorithms. Our organization by features and statistics supports rapid identification of relevant graphs. We have re-created and archived graphs used in research for their long-term preservation.31:Tf32,# Introduction Benchmarking is a crucial aspect of computer science, as it allows researchers, developers, and engineers to compare the performance of various systems, algorithms, or hardware. A benchmark is a standardized test or set of tests used to measure and compare the performance of hardware, software, or systems under specific conditions. Benchmarking aims to provide objective and consistent metrics that allow for fair comparisons and informed decision-making. Benchmarks are widely used in various fields, including computer hardware evaluation, software optimization, and system performance analysis. In all these fields, benchmarking provides a standardized and objective way to compare and assess the performance of different systems, algorithms, or software implementations. It aids in making informed decisions about which solution best suits a specific use case or requirement. The same is true for graph drawing, particularly for studying the performance and results of graph layout algorithms **IMPORTANT: TODO cite CGF**. Benchmark datasets can provide a standardized set of graphs with known properties and characteristics. These graphs can vary in size, density, connectivity, and structure. Researchers can objectively compare their performance or the quality of their results by applying various graph layout algorithms to the same benchmark dataset. In our own work, we have faced challenges in determining which benchmark datasets to use for evaluating the layout algorithms we developed. This led us to build a collection of benchmark datasets used in previous graph layout algorithm papers and a [Graph Benchmark Datasets](https://visdunneright.github.io/gd_benchmark_sets/) website for perusing the collection. We collected 196 papers from Graph Drawing, IEEE venues, and Eurographics venues that include computational evaluations of graph layout algorithms. We then searched for the datasets used for the benchmarks. We collected the data we could find and had permission to archive and re-created datasets that were lost but had sufficient replication instructions. We classified graphs by their features and statistics. We also found text and images from papers using those graphs. This paper aims to present this graph drawing benchmark sets resource to the Graph Drawing and visualization communities so that other authors may benefit from our archiving and organization efforts. We hope this resource will encourage the discoverability of these datasets and the ease of running benchmarks for graph layout algorithms. Moreover, as reliable access to datasets is fundamental for replicability, we aim to preserve these datasets in perpetuity. Beyond collecting available datasets and re-creating lost ones, we archived all our materials [on OSF](https://osf.io/j7ucv/) for long-term availability. This included saving each graph in multiple common file formats to avoid translation issues for individual authors. We believe our work will lead to more reproducible and replicable Graph Drawing research by providing a long-term and open archive of the data we use in our computational evaluations. Specifically, we contribute: - A collection of benchmark datasets used for graph layout algorithm evaluations, including: - Re-creating lost datasets based on paper descriptions and a list of unavailable data, - A classification of these datasets by graph features and statistics to aid in identifying appropriate evaluation candidates, - Exemplar text and images from papers that use these datasets, - A website for perusing this collection, and - A long-term archive of our metadata and the collection to aid in reproducibility and replicability of evaluations. Please see [Research Material Statements](#cell-501) below for our supplemental materials, including links to the website, code and data, OSF archive, and Notion database. 32:T945,The information we collected is a by-product of a larger systematic review we conducted related to graph layout algorithms, which included 196 papers The following figure shows the original data collection process (from **_TODO CITE CGF PAPER_**): ![sources3.svg](${await FileAttachment("sources3(1).svg").url()}) **_TODO (CD 2024-03-08) How to add captions?_** The core of our data collection was the last seven years of Graph Drawing proceedings (264 papers in total), filtering out papers without computational evaluations. We further expanded our graph layout algorithm papers collection by searching IEEE Xplore and Wiley digital libraries to include papers from TVCG and CGF. Then, we checked all the citations in the papers we collected from Graph Drawing, and added to our collection all the papers that were cited more than 4 times in the last 6 years of graph drawing --- to make sure we included algorithm papers that were important, but not published at GD, on IEEE Xplore or on the Wiley digital library. For each paper, we collected which features were handled by the graph layout algorithm presented, and what dataset was used in the evaluation. When collecting features, we always prioritized the authors' own wording and description of the features. The tagging of the papers was done by two people at the same time, over two different passes for sanity-checking purposes. Following this process, we tried to track down the datasets used in computational evaluations: (1) we first looked for official or linked supplemental material, (2) we next Googled the dataset or paper name, (3) finally, we emailed the authors. When in doubt about the artifact replication policy, we asked the owners or authors by email. In cases where it was explicitly mentioned that approval should be received before redistribution, we did not redistribute the datasets. However, if we received approval or did not receive an answer and found no explicit policy preventing redistirbution, we collected and stored the dataset to preserve it for future researchers. If any dataset owner or author discovers their own work in our collection and would like it removed, we kindly request that they contact us (see [Authorship](cell-508) below), and we will promptly remove it. Furthermore, we want to emphasize that we do not assert any ownership rights over the datasets listed.33:T427,{ let d = [] let allbenchmarkdatasets = [...new Set(literature.map(l => l["Dataset tag relations"].split(",").map(a => a.split("(")[0].trim())).flat())].filter(a => a != "") allbenchmarkdatasets = allbenchmarkdatasets.filter(b => !b.includes("Custom")) allbenchmarkdatasets = allbenchmarkdatasets.slice(0, 20) for (let dataset of allbenchmarkdatasets){ let literature_entries_with_this_dataset = literature.filter(l => l["Dataset tag relations"].includes(dataset)) d.push({"dataset": dataset, "count": literature_entries_with_this_dataset.length}) } return Plot.plot({ color: { // legend: true, // type: "categorical", // domain: d3.range(10).map((d, i) => `Category ${i + 1}`), range: ["steelblue"], // scheme: "Tableau10" // use the "accent" scheme }, y: { // tickFormat: "s" }, marks: [ Plot.barX(d, {x: "count", y: "dataset", fill: "dataset", inset: 2, sort: {y: "x", reverse: true}}), Plot.axisY({label: null, lineWidth: 12, marginLeft: 150}), ] }) }34:T906,{ let chosen_collection_type = "Uniform Benchmark" let collection_type = benchmark_datasets.map(a => a["Type of Collection"]).filter(c => c == chosen_collection_type); let y_distance = 20; let svgwidth = 1000; const svg = d3.create('svg') .attr('width', svgwidth) .attr('height', y_distance * collection_type.length + 60); svg.append("text") .attr("x", svgwidth/2) .attr("y", 20) .attr("text-anchor", "middle") .style("font-weight", "bold") .text("What graph features do these datasets contain?") svg.append("text") .attr("x", 300) .attr("y", 45) .style("text-anchor", "end") .style("font-size", "small") .style("fill", "#aaa") .text("Name") svg.append("text") .attr("x", 350) .attr("y", 45) .style("text-anchor", "start") .style("font-size", "small") .style("fill", "#aaa") .text("Features") for (let c of [... new Set(collection_type)]){ if (c == "Skip" || c == "Missed It") continue; let instances = benchmark_datasets.filter(a => a["Type of Collection"] == c); for (let i in instances){ svg.append("text") .attr("x", 300) .attr("y", 65 + i * y_distance) .style("text-anchor", "end") .style("font-size", "small") .text(instances[i]["Name"] + " ") let features = instances[i]["graph features handled"].split(",").map(a => a.trim()) let cur_x = 0; for (let f of features){ let t = svg.append("text") .attr("x", 340 + cur_x) .attr("y", 65 + i * y_distance) .style("text-anchor", "start") .style("font-size", "small") .style("fill", dict_of_graph_features_to_colors[f]) .text(f) // let t = svg.append("div") // .attr("class", "rounded-pill badge") // .style("margin", "2px") // .style("background-color",dict_of_graph_features_to_colors[f]) // .text(f) cur_x += f.length * 8.5; } } // tagrow.append("div") // .attr("class", "rounded-pill badge") // .style("margin", "2px") // .style("background-color", graph_feature_tags_colors[graph_feature_tags.indexOf(graph_feature)%graph_feature_tags_colors.length]) // .text(graph_feature) } return svg.node(); }35:Td28,{ let all_features = featureSelected; console.log(all_features) let y_distance = 20; let svgwidth = 1000; const selectBenchmark = benchmark_datasets.filter(c => { const featureList = c['Graph features in papers'].split(",") let found = false; all_features.forEach((feature) =>{ if(featureList.includes(feature)){ found = true; return true; } }); return found; }); const svg = d3.create('svg') .attr('width', svgwidth) .attr('height', y_distance * selectBenchmark.length + 60); svg.append("text") .attr("x", svgwidth/2) .attr("y", 20) .attr("text-anchor", "middle") .style("font-weight", "bold") .text("Where can I find a dataset with this feature?") svg.append("text") .attr("x", 300) .attr("y", 45) .style("text-anchor", "end") .style("font-size", "small") .style("fill", "#aaa") .text("Name") svg.append("text") .attr("x", 340) .attr("y", 45) .style("text-anchor", "middle") .style("font-size", "small") .style("fill", "#aaa") .text("#Graphs") svg.append("text") .attr("x", 420) .attr("y", 45) .style("text-anchor", "middle") .style("font-size", "small") .style("fill", "#aaa") .text("Original link") svg.append("text") .attr("x", 470) .attr("y", 45) .style("text-anchor", "start") .style("font-size", "small") .style("fill", "#aaa") .text("Origin paper / website") for (let i in selectBenchmark){ svg.append("text") .attr("x", 300) .attr("y", 65 + i * y_distance) .style("text-anchor", "end") .style("font-size", "small") .text(selectBenchmark[i]["Name"] + " ") svg.append("text") .attr("x", 340) .attr("y", 65 + i * y_distance) .style("text-anchor", "middle") .style("font-size", "small") .text(selectBenchmark[i]["Number of Graphs"] + " ") if (selectBenchmark[i]["Originally found at"] != "" && selectBenchmark[i]["Originally found at"] != undefined){ svg.append("a") .attr("href", selectBenchmark[i]["Originally found at"]) .attr("transform", "translate(410, " + (y_distance * i + 65) + ")") .attr("target", "_blank") .append("text") .text("[link]") .style("fill", "#88d") .style("font-size", "small") const paper = (paper_source.find(a => a.Name == selectBenchmark[i]["Origin paper plaintext"]) || {}) let link = "" if('bib' in paper){ const res = extractDOIUrl(paper.bib) if(res) link = res; } if(link != ""){ svg.append("a") .attr("href", link) .attr("transform", "translate(470, " + (y_distance * i + 65) + ")") .attr("target", "_blank") .append("text") .text(selectBenchmark[i]["Origin paper plaintext"].split("(")[0]) .style("fill", "#1565c0") .style("font-size", "small") } else { svg.append("text") .attr("transform", "translate(470, " + (y_distance * i + 65) + ")") .text(selectBenchmark[i]["Origin paper plaintext"].split("(")[0]) .style("fill", "#616161") .style("font-size", "small") } } } return svg.node(); }36:T687,{ let dom = d3.select("#Aggregate-Collection"); dom.selectAll("*").remove() let chosen_collection_type = "Aggregate collection" let collection_type = benchmark_datasets.map(a => a["Type of Collection"]).filter(c => c == chosen_collection_type); dom.append("text") .attr("text-anchor", "middle") .style("font-weight", "bold") .text("List of datasets tagged as " + chosen_collection_type) const div = dom.append("div").attr("class","grid") for (let c of [... new Set(collection_type)]){ if (c == "Skip" || c == "Missed It") continue; let instances = benchmark_datasets.filter(a => a["Type of Collection"] == c); if (c.includes("No report")) c = "Established Network Repository"; for (let i in instances){ div.append("p") .style("text-anchor", "end") .attr("class", "item-left") .style("font-size", "small") .text(instances[i]["Name"] + " ") const related = instances[i]['Related to Literature - Algorithm (Dataset tag relations) 1'] const relatedList = related.split(",") const content = div.append("div") .attr("class", "item-right") let res = [] relatedList.forEach((item)=>{ const name = item.split("(http")[0] const paper = (literature.find(a => name.includes(a.Name)) || {}) if(paper.DOI){ content.append("a") .attr('href',paper.DOI) .style("font-size", "small") .attr("class","paper-names").text(name) } else { content.append("span").style("font-size", "small").attr("class","paper-names").text(name) } }); } } }37:T551,{ let chosen_collection_type = "Subset of other collection" let collection_type = benchmark_datasets.map(a => a["Type of Collection"]).filter(c => c == chosen_collection_type); let y_distance = 20; let svgwidth = 1000; const svg = d3.create('svg') .attr('width', svgwidth) .attr('height', y_distance * collection_type.length + 40); svg.append("text") .attr("x", svgwidth/2) .attr("y", 20) .attr("text-anchor", "middle") .style("font-weight", "bold") .text("List of datasets tagged as " + chosen_collection_type + " and their sources") for (let c of [... new Set(collection_type)]){ if (c == "Skip" || c == "Missed It") continue; let instances = benchmark_datasets.filter(a => a["Type of Collection"] == c); if (c.includes("No report")) c = "Established Network Repository"; for (let i in instances){ svg.append("text") .attr("x", 300) .attr("y", 45 + i * y_distance) .style("text-anchor", "end") .text(instances[i]["Name"] + " ") svg.append("a") .attr("href", "https://www.google.com") .attr("transform", "translate(310, " + (y_distance * i + 45) + ")") .attr("target", "_blank") .append("text") .text(instances[i]["Origin Paper"].split("(")[0]) .style("fill", "#aaa") } } return svg.node(); }38:T432,### Custom-made datasets In the data we collected, we also found several instances of custom-made datasets. We consider custom-made datasets either edits to pre-existing datasets, where the authors found it necessary to either split or modify the dataset in a particular way, or datasets completely made up from scratch using random generators or custom-made code. This can happen in cases where the authors of a paper needed a dataset containing particular characteristics which was not easy to find in the wild, so a new dataset was crafted. For instance, consider the case where the authors of a paper develop an algorithm that works on hypergraphs. They want to test that the algorithm works, and test its performance on hypergraphs of various sizes, but datasets containing hypergraphs are difficult to find. For this reason, the authors craft one dataset synthetically, or take a pre-existing dataset and edit it so that it now contains hyperedges. We split custom-made datasets in three categories, with their occurrences in the corpus of papers illustrated below:39:T47f,**Replicable** datasets indicate cases where the authors have given enough information so that the experiment can be replicated exactly as it was run by the authors of a paper, or closely enough that the results obtained reflect the published ones very closely. This includes cases where either the authors published the entire dataset they used, they published the code they used to generate the dataset, or include an exact description of the steps they took to generate it. **Reproducible** datasets are cases where the authors described the steps they took to generate and/or edit their datasets, but not in-depth enough so that the exact same graphs can be reproduced, and did not redistribute it. Results can still be reproduces somewhat closely if the authors took care to report enough information about their graphs. For **non-replicable** datasets, we indicate cases where the authors did not distribute their datasets and did not include enough information in the paper so that their results could be replicated. This information is closely tied to the distribution of supplemental material in papers, that is shown in the chart below: 3a:Tbda,{ let d = [] let allliteratureyears = [...new Set(literature.map(l => parseInt(l["Year"])))].sort().filter(y => y > 2000) // let allbenchmarkdatasets = [...new Set(literature.map(l => l["Dataset tag relations"].split(",").map(a => a.split("(")[0].trim())).flat())].filter(a => a != "") let allbenchmarkdatasets = [...new Set(benchmark_datasets.filter(a => a["Type of Collection"] != "Established Network Repo (No report)").map(l => l["Name"]))] // allbenchmarkdatasets = allbenchmarkdatasets.filter(b => !b.includes("Custom")) // allbenchmarkdatasets = allbenchmarkdatasets.slice(0, 20) console.log(allbenchmarkdatasets, allliteratureyears) let data_counts = [] for (let dataset of allbenchmarkdatasets){ let literature_entries_with_this_dataset = literature.filter(l => l["Dataset tag clean"].includes(dataset)) let literature_years = [...new Set(literature_entries_with_this_dataset.map(l => l.Year))] var ct = 0 for (let year of allliteratureyears){ let count = literature_entries_with_this_dataset.filter(l => l.Year == year).length ct += count if (year % 2 == 0){ d.push({dataset: dataset, year: parseInt(year), count: count}) } else { if (d.find(a => a.year == year - 1)) { d.find(a => a.year == year - 1).count += count } else { d.push({dataset: dataset, year: parseInt(year) - 1, count: count}) } } } data_counts.push({name: dataset, count: ct}) } data_counts = data_counts.sort((a, b) => a.count < b.count) // console.log(data_counts) let included_datasets = data_counts.splice(0, 10).map(a => a.name) let other_counts = {} // for (let other_dataset of data_counts){ // let all_points = d.filter(a => a.dataset == other_dataset.name) // for (let dpt of all_points){ // if (dpt.year in other_counts){ // other_counts[dpt.year] += dpt.count // } else { // other_counts[dpt.year] = dpt.count // } // } // } console.log(other_counts) d = d.filter(a => included_datasets.includes(a.dataset)) for (const [key, value] of Object.entries(other_counts)) { d.push({dataset: "Other", year: parseInt(key), count: value}) } let year_sums = {} for (let year of allliteratureyears){ year_sums[year] = d.filter(l => l.year == year).reduce((acc, cv) => { return acc + cv.count }, 0) } console.log(year_sums) d = d.sort((a, b) => a.year > b.year) // for (let dv of d){ // dv.count = dv.count / year_sums[dv.year] // } console.log(included_datasets) return Plot.plot({ height: 300, width: "1500", color: { legend: true, type: "categorical", // domain: d3.range(10).map((d) => `Category ${d + 1}`), scheme: "tableau10" // use the "accent" scheme }, y: { // tickFormat: "s" }, marks: [ Plot.areaY(d, {x: "year", y: "count", fill: "dataset"}), // Plot.lineY(d, {x: "year", y: "count"}), Plot.ruleY([0]) ] }) }3b:T5b6,html``3c:T13c8,function add_entry_row(named_list_dom, entry, paper_data, origin_paper_data, pagesContent, notionFolders){ let infocontainer = named_list_dom.append("div") .attr("class", "container") .attr("id", "inforow_" + name_cleanup(entry["Name"])) .style("padding", "2%") let inforow = infocontainer.append("div") .append("div") .attr("class", "card card-body") .append("div") .attr("class", "col small-text") add_simple_field(entry, "Originally found at", inforow) //add buttons add_download_field(entry, inforow); add_simple_field(entry, "Note", inforow) add_simple_field(entry, "Number of Files", inforow) add_simple_field(entry, "Size", inforow) add_simple_field(entry, "Origin Notes", inforow) inforow.append("div").html("Origin paper: ") for (let e of entry["Origin paper plaintext"].split(",")){ e = e.trim(); if (e == "") continue; let origindoi = (paper_data.find(a => a.Name == e) || {}).DOI let cited_paper = origin_paper_data.find(o => o.Name == e) let cite_index = origin_paper_data.indexOf(cited_paper) if (origindoi != undefined && origindoi != ""){ inforow.append("div").html('' + "[link]" + ' ' + "[citation]" + ' ' + e) } else inforow.append("div").html(e) } inforow.append("div").html("Usage examples: ") for (let i in entry["Related to Literature - Algorithm (Dataset tag relations) 1"].split(",")){ let e = entry["Related to Literature - Algorithm (Dataset tag relations) 1"].split(",")[i].split("(")[0].trim() let entryrow = inforow.append("div").attr("class", "row") if (e != "") { let doi = (paper_data.find(a => a.Name == e) || {}).DOI let link; if (doi != undefined && doi != "") link = '[link]' else link = "" entryrow.append("div") .attr("class", "col-8") .html(link + " " + urlify(e)) let tagrow = entryrow.append("div").attr("class", "col-4") if (paper_data.find(a => a.Name == e)){ let feature_collection = (paper_data.find(a => a.Name == e) || {})["Graph feature"].split(",") for (let graph_feature of feature_collection){ graph_feature = graph_feature.trim().toLowerCase() tagrow.append("div") .attr("class", "rounded-pill badge") .style("margin", "2px") .style("background-color", graph_feature_tags_colors[graph_feature_tags.indexOf(graph_feature)%graph_feature_tags_colors.length]) .text(graph_feature) } } } } inforow.append("br") // DRAW REST OF THE PAGE: uncomment when moving over let otherinfo = "" try{ // TODO:Sara replace this for quarterly // let otherinfo = await fetch("notion_data/Benchmark datasets 64e0439269f9497799025562a4087ce1/" + entry["Name"].replace(".", "") + " " + entry["Page id"] + ".md") const location = entry["Name"].replace(".", "") + " " + entry["Page id"] + ".md"; let otherinfo = notionFolders[location]; // otherinfo = await otherinfo.text() //TODO:Sara you need to get the text var converter = new showdown.Converter(); otherinfo = getTextAfterBody(otherinfo); for (let line of otherinfo.split("\n")){ if (line[0] == "!") { // get everything after the first (, concat the rest let img = line.split("(") // concat all the entries after the first for (let i = 2; i < img.length; i++){ img[1] += "(" + img[i] } // remove the last ) img[1] = img[1].substring(0, img[1].length - 1) img = img[1] inforow.append("div") .style("text-align", "center") .append("img") .attr("src", "notion_data/Benchmark datasets 64e0439269f9497799025562a4087ce1/" + img) .attr("width", "80%") } else if (line.includes("STOP RENDERING")){ break; } else inforow.append("div").html(converter.makeHtml(line)) } } catch (e){ console.log(e) } }3d:T786,We discussed above that in a few cases, authors have generated their own datasets to test their algorithms. We call these generated datasets _synthetic_ or _custom_, as opposed to datasets found in the wild. Generating a synthetic dataset can be essential for several reasons, particularly in the context of algorithm development and validation: - **Privacy and Publication Constraints:** Imagine you've created an innovative algorithm using a dataset that, due to privacy concerns, cannot be shared publicly. To validate and share your work without compromising data confidentiality, creating a synthetic dataset that mirrors the essential features of the original data allows you to showcase your algorithm's effectiveness while adhering to privacy restrictions. - **Benchmarking and Comparative Analysis:** Suppose you have access to a single dataset that can be shared and wish to prove your algorithm's robustness across various scenarios. Generating synthetic datasets with _comparable_ characteristics provides a controlled environment to conduct benchmark studies. This approach enables scientists to demonstrate that your algorithm performs consistently well across datasets with analogous features, thereby reinforcing its applicability and reliability. - **Addressing Data Availability Issues:** In certain situations, you might design an algorithm to process graphs with specific attributes only to discover the absence of publicly available datasets showcasing these features. Synthetic datasets become invaluable here, allowing you to create tailored data that incorporates the necessary characteristics. This approach not only facilitates the testing of your algorithm in a relevant context but also helps in illustrating its potential in hypothetical yet plausible scenarios. We use the word _synthetic_ too in cases where the dataset has been altered, sliced, or other modifications have been applied to it.3e:T68e,The following is a practical example of a case where you would need to edit a network: Imagine you are building a visualization to deal with the entirety of the [Enron Corpus](https://en.wikipedia.org/wiki/Enron_Corpus) dataset , which has hundreds of thousands of nodes and edges. Because of its size, you decide to _slice up_ the large dataset in many smaller files, so you can run tests. This particular dataset, in addition to being a challenging problem because of its size, also has an interesting distribution of connection densities: some nodes are extremely well connected, while others are much less connected. Indeed, the dataset is comprised of a collection of emails sent by Enron executives - between themselves or between other employees of the company. Because of how the dataset is constructed - where only the emails from the executives are taken into account - it has a distinctive skew in the connectedness of the data: 158 nodes are extremely well connected, while the rest of the nodes are much less connected. Because of this, there's uncountable mistakes that can be done through slicing this graph: for instance, slicing it so that the subset includes a less dense section of the entire graph will fail to provide a representative section. While the creation of a synthetic dataset is a perfectly viable way to produce a benchmark set, in addition to replicability criteria (as discussed above), we also have to pay particular attention to a number of statistics related to the structure of graphs --- both when generating new datasets, and when slicing up existing datasets to reduce their size, or to create more graphs from a single, larger graph.3f:T5f8,The list of features to take into account to claim that a synthetic graph is _comparable_ to another one would be long, and perhaps out of the scope of this publication. These are just a few examples of what could be relevant: - **Size (nodes, edges):** The total number of nodes and edges in the graph, indicating its overall scale. - **Diameter:** The longest shortest path between any two nodes, showing the graph's maximum extent. - **Density:** The ratio of existing edges to possible edges, reflecting how closely knit the graph is. - **Motifs:** Recurring, significant subgraphs; identify which motifs occur more or less frequently than expected. - **Connectedness:** Evaluates both the number and sizes of graph components, along with detailed analysis per component. - **Centrality Measures (betweenness, closeness, degree):** Quantify the importance of nodes based on their position and connections within the graph. - **Special Cases:** - **Layers:** Characteristics like number of layers, nodes per layer, and inter-layer connections. - **Disjoint Groups:** The count and size distribution of separate clusters, plus an analysis of each group's properties. - **Overlapping Sets:** Number and size distribution of intersecting groups, along with detailed features. - **Additional Node/Edge Data:** Information such as timestamps, attributes, or weights that add context to nodes/edges. - **Dynamic:** Describes changes in the graph over time, including the nature and frequency of node/edge modifications. 40:T56b,The generation of random graphs that accurately mimic specific features presents a complex challenge, that has been explored abundantly in the past, but has found no universal solution yet. Two examples of popular models used to generate synthetic datasets are the Erdős-Rényi (ER) and the Barabási-Albert (BA) models, each one with their distinct focus and limitations: The ER model excels in creating graphs with uniform edge distribution, ideal for testing an algorithm's ability to evenly space nodes and reduce edge crossings. However, it falls short in replicating the complex, non-uniform connections seen in real-world networks, limiting its applicability to scenarios requiring simplicity and randomness. Conversely, the BA model produces scale-free networks with a few highly connected nodes, reflecting the hierarchical structure of many natural and human-made systems. It challenges layout algorithms to effectively display these hubs without cluttering. The limitation here is its focus on growth and preferential attachment, which might not suit all types of networks, particularly those without clear hub structures. As there is no universal solution for random graph generation, _our recommendation_ is to try as much as possible to pay attention to research replicability criteria, such as redistributing the generated dataset as supplemental material in the paper.41:T428,We presented a comprehensive benchmark dataset collection for graph layout algorithms. Compiling, organizing, and making a wide array of datasets with diverse characteristics accessible not only facilitates rigorous and fair comparisons of algorithmic performance but also addresses critical issues of replicability and reproducibility in research. The Graph Benchmark Datasets website, along with the efforts for long-term archival, ensures these valuable resources remain available to the community. Web aim to help both current and future researchers to benefit from a rich repository of data, standardizing the evaluation process for graph layout algorithms, fostering innovation and development within the field and contributes to the advancement of graph drawing and visualization research. With this work, we hope to underscore the importance of accessible, well-documented benchmark datasets in driving scientific progress and highlights our commitment to enhancing the integrity and reliability of computational evaluations in the Graph Drawing community.42:T568,# Research Material Statements The supplemental material for this publication includes: * The [Graph Benchmark Datasets](https://visdunneright.github.io/gd_benchmark_sets/) website, hosted on GitHub Pages. * Code for the website, metadata on the benchmark datasets, and data processing scripts are stored in the [gd_benchmark_sets](https://github.com/visdunneright/gd_benchmark_sets/) GitHub repository. **_TODO (CD 2024-03-08): clean up and add documentation for how to use. Esp. clean the `data` folder, `readme.md`, the random `.ipynb` files. Add `LICENCE` file specifying ideally Apache 2.0 for code, and info to `readme.md` specifying Apache 2.0 for code and CC BY 4.0 for data & metadata._** * This code and metadata, along with the benchmark datasets themselves in several common graph file formats, are archived for long-term availability in the [Benchmark datasets for graph drawing](https://osf.io/j7ucv/) project on OSF. **_TODO (CD 2024-03-08): add the website code + data. This can be done by creating a registration on OSF. I linked the GitHub repo as a data source on OSF, but the registration is what copies it to OSF as an archived snapshot._** * The original database used for metadata collection and storage is available on Notion as [Benchmark datasets](https://picorana.notion.site/64e0439269f9497799025562a4087ce1?v=271e88e50ca24ee0bfd1c99ffa25daf5&pvs=74). 43:T555,# Authorship * **Sara Di Bartolomeo** [![orcid_16x16@2.gif](${await FileAttachment("orcid_16x16@2.gif").url()}) https://orcid.org/0000-0001-9517-3526](https://orcid.org/0000-0001-9517-3526): Conceptualization, Data Collection & Categorization, Writing Original Draft + Review & Editing, Visualization, Validation. * **Eduardo Puerta** [![orcid_16x16@2.gif](${await FileAttachment("orcid_16x16@2.gif").url()}) https://orcid.org/0000-0003-4664-4365](https://orcid.org/0000-0003-4664-4365): Data Collection & Categorization, Writing Original Draft + Review & Editing, Validation. * **Connor Wilson** [![orcid_16x16@2.gif](${await FileAttachment("orcid_16x16@2.gif").url()}) https://orcid.org/0000-0002-6936-4078](https://orcid.org/0000-0002-6936-4078): Data Collection & Categorization, Writing Original Draft + Review & Editing, Validation. * **Tarik Crnovrsanin** [![orcid_16x16@2.gif](${await FileAttachment("orcid_16x16@2.gif").url()}) https://orcid.org/0000-0002-4397-5532](https://orcid.org/0000-0002-4397-5532): Data Collection & Categorization, Writing Original Draft + Review & Editing, Validation. * **Cody Dunne** [![orcid_16x16@2.gif](${await FileAttachment("orcid_16x16@2.gif").url()}) https://orcid.org/0000-0002-1609-9776](https://orcid.org/0000-0002-1609-9776): Supervision, Writing Original Draft + Review & Editing, Validation, Funding Acquisition.44:Tf4e,function make_dataset_name_and_title_list(chosen_collection_type, include_num_graphs){ let collection_type = benchmark_datasets.map(a => a["Type of Collection"]).filter(c => c == chosen_collection_type); let y_distance = 20; let svgwidth = 1000; let numgraphs_offset = 40; const svg = d3.create('svg') .attr('width', svgwidth) .attr('height', y_distance * collection_type.length + 60); svg.append("text") .attr("x", svgwidth/2) .attr("y", 20) .attr("text-anchor", "middle") .style("font-weight", "bold") .text("List of datasets tagged as " + chosen_collection_type + " and their sources") svg.append("text") .attr("x", 300) .attr("y", 45) .style("text-anchor", "end") .style("font-size", "small") .style("fill", "#aaa") .text("Name") if (include_num_graphs) { svg.append("text") .attr("x", 340) .attr("y", 45) .style("text-anchor", "middle") .style("font-size", "small") .style("fill", "#aaa") .text("#Graphs") } svg.append("text") .attr("x", 420 - (include_num_graphs ? 0 : numgraphs_offset)) .attr("y", 45) .style("text-anchor", "middle") .style("font-size", "small") .style("fill", "#aaa") .text("Original link") svg.append("text") .attr("x", 470 - (include_num_graphs ? 0 : numgraphs_offset)) .attr("y", 45) .style("text-anchor", "start") .style("font-size", "small") .style("fill", "#aaa") .text("Origin paper / website") for (let c of [... new Set(collection_type)]){ if (c == "Skip" || c == "Missed It") continue; let instances = benchmark_datasets.filter(a => a["Type of Collection"] == c); if (c.includes("No report")) c = "Established Network Repository"; for (let i in instances){ svg.append("text") .attr("x", 300) .attr("y", 65 + i * y_distance) .style("text-anchor", "end") .style("font-size", "small") .text(instances[i]["Name"] + " ") if (include_num_graphs){ svg.append("text") .attr("x", 340) .attr("y", 65 + i * y_distance) .style("text-anchor", "middle") .style("font-size", "small") .text(instances[i]["Number of Graphs"] + " ") } if (instances[i]["Originally found at"] != "" && instances[i]["Originally found at"] != undefined) { const xPosOff = (include_num_graphs ? 0 : numgraphs_offset); const yPos = (y_distance * i + 65); svg.append("a") .attr("href", instances[i]["Originally found at"]) .attr("transform", "translate("+ (410 - xPosOff) +", " + yPos + ")") .attr("target", "_blank") .append("text") .text("[link]") .style("fill", "#88d") .style("font-size", "small") const paper = (paper_source.find(a => a.Name == instances[i]["Origin paper plaintext"]) || {}) let link = "" if('bib' in paper){ const res = extractDOIUrl(paper.bib) if(res) link = res; } if(link != ""){ link = extractDOIUrl(paper.bib) svg.append("a") .attr("href", link) .attr("transform", "translate("+ (470 - xPosOff)+", " + yPos + ")") .attr("target", "_blank") .append("text") .text(instances[i]["Origin paper plaintext"].split("(")[0]) // .style("fill", "rgb(136, 136, 221)") .style("fill","#1565c0") .style("font-size", "small") } else { // What do we do here svg.append("text") .attr("transform", "translate("+ (470 - xPosOff)+", " + yPos + ")") .text(instances[i]["Origin paper plaintext"].split("(")[0]) .style("fill", "#616161") .style("font-size", "small") } } } } return svg.node(); }45:[{"id":"ff483090d4eda6d994e4148a273b21d0683d11387a6ef5842c8e9dff0d3e5df5f0bf2edea33f98d301c174e20b28948c037d40c8c05fdc02b1bfdf10a74002af","href":"https://static.observableusercontent.com/files/ff483090d4eda6d994e4148a273b21d0683d11387a6ef5842c8e9dff0d3e5df5f0bf2edea33f98d301c174e20b28948c037d40c8c05fdc02b1bfdf10a74002af","name":"Benchmark datasets 64e0439269f9497799025562a4087ce1_all.csv","type":"text/csv","lastModified":1714662435620.58,"size":141478},{"id":"083358f92d6ac44e68c10c196ae903f53db2a887e2dfa920338ad51e89e4b1d8f3cee3e451ffdfaeca62fbf1af66604f5b249fa56af52b045204e7d68dc25449","href":"https://static.observableusercontent.com/files/083358f92d6ac44e68c10c196ae903f53db2a887e2dfa920338ad51e89e4b1d8f3cee3e451ffdfaeca62fbf1af66604f5b249fa56af52b045204e7d68dc25449","name":"Literature - Algorithm 12e01bfc60a84007aa7d2d34293e123d_all.csv","type":"text/csv","lastModified":1714662481368.763,"size":295846},{"id":"b6a5a394dceefabdb5bcbfc5514d727a87935cdb306b9789d07c84d029919f6fdc5c614168b41168e4cf7d2d97cdd873355237adb6325fa2f3be339ec104f21d","href":"https://static.observableusercontent.com/files/b6a5a394dceefabdb5bcbfc5514d727a87935cdb306b9789d07c84d029919f6fdc5c614168b41168e4cf7d2d97cdd873355237adb6325fa2f3be339ec104f21d","name":"Paper Sources cb3332bc548a49a4a4f1e085486f71f1.csv","type":"text/csv","lastModified":1710511145180.984,"size":43911},{"id":"2b9499961e2003e2fa9e782880ea0892d1290d3d848022370b8485c6fbce5566d775d5f04d2ed16b9d71482a8f83a47e93da8d528fbfc75fc057caa179b159da","href":"https://static.observableusercontent.com/files/2b9499961e2003e2fa9e782880ea0892d1290d3d848022370b8485c6fbce5566d775d5f04d2ed16b9d71482a8f83a47e93da8d528fbfc75fc057caa179b159da","name":"Benchmark datasets Pages.zip","type":"application/zip","lastModified":1710511887873.554,"size":47591049},{"id":"677dd8d18ef87e64183c4dc6b751dd21c2f92694826c91dfec5fcd249f6d858e8b3adc1b11f7206ec61b6cbe93b35a5bc212bc5cd7bd593d742dd85212b5eddc","href":"https://static.observableusercontent.com/files/677dd8d18ef87e64183c4dc6b751dd21c2f92694826c91dfec5fcd249f6d858e8b3adc1b11f7206ec61b6cbe93b35a5bc212bc5cd7bd593d742dd85212b5eddc","name":"Benchmark datasets Pages@1.zip","type":"application/zip","lastModified":1710512431287.703,"size":1998343},{"id":"5c5afed09444ab35c758b13b901d4289af4e8139f738edcd79e044ad50bd44cd890018d7b988df1625ea442203c42a299d06998c55d27872a53e36ce598e2a24","href":"https://static.observableusercontent.com/files/5c5afed09444ab35c758b13b901d4289af4e8139f738edcd79e044ad50bd44cd890018d7b988df1625ea442203c42a299d06998c55d27872a53e36ce598e2a24","name":"sources3(1).svg","type":"image/svg+xml","lastModified":1714663704204.025,"size":90157},{"id":"339f991709f50648951c75c9bd077106546f757811aafcd184f3fa488380e9b9ca6d0c40ce98caf4c03b1bc0282bc9a44b4b74147bbec0bc8ffcd7ca4e5e2468","href":"https://static.observableusercontent.com/files/339f991709f50648951c75c9bd077106546f757811aafcd184f3fa488380e9b9ca6d0c40ce98caf4c03b1bc0282bc9a44b4b74147bbec0bc8ffcd7ca4e5e2468","name":"orcid_16x16.gif","type":"image/gif","lastModified":1709911718320.206,"size":169},{"id":"339f991709f50648951c75c9bd077106546f757811aafcd184f3fa488380e9b9ca6d0c40ce98caf4c03b1bc0282bc9a44b4b74147bbec0bc8ffcd7ca4e5e2468","href":"https://static.observableusercontent.com/files/339f991709f50648951c75c9bd077106546f757811aafcd184f3fa488380e9b9ca6d0c40ce98caf4c03b1bc0282bc9a44b4b74147bbec0bc8ffcd7ca4e5e2468","name":"orcid_16x16@1.gif","type":"image/gif","lastModified":1709911724080.319,"size":169},{"id":"339f991709f50648951c75c9bd077106546f757811aafcd184f3fa488380e9b9ca6d0c40ce98caf4c03b1bc0282bc9a44b4b74147bbec0bc8ffcd7ca4e5e2468","href":"https://static.observableusercontent.com/files/339f991709f50648951c75c9bd077106546f757811aafcd184f3fa488380e9b9ca6d0c40ce98caf4c03b1bc0282bc9a44b4b74147bbec0bc8ffcd7ca4e5e2468","name":"orcid_16x16@2.gif","type":"image/gif","lastModified":1709911758906.119,"size":169},{"id":"9b474ec421b0f73f7ca81aa0a8e38cbf1cc6e9c1aadcd79a54b3a3136852579d1cf11637e0a0e94805d67c6e24a8b91ceb493d5488ccf884c0851e02fe5f525b","href":"https://static.observableusercontent.com/files/9b474ec421b0f73f7ca81aa0a8e38cbf1cc6e9c1aadcd79a54b3a3136852579d1cf11637e0a0e94805d67c6e24a8b91ceb493d5488ccf884c0851e02fe5f525b","name":"image.png","type":"image/png","lastModified":1709913006442.644,"size":126501},{"id":"f4a42a0bc0cbe327853f717e97c0530555ba722381df2a085d54728bd525993bbbe02be0dd7ed0acea9d09d75ac0fdf5fb2052ed3e56dd6134640753e463991f","href":"https://static.observableusercontent.com/files/f4a42a0bc0cbe327853f717e97c0530555ba722381df2a085d54728bd525993bbbe02be0dd7ed0acea9d09d75ac0fdf5fb2052ed3e56dd6134640753e463991f","name":"sources3.svg","type":"image/svg+xml","lastModified":1709913044572.624,"size":112505},{"id":"8706ca4251ca17a708bd6943c68c5abec2b262651146bad1359f67176539f7c23122fcee582df40f2d18e5ebd8f50af52ceb5cbd5cf8441aea6d30d52e016d53","href":"https://static.observableusercontent.com/files/8706ca4251ca17a708bd6943c68c5abec2b262651146bad1359f67176539f7c23122fcee582df40f2d18e5ebd8f50af52ceb5cbd5cf8441aea6d30d52e016d53","name":"Rome-Lib c2f20984de724f4c89764b0bc494e99e.md","type":"text/markdown","lastModified":1714751906736.03,"size":19542},{"id":"caa4625483f5662cf903d70cc02052ddc93a082d3ba70f52cc37ba94ef167dd092974b88798a731209980c699b8bd3235853f8ddf535c1b3ff69ab346cb6d538","href":"https://static.observableusercontent.com/files/caa4625483f5662cf903d70cc02052ddc93a082d3ba70f52cc37ba94ef167dd092974b88798a731209980c699b8bd3235853f8ddf535c1b3ff69ab346cb6d538","name":"Literature.csv","type":"text/csv","lastModified":1706704244030.949,"size":297402},{"id":"1d168e003ad5f2f755cb84e98ef040f0f3620ca6f06a0701c0294bbe558569ed771dd96b4121b40ae093ac0bf8638fc47fb5c27c4606d3cc7a9ab32c2f2b1ffd","href":"https://static.observableusercontent.com/files/1d168e003ad5f2f755cb84e98ef040f0f3620ca6f06a0701c0294bbe558569ed771dd96b4121b40ae093ac0bf8638fc47fb5c27c4606d3cc7a9ab32c2f2b1ffd","name":"Benchmark datasets.csv","type":"text/csv","lastModified":1706704257592.859,"size":141548}] 2d:{"title":"Benchmark datasets exploration","cells":[{"id":0,"value":"# Benchmark datasets exploration","pinned":false,"hidden":false,"mode":"md"},{"id":466,"value":"toc()","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"value":"$2f","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"literature = {\n let literature = await FileAttachment(\"Literature - Algorithm 12e01bfc60a84007aa7d2d34293e123d_all.csv\").csv()\n console.log(literature)\n literature = literature.filter(d => !d.Name.includes(\"EXCLUDE\") && !d.Name == \"\")\n return literature\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"literature","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"benchmark_datasets = {\n let b = await FileAttachment(\"Benchmark datasets 64e0439269f9497799025562a4087ce1_all.csv\").csv()\n b = b.filter(l => l.Name != \"\")\n return b\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"data = benchmark_datasets","pinned":false,"hidden":false,"mode":"ojs"},{"id":971,"value":"paper_source = {\n let b = await FileAttachment(\"Paper Sources cb3332bc548a49a4a4f1e085486f71f1.csv\").csv()\n b = b.filter(l => l.Name != \"\")\n return b\n}\n\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":984,"value":"page_content = FileAttachment(\"Benchmark datasets Pages@1.zip\").zip()","pinned":true,"hidden":false,"mode":"ojs"},{"id":746,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":854,"value":"","pinned":true,"hidden":false,"mode":"ojs"},{"id":361,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":903,"value":"","pinned":true,"hidden":false,"mode":"ojs"},{"id":697,"value":"## Collection process","pinned":false,"hidden":false,"mode":"md"},{"id":702,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":1047,"value":"The chart below shows the distribution of papers across different venues:","pinned":false,"hidden":false,"mode":"md"},{"id":705,"value":"{ \n let d = []\n \n let allbenchmarkdatasets = [...new Set(literature.map(l => l[\"Conference\"].split(\",\").map(d => d.trim())).flat().map(a => {\n if (a == \"EuroVis\") return \"Computer Graphics Forum\"\n else return a;\n }))].filter(a => a != \"\")\n\n for (let dataset of allbenchmarkdatasets){\n let literature_entries_with_this_dataset = literature.filter(l => l[\"Conference\"].includes(dataset))\n\n if (literature_entries_with_this_dataset.length < 2) continue;\n\n d.push({\"dataset\": dataset, \"count\": literature_entries_with_this_dataset.length})\n }\n \n return Plot.plot({\n \n color: {\n range: [\"steelblue\"]\n },\n y: {},\n marks: [\n Plot.barX(d, {x: \"count\", y: \"dataset\", fill: \"dataset\",inset: 2, sort: {y: \"x\", reverse: true}}),\n Plot.axisY({label: null, lineWidth: 12, marginLeft: 150, marginTop: 20}),\n Plot.text(['Venues where the papers where published'], {frameAnchor: \"Top\",dy: -10})\n ]\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1055,"value":"The following one, instead, shows the distribution of collected papers' publication date:","pinned":false,"hidden":false,"mode":"md"},{"id":742,"value":"{ \n let d = []\n \n let year_range = [1980, 2023]\n for (let year = year_range[0]; year < year_range[1]; year++){\n let literature_entries_with_this_year = literature.filter(l => parseInt(l[\"Year\"]) == year);\n\n d.push({\"year\": year, \"count\": literature_entries_with_this_year.length})\n }\n console.log(d)\n \n return Plot.plot({\n color: {\n range: [\"steelblue\"]\n },\n y: {},\n height: 500,\n marks: [\n Plot.barX(d, {x: \"count\", y: \"year\", inset: 2}),\n Plot.axisY({label: null, lineWidth: 12, marginLeft: 150, marginTop: 20}),\n Plot.text(['Year of publication of the papers included in the survey'], {frameAnchor: \"Top\",dy: -10})\n ]\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1045,"value":"After collecting the datasets, we looked more in-depth into their contents, running analysis on a number of statistics associated with the graphs contained in them. \n\n**- talk about how the graph feature labels were collected\n- facilitating comparisons and replication of results <- justification for what we did\n- linking to specific papers that use that dataset - not seen in other network repositories! **","pinned":false,"hidden":false,"mode":"md"},{"id":26,"value":"## Datasets in use","pinned":false,"hidden":false,"mode":"md"},{"id":241,"value":"The following chart shows how many times we found a dataset being used in the papers we collected. It excludes custom edits to the datasets, which are discussed later in this document.","pinned":false,"hidden":false,"mode":"md"},{"id":176,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":236,"value":"In the data we collected, the most used dataset is Rome-Lib, followed by assorted collaboration networks (which in many cases refers to datasets of academic collaborations such as dblp or vispubdata). The third most used dataset is from C.Walshaw - it is important to note that the Walshaw dataset is available as part of other collections - for instance, its graphs are found in SNAP. However, during the collection process, we preferred giving precedence to how the authors reported their own information. Thus, if the authors claimed the data was from the Walshaw collection, we reported it as such.\n\nWe deem the popularity of Rome-Lib to be due to its simplicity, versatility, and most importantly the fact that it is linked on graphdrawing.org and offered as a benchmark dataset there. This is also true for the North DAGs.","pinned":false,"hidden":false,"mode":"md"},{"id":460,"value":"### Classification of the datasets","pinned":false,"hidden":false,"mode":"md"},{"id":458,"value":"We classified the datasets in different categories, based on their origins or amount of graphs contained in them:","pinned":false,"hidden":false,"mode":"md"},{"id":363,"value":"{ \n let d = []\n \n let collection_type = benchmark_datasets.map(a => a[\"Type of Collection\"]);\n\n for (let c of [... new Set(collection_type)]){\n if (c == \"Skip\" || c == \"Missed it\") continue;\n let count = collection_type.filter(a => a == c).length;\n if (c.includes(\"No report\")) c = \"Established Network Repository\";\n d.push({\"collection_type\": c, \"count\": count})\n }\n \n return Plot.plot({\n color: {\n // legend: true,\n // type: \"categorical\",\n // domain: d3.range(10).map((d, i) => `Category ${i + 1}`),\n scheme: \"Tableau10\" // use the \"accent\" scheme\n },\n y: {\n // tickFormat: \"s\"\n },\n marks: [\n Plot.barX(d, {x: \"count\", y: \"collection_type\", fill: \"collection_type\", inset: 2, sort: {y: \"x\", reverse: true}}),\n Plot.axisY({label: null, lineWidth: 12, marginLeft: 150}),\n ]\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":473,"value":"**Uniform Benchmark** datasets are standalone widely used collections of graphs featuring uniform characteristics - usually simple, generic graphs, often used in evaluations that run over thousands of graphs to report average completion times, or other experiments where the reported metrics are usually aggregated.","pinned":false,"hidden":false,"mode":"md"},{"id":379,"value":"make_dataset_name_and_title_list(\"Uniform Benchmark\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":571,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":1029,"value":"viewof featureSelected = multiAutoSelect({\n options: [...new Set(benchmark_datasets.map(a => a[\"graph features handled\"].split(\",\").map(a => a.trim())).flat())],\n placeholder: \"Select Features\",\n value: [],\n label: \"feature\"\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":652,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":482,"value":"A popular choice is to use datasets from **Established Network Repositories**. These are ample collections, often organized in dedicated websites which also offer a few stats about the contained graphs.","pinned":false,"hidden":false,"mode":"md"},{"id":442,"value":"make_dataset_name_and_title_list(\"Established Network Repo (No report)\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":869,"value":"TODO: **_Remove number of graphs_**","pinned":false,"hidden":false,"mode":"md"},{"id":455,"value":"A number of papers used individual, **Single Graphs** for their experiments instead of a collection:","pinned":false,"hidden":false,"mode":"md"},{"id":434,"value":"make_dataset_name_and_title_list(\"Single Graph\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":865,"value":"_**TODO: remove number of graphs here**_","pinned":false,"hidden":false,"mode":"md"},{"id":485,"value":"Many papers used graphs from specific domains that contain particular characteristics (e.g., geographical coordinates are often found in airline data). Instead of collecting each one of these individual, contextual datasets, we aggregated them in further subcategories, and called them **Aggregate collections**. Individual information about about each aggregate collection can be found in the papers that contain them.","pinned":false,"hidden":false,"mode":"md"},{"id":1312,"value":"

","pinned":false,"hidden":false,"mode":"html"},{"id":1321,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":439,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":887,"value":"Finally, we collected some datasets that we noticed being subsets of existing collections. This is a phenomenon that can happen through the years, through the redistribution and through the merging of different sources: the Walshaw dataset, for instance, was and still is distributed and cited as its own standalone dataset, but its graphs can be found as part of many other larger collections, such as SNAP. We classified these datasets as **Subsets**.","pinned":false,"hidden":false,"mode":"md"},{"id":447,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"Unfortunately, some of the datasets that were used in the papers in our corpus are lost, or not available anymore. While we did go through the effort, for each one of them, to recover them and store them on OSF, we could not find anywhere the following list of datasets:\n\n_**TODO: check what are the links**_","pinned":false,"hidden":false,"mode":"md"},{"id":450,"value":"make_dataset_name_and_title_list(\"Lost/Unavailable\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":270,"value":"$38","pinned":false,"hidden":false,"mode":"md"},{"id":248,"value":"{ \n let d = []\n \n let allbenchmarkdatasets = [...new Set(literature.map(l => l[\"Dataset tag clean\"].split(\",\").map(d => d.trim())).flat())].filter(a => a != \"\")\n\n for (let dataset of allbenchmarkdatasets){\n if (!dataset.includes(\"Custom\")) continue;\n let literature_entries_with_this_dataset = literature.filter(l => l[\"Dataset tag clean\"].includes(dataset))\n\n d.push({\"dataset\": dataset, \"count\": literature_entries_with_this_dataset.length})\n }\n \n return Plot.plot({\n color: {\n // legend: true,\n type: \"categorical\",\n // domain: d3.range(10).map((d, i) => `Category ${i + 1}`),\n scheme: \"Tableau10\" // use the \"accent\" scheme\n },\n y: {\n // tickFormat: \"s\"\n },\n marks: [\n Plot.barX(d, {x: \"count\", y: \"dataset\", fill: \"dataset\",inset: 2, sort: {y: \"x\", reverse: true}}),\n Plot.axisY({label: null, lineWidth: 12, marginLeft: 150}),\n ]\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":272,"value":"$39","pinned":false,"hidden":false,"mode":"md"},{"id":340,"value":"{ \n let d = []\n \n let allbenchmarkdatasets = [...new Set(literature.map(l => l[\"Supplemental material (Multi-select)\"].split(\",\").map(d => d.trim())).flat())].filter(a => a != \"\")\n\n for (let dataset of allbenchmarkdatasets){\n let literature_entries_with_this_dataset = literature.filter(l => l[\"Supplemental material (Multi-select)\"].includes(dataset))\n\n d.push({\"dataset\": dataset, \"count\": literature_entries_with_this_dataset.length})\n }\n \n return Plot.plot({\n color: {\n // legend: true,\n type: \"categorical\",\n // domain: d3.range(10).map((d, i) => `Category ${i + 1}`),\n scheme: \"Tableau10\" // use the \"accent\" scheme\n },\n y: {\n // tickFormat: \"s\"\n },\n marks: [\n Plot.barX(d, {x: \"count\", y: \"dataset\", fill: \"dataset\",inset: 2, sort: {y: \"x\", reverse: true}}),\n Plot.axisY({label: null, lineWidth: 12, marginLeft: 150}),\n ]\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":358,"value":"This discussion is part of a larger discourse on research replicability, that is gaining traction in the scientific community. The ACM, for instance, has a policy on artifact review and badging, where authors are encouraged to submit their artifacts for review, and if they pass, they receive a badge that indicates the artifact is available for review. This is a step towards making research more replicable and reproducible, and we hope that our work will contribute to this effort. \n\nSee, e.g., ACM's definitions: https://www.acm.org/publications/policies/artifact-review-and-badging-current","pinned":false,"hidden":false,"mode":"md"},{"id":116,"value":"todo: count must be percentage, not sheer count\n- remove the big collections (e.g. SNAP) - because some of the collections are children of other collections, so they might end up being over-represented","pinned":false,"hidden":false,"mode":"md"},{"id":71,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":135,"value":"## Details of the datasets","pinned":false,"hidden":false,"mode":"md"},{"id":1109,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":798,"value":"For each of the datasets collected as part of our process, we conducted a brief analysis of their contents. Where possible, the analysis includes information about the number of nodes per graph, the source of the dataset, which papers have used the dataset and what graph features they took into account. The following section defaults to illustrating the contents of Rome-Lib, but the reader can easily change the dataset in focus by modifying the value of the dropdown menu below:","pinned":false,"hidden":false,"mode":"md"},{"id":328,"value":"viewof dataset_to_be_visualized = Inputs.select(benchmark_datasets.map(b => b.Name), {value: \"Rome-Lib\", label: \"Dataset to visualize\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":303,"value":"{\n let b = benchmark_datasets.find(l => l.Name == dataset_to_be_visualized)[\"sparkline data\"].replaceAll(\"'\", '\"')\n try {\n b = JSON.parse(b)\n return Plot.plot({\n color: {\n range: [\"steelblue\"]\n },\n y: {nice:true},\n x: {nice:true},\n height: 400,\n marks: [\n Plot.line(b.num_nodes.map((d, i) => [i*5, d]), {marginTop: 30}),\n Plot.text(['Distribution of graph sizes by number of nodes in ' + dataset_to_be_visualized], {frameAnchor: \"Top\",dy: -20})\n ]\n })\n } catch { return \"No sparkline information to show\" }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":930,"value":"\n \n

","pinned":false,"hidden":false,"mode":"html"},{"id":933,"value":"{\n let named_list_dom = d3.select(\"#named-list\");\n named_list_dom.selectAll(\"*\").remove()\n let entry = benchmark_datasets.find(l => l.Name == dataset_to_be_visualized);\n const paper_data = literature\n const origin_paper_data = paper_source\n add_entry_row(named_list_dom, entry, paper_data, origin_paper_data, page_content, notionFolders)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":921,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":1172,"value":"notionFolders = Object()","pinned":true,"hidden":false,"mode":"ojs"},{"id":1173,"value":"notionFolders['Rome-Lib c2f20984de724f4c89764b0bc494e99e.md'] = await FileAttachment(\"Rome-Lib c2f20984de724f4c89764b0bc494e99e.md\").text()","pinned":true,"hidden":false,"mode":"ojs"},{"id":954,"value":"graph_feature_tags = {\n let graphFeatureTags = []\n benchmark_datasets.forEach(entry => {\n if (entry[\"graph features handled\"] != \"\" && entry[\"graph features handled\"] != undefined){\n let tags = entry[\"graph features handled\"].split(\",\")\n for (let j = 0; j < tags.length; j++){\n if (tags[j].charAt(0) == ' '){\n tags[j] = tags[j].substring(1).toLowerCase()\n }\n if (!graphFeatureTags.includes(tags[j])){\n graphFeatureTags.push(tags[j])\n }\n }\n }\n })\n\n for (let element of literature){\n let features = (element[\"Graph feature\"]).split(\",\")\n for (let feature of features){\n feature = feature.trim().toLowerCase()\n if (!graphFeatureTags.includes(feature)){\n graphFeatureTags.push(feature)\n }\n }\n }\n return graphFeatureTags\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":956,"value":"graph_feature_tags_colors = [\"#9B9A97\", \"#64473A\", \"#D9730D\", \"#DFAB01\", \"#0F7B6C\", \"#0B6E99\", \"#6940A5\", \"#AD1A72\", \"#E03E3E\"]","pinned":false,"hidden":false,"mode":"ojs"},{"id":926,"value":"function name_cleanup(name){\n return name.replace(\"(\", \"\").replace(\")\", \"\").replace(\" \", \"_\").replace(\".\", \"\").replace(\"'\", \"\").replace(\"&\", \"\").replaceAll(\" \", \"\")\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":961,"value":"function doify(text){\n if (text == \"\" || text == undefined) return text;\n if (text.includes(\"https\")) return (text);\n else return (\"https://doi.org/\" + text);\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":944,"value":"function add_simple_field(entry, field_name, div, name = \"\"){\n if (entry[field_name] != \"\" && entry[field_name] != undefined){\n let title = name === \"\" ? field_name : name;\n div.append(\"div\").html(\"\" + title + \": \" + urlify(entry[field_name]))\n }\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":946,"value":"function add_download_field(entry, div){\n let divSection = div.append(\"div\").html(\"\" + \"Download formatted data: \" + \"\");\n const list = ['OSF link gexf', 'OSF link gml', 'OSF link graphml', 'OSF link json']\n\n list.forEach((item)=>{\n if(entry[item] != \"\" && entry[item] != undefined){\n divSection.append(\"a\")\n // .attr('type', 'button')\n .attr('href', entry[item])\n .attr('class', 'btn btn-secondary btn-sm skinny-button')\n .text(item.split(\"OSF link\").pop().toUpperCase())\n } \n })\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":948,"value":"function urlify(text) {\n var urlRegex = /(([a-z]+:\\/\\/)?(([a-z0-9\\-]+\\.)+([a-z]{2}|aero|arpa|biz|com|coop|edu|gov|info|int|jobs|mil|museum|name|nato|net|org|pro|travel|local|internal))(:[0-9]{1,5})?(\\/[a-z0-9_\\-\\.~]+)*(\\/([a-z0-9_\\-\\.]*)(\\?[a-z0-9+_\\-\\.%=&]*)?)?(#[a-zA-Z0-9!$&'()*+.=-_~:@/?]*)?)(\\s+|$)/gi;\n return text.replace(urlRegex, function(url) {\n return '' + url + '';\n })\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":1012,"value":"function getTextAfterBody(input) {\n const lines = input.split('\\n');\n let emptyLineCount = 0;\n let text = '';\n\n for (let i = 0; i < lines.length; i++) {\n const line = lines[i].trim();\n \n if (line === '# Body') {\n text = lines.slice(i + 1).join('\\n');\n // MathJax.typeset();\n } \n }\n \n return text;\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":779,"value":"{\n // datasets that appeared as subsets of other datasets or have large sections in common with them\n let dataset = benchmark_datasets.find(l => l.Name == dataset_to_be_visualized)\n if (dataset[\"Child collections\"] == \"\") return \"No overlapping collections to show\";\n return \"Overlapping collections: \" + dataset[\"Child collections\"].split(\",\").map(a => a.split(\"(\")[0].trim()).join(\", \")\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":164,"value":"# Random generation","pinned":false,"hidden":false,"mode":"md"},{"id":911,"value":"$3d","pinned":false,"hidden":false,"mode":"md"},{"id":166,"value":"$3e","pinned":false,"hidden":false,"mode":"md"},{"id":319,"value":"$3f","pinned":false,"hidden":false,"mode":"md"},{"id":170,"value":"$40","pinned":false,"hidden":false,"mode":"md"},{"id":906,"value":"# Conclusion","pinned":false,"hidden":false,"mode":"md"},{"id":999,"value":"$41","pinned":false,"hidden":false,"mode":"md"},{"id":501,"value":"$42","pinned":false,"hidden":false,"mode":"md"},{"id":857,"value":"# Acknowledgements\n\nThis work was supported in part by the U.S. National Science Foundation (NSF) under award number CAREER IIS-1762268.\n**_TODO (CD 2024-03-13) Anything to add Sara?_**","pinned":false,"hidden":false,"mode":"md"},{"id":508,"value":"$43","pinned":false,"hidden":false,"mode":"md"},{"id":518,"value":"# License\n\nThis work is licensed under a [Creative Commons Attribution 4.0 International License](https://creativecommons.org/licenses/by/4.0/). All code is released under the [Apache 2.0 License](https://opensource.org/license/apache-2-0).\n","pinned":false,"hidden":false,"mode":"md"},{"id":523,"value":"# Conflict of Interest\n\nThe authors declare that there are no competing interests.","pinned":false,"hidden":false,"mode":"md"},{"id":462,"value":"import {toc} from \"@notionparallax/toc\"\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1185,"value":"showdown = require('https://cdnjs.cloudflare.com/ajax/libs/showdown/2.1.0/showdown.min.js')","pinned":true,"hidden":false,"mode":"ojs"},{"id":565,"value":"$44","pinned":false,"hidden":false,"mode":"ojs"},{"id":1269,"value":"function extractDOIUrl(bibtex) {\n // Regular expression to find the DOI within the BibTeX entry\n const doiRegex = /doi\\s*=\\s*{([^}]+)}/i;\n \n // Try to match the DOI in the BibTeX entry\n const match = bibtex.match(doiRegex);\n \n // Check if a DOI was found\n if (match) {\n // Return the DOI as a full URL\n return `https://doi.org/${match[1].trim()}`;\n } else {\n // Return null or an appropriate message if DOI is not found\n return null;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":580,"value":"dict_of_graph_features_to_colors = {\n let all_graph_features = [... new Set(benchmark_datasets.map(a => a[\"graph features handled\"].split(\",\").map(a => a.trim())).flat().filter(a => a != \"\"))]\n let d = {}\n let colorscheme = d3.interpolateRainbow;\n let count = 0;\n for (let f in all_graph_features){\n d[all_graph_features[f]] = d3.color(colorscheme(count++/all_graph_features.length)).darker(0.7)\n }\n return d;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1023,"value":"import {multiAutoSelect} from \"@john-guerra/multi-auto-select\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W45","stdlib":"1","titling":"auto"}