Paper Info
Title
Diversified Coherent Core Search on Multi-Layer Graphs.
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
2018
10.1007/s00778-019-00542-3
The VLDB Journal
Keywords
DocType
Volume
Multi-layer graph, Dense subgraph, Coherent core, Diversity
Conference
28
Issue
ISSN
Citations 
4
1066-8888
2
PageRank 
References 
Authors
0.35
0
3
Name
Order
Citations
PageRank
Rong Zhu1122.81
Zhaonian Zou233115.78
Jianzhong Li36324.23