  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 k d-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. 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.
