Dense subgraph

An example of a graph

G

with density

d_{G}=1.375

and its densest subgraph induced by the vertices

b,c,d,e

and

h

in red with density

1.4

In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let $G=(E,V)$ be an undirected graph and let $S=(E_{S},V_{S})$ be a subgraph of $G$ . Then the density of $S$ is defined to be $d(S)={|E_{S}| \over |V_{S}|}$ .

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.

Densest $k$ subgraph

There are many variations on the densest subgraph problem. One of them is the densest $k$ subgraph problem, where the objective is to find the maximum density subgraph on exactly $k$ vertices. This problem generalizes the clique problem and is thus NP-hard in general graphs. There exists a polynomial algorithm approximating the densest $k$ subgraph within a ratio of $n^{1/4+\epsilon }$ for every $\epsilon >0$ ,^[1] while it does not admit PTAS unless $NP\subseteq \bigcap _{\epsilon >0}BPTIME(2^{n^{\epsilon }})$ .^[2] The problem remains NP-hard in bipartite graphs and chordal graphs but is polynomial for trees and split graphs.^[3] It is open whether the problem is NP-hard or polynomial in (proper) interval graphs and planar graphs; however, a variation of the problem in which the subgraph is required to be connected is NP-hard in planar graphs.^[4]

Densest at most $k$ subgraph

The objective of the densest at most $k$ problem is to find the maximum density subgraph on at most $k$ vertices. Anderson and Chellapilla showed that if there exists an $\alpha$ approximation for this problem then that will lead to an $\Theta (\alpha ^{2})$ approximation for the densest $k$ subgraph problem.

Densest at least $k$ subgraph

The densest at least $k$ problem is defined similarly to the densest at most $k$ subgraph problem. There is a 2-approximation due to Anderson. It is also NP-complete.^[5]

$K$ -clique densest subgraph

Charalampos Tsourakakis introduced the $k$ -clique densest subgraph problem. This variation of the densest subgraph problem aims to maximize the average number of induced $k$ cliques $d_{k}(S)={|C_{k}(S)| \over |V_{S}|}$ , where $C_{k}(S)$ is the set of $k$ -cliques induced by $S$ . Notice that the densest subgraph problem is obtained as a special case for $k=2$ . This generalization provides an empirically successful poly-time approach for extracting large near-cliques from large-scale real-world networks.

References

↑ Bhaskara, Aditya; Charikar, Moses; Chlamtáč, Eden; Feige, Uriel; Vijayaraghavan, Aravindan (2010), "Detecting high log-densities—an $O (n 1/4)$ approximation for densest $k$ -subgraph", STOC'10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, pp. 201–210, doi:10.1145/1806689.1806719, MR 2743268 .
↑ Khot, Subhash (2006), "Ruling out PTAS for graph min-bisection, dense $k$ -subgraph, and bipartite clique", SIAM Journal on Computing, 36 (4): 1025–1071, CiteSeerX 10.1.1.114.3324, doi:10.1137/S0097539705447037, MR 2272270 .
↑ Corneil, D. G.; Perl, Y. (1984), "Clustering and domination in perfect graphs", Discrete Applied Mathematics, 9 (1): 27–39, doi:10.1016/0166-218X(84)90088-X, MR 754426 .
↑ Keil, J. Mark; Brecht, Timothy B. (1991), "The complexity of clustering in planar graphs" (PDF), Journal of Combinatorial Mathematics and Combinatorial Computing, 9: 155–159, MR 1111849 .
↑ Khuller, Samir; Saha, Barna (2009), "On finding dense subgraphs" (PDF), Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, Lecture Notes in Computer Science, 5555, Berlin: Springer-Verlag, pp. 597–608, doi:10.1007/978-3-642-02927-1_50, MR 2544878

Additional reading

Anderson, R.; Chellapilla, K. (2009), "Finding dense subgraphs with size bounds", WAW: 25–36 .
Anderson, R. (2007), Finding large and small dense subgraphs, arXiv:cs/0702032 .
Feige, U.; Kortsarz, G.; Peleg, D. (1997), "The dense $k$ -subgraph problem", Algorithmica, 29: 410–421, doi:10.1007/s004530010050 .
Goldberg, A. V. (1984), "Finding a maximum density subgraph", Technical report .
Tsourakakis, C. (2015), "The $k$ -clique densest subgraph problem", The International World Wide Web Conference, doi:10.1145/2736277.2741098 .

This article is issued from Wikipedia - version of the 11/13/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Dense subgraph

Densest k subgraph

Densest at most k subgraph

Densest at least k subgraph

K-clique densest subgraph