Jaccard-constrained dense subgraph discovery
Chamalee Wickrama Arachchi Nikolaj Tatti
Finding dense subgraphs is a core problem in graph mining with many
applications in diverse domains. At the same time many real-world networks vary
over time, that is, the dataset can be represented as a sequence of graph
snapshots. Hence, it is natural to consider the question of finding dense
subgraphs in a temporal network that are allowed to vary over time to a certain
degree. In this paper, we search for dense subgraphs that have large pairwise
Jaccard similarity coefficients. More formally, given a set of graph snapshots
and a weight $\lambda$, we find a collection of dense subgraphs such that the
sum of densities of the induced subgraphs plus the sum of Jaccard indices,
weighted by $\lambda$, is maximized. We prove that this problem is NP-hard. To
discover dense subgraphs with good objective value, we present an iterative
algorithm which runs in $\mathcal{O}(n^2k^2 + m \log n + k^3 n)$ time per
single iteration, and a greedy algorithm which runs in $\mathcal{O}(n^2k^2 + m
\log n + k^3 n)$ time, where $k$ is the length of the graph sequence and $n$
and $m$ denote number of nodes and total number of edges respectively. We show
experimentally that our algorithms are efficient, they can find ground truth in
synthetic datasets and provide interpretable results from real-world datasets.
Finally, we present a case study that shows the usefulness of our problem.