11institutetext: HIIT, University of Helsinki<EMAIL_ADDRESS>
# Jaccard-constrained dense subgraph discovery

Chamalee Wickrama Arachchi  Nikolaj Tatti

###### Abstract

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
$\mathit{\mathcal{O}}\mathopen{}\left(n^{2}k^{2}+m\log n+k^{3}n\right)$ time
per single iteration, and a greedy algorithm which runs in
$\mathit{\mathcal{O}}\mathopen{}\left(n^{2}k^{2}+m\log n+k^{3}n\right)$ 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.

##  1 Introduction

Finding dense subgraphs is a core problem in graph mining with many
applications in diverse domains such as social network analysis [20], temporal
pattern mining in financial markets [8], and biological system analysis [10].
Often, many real-world networks vary over time, in which case a sequence of
graph snapshots naturally exists. Consequently, mining dense subgraphs over
time has gained an attention in data mining literature [15, 20, 19, 12].

Our goal is to find dense subgraphs in a temporal network. In order to measure
density, we will use a popular choice of the ratio between number of induced
edges and nodes. This choice is popular since the densest subgraph can be
found in polynomial time [13] and approximated efficiently [5].

Given a graph sequence, there are natural extremes to find the densest
subgraphs: the first approach is to find a common subgraph that maximizes the
sum of densities for individual snapshots, as proposed by Semertzidis et al.
[20] among other techniques. The other approach is to find the densest
subgraphs for each snapshot individually.

In this paper, we study the problem that bridges the gap between these two
extremes, namely we seek dense subgraphs in a temporal network that are
allowed to vary over time to a certain degree. Our approach is to incorporate
the Jaccard similarity index directly into our objective function along with
the density. Here, we reward similar graphs over the snapshots. More formally,
given a graph sequence ${\mathcal{G}}$ and parameter $\lambda$, we seek a
sequence of subgraphs, such that the sum of densities plus the sum of Jaccard
indices, weighted by $\lambda$, is maximized.

We demonstrate the objective in the following toy example.

###### Example 1

$G_{1}$$a$$b$$c$$d$$e$$f$$S_{1}$

$G_{2}$$a$$b$$c$$d$$e$$f$$S_{2}$

$G_{3}$$a$$b$$c$$d$$e$$f$$S_{3}$

Figure 1: Toy graphs used in Example 1

Consider a graph sequence $\\{G_{1},G_{2},G_{3}\\}$ shown in Figure 1, each
graph consisting of $6$ vertices and varying edges. We denote the density
induced by the vertex set $S_{i}$ by
$\mathit{d}\mathopen{}\left(S_{i}\right)$, defined as the ratio between number
of induced edges and nodes,
$\mathit{d}\mathopen{}\left(S_{i}\right)=\frac{{\left|E(S_{i})\right|}}{{\left|S_{i}\right|}}$.

Given a weight parameter $\lambda$ and a sequence of subgraphs
$\left\\{S_{1},S_{2},S_{3}\right\\}$, we define our objective function as
$\sum_{i=1}^{3}\mathit{d}\mathopen{}\left(S_{i}\right)+\lambda\sum_{i<j}\mathit{J}\mathopen{}\left(S_{i},S_{j}\right)$.
Note that Jaccard index between set $S$ and $T$ is defined as
$\mathit{J}\mathopen{}\left(S,T\right)=\frac{|S\cap T|}{|S\cup T|}$.

Assume that we set $\lambda=0.3$ and select $S_{1}=\\{a,b,d,f\\}$,
$S_{2}=\\{a,b,c,f\\}$, and $S_{3}=\\{a,b,d,e,f\\}$. The sum of densities is
$\frac{4}{4}+\frac{6}{4}+\frac{8}{5}=4.1$. Here,
$\mathit{J}\mathopen{}\left(S_{1},S_{2}\right)=\frac{3}{5}=0.6$,
$\mathit{J}\mathopen{}\left(S_{1},S_{3}\right)=\frac{4}{5}=0.8$, and
$\mathit{J}\mathopen{}\left(S_{2},S_{3}\right)=\frac{3}{6}=0.5$. Therefore,
our objective is equal to $4.1+0.3\times(0.6+0.8+0.5)=4.67$.

We show that our problem is NP-hard and consequently propose two greedy
algorithms. The first approach is an iterative algorithm where we start either
with the common densest subgraph or a set of the densest subgraphs for each
individual snapshot and then iteratively improve each individual snapshot. The
improvement step is done with a classic technique used to approximate the
densest subgraph (in a single graph) [2, 5]. We start with the complete
snapshot, and iteratively seek out the vertex so that the remaining graph
yields the largest score. We remove the vertex, and the procedure is repeated
until no vertices remain; the best subgraph for that snapshot is selected.
This is repeated for each snapshot until no improvement is possible. The
second algorithm uses a similar approach except we consider all snapshots at
the same time, and select the best subgraph once we are done.

The appeal of this approach is that, when dealing with a single graph, finding
the next vertex can be done efficiently using a priority queue [5, 2]. We
cannot use this approach directly due to the updates in Jaccard indices.
Instead we maintain a _set_ of priority queues that allow us to find vertices
quickly in practice.

The remainder of the paper is organized as follows. In Section 2, we provide
preliminary notation along with the formal definitions of our optimization
problem. Next, we prove NP-hardness of our problem in Section 3. All our
algorithms and their running times are presented in Section 4. Related work is
discussed in Section 5. Section 6 contains an experimental study both with
synthetic and real-world datasets. Finally, Section 7 summarizes the paper and
provides directions for the future work.

##  2 Preliminary notation and problem definition

We begin by providing preliminary notation and formally defining our problem.

Our input is a sequence of graphs
${\mathcal{G}}=\left\\{G_{1},\ldots,G_{k}\right\\}$, where each snapshot
$G_{i}=(V,E_{i})$ is defined over the same set of nodes. We often denote the
number of nodes and edges by $n={\left|V\right|}$ and
$m_{i}={\left|E_{i}\right|}$, or $m={\left|E\right|}$, if $i$ is omitted.

Given a graph $G=(V,E)$, and a set of nodes $S\subseteq V$, we define
$E(S)\subseteq E$ to be the subset of edges having both endpoints in $S$.

As mentioned before, our goal is to find dense subgraphs in a temporal
network, and for that we need to quantify the density of a subgraph. More
formally, assume an unweighted graph $G=(V,E)$, and let $S\subseteq V$. We
define the _density_ $\mathit{d}\mathopen{}\left(S\right)$ of a single node
set $S$ and extend this definition for a sequence of subgraphs
${\mathcal{S}}=\left\\{S_{1},\ldots,S_{k}\right\\}$ by writing

$\mathit{d}\mathopen{}\left(S_{i}\right)=\frac{{\left|E(S_{i})\right|}}{{\left|S_{i}\right|}}\quad\quad\text{and}\quad\quad\mathit{d}\mathopen{}\left({\mathcal{S}}\right)=\sum_{i=1}^{k}\mathit{d}\mathopen{}\left(S_{i}\right)\quad.$

