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.

Cited By

• http://scholar.google.com/scholar?q=%222009%22+Finding+Dense+Subgraphs+with+Size+Bounds
• http://dl.acm.org/citation.cfm?id=1506844.1506848&preflayout=flat#citedby

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