Finding densest k-connected subgraphs

DOI10.1016/J.DAM.2021.08.032MaRDI QIDQ2235249zbMATH OpenOpenAlexFDO

Authors Francesco Bonchi, David García-Soriano, Atsushi Miyauchi, Charalampos E. Tsourakakis

Publication date 21 October 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.01533

zbMATH Keywords

approximation algorithmsconnectivitydensest subgraph problemdense subgraph discovery

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Connectivity (05C40) Density (toughness, etc.) (05C42)

Abstract: Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph $G=(V,E,w)$, we are asked to find $SsubseteqV$ that maximizes the density $d(S)$, i.e., half the weighted average degree of the induced subgraph $G[S]$. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph $G=(V,E,w)$ and a positive integer/real $k$, we are asked to find $SsubseteqV$ that maximizes the density $d(S)$ under the constraint that $G[S]$ is $k$-vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader's theorem in graph theory and its extensions.

Recommendations

• Finding Connected Dense $$k$$-Subgraphs
• Finding connected \(k\)-subgraphs with high density
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• Finding dense subgraphs with maximum weighted triangle density

Cites work

• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 3627227 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A simple min-cut algorithm
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• An algorithm for finding all thek-components of a digraph
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Depth-First Search and Linear Graph Algorithms
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Deterministic Edge Connectivity in Near-Linear Time
• Dividing a Graph into Triconnected Components
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Finding Dense Subgraphs with Size Bounds
• Local flow partitioning for faster edge connectivity
• Minimum cuts in near-linear time
• On Finding Dense Subgraphs
• On the number of edges in a graph with no \((k + 1)\)-connected subgraphs
• Rubber bands, convex embeddings and graph connectivity
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• The dense \(k\)-subgraph problem
• The densest subgraph problem with a convex/concave size function
• Using expander graphs to find vertex connectivity
• k-Blocks and Ultrablocks in Graphs

Cited in

(18)

• Computing the \(k\) densest subgraphs of a graph
• Finding dense subgraphs with maximum weighted triangle density
• Identifying well-connected communities in real-world and synthetic networks
• Efficient mining algorithm of \(K\)-densely probability attribute sub-graph in a complicated network
• Fast algorithms for constrained graph density problems
• Finding Dense Subgraphs with Size Bounds
• Greedily finding a dense subgraph
• Finding Connected Dense $$k$$-Subgraphs
• Finding connected \(k\)-subgraphs with high density
• Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)
• Finding lasting dense subgraphs
• Top-\(k\) overlapping densest subgraphs
• Finding highly connected subgraphs
• A graph theoretical analysis of the number of edges in \(k\)-dense graphs
• The densest subgraph problem with a convex/concave size function
• Sandwiching a densest subgraph by consecutive cores
• Finding maximum subgraphs with relatively large vertex connectivity
• LATIN 2004: Theoretical Informatics

This page was built for publication: Finding densest \(k\)-connected subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235249)