Title :
On hard limits of eigen-analysis based planted clique detection
Author :
Nadakuditi, Raj Rao
Author_Institution :
Dept. of EECS, Univ. of Michigan, Ann Arbor, MI, USA
Abstract :
We study the problem of detecting or discovering a planted clique embedded in a random graph. Using recent results from random matrix theory, we demonstrate the presence of a phase transition in eigen-analysis based methods for planted clique detection. The transition separates a regime in which eigen-analysis based methods will successfully detect the planted clique and the associated vertices from one in which the planted clique is present but is undetectable. We validate the prediction with numerical simulations.
Keywords :
eigenvalues and eigenfunctions; graph theory; matrix algebra; numerical analysis; phase transformations; eigen-analysis; numerical simulation; phase transition; planted clique detection; random graph; random matrix theory; Algorithm design and analysis; Approximation algorithms; Communities; Eigenvalues and eigenfunctions; Numerical simulation; Sparse matrices; Symmetric matrices; network; planted clique; random matrix theory;
Conference_Titel :
Statistical Signal Processing Workshop (SSP), 2012 IEEE
Conference_Location :
Ann Arbor, MI
Print_ISBN :
978-1-4673-0182-4
Electronic_ISBN :
pending
DOI :
10.1109/SSP.2012.6319639