We will use the Jaccard index in order to measure the similarity between two
subgraphs. More formally, given two sets of nodes $S$ and $T$, we write

$\mathit{J}\mathopen{}\left(S,T\right)=\frac{|S\cap T|}{|S\cup T|}\quad.$

Ideally, we would like to have each subgraph to have high density, and share
as many nodes as possible with each other. This leads to the following score
and optimization problem. More specifically, given a weight parameter
$\lambda$ and a sequence of subgraphs
${\mathcal{S}}=\left\\{S_{1},\ldots,S_{k}\right\\}$ we define a score

$\mathit{q}\mathopen{}\left({\mathcal{S}};\lambda\right)=\mathit{d}\mathopen{}\left({\mathcal{S}}\right)+\lambda\sum_{i=1}^{k}\sum_{j=i+1}^{k}\mathit{J}\mathopen{}\left(S_{i},S_{j}\right)\quad.$

######  Problem 1 (Jaccard Weighted Densest Subgraphs (JWDS))

Given a graph sequence ${\mathcal{G}}=\left\\{G_{1},\dots,G_{k}\right\\}$,
with $G_{i}=(V,E_{i})$, and a real number $\lambda$, find a collection of
subset of vertices ${\mathcal{S}}=\left\\{S_{1},\dots,S_{k}\right\\}$, such
that $\mathit{q}\mathopen{}\left({\mathcal{S}}\right)$ is maximized.

We will consider two extreme cases. The first case is when $\lambda$ is very
large, say $\lambda=\sum m_{i}$, which we refer to as _densest common
subgraph_ or DCS. This problem can be solved by first flattening the graph
sequence into one weighted graph, where an edge weight is the number of
snapshots in which an edge occurs. The problem is then a standard (weighted)
densest subgraph problem that can be solved using the method given by Goldberg
[13] in $\mathit{\mathcal{O}}\mathopen{}\left(nm\log n\right)$ time. The other
extreme case is $\lambda=0$ which can be found by solving the densest subgraph
problem for each individual snapshot.

The main difference from prior studies [15, 20] is that we allow the subsets
to be varied within a given margin (which is defined by Jaccard coefficient),
without enforcing subsets to be fully identical.

##  3 Computational complexity

The problem of finding a common subgraph which maximizes the sum of densities
can be solved optimally in polynomial time. Moreover, if we set $\lambda=0$,
then we can solve the problem by finding optimal dense subgraphs for each
snapshot individually. Next we show that JWDS is NP-hard. Note that the
hardness relies on the fact that we can choose a specific $\lambda$.

###### Proposition 1

JWDS is NP-hard.

###### Proof

We will prove the hardness by reducing from a 2-bounded 3-set packing problem
3DM-2, a problem where we are given a set of items $U$, a family of sets
$\mathcal{C}$ each of size $3$ such that each item in $U$ is included in
exactly two sets, and are asked to find a maximum matching [7].

Assume that we are given an instance with $r={\left|\mathcal{U}\right|}$ items
and $\ell={\left|\mathcal{C}\right|}$ sets. For each set $C_{i}$ we introduce
two nodes $v_{i}$ and $v^{\prime}_{i}$, and for each item $u_{i}$ we introduce
a node $w_{i}$. We also introduce four additional nodes $z_{1}$, $z_{2}$,
$z_{3}$, and $z_{4}$. In total, we have $n=2\ell+r+4$ nodes.

Let $u_{i}$ be an item and let $C_{a}$ and $C_{b}$ be two sets containing
$u_{i}$. We add two snapshots: the first graph $G_{i}$ contains
$(z_{1},z_{2})$, $(z_{1},z_{3})$, $(w_{i},z_{1})$, $(v_{a},z_{1})$, and
$(v_{b},z_{1})$ edges and the second graph $G_{i}^{\prime}$ contains
$(z_{1},z_{2})$, $(z_{1},z_{3})$, $(w_{i},z_{1})$, $(v_{a}^{\prime},z_{1})$,
and $(v_{b}^{\prime},z_{1})$ edges.

We also add $q=2rn^{4}$ graphs $F_{j}$, each with three edges $(z_{1},z_{2})$,
$(z_{1},z_{3})$, and $(z_{1},z_{4})$. We set $\lambda=0.55/q$.

Let ${\mathcal{S}}$ be the optimal solution. We claim that

$\begin{split}\mathit{q}\mathopen{}\left({\mathcal{S}}\right)\geq
T_{1}+T_{2}+T_{3},\text{ where }&T_{1}=q\frac{3}{4}+\lambda{q\choose 2},\
T_{2}=2r\times 1.08,\ \text{ and }\\\ &T_{3}=3\lambda{2r\choose 2}+8\lambda
p+4\lambda r/5,\end{split}$ (1)

if and only if there is a matching with $p$ sets.

Assume that Eq. 1 holds. Let $Q_{j}$ be the optimal subgraphs in $F_{j}$.
Write $S_{i}$ to be the optimal subgraph in $G_{i}$ and $S^{\prime}_{i}$ to be
the optimal subgraph in $G_{i}^{\prime}$. Due to symmetry, we can safely
assume that the subgraphs $Q_{j}$ are all equal. Next, we claim that the
densities and the Jaccard indices of $S_{i}$ and $S_{i}^{\prime}$ cannot reach
$q\frac{3}{4}$ and therefore,
$Q_{j}=\left\\{z_{1},z_{2},z_{3},z_{4}\right\\}$. The second highest density
that any $F_{j}$ can reach is $q\frac{2}{3}$. To prove the claim, we argue
that the densities and the Jaccard indices of $S_{i}$ and $S_{i}^{\prime}$ can
not reach $\Delta=q(\frac{3}{4}-\frac{2}{3})=\frac{q}{12}$. Since $n\geq 4$,
$\Delta>42r$. There are $2r$ number of density terms for $S_{i}$ and
$S_{i}^{\prime}$ with each density less than 1. Since Jaccard index is always
less than or equal to 1, their Jaccard terms can not exceed
$\lambda(2rq+{2r\choose 2})$. Combining both density and Jaccard terms results
in an amount less than $4r$ proving the claim. Therefore densities and Jaccard
indices of $Q_{j}$ now correspond to $T_{1}$.

Next, we claim that $S_{i}$ (and $S_{i}^{\prime}$) consists of 4 nodes and 3
edges, two of them being $(z_{1},z_{2})$ and $(z_{1},z_{3})$. Fix $S_{i}$ with
$y={\left|E(S_{i})\right|}$ edges and $x={\left|S_{i}\right|}$ nodes. Let
$z={\left|S_{i}\cap\left\\{z_{1},z_{2},z_{3},z_{4}\right\\}\right|}$ be the
intersection with $Q_{j}$. We can show that the score is

$\mathit{q}\mathopen{}\left({\mathcal{S}}\right)=\frac{y}{x}+0.55\frac{z}{x+4-z}+R+C,$

