English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

PageRank is a famous measure of graph centrality that has numerousapplications in practice. The problem of computing a single node's PageRank hasbeen the subject of extensive research over a decade. However, existing methodsstill incur large time complexities despite years of efforts. Even onundirected graphs where several valuable properties held by PageRank scores,the problem of locally approximating the PageRank score of a target noderemains a challenging task. Two commonly adopted techniques, Monte-Carlo basedrandom walks and backward push, both cost $O(n)$ time in the worst-casescenario, which hinders existing methods from achieving a sublinear timecomplexity like $O(\sqrt{m})$ on an undirected graph with $n$ nodes and $m$edges.  In this paper, we focus on the problem of single-node PageRank computation onundirected graphs. We propose a novel algorithm, SetPush, for estimatingsingle-node PageRank specifically on undirected graphs. With non-trivalanalysis, we prove that our SetPush achieves the$\tilde{O}\left(\min\left\{d_t, \sqrt{m}\right\}\right)$ time complexity forestimating the target node $t$'s PageRank with constant relative error andconstant failure probability on undirected graphs. We conduct comprehensiveexperiments to demonstrate the effectiveness of SetPush.

Estimating Single-Node PageRank in $\tilde{O}\left(\min\{d_t, \sqrt{m}\}\right)$ Time