Technical Perspective of Efficient Directed Densest Subgraph Discovery

摘要

Consider a directed graph G = (V, E). Given two (possibly overlapping) subsets S,T ⊂　V, denote by E(S, T) the set of edges (s, t) ∈ E with s ∈ S and t ∈ T and by G(S, T) the subgraph with S U T as the vertex set and E(S, T) as the edge set. The density of G(S,T) equals |E(S,T)||S‖T|~(1/2). The directed densest subgraph (DDS) problem is to return a pair (S, T) maximizing the density of G(S,T).