where $R$ contains the Jaccard terms using $S_{i}$ and not $Q_{j}$, and $C$
contains the remaining densities and Jaccard terms not depending on $S_{i}$.
The first two terms form a fraction with a denominator of at most $n^{2}$.
Consequently, any changes to $x$, $y$, and $z$ change the first two terms by
at least $n^{-4}$. Note that $R$ contains only $2r-1$ terms, and due to
$\lambda$, we have $R<n^{-4}$. In other words, ${\mathcal{S}}$ must optimize
the first two terms. Since there are only $6$ non-singleton nodes in $G_{i}$,
$x\leq 6$. Moreover, $z\leq\min(3,x)$ and $y\leq\min(5,x-1)$. Enumerating all
the possible combinations show that $x=4$ and $z=y=3$ yield optimal score.
This is only possible if $S_{i}$ consists of 4 nodes and 3 edges, two of them
being $(z_{1},z_{2})$ and $(z_{1},z_{3})$. Now, densities of $S_{i}$ (and
$S_{i}^{\prime}$) and Jaccard indices between $S_{i}$ (and $S^{\prime}_{i}$)
and $Q_{j}$ correspond to $T_{2}$.

Finally, let us look now at the Jaccard terms between $S_{i}$ and/or
$S^{\prime}_{j}$. These terms will constitute $T_{3}$. Let $a$ be the number
of nodes $v_{i}$ or $v_{i}^{\prime}$ that are included in 3 subgraphs; any
such node will yield 3 Jaccard terms of value 1. Let $b$ be the number of
nodes $v_{i}$, $v_{i}^{\prime}$, or $w_{i}$ that are included in 2 subgraphs;
any such node will yield one Jaccard term of value 1. The remaining Jaccard
terms between $S_{i}$ and $S_{i}^{\prime}$ are all of value $3/5$. In summary,
the terms are equal to

$\lambda{2r\choose 2}\frac{3}{5}+\lambda a3\left(1-\frac{3}{5}\right)+\lambda
b\left(1-\frac{3}{5}\right)=\frac{\lambda 3}{5}{2r\choose 2}+\lambda
a\frac{4}{5}+\frac{\lambda(a+b)2}{5}\quad.$

Assume that $a<2p$. Then since $a+b\leq 2r$ these terms are less than $T_{3}$,
which is a contradiction. Therefore, $a\geq 2p$. Now, there are $p$ vertices
in $\left\\{v_{i}\right\\}$ or $p$ vertices in
$\left\\{v_{i}^{\prime}\right\\}$ that are included in 3 subgraphs. These sets
correspond to matchings, and at least one of them will have $p$ sets.

To prove the other direction, assume there is a matching $\mathcal{M}$ with
$p$ sets. To form the subgraph sequence, we first select $(z_{1},z_{2})$ and
$(z_{1},z_{3})$ in every set. For $u_{i}\in C_{j}\in\mathcal{M}$, we also
select $(v_{j},z_{1})$ in $G_{i}$ and $(v_{j}^{\prime},z_{1})$ in
$G_{i}^{\prime}$. For an item $u_{i}$ not covered by $\mathcal{M}$, we select
$(w_{i},z_{1})$ in $G_{i}$ and $(w_{i},z_{1})$ in $G_{i}^{\prime}$. A
straightforward calculation shows that this sequence yields the score given in
Eq. 1. ∎

##  4 Algorithms

Since our problem is NP-hard, we need to resort to heuristics. In this section
we present two algorithms that we will use to find good subgraphs.

The first algorithm is as follows. We start with an initial cadidate
${\mathcal{S}}$. This set is either the solution of the densest common
subgraph or the densest subgraphs of each individual snapshots; we test both
and select the best end result.

In order to improve the initial set we employ the strategy used in [2, 5] when
approximating the densest subgraph: Here, the algorithm starts with the whole
graph and removes a node with the minimum degree, or equivalently, removes a
node such that the remaining subgraph has the highest density. This is
continued until no nodes remained, and among the tested subgraphs the one with
the highest density is selected.

We employ a similar strategy. For a snapshot $G_{i}$, we start with $S_{i}=V$,
and then iteratively remove the vertices so that the score is maximal. After
removing all vertices, we pick the subgraph for $S_{i}$ which maximizes our
objective $\mathit{q}\mathopen{}\left({\mathcal{S}};\lambda\right)$. We
iterate over all snapshots, we keep on modifying the sets until the algorithm
converges. The pseudo-code for this approach is given in Algorithm 1.

1

2while changes do

3 foreach $i=1,\dots,k$ do

4 $C\leftarrow V$;

5 foreach $j=2,\ldots,{\left|V\right|}$ do

6 $u\leftarrow\displaystyle\arg\max_{v\in
C}\mathit{q}\mathopen{}\left(S_{1},\ldots,S_{i-1},C\setminus\\{v\\},S_{i+1},\ldots,S_{k}\right)$;

7 $C\leftarrow C\setminus\\{u\\}$;

8

9 $S_{i}\leftarrow$ best tested $C$, if the score improves;

10

11

12return ${\mathcal{S}}$;

Algorithm 1 $\textsc{Itr}({\mathcal{G}},\lambda,{\mathcal{S}})$, finds
subgraphs with good $\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$

Our second algorithm is similar to Itr. In Algorithm 1 we consider each
snapshot separately and peel off vertices. In our second algorithm, we
initialize each $S_{i}$ with $V$. In each iteration, we find a snapshot
$S_{i}$ and a vertex $v$ so that the remaining subgraph sequence is maximized.
We remove the node and continue until no nodes are left. In the process, we
choose the one which maximizes our objective function. The pseudo-code for
this method is given in Algorithm 2.

1 ${\mathcal{S}}\leftarrow S_{1},\ldots,S_{k}$, where $S_{i}=V$;

2 while there are nodes do

3 $u,j\leftarrow\displaystyle\arg\max_{v,i\mid v\in
S_{i}}\mathit{q}\mathopen{}\left(S_{1},\ldots,S_{i-1},S_{i}\setminus\\{v\\},S_{i+1},\ldots,S_{k}\right)$;

4 $S_{j}\leftarrow S_{j}\setminus\left\\{u\right\\}$;

5

6return best tested ${\mathcal{S}}$;

Algorithm 2 $\textsc{Grd}({\mathcal{G}},\lambda)$, finds subgraphs with good
$\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$

The bottleneck in both algorithms is finding the next vertex to delete. Let us
now consider how we can speed up this selection. To this end, select $S_{i}$
and let $v\in S_{i}$. Let us write ${\mathcal{S}}^{\prime}$ to be
${\mathcal{S}}$ with $S_{i}$ replaced with $S_{i}\setminus\left\\{v\right\\}$.
We can write the score difference between ${\mathcal{S}}$ and
${\mathcal{S}}^{\prime}$ as

$\mathit{q}\mathopen{}\left({\mathcal{S}}^{\prime}\right)-\mathit{q}\mathopen{}\left({\mathcal{S}}\right)=\frac{{\left|E(S_{i})\right|}-\deg
v}{{\left|S_{i}\right|}-1}-\frac{{\left|E(S_{i})\right|}}{{\left|S_{i}\right|}}+\sum_{j\neq
i}\mathit{J}\mathopen{}\left(S_{i}\setminus\left\\{v\right\\},S_{j}\right)-\mathit{J}\mathopen{}\left(S_{i},S_{j}\right)\quad.$
(2)

