Name
Abstract | ||
|---|---|---|
In this paper, we aim to understand the distribution of the densest subgraphs of a given graph under the density notion of average-degree. We show that the structures, the relationships and the distributions of all the densest subgraphs of a graph G can be encoded in O(L) space in an index called the ds-Index. Here L denotes the maximum output size of a densest subgraph of G. More importantly, ds-Indexcan report all the minimal densest subgraphs of G collectively in O(L) time and can enumerate all the densest subgraphs of G with an O(L) delay. Besides, the construction of ds-Indexcosts no more than finding a single densest subgraph using the state-of-the-art approach. Our empirical study shows that for web-scale graphs with one billion edges, the ds-Indexcan be constructed in several minutes on an ordinary commercial machine.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3366423.3380033 | WWW '20: The Web Conference 2020
Taipei
Taiwan
April, 2020 |
Keywords | DocType | ISBN |
Densest Subgraph, Graph Analytics, Query Processing | Conference | 978-1-4503-7023-3 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lijun Chang | 1 | 670 | 44.24 |
| Miao Qiao | 2 | 3 | 3.44 |