Finding the largest completely connected subgraph in a random graph has always been an attractive problem because the "hard" regime, between solutions which are found by easy local search methods, and the upper limits of solutions known to exist but not easily discovered is large. The challenge of solving this problem is usually posed in asymptotic terms, yet at the scales typical of modern big data this kind of search is in a finite-sized regime, with much interesting structure. We have studied both simple and exotic approaches for discovering both naturally occurring and "planted" solutions, using spectral and belief propagation methods, as well as greedy local search...
Federico Ricci Tersenghi