graph algorithms

WNCG Student Wins Award for Paper on Epidemic Processes

Ph.D. student Jessica Hoffmann received second place in the INFORMS Nicholson Student Paper competition. She received the award for her recent paper "Learning Graphs from Noisy Epidemic Cascades" with her advisor, WNCG professor Constantine Caramanis.

Epidemics are a powerful framework for modeling human and computer viruses, as well as influence, rumors, information and disinformation. Hoffmann’s research develops algorithms to solve an inverse problem on graphs, in order to understand the precise spreading mechanisms.

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