Local Partitioning and hidden Cliques in Massive Graphs 

A local partitioning algorithm finds a “community” for a given node in a large graph (i.e., a set of nodes with relatively few bonds to the outside) by examining only a small part of the entire graph. I will describe the “evolving set” partitioning algorithm, developed jointly with Reid Andersen, which is based on earlier work with Ben Morris on mixing times for Markov chains.   In the second part of the talk, I’ll present progress on the “hidden clique” problem: locating a fully connected “clique” in a typical dense graph on n nodes. Currently, cliques can be found in polynomial time only if their size exceeds the square root of n. The first technique to do this, analyzed by Alon et al, was spectral; in joint work with Yael Dekel and Ori Gurel-Gurevich, we found the first algorithm that identifies the hidden clique in quadratic time with high probability. Perhaps surprisingly, it is simpler. Whether smaller hidden cliques (e.g., of size the cube root of n) can be detected remains a tantalizing open problem.

Reception at 4:30pm in the 3rd floor lounge of Hanes Hall

Youtube videos: Lec1_1, Lec1_2

Share this Event