Loading Events

« All Events

Colloquium – Shweta Jain

December 3 @ 11:00 am - 12:00 pm

Shweta Jain
Computing Innovation Fellow
University of Utah

December 3, 2021
11:00am
3115 MEB

Join Zoom Meeting
https://utah.zoom.us/j/94140467542?pwd=dnNvUnVIOE1mZXZucDh0YnNCSjNNQT09

Meeting ID: 941 4046 7542
Passcode: 433398

Counting cliques in real-world graphs

Cliques are important structures in network science that have been used in spam detection, community detection and many other applications. Obtaining the counts of k-cliques in real-world graphs with millions of nodes and edges is a challenging problem due to combinatorial explosion. Essentially, as k increases, the number of k-cliques goes up exponentially. Most techniques are (typically) able to count k-cliques for only up to k=5.

In this talk, I will present two algorithms for obtaining k-clique counts that in practice gave orders of magnitude speedup even over other parallel algorithms and improved the worst case running time of clique counting from O(2^n) to O(3^(n/3)) (these papers won the Best Paper Awards at WWW and WSDM, respectively). I will also highlight some recent results that provide theoretical justification for the empirical success of these algorithms in c-closed graphs (a graph class inspired by real-world graphs)

Joint work with Balaram Behera, Edin Husić, Tim Roughgarden and C. Seshadhri

Details

Date:
December 3
Time:
11:00 am - 12:00 pm
Event Category:

Venue

3115 MEB