Finding densest k-connected subgraphs

DOI10.1016/J.DAM.2021.08.032zbMATH Open1476.05096arXiv2007.01533OpenAlexW3039988939MaRDI QIDQ2235249FDOQ2235249

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)

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.

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

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

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)

Cites Work

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

Cited In (18)

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

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)