Let us first consider Grd. To find the optimal $v$ and $i$, we will group the
nodes in $S_{i}$ such that the sum in Eq. 2 is equal for the nodes in the same
group. In order to do that we group the nodes based on the following
condition: if two nodes $u,v\in S_{i}$ belong to the exactly same $S_{j}$ for
each $j$, that is, $u\in S_{j}$ if and only if $v\in S_{j}$, then $u$ and $v$
belong to the same group. Let us write $\mathcal{P}$ to be the collection of
all these groups (across all $i$).

Select $P\in\mathcal{P}$. Since the sum in Eq. 2 is constant for all nodes in
$P$, the node in $P$ maximizing Eq. 2 must have the smallest degree. Thus, we
maintain the nodes in $P$ in a priority queue keyed by the degree. We also
maintain the difference of the Jaccard indices, the sum in Eq. 2. In order to
maintain the difference, we maintain the sizes of intersection
${\left|S_{i}\cap S_{j}\right|}$ and the union ${\left|S_{i}\cup
S_{j}\right|}$ for all $i$ and $j$. To find the optimal $v$ and $i$, we find
the vertex with the smallest degree in each group, and then compare these
candidates among different groups.

This data structure leads to the following running time.

###### Proposition 2

Assume a graph sequence $G_{1},\ldots,G_{k}$ with $n$ nodes and total
$m=\sum_{i}m_{i}$ edges. Let $\mathcal{P}_{ir}$ be the groups of $S_{i}$
(based on the node memberships in other snapshots) when deleting $r$th node.
Define $\Delta=\max{\left|\mathcal{P}_{ir}\right|}$. Then the running time of
Grd is in

$\mathit{\mathcal{O}}\mathopen{}\left(nk^{2}\Delta+m\log n+k^{2}n(k+\log
n)\right)\subseteq\mathit{\mathcal{O}}\mathopen{}\left(n^{2}k^{2}+m\log
n+k^{3}n\right)\quad.$

###### Proof

Finding the best node $u$ and the snapshot $S_{i}$ requires
$\mathit{\mathcal{O}}\mathopen{}\left(\sum_{i}{\left|\mathcal{P}_{ir}\right|}\right)\in\mathit{\mathcal{O}}\mathopen{}\left(k\Delta\right)$
time. Consider deleting $u$ from $S_{i}$.

Deleting $u$ from its queue requires
$\mathit{\mathcal{O}}\mathopen{}\left(\log n\right)$ time. Upon deletion, we
update the degrees of the neighboring nodes in the corresponding queues, in
_total_ time of $\mathit{\mathcal{O}}\mathopen{}\left(m\log n\right)$.
Updating the intersection and the union sizes requires
$\mathit{\mathcal{O}}\mathopen{}\left(k\right)$ time.

We also need to update the gain coming from Jaccard indices for each group
$P$. Only one term changes if $P$ is not a subset of $S_{i}$; there are at
most $k\Delta$ such groups. Otherwise, if $P\subseteq S_{i}$, then $k-1$ terms
change; there are at most $\Delta$ such groups. In summary, we need
$\mathit{\mathcal{O}}\mathopen{}\left(k\Delta\right)$ time.

Node $u$ is included in $\mathit{\mathcal{O}}\mathopen{}\left(k\right)$
queues. As we remove $u$ from $S_{i}$, these queues need to be updated by
moving $u$ to the correct queue. A single such update requires deleting $u$
from its current queue, finding (and possibly creating) the new queue, and
adding $u$ to it. This can be done in
$\mathit{\mathcal{O}}\mathopen{}\left(k+\log n\right)$ time.

Combining these times proves the claim. ∎

We should point out that the running time depends on $\Delta$, the number of
queues in a single snapshot. This number may be as high the number of
vertices, $n$, but ideally $\Delta\ll n$.

The same data structure can be also used Itr. The only difference is that we
do not select optimal $i$; instead $i$ is fixed when looking for the next
vertex to delete. Trivial adjustments to the proof of Prop. 2 imply the
following claim.

###### Proposition 3

Assume a graph sequence $G_{1},\ldots,G_{k}$ with $n$ nodes and total
$m=\sum_{i}m_{i}$ edges. Let $\mathcal{P}_{ir}$ be the groups of $S_{i}$
(based on the node memberships in other snapshots) when deleting $r$th node.
Define $\Delta=\max{\left|\mathcal{P}_{ir}\right|}$. Then the running time of
a single iteration of Itr is in

$\mathit{\mathcal{O}}\mathopen{}\left(nk^{2}\Delta+m\log n+k^{2}n(k+\log
n)\right)\subseteq\mathit{\mathcal{O}}\mathopen{}\left(n^{2}k^{2}+m\log
n+k^{3}n\right)\quad.$

##  5 Related work

In this section we discuss previous studies on discovering the densest
subgraph in a single graph, the densest common subgraph over multiple graphs,
overlapping densest subgraphs, and other types of density measures.

The densest subgraph: Given an undirected graph, finding the subgraph which
maximizes density has been first studied by Goldberg [13] where an exact,
polynomial time algorithm which solves a sequence of min-cut instances is
presented. Asahiro et al. [2] provided a linear time, greedy algorithm proved
to be an $1/2$-approximation algorithm by Charikar [5]. The idea of the
algorithm is that at each iteration, a vertex with minimum degree is removed,
and then the densest subgraph among all the produced subgraphs is chosen.

Several variants of the densest subgraph problem constrained on the size of
the subgraph ${\left|S\right|}$ have been studied: finding the densest
$k$-subgraph (${\left|S\right|}=k$) [9, 16, 2], _at most_ $k$-subgraph
(${\left|S\right|}\leq k$) [1, 17], and _at least_ $k$-subgraph
(${\left|S\right|}\geq k$) [1, 17]. Unlike the densest subgraph problem, when
the size constraint is applied, the densest $k$-subgraph problem becomes NP-
hard [9]. Furthermore, there is no polynomial time approximation scheme (PTAS)
[16]. Approximating the problem of finding at most $k$-subgraph is shown as
hard as the densest $k$-subgraph problem by Khuller and Saha [17]. To find
exactly $k$-size densest subgraph, Bhaskara et al. [4] gave an
$\mathit{\mathcal{O}}\mathopen{}\left(n^{1/4+\epsilon}\right)$-approximation
algorithm for every $\epsilon>0$ that runs in
$n^{\mathit{\mathcal{O}}\mathopen{}\left(1/\epsilon\right)}$ time. Andersen
and Chellapilla [1] provided a linear time $1/3$-approximation algorithm for
at least $k$ densest subgraph problem.

