Dense subgraph

An example of a graph G with density d_G = 1.375 and its densest subgraph induced by the vertices b, c, d, e and h in red with density 1.4 .

In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let G = (V, E) be an undirected graph and let S = (V_S, E_S) be a subgraph of G. Then the density of S is defined to be:

${\displaystyle d(S)={|E_{S}| \over |V_{S}|}}$

The density of the maximally dense subgraph of a graph is sometimes referred to as its subgraph density. A subgraph with maximal density can also be seen as a subgraph with maximal average degree in the graph.

Subgraph density is asymptotic to the related notion of arboricity and to graph degeneracy.

Densest subgraph

The densest subgraph problem is that of finding a subgraph of maximum density. In 1984, Andrew V. Goldberg developed a polynomial time algorithm to find the maximum density subgraph using a max flow technique. This has been improved by Gallo, Grigoriadis and Tarjan in 1989 ^[1] to run in O(nm log(n²/m)) time. A simple LP for finding the optimal solution was given by Charikar in 2000. ^[2]

Many of the exact algorithms for solving the densest subgraph problem are impractical on real-world data ^[3] , which has led to the study of approximation algorithms for the densest subgraph problem. A simple ${\textstyle {\frac {1}{2}}}$ approximation for finding the densest subgraph was given by Charikar in 2000, based on a peeling procedure which was first proposed by Asahiro, Iwama, Tamaki, and Tokuyama in 1996 as an approximation algorithm for the densest ${\displaystyle k}$ subgraph problem. ^[4] In this algorithm, the vertex with the lowest degree is repeatedly removed, creating an ordering of vertices ${\displaystyle v_{1},v_{2},\dots ,v_{n}}$, where ${\displaystyle v_{i}}$ is the ${\displaystyle i}$th vertex in the graph to be removed. The subgraph returned by the algorithm is the graph induced by the set ${\displaystyle S_{i}=\{v_{i},v_{i+1},\dots ,v_{n}\}}$ with the highest density. By using the dual of the LP for the exact algorithm he provided, Charikar proved that this procedure runs in linear time and yields a subgraph with at least 50% of the optimal density. ^[2] Though 50% is a tight bound, in practice, this greedy peeling procedure yields about 80% of the optimal density on real-world graphs. ^[3]

In 2020, Boob et al. gave an iterative peeling algorithm that aims to get closer to the optimal subgraph by repeated the peeling procedure multiple times. ^[3] Instead of removing the vertices based on their current degree, a load is assigned to each vertex based on data from previous iterations, and vertices are peeled based on their loads. In 2022, Chekuri, Quanrud, and Torres proved that this procedure converges to a ${\displaystyle (1-\epsilon )}$ approximation for the densest subgraph problem after ${\textstyle O({\frac {\Delta \log n}{\lambda ^{*}\epsilon ^{2}}})}$ iterations of the algorithm, where ${\textstyle \lambda ^{*}}$ is the optimal density and ${\displaystyle \Delta }$ is the maximum degree in the graph. ^[5] They also showed that a similar algorithm could be used to find densest hypergraphs.

Densest k subgraph

There are many variations on the densest subgraph problem. One of them is the densest k subgraph problem, where the objective is to find the maximum density subgraph on exactly k vertices. This problem generalizes the clique problem and is thus NP-hard in general graphs. There exists a polynomial algorithm approximating the densest k subgraph within a ratio of ${\displaystyle n^{1/4\,+\,\epsilon }}$ for every ${\displaystyle \epsilon >0}$, ^[6] while it does not admit an ${\displaystyle n^{1/\!\operatorname {polyloglog} n}}$-approximation in polynomial time unless the exponential time hypothesis is false. ^[7] Under a weaker assumption that ${\displaystyle {\mathsf {NP}}\nsubseteq \bigcap _{\epsilon >0}{\mathsf {BPTIME}}(2^{n^{\epsilon }})}$, no PTAS exists for the problem. ^[8]

