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

Over the last two decades, frameworks for distributed-memory parallelcomputation, such as MapReduce, Hadoop, Spark and Dryad, have gainedsignificant popularity with the growing prevalence of large network datasets.The Massively Parallel Computation (MPC) model is the de-facto standard forstudying graph algorithms in these frameworks theoretically. Subgraph countingis one such fundamental problem in analyzing massive graphs, with the mainalgorithmic challenges centering on designing methods which are both scalableand accurate.  Given a graph $G=(V, E)$ with $n$ vertices, $m$ edges and $T$ triangles, ourfirst result is an algorithm that outputs a $(1+\varepsilon)$-approximation to$T$, with asymptotically \emph{optimal round and total space complexity}provided any $S \geq \max{(\sqrt m, n^2/m)}$ space per machine and assuming$T=\Omega(\sqrt{m/n})$. Our result gives a quadratic improvement on the boundon $T$ over previous works. We also provide a simple extension of our result tocounting \emph{any} subgraph of $k$ size for constant $k \geq 1$. Our secondresult is an $O_{\varepsilon}(\log \log n)$-round algorithm for exactlycounting the number of triangles, whose total space usage is parametrized bythe \emph{arboricity} $\alpha$ of the input graph. We extend this result toexactly counting $k$-cliques for any constant $k$. Finally, we prove that arecent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactlycounting all subgraphs of size at most $5$ can be implemented in the MPC modelin total space.

Massively Parallel Algorithms for Small Subgraph Counting