densest_subgraph#

densest_subgraph(G, iterations=1, *, method='fista')[source]#

Returns an approximate densest subgraph for a graph G.

This function runs an iterative algorithm to find the densest subgraph, and returns both the density and the subgraph. For a discussion on the notion of density used and the different algorithms available on networkx, please see the Notes section below.

Parameters:

GNetworkX graph: Undirected graph.
iterationsint, optional (default=1): Number of iterations to use for the iterative algorithm. Can be specified positionally or as a keyword argument.
methodstring, optional (default=’fista’): The algorithm to use to approximate the densest subgraph. Supported options: ‘greedy++’ by Boob et al. [2] and ‘fista’ by Harb et al. [3]. Must be specified as a keyword argument. Other inputs produce a ValueError.

Returns:

dfloat: The density of the approximate subgraph found.
Sset: The subset of nodes defining the approximate densest subgraph.

Notes

Problem Definition: The densest subgraph problem (DSG) asks to find the subgraph $S \subseteq V (G)$ with maximum density. For a subset of the nodes of $G$ , $S \subseteq V (G)$ , define $E (S) = {(u, v) : (u, v) \in E (G), u \in S, v \in S}$ as the set of edges with both endpoints in $S$ . The density of $S$ is defined as $| E (S) | / | S |$ , the ratio between the edges in the subgraph $G [S]$ and the number of nodes in that subgraph. Note that this is different from the standard graph theoretic definition of density, defined as $\frac{2 | E (S) |}{| S | (| S | - 1)}$ , for historical reasons.

Exact Algorithms: The densest subgraph problem is polynomial time solvable using maximum flow, commonly referred to as Goldberg’s algorithm. However, the algorithm is quite involved. It first binary searches on the optimal density, $d^{*}$ . For a guess of the density $d$ , it sets up a flow network $G^{'}$ with size $O (m)$ . The maximum flow solution either informs the algorithm that no subgraph with density $d$ exists, or it provides a subgraph with density at least $d$ . However, this is inherently bottlenecked by the maximum flow algorithm. For example, [2] notes that Goldberg’s algorithm was not feasible on many large graphs even though they used a highly optimized maximum flow library.

Charikar’s Greedy Peeling: While exact solution algorithms are quite involved, there are several known approximation algorithms for the densest subgraph problem.

Charikar [1] described a very simple 1/2-approximation algorithm for DSG known as the greedy “peeling” algorithm. The algorithm creates an ordering of the nodes as follows. The first node $v_{1}$ is the one with the smallest degree in $G$ (ties broken arbitrarily). It selects $v_{2}$ to be the smallest degree node in $G ∖ v_{1}$ . Letting $G_{i}$ be the graph after removing $v_{1}, . . ., v_{i}$ (with $G_{0} = G$ ), the algorithm returns the graph among $G_{0}, . . ., G_{n}$ with the highest density.

Greedy++: Boob et al. [2] generalized this algorithm into Greedy++, an iterative algorithm that runs several rounds of “peeling”. In fact, Greedy++ with 1 iteration is precisely Charikar’s algorithm. The algorithm converges to a $(1 - ϵ)$ approximate densest subgraph in $O (Δ (G) \log n / ϵ^{2})$ iterations, where $Δ (G)$ is the maximum degree, and $n$ is the number of nodes in $G$ . The algorithm also has other desirable properties as shown by [4] and [5].

FISTA Algorithm: Harb et al. [3] gave a faster and more scalable algorithm using ideas from quadratic programming for the densest subgraph, which is based on a fast iterative shrinkage-thresholding algorithm (FISTA) algorithm. It is known that computing the densest subgraph can be formulated as the following convex optimization problem:

Minimize $\sum_{u \in V (G)} b_{u}^{2}$

Subject to:

$b_{u} = \sum_{v : {u, v} \in E (G)} x_{u v}$ for all $u \in V (G)$

$x_{u v} + x_{v u} = 1.0$ for all ${u, v} \in E (G)$

$x_{u v} \geq 0, x_{v u} \geq 0$ for all ${u, v} \in E (G)$

Here, $x_{u v}$ represents the fraction of edge ${u, v}$ assigned to $u$ , and $x_{v u}$ to $v$ .

The FISTA algorithm efficiently solves this convex program using gradient descent with projections. For a learning rate $α$ , the algorithm does:

1. Initialization: Set $x_{u v}^{(0)} = x_{v u}^{(0)} = 0.5$ for all edges as a feasible solution.

2. Gradient Update: For iteration $k \geq 1$ , set $x_{u v}^{(k + 1)} = x_{u v}^{(k)} - 2 α \sum_{v : {u, v} \in E (G)} x_{u v}^{(k)}$ . However, now $x_{u v}^{(k + 1)}$ might be infeasible! To ensure feasibility, we project $x_{u v}^{(k + 1)}$ .

3. Projection to the Feasible Set: Compute $b_{u}^{(k + 1)} = \sum_{v : {u, v} \in E (G)} x_{u v}^{(k)}$ for all nodes $u$ . Define $z_{u v}^{(k + 1)} = x_{u v}^{(k + 1)} - 2 α b_{u}^{(k + 1)}$ . Update $x_{u v}^{(k + 1)} = C L A M P ((z_{u v}^{(k + 1)} - z_{v u}^{(k + 1)} + 1.0) / 2.0)$ , where $C L A M P (x) = max (0, min (1, x))$ .

With a learning rate of $α = 1 / Δ (G)$ , where $Δ (G)$ is the maximum degree, the algorithm converges to the optimum solution of the convex program.

Fractional Peeling: To obtain a discrete subgraph, we use fractional peeling, an adaptation of the standard peeling algorithm which peels the minimum degree vertex in each iteration, and returns the densest subgraph found along the way. Here, we instead peel the vertex with the smallest induced load $b_{u}$ :

Compute $b_{u}$ and $x_{u v}$ .

2. Iteratively remove the vertex with the smallest $b_{u}$ , updating its neighbors’ load by $x_{v u}$ .

Fractional peeling transforms the approximately optimal fractional values $b_{u}, x_{u v}$ into a discrete subgraph. Unlike traditional peeling, which removes the lowest-degree node, this method accounts for fractional edge contributions from the convex program.

This approach is both scalable and theoretically sound, ensuring a quick approximation of the densest subgraph while leveraging fractional load balancing.

References

[1]

Charikar, Moses. “Greedy approximation algorithms for finding dense components in a graph.” In International workshop on approximation algorithms for combinatorial optimization, pp. 84-95. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000.

[2] (1,2,3)

Boob, Digvijay, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. “Flowless: Extracting densest subgraphs without flow computations.” In Proceedings of The Web Conference 2020, pp. 573-583. 2020.

[3] (1,2)

Harb, Elfarouk, Kent Quanrud, and Chandra Chekuri. “Faster and scalable algorithms for densest subgraph and decomposition.” Advances in Neural Information Processing Systems 35 (2022): 26966-26979.

[4]

Harb, Elfarouk, Kent Quanrud, and Chandra Chekuri. “Convergence to lexicographically optimal base in a (contra) polymatroid and applications to densest subgraph and tree packing.” arXiv preprint arXiv:2305.02987 (2023).

[5]

Chekuri, Chandra, Kent Quanrud, and Manuel R. Torres. “Densest subgraph: Supermodularity, iterative peeling, and flow.” In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1531-1555. Society for Industrial and Applied Mathematics, 2022.

Examples

>>> G = nx.star_graph(4)
>>> nx.approximation.densest_subgraph(G, iterations=1)
(0.8, {0, 1, 2, 3, 4})