Dense subgraphs capture strong communities in social networks and entities possessing strong interactions in biological networks. In particular, k-clique counting and listing have applications in identifying important actors in a graph. However, finding k-cliques is computationally expensive, and thus it is important to have fast parallel algorithms. We present a new parallel algorithm for k-clique counting  that has polylogarithmic span  and is work-efficient with respect to the well-known sequential algorithmfor k-clique listing by Chiba and Nishizeki . Our algorithm can be extended to support listing and enumeration, and is based on computing low out-degree orientations . We present a new linear-work and polylogarithmic span algorithm for computing such orientations, and new parallel algorithms for producing unbiased estimations of clique counts  . Finally, we design  new parallel work-efficient algorithms for approximating the k-clique densest subgraph . Our first algorithm gives a 1/k-approximation and is based on iteratively peeling vertices with the lowest clique counts; our algorithm is work-efficient, but we prove that this process is P-complete and hence does not have polylogarithmic span. Our second algorithm gives a 1/(k(1+\epsilon))-approximation , is work-efficient, and has polylogarithmic span. In addition, we implement these algorithms and propose optimizations . On a 60-core machine , we achieve 13.23 -38.99 x and 1.19 -13.76 x self-relative parallel speedup for k-clique counting and k-clique densest subgraph, respectively. Compared to the state-of-the-art parallel k-clique counting algorithms, we achieve a 1.31-9.88 x speedup, and compared to existing implementations of k-clique densest subgraph, we achieve a 1.01-11.83 x speedup. We are able to compute the 4-clique counts on the largest publicly-available graph with over two hundred billion edges  .
 We present a new parallel algorithm for k-clique counting /listing that has polylogarithmic span (parallel time) and is work-efficient (matches the work of the best sequential algorithm) for sparse graphs . Our algorithm is based on computing low out-degree orientations , which we present new linear-work and polylogarithmic-span algorithms for computing in parallel. We also present new parallel algorithms for producing unbiased estimations of clique counts using graph sparsification . Finally, we design two new parallel work-efficient algorithms for approximating the k-clique densest subgraph , the first of which is a 1/k-approximation and the second of which is a 1/(k(1+\epsilon))-approximation and has polylogarithmic span. Our first algorithm does not have polylogarithmic span, but we prove that it solves a P-complete problem. In addition to the theoretical results, we also implement the algorithms and propose various optimizations to improve their practical performance . On a 30-core machine with two-way hyper-threading, our algorithms achieve 13.23 --38.99 x and 1.19 --13.76 x self-relative parallel speedup for k-clique counting and k-clique densest subgraph, respectively. Compared to the state-of-the-art parallel k-clique counting algorithms, we achieve up to 9.88 x speedup, and compared to existing implementations of k-clique densest subgraph, we achieve up to 11.83 x speedup. We are able to compute the 4-clique counts on the largest publicly-available graph with over two hundred billion edges for the first time .
D
Dense subgraphs capture strong communities in social networks and entities possessing strong interactions in biological networks. In particular, k-clique counting and listing have applications in identifying important actors in a graph. However, finding k-cliques is computationally expensive, and thus it is important to have fast parallel algorithms.
A
/listing
A
(parallel time)
R
with respect to the well-known sequential algorithmfor k-clique listing by Chiba and Nishizeki
(matches the work of the best sequential algorithm) for sparse graphs
D
can be extended to support listing and enumeration, and
R
. We present a
, which we present
R
polylogarithmic span algorithm for computing such orientations, and
polylogarithmic-span algorithms for computing in parallel. We also present
A
using graph sparsification
A
two
R
. Our first algorithm gives
, the first of which is
R
is based on iteratively peeling vertices with the lowest clique counts; our algorithm is work-efficient, but we prove that this process is P-complete and hence does not have polylogarithmic span. Our second algorithm gives
the second of which is
D
, is work-efficient,
R
In addition, we implement these
Our first algorithm does not have polylogarithmic span, but we prove that it solves a P-complete problem. In addition to the theoretical results, we also implement the
R
optimizations
various optimizations to improve their practical performance
R
60-core machine , we
30-core machine with two-way hyper-threading, our algorithms
R
-38.99
--38.99
R
-13.76
--13.76
R
a 1.31-9.88
up to 9.88
R
a 1.01-11.83
up to 11.83
A
for the first time