Name
Abstract | ||
|---|---|---|
Mining dense subgraphs on multi-layer graphs is an interesting problem, which has witnessed lots of applications in practice. To overcome the limitations of the quasi-clique-based approach, we propose d-coherent core (d-CC), a new notion of dense subgraph on multi-layer graphs, which has several elegant properties. We formalize the diversified coherent core search (DCCS) problem, which finds kd-CCs that can cover the largest number of vertices. We propose a greedy algorithm with an approximation ratio of
$$1 - 1/e$$
and two search algorithms with an approximation ratio of 1/4. Furthermore, we propose some optimization techniques to further speed up the algorithms. The experiments verify that the search algorithms are faster than the greedy algorithm and produce comparably good results as the greedy algorithm in practice. As opposed to the quasi-clique-based approach, our DCCS algorithms can fast detect larger dense subgraphs that cover most of the quasi-clique-based results. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00778-019-00542-3 | The VLDB Journal |
Keywords | Field | DocType |
Multi-layer graph, Dense subgraph, Coherent core, Diversity | Data mining,Graph,Search algorithm,Multi layer,Vertex (geometry),Computer science,Theoretical computer science,Greedy algorithm,Speedup | Journal |
Volume | Issue | ISSN |
28 | 4 | 1066-8888 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rong Zhu | 1 | 12 | 2.81 |
| Zhaonian Zou | 2 | 331 | 15.78 |
| Jianzhong Li | 3 | 63 | 24.23 |