DOI
https://doi.org/10.11606/D.45.2022.tde-30012023-194317
Documento
Autor
Nome completo
Félix Yowtang Liu
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2023
Kohayakawa, Yoshiharu (Presidente)
Griffiths, Simon Richard
Hoppen, Carlos
Título em português
Uma análise espectral do grafo com clique plantada
Palavras-chave em português
Análise espectral
Clique escondida
Lei semicircular
Teoria de matrizes aleatórias
Teoria de perturbação de matrizes
Resumo em português
Título em inglês
A spectral analysis of the planted clique graph
Palavras-chave em inglês
Hidden clique
Matrix perturbation theory
Random matrix theory
Semicircle law
Spectral analysis
Resumo em inglês
The planted clique graph G(n, p, k) is the random graph on n vertices in which each edge is added independently with probability p and then a k-set of its vertices is chosen uniformly and made into a clique - the planted clique. This model was suggested independently by Jerrum (1992) and Kucera (1995) to describe the planted clique problem, which consists in recovering the planted clique of a graph drawn from G(n, p, k). A first development since the problem was proposed was provided by Alon-Krivelevich-Sudakov (1998): An efficient spectral algorithm that almost surely finds the planted clique of G(n, 1/2, k), with k >= 10 n^1/2. Since then, other algorithms were found for k = Omega(n^1/2); but the problem remains unsolved for k = o(n^1/2); a fact that has been used as a hardness assumption in several works. The algorithm presented by Alon-Krivelevich-Sudakov relies on the behavior of the largest eigenvalues of A and on properties of the eigenvector of its second largest eigenvalue. Similar phenomena was observed by Nadakuditi (2012) when considering the B = A - E matrix, where E is the expected matrix of A with k = 0. While Alon-Krivelevich-Sudakov's analysis does not provide insights that explain the behavior of the spectrum of A, Nadakuditi takes some steps towards an explanation by showing a relationship between B and a particular class of zero-mean symmetric random matrices whose spectrum is well studied - the Wigner matrices. The approach followed by Nadakuditi was described and exemplified by Nadakuditi-Newman (2012), when it was presented as a manner to study the spectrum of the so-called stochastic block model, which generalizes many random graphs with planted structures. Inspired by Nadakuditi-Newman's approach, we show how the spectral behavior of A and B can be explained by regarding those matrices as the result of rank-one perturbations over Wigner matrices. Besides studying those matrices under the G(n, p, k) distribution, we also consider analogous matrices for a variant with loops of the planted clique graph. Furthermore, we offer a more detailed and complete characterization of the spectrum of those matrices under k = O((n log n)^1/2) and kq >= c(pqn)^1/2, with c > 3; showing that besides a few of the largest and smallest eigenvalues, all the others almost surely are distributed according to a semicircular law - which is the characteristic distribution of the spectra of Wigner matrices.

AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
plantedclique.pdf (799.78 Kbytes)
Data de Publicação
2023-01-31

AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI