Real-World Networks Are Low-Dimensional: Theoretical and Practical Assessment
Authors: Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our analysis on GIRGs allows us to obtain a linear-time algorithm for determining the dimensionality of a network. Our algorithm bridges the gap between theory and practice, as it comes with a rigorous proof of correctness and yields results comparable to prior empirical approaches, as indicated by our experiments on real-world instances. The efficiency of our algorithm makes it applicable to very large data-sets. |
| Researcher Affiliation | Academia | Tobias Friedrich1 , Andreas G obel1 , Maximilian Katzmann2 and Leon Schiller3 1Hasso Plattner Institute, University of Potsdam, Germany 2Karlsruhe Institute of Technology, Germany 3ETH, Z urich, Switzerland |
| Pseudocode | No | The paper describes an algorithm and a statistical test in mathematical and textual form but does not include a formally structured pseudocode block or algorithm listing. |
| Open Source Code | Yes | 2Code: https://github.com/leon-schi/dimensionality-estimation. |
| Open Datasets | Yes | Our dataset of real-world networks for the plots in Figure 1 outside the histogram is a collection of 65 networks from the SNAP-dataset [Leskovec and Krevl, ] and Network Repository [Rossi and Ahmed, 2015] with sizes between 10k and 4M vertices. The histogram in Figure 1 additionally uses a dataset of 2976 real-world networks from [Bl asius and Fischbeck, 2022]. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, or test data splits (percentages, counts, or cross-validation setups) for reproducing the experiments. |
| Hardware Specification | No | The paper describes the implementation and evaluation of the algorithm but does not specify any hardware details (e.g., CPU, GPU models, memory) used for running the experiments. |
| Software Dependencies | No | The paper states that the algorithm was implemented but does not list specific software dependencies with their version numbers required to replicate the experiment. |
| Experiment Setup | Yes | Fix a constant 1 < c < 2/3 and a weight wc w0. [...] The dimension was inferred by taking a weighted median (weighted by the size of the induced subgraph of vertices with weight in [wc, cwc]) over different choices of wc ranging in {2, . . . , 300}. |