Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
复制标题
最稠密子图：超模块化、迭代剥离和流程
DOI：
10.1137/1.9781611977073.64
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Torres, Manuel
中科院分区：
文献类型：
--
作者：
Chekuri, Chandra;Quanrud, Kent;Torres, Manuel
图中最密集的子图问题(DSG)，在最简单的形式下，如下。给定一个无向图G=(V，E)，找出一个顶点的子集⊆VOO，它最大化比率|E(S)|/|S|其中S是有两个端点INS的边的集合。DSG及其几个变种在理论和实践中都得到了很好的研究，并在数据挖掘和网络分析中有许多应用。本文从超模的角度对DSG的快速算法和结构进行了研究。为此，我们考虑最稠密超模子集问题：给定一个非负的超模函数f：2V→ℝ+，Maximizef(S)/|S|对于最稠密超模子集问题，我们描述了一个简单的基于流的算法，它在确定的(m/∊)时间内输出(1-∊)-近似，其中是边数。我们的算法是第一个对mand 1/∊具有近线性依赖性的算法，并改进了以前基于LP松弛的方法。贪婪剥离算法由于其效率、经验性能和最坏情况下的逼近保证而在DSG和几个变种中非常流行。我们描述了一种简单的DSS剥离算法，并以一种统一的方式分析了它的逼近保证。Bob等人。[12]提出了DSG的一种迭代剥离算法，在实际应用中效果很好，并对其收敛到最优值提出了猜想。我们肯定地回答了他们的猜想，并且实际上证明了他们的算法的自然推广收敛于任何超模函数f的(1-∊)逼近；我们证明的关键是考虑由超模函数的Lovász扩张导出的LP公式。对于广义随机数组，我们证明了迭代次数的界，其中Δ是最大次数，λ∗是最优值。我们的工作表明，对于文献中考虑的几个目标，迭代剥离可以是一种有效的启发式方法。最后，我们证明了最密集-至少-最少ksubgraph[37]的2-近似推广到超模设置。我们还对这个问题的剥离算法进行了统一的分析，并通过这个分析得到了决策支持系统对于凹函数的推广到最大值(S)/g(|S|)的一个近似保证。
The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graphG = (V, E) find a subsetS⊆Vof vertices that maximizes the ratio|E(S)|/|S|whereE(S) is the set of edges with both endpoints inS. DSG and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of DSG via the lens ofsupermodularity. For this we consider the densest supermodular subset problem (DSS): given a non-negative supermodular functionf:2V→ ℝ+, maximizef(S)/|S|.For DSG we describe a simple flow-based algorithm that outputs a (1–∊)-approximation in deterministicÕ(m/∊) time wheremis the number of edges. Our algorithm is the first to have a near-linear dependence onmand 1/∊and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed DSG.Greedy peeling algorithms have been very popular for DSG and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for DSS and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al. [12] developed aniterativepeeling algorithm for DSG which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a (1–∊)-approximation foranysupermodular functionf;the key to our proof is to consider an LP formulation that is derived via the Lovász extension of a supermodular function. For DSG the bound on the number of iterations we prove is where Δ is the maximum degree andλ∗ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature.Finally, we show that the 2-approximation for densest-at-least-ksubgraph [37] extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of DSS to maximizef(S)/g(|S|) for a concave functiong.