Postdoctoral Scholar
University of Illinois Urbana-Champaign
PhD '20 University of California, Santa Cruz
Areas of Interest
- Artificial Intelligence
- Theory
Poster
Counting cliques in real-world graphs
Abstract
Cliques are important structures in network science that have been used in numerous applications including spam detection, graph analysis, graph modeling, community detection among others. 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. Existing techniques are (typically) able to count k-cliques for only up to k=5. In this poster, I will present two algorithms, TuránShadow and Pivoter, for obtaining k-clique counts that vastly improve the state of the art, both in theory and in practice. These papers won the Best Paper Awards at WWW, 2017 and WSDM, 2020, respectively.
Bio
Shweta Jain received her Ph.D. in Computer Science from the University of California, Santa Cruz where she was advised by Prof. Seshadhri Comandur. She also has a Masters degree in Computer Science from the University of Chicago. Her work aims to bridge the gap between practice and theory by designing provably efficient algorithms that work well in practice, esp. graph algorithms, and algorithms for massive data. Her work has received Best Paper Awards at WWW and WSDM.