The problem remains NP-hard in bipartite graphs and chordal graphs but is polynomial for trees and split graphs. ^[9] It is open whether the problem is NP-hard or polynomial in (proper) interval graphs and planar graphs; however, a variation of the problem in which the subgraph is required to be connected is NP-hard in planar graphs. ^[10]

Densest at most k subgraph

The objective of the densest at most ${\displaystyle k}$ problem is to find the maximum density subgraph on at most ${\displaystyle k}$ vertices. Andersen and Chellapilla showed that if there exists an ${\displaystyle \alpha }$-approximation for this problem then that will lead to an ${\displaystyle \Theta (\alpha ^{2})}$-approximation for the densest ${\displaystyle k}$ subgraph problem. ^[11] Later, this was improved by Khuller and Saha who showed that an ${\displaystyle \alpha }$-approximation for densest at most ${\displaystyle k}$ subgraph implies a ${\displaystyle 4\alpha }$-approximation for the densest ${\displaystyle k}$ subgraph problem. ^[12]

Densest at least k subgraph

The densest at least ${\displaystyle k}$ problem is defined similarly to the densest at most ${\displaystyle k}$ subgraph problem. The problem is NP-complete, ^[12] but admits 2-approximation in polynomial time. ^[13] Moreover, there is some evidence that this approximation algorithm is essentially the best possible: assuming the small set expansion hypothesis (a computational complexity assumption closely related to the unique games conjecture), then it is NP-hard to approximate the problem to within ${\displaystyle (2-\epsilon )}$ factor for every constant ${\displaystyle \epsilon >0}$. ^[14]

K-clique densest subgraph

Charalampos Tsourakakis introduced the ${\displaystyle k}$-clique densest subgraph problem. This variation of the densest subgraph problem aims to maximize the average number of induced ${\displaystyle k}$ cliques ${\displaystyle d_{k}(S)={|C_{k}(S)| \over |V_{S}|}}$, where ${\displaystyle C_{k}(S)}$ is the set of ${\displaystyle k}$-cliques induced by ${\displaystyle S}$. Notice that the densest subgraph problem is obtained as a special case for ${\displaystyle k=2}$. This generalization provides an empirically successful poly-time approach for extracting large near-cliques from large-scale real-world networks.

Locally top-k densest subgraph

Qin et al. introduced the problem of top-k locally densest subgraphs discovery in a graph, each of which achieves the highest density in its local region in the graph: it is neither contained in any supergraph with the same or larger density, nor it contains subgraphs with density being loosely connected with the rest of the local densest subgraph. Note that the densest subgraph problem is obtained as a special case for ${\displaystyle k=1}$. The set of locally densest subgraphs in a graph can be computed in polynomial time.

References

