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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we provide faster algorithms for computing various fundamentalquantities associated with random walks on a directed graph, including thestationary distribution, personalized PageRank vectors, hitting times, andescape probabilities. In particular, on a directed graph with $n$ vertices and$m$ edges, we show how to compute each quantity in time$\tilde{O}(m^{3/4}n+mn^{2/3})$, where the $\tilde{O}$ notation suppressespolylogarithmic factors in $n$, the desired accuracy, and the appropriatecondition number (i.e. the mixing time or restart probability).  Our result improves upon the previous fastest running times for theseproblems; previous results either invoke a general purpose linear system solveron a $n\times n$ matrix with $m$ non-zero entries, or depend polynomially onthe desired error or natural condition number associated with the problem (i.e.the mixing time or restart probability). For sparse graphs, we obtain a runningtime of $\tilde{O}(n^{7/4})$, breaking the $O(n^{2})$ barrier of the bestrunning time one could hope to achieve using fast matrix multiplication.  We achieve our result by providing a similar running time improvement forsolving directed Laplacian systems, a natural directed or asymmetric analog ofthe well studied symmetric or undirected Laplacian systems. We show how tosolve such systems in time $\tilde{O}(m^{3/4}n+mn^{2/3})$, and efficientlyreduce a broad range of problems to solving $\tilde{O}(1)$ directed Laplaciansystems on Eulerian graphs. We hope these results and our analysis open thedoor for further study into directed spectral graph theory.

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More