2013 DenserThantheDensestSubgraphExt

• (Tsourakakis et al., 2013) ⇒ Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. (2013). “Denser Than the Densest Subgraph: Extracting Optimal Quasi-cliques with Quality Guarantees.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487645

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Denser+Than+the+Densest+Subgraph%3A+Extracting+Optimal+Quasi-cliques+with+Quality+Guarantees
• http://dl.acm.org/citation.cfm?id=2487575.2487645&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; dense subgraph; graph mining; quasi-clique

Abstract

Finding dense subgraphs is an important graph-mining task with many applications. Given that the direct optimization of edge density is not meaningful, as even a single edge achieves maximum density, research has focused on optimizing alternative density functions. A very popular among such functions is the average degree, whose maximization leads to the well-known densest-subgraph notion. Surprisingly enough, however, densest subgraphs are typically large graphs, with small edge density and large diameter.

In this paper, we define a novel graph density function, which gives subgraphs of much higher quality than densest subgraphs: the graphs found by our method are compact, dense, and with smaller diameter. We show that the proposed function can be derived from a general framework, which includes other important density functions as subcases and for which we show interesting general theoretical properties. To optimize the proposed function we provide an additive approximation algorithm and a local-search heuristic. Both algorithms are very efficient and scale well to large graphs.

We evaluate our algorithms on real and synthetic datasets, and we also devise several application studies as variants of our original problem. When compared with the method that finds the subgraph of the largest average degree, our algorithms return denser subgraphs with smaller diameter. Finally, we discuss new interesting research directions that our problem leaves open.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 DenserThantheDensestSubgraphExt	Francesco Bonchi Aristides Gionis Francesco Gullo Charalampos Tsourakakis Maria Tsiarli			Denser Than the Densest Subgraph: Extracting Optimal Quasi-cliques with Quality Guarantees				10.1145/2487575.2487645		2013