{'fraction_non_alphanumeric': 0.049069373942470386, 'fraction_numerical': 0.011602610587382161, 'mean_word_length': 4.062652961331375, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Top-k Overlapping Densest Subgraphs: Approximation and Complexity

A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort has been put on the problem of finding a single dense subgraph, only recently the focus has been shifted to the problem of finding a set of dens- est subgraphs. Some approaches aim at finding disjoint subgraphs, while in many real-world networks communities are often overlapping. An approach introduced to find possible overlapping subgraphs is the Top-k Overlapping Densest Subgraphs problem. For a given integer k>= 1, the goal of this problem is to find a set of k densest subgraphs that may share some vertices. The objective function to be maximized takes into account both the density of the subgraphs and the distance between subgraphs in the solution. The Top-k Overlapping Densest Subgraphs problem has been shown to admit a 1/10-factor approximation algorithm. Furthermore, the computational complexity of the problem has been left open. In this paper, we present contributions concerning the approximability and the computational complexity of the problem. For the approximability, we present approximation algorithms that improves the approximation factor to 1/2 , when k is bounded by the vertex set, and to 2/3 when k is a constant. For the computational complexity, we show that the problem is NP-hard even when k = 3.


Introduction
One of the most studied and central problem in graph mining is the identification of cohesive subgraphs. This problem has been applied in several contexts, from social network analysis [13] to finding functional motifs in biological networks [7]. Different definitions of cohesive graphs have been proposed and applied in literature. One of the most notable example is clique, and finding a maximum size clique is a well-known and studied problem in theoretical computer science [11]. Other interesting definitions of cohesive subgraph have been proposed in literature, for example relaxed cliques [1,15,12]. A relaxed clique is a graph that satisfies a relaxation of some clique property. Notable examples of relaxed cliques are s-clubs, t-cliques, k-core, and s-plex (for an overview of the different clique relaxations, see [12]).
Most of the definitions of cohesive subgraph lead to NP-hard problems, in some cases even hard to approximate. For example, finding a clique of maximum size is NP-hard [11] and it is even hard to approximate within factor O(|V | 1−ε ), for each ε > 0, on an input graph G = (V, E) [18]. Similarly, finding an s-club of maximum size is NP-hard [4] and the problem admits an approximation factor of O(|V | 1/2 ) [2], on an input graph G = (V, E), while it is not approximable within factor O(|V | 1/2−ε ), for each ε > 0 and s ≥ 2 [2].
One definition of dense subgraph that leads to a polynomial time algorithm is that of average-degree density. For this problem Goldberg gives an elegant polynomial-time algorithm that reduces the problem to that of computing a minimum cut on an auxiliary graph [10]. Furthermore, a fast greedy algorithm that achieves a factor of 1 2 for the problem of computing a subgraph of maximum density has been given in [5].
The densest subgraph problem aims at finding a single subgraph, but in many applications it is of interest finding a collection of k > 1 dense subgraphs of a given graph. More precisely, it is interesting to compute the k subgraphs having maximum density in a given graph. A recent approach proposed in [8] asks for a collection of the top k densest, possibly overlapping, subgraphs (denoted as Dense-Overlapping-k-Subgraphs), since in many real-world cases dense subgraphs are related to non disjoint communities. As pointed out in [14,8] for example hubs are vertices that may be part of several communities and hence of several densest subgraphs, thus motivating the quest for overlapping distinct subgraphs. Dense-Overlapping-k-Subgraphs, proposed in [8], addresses this problem by looking for a collection of k subgraphs that maximize an objective function that takes into account both the density of the subgraphs and the distance between the subgraphs of the solution, thus allowing some overlapping between the subgraphs which depends on a parameter λ.
When λ is small compared to the density, then the density plays a dominant role in the objective function, so the output subgraphs can share a significant part of vertices. On the other hand, if λ is large compared to the density, then the subgraphs will share few or no vertices, so the subgraphs may be disjoint.
An approach similar to Dense-Overlapping-k-Subgraphs was proposed in [3], where the goal is to find a set of k subgraphs of maximum density, such that the maximum pairwise Jaccard coefficient of the subgraphs is bounded. A dynamic variant of the problem, whose goal is finding a set of k disjoint subgraphs , has been recently considered in [16].
Other approaches related to Dense-Overlapping-k-Subgraphs include covering or partitioning an input graph in dense subgraphs, like Minimum Clique Partition [9] or Minimum s-Club Covering [6]. However, notice that, these approaches require that all the vertices of the graph belong to some dense subgraph of the solution, which is not the case for Dense-Overlapping-k-Subgraphs.
Dense-Overlapping-k-Subgraphs has been shown to be approximable within factor 1 10 [8], while its computational complexity has been left open in [8]. In this paper, we present algorithmic and complexity results on Dense-Overlapping-k-Subgraphs. Concerning the approximation of the problem, we provide in Section 3 a 2 3 -approximation algorithm when k is a constant, and we present a 1 2 -approximation algorithm when k is smaller than the size of the vertex set. This last assumption is reasonable, for example notice that the experimental results in [8] consider k = 20, even for graphs having thousands or millions of vertices.
From the computational complexity point of view, we show in Section 4 that the problem is NP-hard even if k = 3 (that is we ask for three densest subgraphs), when λ is a large value. We conclude the paper in Section 5 with some open problems. Some of the proofs are omitted due to page limit.

Definitions
In this section, we present some definitions that will be useful in the rest of the paper. Moreover, we provide the formal definition of the problem we are interested in.
All the graphs we consider in this paper are undirected. Given a graph G = (V, E), and a set V ⊆ V , we denote by Given a subset U ⊆ V , we denote by E(U ) the set of edges of G having both endpoints in U . Moreover, we denote by the set of edges having exactly one endpoint in V 1 and exactly one endpoint in V 2 , formally Now, we present the definition of density of a subgraph.
, among the subgraphs of G. The densest subgraph in the graph of Fig. 1 is that induced by {v 6 , v 7 , v 8 , v 9 , v 10 } and has density 8 5 . Given a graph G = (V, E) and a collection of subgraphs The goal of the problem we are interested in is to find a collection of k subgraphs with high density and that can overlap. However, allowing overlap leads to a solution that may contain k copies of the same subgraph. To address such an issue, in [8] a distance function between subgraphs of the collection is included in the objective function (to be maximized). We present here the distance function between two subgraphs presented in [8].
Definition 2. Given a graph G = (V, E) and two subgraphs and G[Z] as follows: else. Now, we are able to define the problem we are interested in.
Next, we introduce some definitions that will be useful to design the approximation algorithms in Section 3.

Definition 3. Consider a collection
Notice that a subgraph can be both minimal and maximal, for example if it is disjoint from any other subgraph of W (see Fig. 1

Goldberg's Algorithm and Extended Goldberg's Algorithm
Goldberg's Algorithm [10] computes in polynomial time an optimal solution for the Densest-Subgraph problem that, given as input a graph G = (V, E), asks for a subgraph G[V ] in G having maximum density. In order to compute the optimal solution, Goldberg's Algorithm reduces the Densest-Subgraph problem to the problem of computing a minimum cut in a weighted auxiliary graph G A = (V A , E A , w A ) computed by adding two vertices s (the sink) and t (the target) to V , where both s and t are connected with every vertex of V , and by defining weights for the edges in E A . The time complexity of Goldberg's Algorithm is O(|V ||E| log |V |). Given a graph G = (V, E) and a subset G , which can computed with Goldberg's Algorithm.
In this paper, we consider also a modification of Goldberg's Algorithm given in [17]. We refer to this algorithm as the Extended Goldberg's Algorithm. Extended Goldberg's Algorithmin [17] addresses a constrained variant of Densest-Subgraph, where some vertices are forced to be in a densest subgraph, that is we want to compute a densest subgraph G[V ] constrained to the fact that a set S ⊆ V . We denote by Dense-Subgraph(G[V ], C(S)) a densest subgraph of G[V ] that is forced to contain S, that is a densest subgraph G[Z] of G[V ] such that S ⊆ Z, where S is called the constrained set. Notice that Dense-Subgraph(G[V ], C(S)) can be computed with the Extended Goldberg's Algorithm in time O(|V ||E| log(|V | 2 /|E|)) [17].

Approximating Dense-Overlapping-k-Subgraphs
In this section, we present a 2 3 -approximation algorithm for Dense-Overlapping-k-Subgraphs when k is a constant and a 1 2 when k is not a constant. The two approximation algorithms iteratively computes a solution for an intermediate problem, called Densest-Distinct-Subgraph. When k is constant we are able to solve the Densest-Distinct-Subgraph problem in polynomial time, while for general k we are able to provide a 1 2 -approximation algorithm for it. First, we introduce the Densest-Distinct-Subgraph problem, then we present the two approximation algorithms and the analysis of their approximation factor.
Notice that Densest-Distinct-Subgraph is not identical to compute a densest subgraph of G, as we need to ensure that the returned subgraph G[Z] is distinct from any subgraph in W. In particular, if we apply the Goldberg's algorithm, we may compute a subgraph of G which is a subgraph already in W. When W = ∅, then Densest-Distinct-Subgraph is exactly the Densest-Subgraph problem.

Approximation for Constant k
First, we show that Densest-Distinct-Subgraph is polynomial-time solvable when k is a constant, then we show how to obtain an approximation algorithm for Dense-Overlappingk-Subgraph by iteratively solving Densest-Distinct-Subgraph.

A Polynomial-Time Algorithm for Densest-Distinct-Subgraph
The following lemma shows how to define an optimal solution for Densest-Distinct-Subgraph by defining three different cases for an optimal solution of the problem. Then, one of the following cases holds: Next, based on Lemma 1, we show how to compute an optimal solution of Dense-Distinct-Subgraph. We provide three algorithms that are applied for each case of Lemma 1.
For the first case of Lemma 1, Algorithm 3 computes a densest subgraph G[Z 1 ] which is a proper subgraph of a minimal subgraph in W. Algorithm 3 consider the minimal For the second case of Lemma 1, Algorithm 4 computes a densest subgraph G[Z 2 ] which is a proper supergraph of a maximal graph in W. Algorithm 4 iterates over each maximal subgraph G[W j,h ] of W and, for each of such subgraphs, applies the Goldberg's Extended Consider the third case of Lemma 1. Algorithm 5 computes a densest subgraph Finally, an optimal solution of Densest-Distinct-Subgraph is computed by returning the graph of maximum density among G[ We prove the correctness of the algorithm in the next theorem.
A 2 3 -Approximation Algorithm when k is a Constant We show that by solving the Densest-Distinct-Subgraph problem optimally we achieve a 2 3 approximation ratio for Dense-Overlapping-k-Subgraphs. The approximation algorithm computes the solution of maximum value r(W) between the solution returned by Algorithm 1 and the solution consisting of k singletons.
First, we consider the approximation solution returned by Algorithm 1. At each step, Algorithm 1 computes an optimal solution of Densest-Distinct-Subgraph and the output subgraph is added to the solution.

Algorithm 1: Algorithm that returns an approximated solution of
Now, we prove a bound on the value r(W) of a solution W returned by Algorithm 1.
The second inequality follows from Lemma 2.
We prove the first inequality of the lemma by induction on k. Recall that dens( . Assume that the lemma holds for k − 1, we prove that is holds for k. First, notice that thus concluding the proof.
We can prove that the maximum solution returned by Algorithm 1 and A T is a 2 3 approximated solution of Dense-Overlapping-k-Subgraphs.

Approximation When k is not a Constant
Now, we show that Dense-Overlapping-k-Subgraphs can be approximated within factor 1 2 when k is not a constant. The approximation algorithm (Algorithm 2), while W does not contain overlapping subgraphs (see Property 1), adds to W a subgraph which is an optimal solution of Densest-Distinct-Subgraph. When Property 1 holds, Algorithm 2 completes W, so that W contains k subgraphs, by adding subgraphs each with density at least 1 2 of the density of the optimal solution of the Densest-Distinct-Subgraph problem.

Analysis of Phase 1
We show that, while W does not satisfy Property 1, Densest-Distinct-Subgraph can be solved in polynomial time by an algorithm that computes the subgraph of maximum density among the solutions returned by Algorithm 3, Algorithm 4 (described in Section 3.1, and Algorithm 6 (described later).
First, we show a property of an optimal solution of the Densest-Distinct-Subgraph problem when Property 1 does not hold.
} be a collection of subgraphs that does not satisfy Property 1, then one of the following cases holds: is a supergraph of a maximal subgraph in W 3. There exist two vertices u, v ∈ V such that u, v ∈ Z and there is no subgraph in W that contains u and v 4. There exist two vertices u, w ∈ V such that u ∈ Z, w / ∈ Z, and there is no subgraph in W that contains u and does not contain w. 5. There exist three vertices u, v, w ∈ V such that u, v ∈ Z, w / ∈ Z, and there is no subgraph in W that contains u and v and does not contain w. Based on Lemma 4, we can prove the following result.

Analysis of Phase 2
Assume that Property 1 holds, we consider Phase 2 of Algorithm 2. Given two overlapping subgraphs G[W i ] and G[W j ] of W, with W i ∩ W j = W i,j , Algorithm 2 adds h subgraphs until |W| = k as follows.
If |W i,j | ≤ 3, then Phase 2 of Algorithm 2 adds the densest h distinct subgraphs (not already in W) induced by W i ∪ {v}, for some v ∈ V \ W i , and by W j ∪ {u}, for some u ∈ V \ W j .
If |W i,j | ≥ 4, then Phase 2 of Algorithm 2 adds the h subgraphs (not already in W) Next, we show that, after Phase 2 of Algorithm 2, |W| = k and that each subgraph added has density at least 1 2 We start by proving that, after Phase 2 of Algorithm 2, |W| = k. Consider now the case that |W i,j | ≥ 4. There exist at least |V \ W i,j | − 1 subgraphs induced by W i ∪{u}, with u / ∈ (W i ∩W i,j ), or by W j ∪{u}, with u / ∈ (W j ∩W i,j ). There exist at least |W i,j | subgraphs induced by W j \ {u}, for some u ∈ W i ∩ W j . Since k ≤ |V | − 1, it follows that also in this case at least k subgraphs belong to W after Phase 2 of Algorithm 2. Now, we show that the density of the subgraphs added by Phase 2 of Algorithm 2 is at least 1 We can conclude the analysis of the approximation factor with the following result.
We can conclude that r(W) ≥ 1 2 r(W o ).

Complexity of Dense-Overlapping-k-Subgraphs
In this section, we consider the computational complexity of Dense-Overlapping-k-Subgraphs and we show that the problem is NP-hard even if k = 3. We denote this restriction of the problem by Dense-Overlapping-3-Subgraphs. We prove the result by giving a reduction from 3-Clique Partition. We recall that 3-Clique Partition, given a graph G P = (V P , E P ), asks for a partition of G P into three cliques. More formally, let G P = (V P , E P ) be an input graph, 3-Clique Partition asks for a partition of V into V P,1 , V P,2 , V P,3 such that V P = V P,1 V P,2 V P,3 and each G[V i ], with 1 ≤ i ≤ 3, is a clique.
Given an instance of G P = (V P , E P ) of 3-Clique Partition, the input graph G = (V, E) of Dense-Overlapping-3-Subgraphs is identical to G P = (V P , E P ). Define λ = 3|V | 3 . In order to define a reduction from 3-Clique Partition to Dense-Overlapping-3-Subgraphs, we show the following results.
Lemma 8. Let G P = (V P , E P ) be a graph instance of 3-Clique Partition and let G = (V, E) be the corresponding graph instance of Dense-Overlapping-3-Subgraphs. Given three cliques Lemma 9. Let G P = (V P , E P ) be a graph instance of 3-Clique Partition and let G = (V, E) be the corresponding graph instance of Dense-Overlapping-3-Subgraphs. Given a so- We can conclude that Dense-Overlapping-3-Subgraphs is NP-hard.

Conclusion
In this paper we have considered the Dense-Overlapping-k-Subgraphs problem, a problem recently proposed for the analysis of networks. We have shown that Dense-Overlapping-k-Subgraphs is NP-hard when k = 3 and we have given two approximation algorithms of factor 2 3 and 1 2 when k is a constant and when k is smaller than the number of vertices in the graph.
For future works, it would be interesting to further investigate the approximability of Dense-Overlapping-k-Subgraphs, possibly improving the approximation factor or improving the time complexity of our approximation algorithms. A second interesting open problem is the computation complexity of Dense-Overlapping-k-Subgraphs. In our reduction the value of λ is large, the complexity of Dense-Overlapping-k-Subgraphs is open when λ is a constant. Another open problem is the computational complexity of Dense-Overlapping-k-Subgraphs when k = 2. A third direction for future works, is the experimental analysis of the 1 2approximation algorithm we have designed, comparing the results with that of [8]. Then, one of the following cases holds: is a proper subgraph of a minimal subgraph in W Case 2 G[Z] is a maximal subgraph with respect to the subgraphs of W Case 3 There exist t vertices u 1 , . . . , u t , with u i ∈ W i , 1 ≤ i ≤ t, that can be partitioned in two sets U 1 , Proof. Consider an optimal solution G[Z] of Densest-Distinct-Subgraph on instance (G = (V, E), W). Recall that G[Z] must be different from the subgraphs in W. First, we consider two cases: either there exists a subgraph G[W r ] in W such that Z ⊆ W r (Case a) or not (Case b). Consider Case a). We distinguish two subcases. In the first subcase, there exists a minimal subgraph G[W q ] of W such that Z ⊂ G[W q ]. It follows that Case 1 of the lemma holds.
In the second subcase, Proof of Theorem 2 Proof. By Lemma 3, it holds dens(W) ≥ dens(W o ) and thus in this case A T returns a solution having approximation factor 2 3 .
We can conclude that Proof of Lemma 4 } be a collection of subgraphs that do not satisfy Property 1, then an optimal solution G[Z] of Densest-Distinct-Subgraph on instance (G, W) satisfies one of the following property: is a subgraph of a minimal subgraph in W 2. G[Z] is a supergraph of a maximal subgraph in W 3. There exist two vertices u, v ∈ V such that u, v ∈ Z and there is no subgraph in W that contains u and v 4. There exist two vertices u, w ∈ V such that u ∈ Z, w / ∈ Z, and there is no subgraph in W that contains u and does not contain w. 5. There exist three vertices u, v, w ∈ V such that u, v ∈ Z, w / ∈ Z, and there is no subgraph in W that contains u and v and does not contain w.
Proof. Assume that 1) and 2) do not hold. If G[Z] is not a subgraph of a graph in W, it follows that there exist two vertices u and v that do not belong to any subgraph in W and that belong to Z, thus case 3 of the lemma holds.
Assume Each edge {w, v}, with v ∈ W i,j and w ∈ W j \W i,j , is not considered in u∈Wi,j It follows that Since |W i,j | ≥ 4, it follows that Since, Algorithm 2 adds the h most dense subgraphs among the choice of u ∈ W i,j so that |W| = k, this completes the proof. . Assume that the lemma holds for k − 1, we prove that is holds for k. First, notice that By induction hypothesis Consider an optimal solution G[ where , is a clique and, by construction, G[V i ] is also a clique, it follows that Since dens(W) ≤ 3(|V |−1) 2 , as |Ei| |Vi| ≤ |Vi|−1 2 ≤ |V |−1 2 , and λ = 3|V | 3 , it follows that