1. Gallo, Giorgio; Grigoriadis, Michael D.; Tarjan, Robert E. (1989), "A fast parametric maximum flow algorithm and applications", SIAM Journal on Computing, 18 (1): 30–55, doi:10.1137/0218003, MR   0978165
2. Charikar, Moses (2000), "Greedy approximation algorithms for finding dense components in a graph", in Jansen, Klaus; Khuller, Samir (eds.), Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1913, Springer, pp. 84–95, doi:10.1007/3-540-44436-X_10, ISBN   978-3-540-67996-7
3. Boob, Digvijay; Gao, Yu; Peng, Richard; Sawlani, Saurabh; Tsourakakis, Charalampos; Wang, Di; Wang, Junxing (2020-04-20). "Flowless: Extracting Densest Subgraphs Without Flow Computations". Proceedings of The Web Conference 2020. WWW '20. New York, NY, USA: Association for Computing Machinery: 573–583. doi:10.1145/3366423.3380140. ISBN   978-1-4503-7023-3.
4. Asahiro, Yuichi; Iwama, Kazuo; Tamaki, Hisao; Tokuyama, Takeshi (1996). Karlsson, Rolf; Lingas, Andrzej (eds.). "Greedily finding a dense subgraph". Algorithm Theory — SWAT'96. Berlin, Heidelberg: Springer: 136–148. doi:10.1007/3-540-61422-2_127. ISBN   978-3-540-68529-6.
5. Chekuri, Chandra; Quanrud, Kent; Torres, Manuel R. (January 2022), "Densest Subgraph: Supermodularity, Iterative Peeling, and Flow", Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 1531–1555, doi:10.1137/1.9781611977073.64 , retrieved 2024-12-12
6. Bhaskara, Aditya; Charikar, Moses; Chlamtáč, Eden; Feige, Uriel; Vijayaraghavan, Aravindan (2010), "Detecting high log-densities—an O(n^1/4) approximation for densest k-subgraph", STOC'10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, pp. 201–210, doi:10.1145/1806689.1806719, ISBN   9781450300506, MR   2743268, S2CID   1391318 .
7. Manurangsi, Pasin (2017), "Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph", STOC'17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, pp. 954–961, arXiv: 1611.05991 , doi:10.1145/3055399.3055412, ISBN   9781450345286, S2CID   1892186 .
8. Khot, Subhash (2006), "Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique", SIAM Journal on Computing , 36 (4): 1025–1071, CiteSeerX   10.1.1.114.3324 , doi:10.1137/S0097539705447037, MR   2272270, S2CID   16514252 .
9. Corneil, D. G.; Perl, Y. (1984), "Clustering and domination in perfect graphs", Discrete Applied Mathematics , 9 (1): 27–39, doi: 10.1016/0166-218X(84)90088-X , MR   0754426 .
10. Keil, J. Mark; Brecht, Timothy B. (1991), "The complexity of clustering in planar graphs" (PDF), Journal of Combinatorial Mathematics and Combinatorial Computing, 9: 155–159, MR   1111849 .
11. Andersen, Reid; Chellapilla, Kumar (2009). "Finding Dense Subgraphs with Size Bounds". In Avrachenkov, Konstantin; Donato, Debora; Litvak, Nelly (eds.). Algorithms and Models for the Web-Graph. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 25–37. doi:10.1007/978-3-540-95995-3_3. ISBN   978-3-540-95995-3.
12. Khuller, Samir; Saha, Barna (2009), "On finding dense subgraphs" (PDF), Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, Lecture Notes in Computer Science, vol. 5555, Berlin: Springer-Verlag, pp. 597–608, CiteSeerX   10.1.1.722.843 , doi:10.1007/978-3-642-02927-1_50, ISBN   978-3-642-02926-4, MR   2544878
13. Andersen, Reid (2007), Finding large and small dense subgraphs, arXiv: cs/0702032 , Bibcode:2007cs........2032A
14. Manurangsi, Pasin (2018), "Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis", Algorithms, 11 (1): 10, arXiv: 1705.03581 , doi: 10.3390/a11010010 , MR   3758880

Further reading

• Andersen, R.; Chellapilla, K. (2009), "Finding dense subgraphs with size bounds", WAW: 25–36.
• Feige, U.; Kortsarz, G.; Peleg, D. (1997), "The dense k-subgraph problem", Algorithmica , 29 (3): 410–421, CiteSeerX   10.1.1.25.9443 , doi:10.1007/s004530010050, S2CID   8354738 .
• Goldberg, A. V. (1984), "Finding a maximum density subgraph", Technical Report.
• Tsourakakis, C. (2015), "The K-clique Densest Subgraph Problem", Proceedings of the 24th International Conference on World Wide Web, pp. 1122–1132, CiteSeerX   10.1.1.695.7667 , doi:10.1145/2736277.2741098, ISBN   9781450334693, S2CID   14586622 .
• Qin, Lu; Li, Rong{-}Hua; Chang, Lijun; Zhang, Chengqi (2015), "Locally densest subgraph discovery", in Cao, Longbing; Zhang, Chengqi; Joachims, Thorsten; Webb, Geoffrey I.; Margineantu, Dragos D.; Williams, Graham (eds.), Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, {ACM}, pp. 965–974, doi:10.1145/2783258.2783299, ISBN   9781450336642, S2CID   11041435 .