Detecting hidden cliques from noisy observations

In this paper we present a methodology to uncover hidden cliques/communities among a set of nodes when observations of their relationships or connectivities are noisy. Existing literature in community detection typically starts with the assumption that the statistical properties of community structure is known a priori, as well as the number of communities, so the task at hand is solely to partition the set into the given number of groups. In practice neither assumption is necessarily true. Motivated by this, we set out to determine a detectability condition (from spectral analysis) prior to performing the partitioning task, and further illustrate how to combine this detectability condition with clustering algorithms to arrive at desirable partitions without a priori information on the clique structure. We validate our results via simulation and make comparison with existing heuristics to demonstrate its advantages.