Finding dense subgraphs in massive graphs.
Given a large graph and a parameter k we are interested in detecting dense subgraphs of size k. The Densest-k-Subgraph (DkS) problem is fundamental for many applications including graph and cluster analysis, cyber-community detection and computer security and spam detection. Our research group has developed a novel algorithm with provable approximation guarantees for DkS. Our algorithm significantly outpeforms the previous state of the art for several types of real-world graphs ranging from social networks to communication graphs.