Information-Theoretic Thresholds for Planted Dense Cycles

The Watts-Strogatz small-world model has been an influential random graph model since its proposal in 1998 due to the ubiquity of the small-world phenomenon in complex networks [WS98, Wat04]. In this model, there are n vertices with latent positions on a circle, and the vertices are more likely to be connected to their k-nearest geometric neighbors than to more distant vertices. In other words, a denser cycle of length n and width k is "planted" in the sparser ambient random graph on n vertices. Informally, the small-world model can also be viewed as an interpolation between a random geometric graph [Pen03], where edges exist only between vertices with nearby locations on a circle, and an Erdős-Rényi graph [ER59], where edges are random and independent. As a consequence, a small-world network tends to have a high clustering coefficient due to the geometry while preserving low distances between vertices in a random graph. While there has been extensive literature on small-world networks and geometric graphs, the associated statistical problems, such as detection and recovery of the latent geometry from the observed random graph, have only gained attention more recently.