The densest common subgraph over multiple graphs: Jethava and Beerenwinkel
[15] extended the densest subgraph problem (DCS) for the case of multiple
graph snapshots. As a measure the authors’ goal was to maximize the minimum
density. Moreover, Semertzidis et al. [20] introduced several variants of this
problem by varying the aggregate function of the optimization problem, one
variant, BFF-AA, is same as the DCS problem discussed in Section 2. DCS can be
solved exactly through a reduction to the densest subgraph problem, and is
consequently polynomial. The hardness of DCS variants has been addressed [6].

Overlapping densest subgraphs of a single graph: Finding multiple dense
subgraphs in a single graph which allows graphs to be overlapped is studied by
adding a hard constraint to control the overlap of subgraphs [3]. Later,
Galbrun et al. [11] formulated the same problem adding a penalty in the
objective function for the overlap. The difference of our problem to the works
of Balalau et al. [3] and Galbrun et al. [11] is that our goal is to find a
collection of dense subgraphs over multiple graph snapshots (one dense
subgraph for each graph snapshot) while they discover a set of dense subgraphs
within a single graph. Due to this difference, we want to reward similar
subgraphs while the authors want to penalize similar subgraphs.

Other density measures: We use the ratio of edges over the nodes as our
measures as it allows us to compute it efficiently. Alternative measures have
been also considered. One option is to use the proportion of edges instead,
that is, ${\left|E\right|}/{{\left|V\right|}\choose 2}$. The issue with this
measure is that a single edge yields the highest density of 1. Moreover,
finding the largest graph with the edge proportion of 1 is equal to finding a
clique, a classic problem that does not allow any good approximation [14]. As
an alternative approach, Tsourakakis et al. [24] proposed finding subgraphs
with large score ${\left|E\right|}-\alpha{{\left|V\right|}\choose 2}$.
Optimizing this measure is an NP-hard problem but an algorithm similar to the
one given by Asahiro et al. [2] leads to an additive approximation guarantee.
In similar vein, Tatti [21] considered subgraphs maximizing
${\left|E\right|}-\alpha{\left|V\right|}$ and showed that they form nested
structure similar to $k$-core decomposition. An alternative measure called
triangle-density has been proposed by Tsourakakis [23] as a ratio of triangles
and the nodes, possibly producing smaller graphs. Like the density, optimizing
this measure can be done in polynomial time. We leave adopting these measures
as a future work.

##  6 Experimental evaluation

Table 1: Characteristics of synthetic datasets. Here, ${\left|V^{d}\right|}$ and ${\left|V^{s}\right|}$ give initial number of dense and sparse vertices respectively, $\operatorname{E}\mathopen{}\left[{\left|E\right|}\right]$ is the expected number of edges, $k$ is the number of snapshots, $p_{d}$, $p_{s}$, and $p_{c}$ gives the dense, sparse, and cross edge probabilities, $J_{min}=\min_{i<j}J(V^{d}_{i},V^{d}_{j})$ is the minimum Jaccard index between ground truth dense sets of vertices, $d_{true}$ is the ground truth density of dense components, $d_{dcs}$ gives the density of densest common subgraph, and $d_{ind}$ gives the sum of densities of locally densest subgraph from each graph snapshot.  _Dataset_ | ${\left|V^{d}\right|}$ | ${\left|V^{s}\right|}$ | $\operatorname{E}\mathopen{}\left[{\left|E\right|}\right]$ | $k$ | $p_{d}$ | $p_{s}$ | $p_{c}$ | $d_{true}$ | $d_{dcs}$ | $d_{ind}$ | $J_{min}$
---|---|---|---|---|---|---|---|---|---|---|---
Syn-1 | $100$ | $900$ | $672.8$ | $10$ | $0.05$ | $0.0005$ | $0.0005$ | $34.68$ | $24.26$ | $35.74$ | $0.47$
Syn-2 | $100$ | $5\,000$ | $3\,850.2$ | $5$ | $0.05$ | $0.0001$ | $0.0001$ | $40.47$ | $13.03$ | $40.57$ | $0.18$
Syn-3 | $120$ | $1\,200$ | $3\,922$ | $5$ | $0.06$ | $0.005$ | $0.002$ | $27.4$ | $17.62$ | $27.62$ | $0.45$
Syn-4 | $250$ | $5\,000$ | $4\,709$ | $8$ | $0.03$ | $0.001$ | $0.001$ | $55.79$ | $29.65$ | $55.98$ | $0.27$
Syn-5 | $500$ | $3\,500$ | $12\,136.29$ | $7$ | $0.05$ | $0.0003$ | $0.0003$ | $112.11$ | $87.27$ | $112.12$ | $0.53$
Syn-6 | $350$ | $3\,500$ | $32\,015$ | $5$ | $0.06$ | $0.005$ | $0.002$ | $67.96$ | $52.17$ | $67.96$ | $0.49$
Table 2:  Computational statistics from the experiments for synthetic datasets using Itr and Grd algorithms. Here, $\lambda$ is the parameter in $\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$, $i$ is the number of iterations using Itr, columns $d_{dis}$ and $\mathit{q}$ are the sum of densities and scores of the discovered sets, $J_{min}$ provide the minimum Jaccard index between discovered sets, columns $\rho$ give the average Jaccard index between discovered and ground truth sets, and columns $time$ give the computational time in seconds.  |  | Itr | Grd
---|---|---|---
_Data_ | $\lambda$ | $d_{dis}$ | $\mathit{q}$ | $J_{min}$ | $\rho$ | $time$ | $i$ | $d_{dis}$ | $\mathit{q}$ | $J_{min}$ | $\rho$ | $time$
Syn-1 | $0.3$ | $34.84$ | $43.1$ | $0.51$ | $0.93$ | $10$ | $4$ | $34.84$ | $43.09$ | $0.5$ | $0.93$ | $30$
| $0.5$ | $33.54$ | $48.97$ | $0.54$ | $0.89$ | $11$ | $5$ | $33.44$ | $48.97$ | $0.54$ | $0.88$ | $33$
| $0.7$ | $26.43$ | $56.08$ | $0.84$ | $0.74$ | $4$ | $2$ | $26.22$ | $56.08$ | $0.86$ | $0.73$ | $32$
Syn-2 | $0.3$ | $40.57$ | $41.18$ | $0.18$ | $0.99$ | $50$ | $3$ | $40.57$ | $40.77$ | $0.18$ | $0.99$ | $92$
| $0.4$ | $40.57$ | $41.39$ | $0.18$ | $0.99$ | $53$ | $3$ | $40.57$ | $41.39$ | $0.18$ | $0.99$ | $84$
| $0.5$ | $40.57$ | $41.6$ | $0.18$ | $0.99$ | $50$ | $3$ | $40.57$ | $41.6$ | $0.18$ | $0.99$ | $87$
Syn-3 | $0.4$ | $27.59$ | $29.59$ | $0.44$ | $0.97$ | $16$ | $3$ | $27.6$ | $29.59$ | $0.44$ | $0.97$ | $29$
| $0.5$ | $27.59$ | $30.1$ | $0.44$ | $0.97$ | $18$ | $3$ | $27.6$ | $30.08$ | $0.44$ | $0.97$ | $26$
| $0.8$ | $27.44$ | $31.65$ | $0.46$ | $0.98$ | $17$ | $3$ | $27.6$ | $31.56$ | $0.43$ | $0.98$ | $28$
Syn-4 | $0.4$ | $55.75$ | $60.38$ | $0.27$ | $0.98$ | $66$ | $2$ | $55.89$ | $60.42$ | $0.27$ | $0.98$ | $307$
| $0.5$ | $55.82$ | $61.56$ | $0.27$ | $0.98$ | $132$ | $4$ | $55.83$ | $61.55$ | $0.27$ | $0.98$ | $308$
| $0.6$ | $55.76$ | $62.71$ | $0.27$ | $0.98$ | $132$ | $4$ | $55.79$ | $62.71$ | $0.27$ | $0.98$ | $285$
Syn-5 | $0.01$ | $112.12$ | $112.26$ | $0.53$ | $1$ | $73$ | $2$ | $112.12$ | $112.26$ | $0.53$ | $1$ | $249$
| $0.4$ | $112.12$ | $117.7$ | $0.53$ | $1$ | $69$ | $2$ | $112.12$ | $116.3$ | $0.53$ | $1$ | $251$
| $0.5$ | $112.12$ | $119.09$ | $0.53$ | $1$ | $103$ | $3$ | $112.12$ | $119.09$ | $0.53$ | $1$ | $257$
Syn-6 | $0.1$ | $67.96$ | $68.61$ | $0.49$ | $1$ | $42$ | $2$ | $67.96$ | $68.61$ | $0.49$ | $1$ | $226$
| $0.8$ | $67.96$ | $73.18$ | $0.49$ | $1$ | $67$ | $3$ | $67.96$ | $73.17$ | $0.49$ | $1$ | $252$
| $1$ | $67.95$ | $74.49$ | $0.49$ | $1$ | $69$ | $3$ | $67.96$ | $74.48$ | $0.49$ | $1$ | $238$

