Title: Mining Density Contrast Subgraphs,
Abstract: Dense subgraph discovery is a key primitive in many graph mining
applications, such as detecting communities in social networks and mining gene
correlation from biological data. Most studies on dense subgraph mining only
deal with one graph. However, in many applications, we have more than one graph
describing relations among a same group of entities. In this paper, given two
graphs sharing the same set of vertices, we investigate the problem of
detecting subgraphs that contrast the most with respect to density. We call
such subgraphs Density Contrast Subgraphs, or DCS in short. Two widely used
graph density measures, average degree and graph affinity, are considered. For
both density measures, mining DCS is equivalent to mining the densest subgraph
from a "difference" graph, which may have both positive and negative edge
weights. Due to the existence of negative edge weights, existing dense subgraph
detection algorithms cannot identify the subgraph we need. We prove the
computational hardness of mining DCS under the two graph density measures and
develop efficient algorithms to find DCS. We also conduct extensive experiments
on several real-world datasets to evaluate our algorithms. The experimental
results show that our algorithms are both effective and efficient.