- This event has passed.
Colloquium – Shweta Jain
December 3, 2021 @ 11:00 am - 12:00 pm
Computing Innovation Fellow
University of Utah
December 3, 2021
Join Zoom Meeting
Meeting ID: 941 4046 7542
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