Efficient and Local Parallel Random Walks
Authors: Michael Kapralov, Silvio Lattanzi, Navid Nouri, Jakab Tardos
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | 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 michael.kapralov@epfl.ch Silvio Lattanzi Google Research silviol@google.com Navid Nouri EPFL navid.nouri@epfl.ch Jakab Tardos EPFL jakab.tardos@epfl.ch |
| 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. |