The goal in this section is to experimentally evaluate our algorithms. We
first generate several synthetic datasets and plant dense subgraph components,
in each snapshot and test how well our algorithms discover the ground truth.
Next we study the performance of the algorithm on real-world temporal datasets
in terms of running time. We compare our results with the solutions obtained
with the densest common subgraph [20] and the sum of densities of locally
dense subgraphs [13]. Finally, we present results of a case study.

We implemented the algorithms in Python111The source code is available at
https://version.helsinki.fi/dacs/.  and performed the experiments using a
2.4GHz Intel Core i5 processor and 16GB RAM.

Synthetic datasets: Next, we explain in detail how the synthetic datasets are
generated, the statistics and the related parameters are given in Table 1.

Each dataset consists of $k$ graphs given as $\\{G_{1},\ldots,G_{k}\\}$. We
split the vertex set into dense and sparse components $V^{d}$ and $V^{s}$. To
generate the $i$th snapshot we create two components $V^{d}_{i}$ and
$V^{s}_{i}$ by starting from $V^{d}$ and $V^{s}$ and moving nodes from $V^{s}$
to $V^{d}$ with a probability of $\eta_{i}$. The probability $\eta_{i}$ is
selected randomly for each snapshot from a uniform distribution $[0.01,0.09]$.
Once the vertices are generated, we sample the edges using a stochastic block
model, with the edge probabilities being $p_{d}$, $p_{s}$, and $p_{c}$ for
dense component, sparse component, and cross edges, respectively. We created
$6$ such synthetic datasets in total to test our algorithms.

Results of synthetic datasets: We report our results in Table 2.

First, we observe that the discovered density values $d_{dis}$ approximately
match each other, that is, both Itr and Grd perform equally well in terms of
the densities. Similar result holds also for the scores
$\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$ and minimum Jaccard
coefficients $J_{min}$. However, Itr runs faster than Grd. This is probably
due to the fact that Grd takes more time to select the next vertex to delete,
which is the bottleneck in both algorithms despite of having same asymptotic
time complexity per iteration in Itr and overall time complexity in Grd. Let
us now compare the discovered sets to the ground truth, given in columns
$\rho$. We can see both algorithms gives similar values which indicates
equally good performance of Itr and Grd.

Our next step is to study the effect of the input parameter $\lambda$. First,
we observe Figure 2 which demonstrates $\rho$ as a function of $\lambda$. In
Figure 2, we see that $\rho$ gradually decreases as we increase $\lambda$.
This is due to the fact that when we increase the weight of constraint part of
$\mathit{q}$, the algorithms try to find dense sets with higher Jaccard
coefficients which eventually forces to deviate from its ground truth.
Furthermore, if we set $\lambda=2$, we can see a drastic change in $\rho$.

Let us now consider Figure 2 which demonstrates how the discovered sum of
densities change with respect to $\lambda$. We see the decreasing trend
showing that second term in the objective function starts to dominate with the
increase of $\lambda$.

Next, we study how the score function $\mathit{q}$ behaves over $\lambda$
shown in Figure 2. We can observe that both Itr and Grd have an increasing
trend when we increase $\lambda$ from $0.3$ to $2.3$. This is expected as
larger $\lambda$ should yield larger scores.

$0.5$$1$$1.5$$2$$0$$0.2$$0.4$$0.6$$0.8$$1$$\lambda$$\rho$ItrGrd(a) | $0.5$$1$$1.5$$2$$20$$25$$\lambda$$d_{dis}$(b) | $0.5$$1$$1.5$$2$$30$$35$$40$$\lambda$$\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$(c)
---|---|---

