{"id":"arxiv/2607.11333","url":"https://arxiv.org/abs/2607.11333","tags":["cs.DS","cs.DM","math.CO","math.SP"],"score":0,"title":"Finding Nearly-Periodic Components in Digraphs and Markov Chains from the Spectrum of Rotated Laplacian Matrices","domain":"cs.DS","source":"arxiv","authors":["Salil Vadhan","Jiyu Zhang"],"reviews":0,"subject":"cs.DS","summary":"Inspired by recent advances in notions of spectral approximation of digraphs [Ahm+20], we study spectral algorithms for finding periodic structures in digraphs via the spectrum of a class of rotated Laplacian matrices. This class of Laplacian matrices was previously studied by Lange, Liu, Peyerimhoff, and Post [Lan+15]. We consider a notion of periodicity ratio that generalizes the bipartiteness ratio of Trevisan [Tre09], and show that it is closely related to the spectrum of rotated Laplacian matrices. In particular, if the digraph is strongly connected and represents a Markov chain, this…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}