Flowless: Extracting Densest Subgraphs Without Flow Computations
Flowless: Extracting Densest Subgraphs Without Flow Computations
复制标题
DOI：
10.1145/3366423.3380140
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Digvijay Boob;Yu Gao;Richard Peng;Saurabh Sawlani;Charalampos E. Tsourakakis;Di Wang;Junxing Wang
中科院分区：
文献类型：
--
作者：
Digvijay Boob;Yu Gao;Richard Peng;Saurabh Sawlani;Charalampos E. Tsourakakis;Di Wang;Junxing Wang
寻找图的稠密分支是图挖掘和数据分析中的一个重要问题。要求找到具有最大平均度的子图的稠密子图问题（DSP）形成稠密子图发现中的基本原语，其应用范围从社区检测到生物网络模块的无监督发现[16]。使用最大流[14，17，22]，DSP在多项式时间内完全可解。由于最大流的高计算成本，Charikar的贪婪近似算法由于其线性时间和线性空间复杂度而在实践中通常是优选的[3，8]。它构成了大规模动态图的可扩展解决方案中的关键算法思想[5，7]。然而，其输出密度可能是最佳解决方案的2倍。在本文中，我们设计的贪婪++，迭代剥离算法，改善后的Charikar的贪婪算法的性能显着。我们的迭代贪婪算法能够通过在Charikar的贪婪算法中增加几个通道来快速输出接近最优和最优的解决方案。此外，Greedy++对结构异质性（例如，在真实世界的数据集上。我们的算法的一个额外的属性是，它能够快速评估，而不计算最大流量，Charikar的近似质量是否在一个给定的图形实例更接近最坏情况下的理论保证或最优性。我们还证明了我们的方法具有显着的效率优势，基于最大流的精确优化算法。例如，我们的算法在各种真实世界的图中平均实现了145倍的加速比，同时找到密度至少为密度子图密度的90%的子图。
The problem of finding dense components of a graph is a major primitive in graph mining and data analysis. The densest subgraph problem (DSP) that asks to find a subgraph with maximum average degree forms a basic primitive in dense subgraph discovery with applications ranging from community detection to unsupervised discovery of biological network modules [16]. The DSP is exactly solvable in polynomial time using maximum flows [14, 17, 22]. Due to the high computational cost of maximum flows, Charikar’s greedy approximation algorithm is usually preferred in practice due to its linear time and linear space complexity [3, 8]. It constitutes a key algorithmic idea in scalable solutions for large-scale dynamic graphs [5, 7]. However, its output density can be a factor 2 off the optimal solution. In this paper we design Greedy++, an iterative peeling algorithm that improves upon the performance of Charikar’s greedy algorithm significantly. Our iterative greedy algorithm is able to output near-optimal and optimal solutions fast by adding a few more passes to Charikar’s greedy algorithm. Furthermore Greedy++ is more robust against the structural heterogeneities (e.g., skewed degree distributions) in real-world datasets. An additional property of our algorithm is that it is able to assess quickly, without computing maximum flows, whether Charikar’s approximation quality on a given graph instance is closer to the worst case theoretical guarantee of or to optimality. We also demonstrate that our method has significant efficiency advantage over the maximum flow based exact optimal algorithm. For example, our algorithm achieves ∼ 145 × speedup on average across a variety of real-world graphs while finding subgraphs of density that are at least 90% as dense as the densest subgraph.