Figure 2:  Average Jaccard index to the ground truth $\rho$ as a function of $\lambda$ in Figure 2. Discovered density $d_{dis}$ as a function of $\lambda$ in Figure 2. Scores $\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$ as a function of $\lambda$ in Figure 2. This experiment was performed using Syn-3 dataset.  Table 3:  Characteristics of real-world datasets. Here, ${\left|V\right|}$ gives the number of vertices, ${\left|E\right|}$ is the expected number of edges, $k$ is the number of snapshots, $d_{dcs}$ gives the density of densest common subgraph, and $d_{ind}$ gives the sum of densities of locally densest subgraph from each graph snapshot.  _Data_ | ${\left|V\right|}$ | ${\left|E\right|}$ | $k$ | $d_{dcs}$ | $d_{ind}$
---|---|---|---|---|---
Twitter-# | $806$ | $101.2$ | $15$ | $7.54$ | $38.79$
Enron | $1\,079$ | $23.2$ | $183$ | $43.47$ | $185.34$
Facebook | $4\,117$ | $83.13$ | $104$ | $14$ | $88.65$
Students | $889$ | $43.68$ | $122$ | $24.15$ | $117.98$
Twitter-user | $4\,605$ | $109.19$ | $93$ | $23$ | $90.63$
Tumblr | $1\,980$ | $65.3$ | $89$ | $36.67$ | $103.98$
Table 4:  Computational statistics from the experiments for real-world datasets. Here, $\lambda$ is the parameter in $\mathit{q}\mathopen{}\left(\cdot;\lambda\right)$, $i$ gives the number of iterations using Itr, columns $d_{dis}$ are the discovered sum of densities, columns $\mathit{q}$ are the discovered scores, and columns $time$ give the computational time in seconds.  |  | Itr | Grd
---|---|---|---
_Data_ | $\lambda$ | $d_{dis}$ | $\mathit{q}$ | $time$ | $i$ | $d_{dis}$ | $\mathit{q}$ | $time$
Twitter-# | $0.3$ | $37.34$ | $40.52$ | $2.81$ | $5$ | $37.65$ | $38.13$ | $5.79$
| $0.5$ | $14.14$ | $54.54$ | $3.06$ | $7$ | $31.01$ | $42.37$ | $6.38$
| $0.7$ | $11$ | $74.7$ | $2.62$ | $5$ | $16.8$ | $56.18$ | $6.23$
| $0.8$ | $11$ | $83.8$ | $2.79$ | $6$ | $9.33$ | $75.47$ | $6.88$
Enron | $0.05$ | $130.43$ | $357.29$ | $72.02$ | $5$ | $122.08$ | $343.02$ | $816.54$
| $0.1$ | $111.88$ | $593.87$ | $148.9$ | $10$ | $62.08$ | $589.96$ | $826.28$
| $0.5$ | $95.88$ | $2\,662.7$ | $81.56$ | $6$ | $20$ | $3\,139.25$ | $854.43$
| $5$ | $88.66$ | $25\,254.81$ | $98.87$ | $7$ | $20$ | $31\,212.5$ | $774.39$
Facebook | $0.1$ | $52.86$ | $126.98$ | $214.74$ | $7$ | $56.03$ | $85.64$ | $9\,461.59$
| $0.5$ | $36.4$ | $446.09$ | $148.94$ | $6$ | $25.47$ | $344.6$ | $10\,193.96$
| $0.7$ | $31.25$ | $657.92$ | $185.91$ | $7$ | $23.41$ | $475.83$ | $9\,781.9$
| $1$ | $27.41$ | $922.45$ | $136.72$ | $6$ | $22.48$ | $659.32$ | $9\,034.35$
Students | $0$ | $108.9$ | $108.9$ | $124.38$ | $4$ | $102.7$ | $102.7$ | $2\,787.8$
| $0.2$ | $46.99$ | $526.19$ | $100.17$ | $5$ | $33.17$ | $567.84$ | $2\,178.28$
| $0.5$ | $46.17$ | $1\,258.41$ | $79.65$ | $4$ | $33.17$ | $1\,369.86$ | $2\,256.26$
| $0.8$ | $44.5$ | $2\,020.81$ | $78.61$ | $4$ | $33.17$ | $2\,171.88$ | $2\,125.67$
Twitter-user | $0.01$ | $79.21$ | $81.61$ | $572.25$ | $8$ | $63.53$ | $68.53$ | $7\,524.47$
| $0.1$ | $12.04$ | $269$ | $260.31$ | $9$ | $13.9$ | $212.28$ | $6\,422.46$
| $0.2$ | $11.49$ | $545.93$ | $149.91$ | $5$ | $11.64$ | $423.1$ | $6\,770.16$
| $0.5$ | $11.49$ | $1\,347.59$ | $150.08$ | $5$ | $10.83$ | $1\,040.05$ | $6\,847.68$
Tumblr | $0.1$ | $71.33$ | $316.07$ | $50.23$ | $4$ | $66.47$ | $302.83$ | $1\,229.98$
| $0.5$ | $64.37$ | $1\,456.47$ | $49.31$ | $4$ | $62.97$ | $1\,291.82$ | $1\,151.85$
| $0.7$ | $59.25$ | $2\,182.29$ | $48.96$ | $4$ | $62.97$ | $1\,783.35$ | $1\,217.76$
| $1$ | $59.17$ | $3\,092.08$ | $48.37$ | $4$ | $62.97$ | $2\,520.66$ | $1\,252.05$

Real-world datasets: We consider $6$ publicly available, real-world datasets.
The details of the datasets are shown in Table 3. Twitter-#
[22]222https://github.com/ksemer/BestFriendsForever-BFF- is a hashtag network
where nodes correspond to hashtags and edges corresponds to the interactions
where two hashtags appear in a tweet. This dataset contains $15$ such daily
graph snapshots in total. Enron333http://www.cs.cmu.edu/~./enron/ is a popular
dataset which contains email communication data within senior management of
Enron company. It contains $183$ daily snapshots in which daily email count is
at least $5$. Facebook [25]444https://networkrepository.com/fb-wosn-
friends.php is a network of Facebook users in New Orleans regional community.
It contains a set of facebook wall posts among these users during 9th of June
to 20th of August, 2006.
Students555https://toreopsahl.com/datasets/\\#online_social_network is an
online message network at the University of California, Irvine. It spans over
$122$ days. Twitter-user [19]666https://github.com/polinapolina/segmentation-
meets-densest-subgraph/tree/master/data is a network of twitter users in
Helsinki 2013. It contains a set of tweets which appear each others’ names.
Tumblr [18]777http://snap.stanford.edu/data/memetracker9.html contains phrase
or quote mentions appeared in blogs and news media. It contains author and
meme interactions of users over $3$ months from February to April in 2009.

Results of real-world datasets: We report the results obtained from the
experiments with real-world datasets in Table 4.

First, we compare scores $\mathit{q}$ obtained using Itr and Grd. As we can
see, apart from few cases in Enron and Students datasets, Itr achieves greater
score than Grd. Furthermore, we can observe in $time$ columns, Itr runs faster
than Grd. Next, let us observe column $i$ which gives number of iterations
with Itr algorithm. We can see that we have at most $10$ number of iterations
which is reasonable to deal with real-world datasets.

As we compare columns $d_{dis}$ which show discovered densities, we can
occasionally see approximately similar values but also deviations. Next, let
us observe the effect of $\lambda$ on $d_{dis}$ and $\mathit{q}$. Based on
$\lambda$, the ratio between $d_{dis}$ and $\mathit{q}$ tends to change. For
example, in general, when $\lambda$ is lowered, $d_{dis}$ tends to increase
while $\mathit{q}$ decreases, as expected.

Table 5: Twitter hash tags discovered for Twitter-8 dataset.  DCS: abudhabigp,
fp1, abudhabi, guti, f1, pushpush, skyf1, hulk, allowin, bottas, kimi, fp3,
fp2, unleashthehulk, density: $7.07$
---
Itr algorithm: $\lambda=0.8$, density: $12.23$, objective: $21.76$
Day 1: indiangp, skyf1, kimi, f1
Day 2: abudhabigp, skyf1, f1
Day 3: kimi, skyf1, abudhabigp, f1
Day 4: abudhabigp, skyf1, f1
Day 5: abudhabigp, english, arabic, spanish, french, danish, swedish, f1,
endimpunitybh, skyf1, bahrain
Day 6: abudhabigp, fp1, abudhabi, guti, f1, skyf1, hulk, allowin, bottas,
kimi, fp3, fp2
Day 7: abudhabigp, abudhabi, guti, f1, pushpush, skyf1, hulk, allowin, bottas,
kimi, fp3, quali
Day 8: abudhabigp, skyf1, f1

