graph algorithms

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.

WNCG Ph.D Students Dimitris Papailiopoulos and Yannis Mitliagkas, along with WNCG Professors Alex Dimakis and Constantine Caramanis, have developed an efficient low-rank framework for finding dense components of graphs with billions of connections.