Algorithms Seminar

Enumerating Patterns in Social Networks - A Distribution-Free Model

September 28, -
Speaker(s): Fan Wei


Fox et al introduced the model of c-closed graphs, a distribution-free model motivated by one of the most universal signatures of social networks, triadic closure. Even though enumerating maximal cliques in an arbitrary network can run in exponential time, it is known that for c-closed graph, enumerating maximal cliques and maximal complete bipartite graphs is always fast, i.e., with complexity being polynomial in the number of vertices in the network. In this work, we investigate further by enumerating maximal blow-ups of an arbitrary graph H in c-closed graphs. We prove that given any finite graph H, the number of maximal blow-ups of H in any c-closed graph on n vertices is always at most polynomial in n. When considering maximal induced blow-ups of a finite graph H, we provide a characterization of graphs H when the bound is always polynomial in n. A similar general theorem is also proved when H is infinite.

Speaker Bio

Fan Wei is Assistant Professor of Mathematics and Assistant Professor of Computer Science at Duke University. Previously an instructor in the Department of Mathematics at Princeton University, she also conducted research at Microsoft Research New England and Microsoft Research Redmond Theory group. She received a PhD in mathematics from Stanford University, a bachelors degree in Mathematics from MIT, and a Master of Advanced Study with Distinction from Cambridge University, UK. Dr. Wei's research interests include extremal combinatorics, probabilistic combinatorics, and applications of combinatorics to computer science. She is especially interested in using tools from probability, analysis and algebra to analyze large networks or other combinatorial objects.


LSRC D344 or join virtually via Zoom


Yiheng Shen