Interseção de Vizinhança em Grafos via Amostragem de P3 - Ribeiro, Vinícius M.; Vignatti, André L. (Anais do Encontro de Teoria da Computação (ETC), 2025)
A interseção de vizinhança é uma métrica fundamental em análise de redes sociais e mineração de dados, e desempenha um papel central no cálculo de métricas e medidas de similaridade. Nesse artigo, propomos um algoritmo aleatorizado eficiente, utilizando amostragem de P 3 , para calcular a interseção de vizinhança para todas as combinações de pares de vértices em um grafo. Com probabilidade de pelo menos 1−δ, garantimos que todas as aproximações do algoritmo estão a uma distância de no máximo ϵ de seu valor real. Aplicamos técnicas da teoria de aprendizado computacional para obter um tamanho de amostra independente de qualquer propriedade quantitativa do grafo.