Dense subgraph

This is formalized as follows: let G = (V, E) be an undirected graph and let S = (VS, ES) be a subgraph of G. Then the density of S is defined to be: The density of the maximally dense subgraph of a graph is sometimes referred to as its subgraph density.

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

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(n2/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.

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

[4] In this algorithm, the vertex with the lowest degree is repeatedly removed, creating an ordering of vertices

The subgraph returned by the algorithm is the graph induced by the set

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

approximation for the densest subgraph problem after

[5] They also showed that a similar algorithm could be used to find densest hypergraphs.

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.

There exists a polynomial algorithm approximating the densest k subgraph within a ratio of

[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.

problem is to find the maximum density subgraph on at most

problem is defined similarly to the densest at most

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

This variation of the densest subgraph problem aims to maximize the average number of induced

Notice that the densest subgraph problem is obtained as a special case for

This generalization provides an empirically successful poly-time approach for extracting large near-cliques from large-scale real-world networks.

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

The set of locally densest subgraphs in a graph can be computed in polynomial time.