2009 FindingDenseSubgraphswithSizeBo
- (Andersen & Chellapilla, 2009) ⇒ Reid Andersen, and Kumar Chellapilla. (2009). “Finding Dense Subgraphs with Size Bounds.” In: Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph. ISBN:978-3-540-95994-6 doi:10.1007/978-3-540-95995-3_3
Subject Headings: Dense Subgraph Finding.
Notes
Cited By
Quotes
Abstract
We consider the problem of finding dense subgraphs with specified upper or lower bounds on the number of vertices. We introduce two optimization problems: the densest at-least-k-subgraph problem (dalks), which is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (damks), which is defined similarly. These problems are relaxed versions of the well-known densest k-subgraph problem (dks), which is to find the densest subgraph with exactly k vertices. Our main result is that dalks can be approximated efficiently, even for web-scale graphs. We give a (1/3) - approximation algorithm for dalks that is based on the core decomposition of a graph, and that runs in time O(m + n)), where n is the number of nodes and m is the number of edges. In contrast, we show that damks is nearly as hard to approximate as the densest k-subgraph problem, for which no good approximation algorithm is known. In particular, we show that if there exists a polynomial time approximation algorithm for damks with approximation ratio γ, then there is a polynomial time approximation algorithm for dks with approximation ratio γ 2/8. In the experimental section, we test the algorithm for dalks on large publicly available web graphs. We observe that, in addition to producing near-optimal solutions for dalks, the algorithm also produces near-optimal solutions for dks for nearly all values of k.
References
;
Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|
2009 FindingDenseSubgraphswithSizeBo | Kumar Chellapilla Reid Andersen | Finding Dense Subgraphs with Size Bounds | 10.1007/978-3-540-95995-3_3 | 2009 |