Interseção de Vizinhança em Grafos via Amostragem de P3
Resumo
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 P3, 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.
Referências
Besta, M., Kanakagiri, R., Kwasniewski, G., Ausavarungnirun, R., Beránek, J., Kanellopoulos, K., Janda, K., Vonarburg-Shmaria, Z., Gianinazzi, L., Stefan, I., Luna, J. G., Golinowski, J., Copik, M., Kapp-Schwoerer, L., Di Girolamo, S., Blach, N., Konieczny, M., Mutlu, O., and Hoefler, T. (2021). Sisa: Set-centric instruction set architecture for graph mining on processing-in-memory systems. In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, page 282–297, New York, NY, USA. Association for Computing Machinery.
Besta, M., Miglioli, C., Labini, P. S., Tětek, J., Iff, P., Kanakagiri, R., Ashkboos, S., Janda, K., Podstawski, M., Kwaśniewski, G., Gleinig, N., Vella, F., Mutlu, O., and Hoefler, T. (2022). Probgraph: high-performance and high-accuracy graph mining with probabilistic set representations. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Dallas, Texas. IEEE Press.
Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, USA.
Har-Peled, S. and Sharir, M. (2011). Relative (p, ϵ)-approximations in geometry. Discrete Comput. Geom., 45(3):462–496.
Menczer, F., Fortunato, S., and Davis, C. (2020). A First Course in Network Science. Cambridge University Press, UK.
Newman, M. (2010). Networks: An Introduction. Oxford University Press, Inc., UK.
Ribeiro, V. M. and Vignatti, A. L. (2025). Efficient approximations of neighborhood intersection in large graphs via sampling. Technical report, Federal University of Paraná.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, UK.
Walker, A. (1974). New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters, 10:127–128.
Besta, M., Miglioli, C., Labini, P. S., Tětek, J., Iff, P., Kanakagiri, R., Ashkboos, S., Janda, K., Podstawski, M., Kwaśniewski, G., Gleinig, N., Vella, F., Mutlu, O., and Hoefler, T. (2022). Probgraph: high-performance and high-accuracy graph mining with probabilistic set representations. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Dallas, Texas. IEEE Press.
Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, USA.
Har-Peled, S. and Sharir, M. (2011). Relative (p, ϵ)-approximations in geometry. Discrete Comput. Geom., 45(3):462–496.
Menczer, F., Fortunato, S., and Davis, C. (2020). A First Course in Network Science. Cambridge University Press, UK.
Newman, M. (2010). Networks: An Introduction. Oxford University Press, Inc., UK.
Ribeiro, V. M. and Vignatti, A. L. (2025). Efficient approximations of neighborhood intersection in large graphs via sampling. Technical report, Federal University of Paraná.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, UK.
Walker, A. (1974). New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters, 10:127–128.
Publicado
20/07/2025
Como Citar
RIBEIRO, Vinícius M.; VIGNATTI, André L..
Interseção de Vizinhança em Grafos via Amostragem de P3. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 11-15.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.7446.
