Distributed PageRank Computation: An Improved Theoretical Study
Authors: Siqiang Luo4496-4503
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Distributed Page Rank Computation: An Improved Theoretical Study,Previously, little works have been spent on the distributed Page Rank algorithms with provably desired complexity and accuracy. Given a graph with n nodes and if we model the distributed computation model as the well-known congested clique model, the state-of-the-art algorithm takes O( log n) communication rounds to approximate the Page Rank value of each node in G, with a probability at least 1 1 n. In this paper, we present improved distributed algorithms for computing Page Rank. Particularly, our algorithm performs O(log log n) rounds (a significant improvement compared with O( log n) rounds) to approximate the Page Rank values with a probability at least 1 1 n. |
| Researcher Affiliation | Academia | Siqiang Luo The University of Hong Kong Pokfulam, Hong Kong sqluo@cs.hku.hk |
| Pseudocode | Yes | Algorithm 1. Round 0. For any node v and each neighbor u of v, v initializes a random walk with the label (v, u, 1), and node v sends the label as a message to node u. ... Algorithm 2. ... Algorithm 3. ... Algorithm 4 (Compute Page Rank). ... Algorithm 5 (Compute BPPR). |
| Open Source Code | No | No statement about open-source code for the described methodology. |
| Open Datasets | No | No mention of specific datasets or their public availability. The paper deals with abstract graphs of 'n' nodes. |
| Dataset Splits | No | No mention of dataset splits. |
| Hardware Specification | No | No mention of hardware specifications. |
| Software Dependencies | No | No mention of software dependencies with specific versions. |
| Experiment Setup | No | No mention of experimental setup details like hyperparameters or training settings. |