Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search

The model of k-core discovers a novel hierarchical structure of a network, which has been widely applied in various areas, e.g., sociology, biology, and brain science. Based on the containment relations of k-cores with different
$k$
, the hierarchical core decomposition (HCD) of a graph formalizes the hierarchy of all k-cores for each possible
$k$
• HCD is effective in locating high-quality subgraphs (e.g., densest subgraph search) and exploring particular network phenomena (e.g., user engagement study). However, existing solutions of HCD are still not efficient enough, for both the hierarchy construction and the subgraph search on the hierarchy. In this paper, we propose the first parallel construction algorithm PHCD for HCD, using a new union-find-based paradigm, and the first parallel algorithm PBKS to search high-quality subgraphs from the hierarchy with respect to various community scoring metrics. We prove the problem of hierarchy construction is
$\mathcal{P}$
-complete (difficult to parallelize effectively). Despite the negative result, our PHCD has a near-linear time cost, and PBKS is time-optimal in score computation for most community metrics. Extensive experiments are conducted on 10 real-world networks, where our proposed parallel algorithms significantly outperform the existing solutions, for both the hierarchy construction and the subgraph search.