We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. If it links a repository, it is listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
Personalized PageRank (PPR) is a critical measure of the importance of a node t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to s on a directed graph $G$ with $n$ nodes and $m$ edges, and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for solving two variants of SSPPR: (i) high-precision queries and (ii) approximate queries. For high-precision queries, Power Iteration (PowItr) and Forward Push (FwdPush) are two fundamental approaches. Given an absolute error threshold $λ$, the only known bound of FwdPush is $O(\frac{m}λ)$, much worse than the $O(m \log \frac{1}λ)$-bound of PowItr. Whether FwdPush can achieve the same running time bound as PowItr does still remains an open question in the research community. We give a positive answer to this question by showing that the running time of a common implementation of FwdPush is actually bounded by $O(m \cdot \log \frac{1}λ)$.Based on this finding, we propose a new algorithm, called Power Iteration with Forward Push (PowerPush), which incorporates the strengths of both PowItr and FwdPush. For approximate queries (with a relative error $ε$), we propose a new algorithm, called SpeedPPR, with overall expected time bounded by $O(n \cdot \log n \cdot \log \frac{1}ε)$ on scale-free graphs. This bound greatly improves the $O(\frac{n \cdot \log n}ε)$ bound of a state-of-the-art algorithm FORA.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2101.03652")
get_code_for_paper("2101.03652")
have("2101.03652")
Connect an agent — have() is free.