The densest subgraph problem with a convex/concave size function

DOI10.1007/S00453-017-0400-7MaRDI QIDQ1799206zbMATH OpenOpenAlexFDO

Authors Yasushi Kawase, Atsushi Miyauchi

Publication date 18 October 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.03603, https://drops.dagstuhl.de/opus/volltexte/2016/6814/

zbMATH Keywords

approximation algorithmsdense subgraph extractiondensest subgraph problemgraphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Abstract: In the densest subgraph problem, given an edge-weighted undirected graph $G=(V,E,w)$, we are asked to find $SsubseteqV$ that maximizes the density, i.e., $w(S)/|S|$, where $w(S)$ is the sum of weights of the edges in the subgraph induced by $S$. This problem has often been employed in a wide variety of graph mining applications. However, the problem has a drawback; it may happen that the obtained subset is too large or too small in comparison with the size desired in the application at hand. In this study, we address the size issue of the densest subgraph problem by generalizing the density of $SsubseteqV$. Specifically, we introduce the $f$-density of $SsubseteqV$, which is defined as $w(S)/f(|S|)$, where $f:mathbb{Z}_{geq0}ightarrowmathbb{R}_{geq0}$ is a monotonically non-decreasing function. In the $f$-densest subgraph problem ($f$-DS), we aim to find $SsubseteqV$ that maximizes the $f$-density $w(S)/f(|S|)$. Although $f$-DS does not explicitly specify the size of the output subset of vertices, we can handle the above size issue using a convex/concave size function $f$ appropriately. For $f$-DS with convex function $f$, we propose a nearly-linear-time algorithm with a provable approximation guarantee. On the other hand, for $f$-DS with concave function $f$, we propose an LP-based exact algorithm, a flow-based $O(|V{|}^3)$-time exact algorithm for unweighted graphs, and a nearly-linear-time approximation algorithm.

Recommendations

• The densest subgraph problem with a convex/concave size function
• On Finding Dense Subgraphs
• A general tractable density concept for graphs
• Finding densest \(k\)-connected subgraphs
• Finding Dense Subgraphs with Size Bounds

Cites work

• An o(n^3 )-Time Maximum-Flow Algorithm
• Combinatorial Optimization with Rational Objective Functions
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Discounted average degree density metric and new algorithms for the densest subgraph problem
• Finding Dense Subgraphs with Size Bounds
• Greedily Finding a Dense Subgraph
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• On Finding Dense Subgraphs
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Submodular functions and optimization.
• The dense \(k\)-subgraph problem
• The densest subgraph problem with a convex/concave size function

Cited in

(15)

• In search of the densest subgraph
• Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity
• Computing the \(k\) densest subgraphs of a graph
• Finding densest \(k\)-connected subgraphs
• Density functions subject to a co-matroid constraint
• The density maximization problem in graphs
• The densest subgraph problem with a convex/concave size function
• Dense subgraph problems with output-density conditions
• Discounted average degree density metric and new algorithms for the densest subgraph problem
• Covering a graph with densest subgraphs
• Extracting densest sub-hypergraph with convex edge-weight functions
• A study on modularity density maximization: column generation acceleration and computational complexity analysis
• Covering a graph with densest subgraphs
• Approximation algorithm for extracting densest subgraph over matching-like constraints
• On the generalized mean densest subgraph problem: complexity and algorithms

Describes a project that uses

Uses Software

• MotifCut
• MCODE

This page was built for publication: The densest subgraph problem with a convex/concave size function

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