Show simple item record

dc.contributor.authorBoob, Digvijayen_US
dc.contributor.authorGao, Yuen_US
dc.contributor.authorPeng, Richarden_US
dc.contributor.authorSawlani, Saurabhen_US
dc.contributor.authorTsourakakis, Charalamposen_US
dc.contributor.authorWang, Dien_US
dc.contributor.authorWang, Junxingen_US
dc.coverage.spatialTaipeien_US
dc.date2020-01-10
dc.date.accessioned2020-09-16T17:17:15Z
dc.date.available2020-09-16T17:17:15Z
dc.date.issued2020-04
dc.identifier.citationDigvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, Junxing Wang. 2020. "Flowless: Extracting Densest Subgraphs Without Flow Computations." WWW '20: Proceedings of The Web Conference 2020. The Web Conference 2020. Taipei, 2020-04-20 - 2020-04-24. https://doi.org/10.1145/3366423.3380140
dc.identifier.urihttps://hdl.handle.net/2144/41396
dc.description.abstractThe 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.en_US
dc.format.extentp. 573 - 583en_US
dc.language.isoen_US
dc.publisherAssociation for Computing Machineryen_US
dc.relation.ispartofWWW '20: Proceedings of The Web Conference 2020
dc.titleFlowless: extracting densest subgraphs without flow computationsen_US
dc.typeConference materialsen_US
dc.description.versionFirst author draften_US
dc.identifier.doi10.1145/3366423.3380140
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US
dc.identifier.mycv540400


This item appears in the following Collection(s)

Show simple item record