graph algorithms

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.

Community Detection in Massive 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.

Subscribe to RSS - graph algorithms