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. Further, we implemented a distributed version of our algorithm using the MapReduce framework scaling up to 800 cores on Amazon EC2. This allowed us to find dense clusters in massive graphs with billions of edges.

Our paper will appear in ICML 2014.
http://users.ece.utexas.edu/~dimakis/DKS_ICML.pdf