Name
Abstract | ||
|---|---|---|
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
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>
, the hierarchical core decomposition (HCD) of a graph formalizes the hierarchy of all k-cores for each possible
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>
• 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
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{P}$</tex>
-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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/ICDE53745.2022.00090 | 2022 IEEE 38th International Conference on Data Engineering (ICDE) |
Keywords | DocType | ISSN |
hierarchical decomposition,k core,parallel algorithm | Conference | 1063-6382 |
ISBN | Citations | PageRank |
978-1-6654-0884-4 | 0 | 0.34 |
References | Authors | |
52 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deming Chu | 1 | 0 | 0.34 |
| Fan Zhang | 2 | 0 | 9.13 |
| Wenjie Zhang | 3 | 1616 | 105.67 |
| Xuemin Lin | 4 | 5585 | 307.32 |
| Ying Zhang | 5 | 1288 | 90.39 |