Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Efficient and Local Parallel Random Walks
Authors: Michael Kapralov, Silvio Lattanzi, Navid Nouri, Jakab Tardos
NeurIPS 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we complement our theoretical analysis with experimental results showing that our algorithm is significantly more scalable than previous approaches. |
| Researcher Affiliation | Collaboration | Michael Kapralov EPFL EMAIL Silvio Lattanzi Google Research EMAIL Navid Nouri EPFL EMAIL Jakab Tardos EPFL EMAIL |
| Pseudocode | Yes | Algorithm 1 Stitching algorithm. Algorithm 2 Main Algorithm (Budgeting) |
| Open Source Code | No | The paper does not provide an explicit statement or link for the open-sourcing of the code for the methodology described. It mentions using "Apache Hadoop library" but does not offer its own implementation code. |
| Open Datasets | Yes | As our datasets, we use several real-world graphs form the Stanford Network Analysis Project [LK14, LKF07, LLDM08, KY04, YL12]. |
| Dataset Splits | No | The paper describes running experiments on entire real-world graphs from the Stanford Network Analysis Project but does not specify any training, validation, or test splits for these datasets. |
| Hardware Specification | Yes | The experiments were performed on Amazon s Elastic Map-Reduce system using the Apache Hadoop library. The clusters consisted of 30 machines, each of modest memory and computing power (Amazon s m4.large instance) so as to best adhere to the MPC setting. |
| Software Dependencies | No | The paper mentions using "Apache Hadoop library" but does not provide a specific version number for it or any other software dependencies crucial for replication. |
| Experiment Setup | Yes | The main parameters defining the algorithm are as follows: ℓ the length of a target random walk (16 and 32 in various experiments), C The number of cycles (iterations of the for-loop in Line 5 of Algorithm 2) performed. , B0 the initial budget-per-degree of each vertex, λ the approximate scaling of the budgets of the root vertices each cycle, τ a parameter defining the amount of excess budget used in stitching. ... Table 2: Experiments with ℓ= 16, C = 3, B0 = 6n/m, λ = 32, τ = 1.4. |