Dense Subgraph
Jump to navigation
Jump to search
A Dense Subgraph is a subgraph with ...
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/dense_subgraph Retrieved:2015-9-8.
- In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let [math]\displaystyle{ G=(E,V) }[/math] be an undirected graph and let [math]\displaystyle{ S=(E_S,V_S) }[/math] be a subgraph of [math]\displaystyle{ G }[/math] . Then the density of [math]\displaystyle{ S }[/math] is defined to be [math]\displaystyle{ d_S = {|E_S|\over|V_S|} }[/math] .
The densest subgraph problem is that of finding a subgraph of maximum density. In 1984, Andrew V. Goldberg developed a polynomial time algorithm to find the maximum density subgraph using a max flow technique.
- In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let [math]\displaystyle{ G=(E,V) }[/math] be an undirected graph and let [math]\displaystyle{ S=(E_S,V_S) }[/math] be a subgraph of [math]\displaystyle{ G }[/math] . Then the density of [math]\displaystyle{ S }[/math] is defined to be [math]\displaystyle{ d_S = {|E_S|\over|V_S|} }[/math] .
2013
- (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
- QUOTE: Finding dense subgraphs is an important graph-mining task with many applications.
2001
- (Feige et al., 2001) ⇒ Uriel Feige, David Peleg, and Guy Kortsarz. (2001). “The Dense K-subgraph Problem." Algorithmica 29, no. 3
- QUOTE: This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O (n δ), for some δ < 1/3.