Case study using Twitter-8 dataset: In this section, we present a case-study
and analyze the result which illustrates trending twitter hash tags over a
span of $8$ days, under a Jaccard constrained environment.

Twitter-8 contains a hashtag network from November, 2013. We prepared this
dataset by extracting first $8$ daily graph snapshots from Twitter-# dataset.
Here, each node of the graph represents a specific hashtag. As seen in the
tags from Table 5, Formula-1 racing car event which occurred on Abu Dhabi has
been trending during the period. We set $\lambda=0.8$ and find different sets
of dense subgraphs for each day using Itr. On Day 1, tags indeangp, skyf1,
kimi, and f1 have been added to the dense hashtag collection whereas on Day 2,
the tag kimi who is a Finnish racing legend and the tag indeangp have been
removed from trending list. On Day 3, kimi has been re-entered into the
trending list and the tag indeangp has been replaced by abudhabigp. On Day 6,
the tags like bottas (another Finnish racing car driver), fp2 (Free practice
2), fp3 (Free practice 3), and etc have been added which indicates that
additional racing car event related tags are trending. On Day 5, we can
observe more new tags like bahrain, english, arabic, french, danish, and
swedish have been appeared which seems not directly related to racing car
event. Moreover, new dense collection gives a higher density of $12.22$ with
respect to the DCS density of $7.07$.

##  7 Concluding remarks

We introduced a novel Jaccard weighted, dense subgraph discovery problem
(JWDS) for graphs with multiple snapshots. Here, our goal was to find a dense
subset of vertices from each graph snapshot such that the sum of densities and
the similarity between the snapshots is maximized.

We proved that our problem is NP-hard, and designed an iterative algorithm
which runs in $\mathit{\mathcal{O}}\mathopen{}\left(n^{2}k^{2}+m\log
n+k^{3}n\right)$ time per iteration and a greedy algorithm which runs in
$\mathit{\mathcal{O}}\mathopen{}\left(n^{2}k^{2}+m\log n+k^{3}n\right)$ time.

We experimentally showed that the number of iterations was low in iterative
algorithm, and that the algorithms could find the ground truth using synthetic
datasets and could discover dense collections in real world datasets. We also
studied the effect of our user parameter $\lambda$. Finally, we performed a
case study showing interpretable results.

The paper introduces several interesting directions for future work. In this
paper, we enforced the pairwise Jaccard constraint between all available pairs
of snapshots. However, we can relax this constraint further by letting only a
portion of sets which lies within a specific window to assure the Jaccard
similarity constraint which may lead to future work. Another possible
direction is adopting different type of density for our problem setting.

## References

  * Andersen and Chellapilla [2009] Andersen, R., Chellapilla, K.: Finding dense subgraphs with size bounds.  In: WAW. pp. 25–37 (2009)
  * Asahiro et al. [2000] Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph.  Journal of Algorithms 34(2), 203–221 (2000)
  * Balalau et al. [2015] Balalau, O.D., Bonchi, F., Chan, T.H., Gullo, F., Sozio, M.: Finding subgraphs with maximum total density and limited overlap.  In: WSDM. pp. 379–388 (2015)
  * Bhaskara et al. [2010] Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $O(n^{1/4})$ approximation for densest k-subgraph.  In: STOC. pp. 201–210 (2010)
  * Charikar [2000] Charikar, M.: Greedy approximation algorithms for finding dense components in a graph.  In: APPROX. pp. 84–95 (2000)
  * Charikar et al. [2018] Charikar, M., Naamad, Y., Wu, J.: On finding dense common subgraphs (2018), https://arxiv.org/abs/1802.06361
  * Chlebík and Chlebíková [2003] Chlebík, M., Chlebíková, J.: Approximation hardness for small occurrence instances of np-hard problems.  In: CIAC. pp. 152–164 (2003)
  * Du et al. [2009] Du, X., Jin, R., Ding, L., Lee, V.E., Thornton, J.H.: Migration motif: A spatial-temporal pattern mining approach for financial markets.  In: KDD. pp. 1135–1144 (2009)
  * Feige et al. [2001] Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem.  Algorithmica 29, 410–421 (2001)
  * Fratkin et al. [2006] Fratkin, E., Naughton, B.T., Brutlag, D.L., Batzoglou, S.: Motifcut: regulatory motifs finding with maximum density subgraphs.  Bioinformatics 22(14), e150–e157 (2006)
  * Galbrun et al. [2016] Galbrun, E., Gionis, A., Tatti, N.: Top-k overlapping densest subgraphs.  DMKD 30(5), 1134–1165 (2016)
  * Galimberti et al. [2020] Galimberti, E., Bonchi, F., Gullo, F., Lanciano, T.: Core decomposition in multilayer networks: Theory, algorithms, and applications.  TKDD 14(1), 1–40 (2020)
  * Goldberg [1984] Goldberg, A.V.: Finding a maximum density subgraph (1984)
  * Hstad [1996] Hstad, J.: Clique is hard to approximate within $n^{1-\epsilon}$.  In: STOC. pp. 627–636 (1996)
  * Jethava and Beerenwinkel [2015] Jethava, V., Beerenwinkel, N.: Finding dense subgraphs in relational graphs.  In: ECMLPKDD. pp. 641–654 (2015)
  * Khot [2006] Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique.  SIAM Journal on Computing 36(4), 1025–1071 (2006)
  * Khuller and Saha [2009] Khuller, S., Saha, B.: On finding dense subgraphs.  In: ICALP. pp. 597–608 (2009)
  * Leskovec et al. [2009] Leskovec, J., Backstrom, L., Kleinberg, J.: Meme-tracking and the dynamics of the news cycle.  In: KDD. pp. 497–506 (2009)
  * Rozenshtein et al. [2020] Rozenshtein, P., Bonchi, F., Gionis, A., Sozio, M., Tatti, N.: Finding events in temporal networks: segmentation meets densest subgraph discovery.  KAIS 62(4), 1611–1639 (2020)
  * Semertzidis et al. [2019] Semertzidis, K., Pitoura, E., Terzi, E., Tsaparas, P.: Finding lasting dense subgraphs.  DMKD 33(5), 1417–1445 (2019)
  * Tatti [2019] Tatti, N.: Density-friendly graph decomposition.  TKDD 13(5), 1–29 (2019)
  * Tsantarliotis and Pitoura [2015] Tsantarliotis, P., Pitoura, E.: Topic detection using a critical term graph on news-related tweets.  In: EDBT/ICDT Workshops. pp. 177–182 (2015)
  * Tsourakakis [2015] Tsourakakis, C.: The k-clique densest subgraph problem.  In: WWW. pp. 1122–1132 (2015)
  * Tsourakakis et al. [2013] Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., Tsiarli, M.: Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees.  In: KDD. pp. 104–112 (2013)
  * Viswanath et al. [2009] Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On the evolution of user interaction in facebook.  In: WOSN. pp. 37–42 (2009)