Efficient approximations of common neighbors in large networks via sampling

Abstract

Resumo : Vizinhos Comuns (CN) é uma quantidade fundamental na análise de redes e mineração de dados, servindo de base para várias métricas e medidas de similaridade. Neste trabalho, abordamos o problema de contar aproximadamente o número de vizinhos comuns para todos os pares de vértices em um grafo. Como o cálculo exato aumenta com o tamanho do grafo, ele se torna computacionalmente proibitivo para redes de larga escala. Para superar essa limitação, propomos algoritmos eficientes baseados em amostragem que aproximam CN com fortes garantias probabilísticas. Com base nos resultados da teoria da dimensão VC, nossos algoritmos obtêm tamanhos de amostra que são independentes do tamanho do grafo e dependem apenas de seu grau máximo, oferecendo uma solução prática e escalável para análise de redes de larga escala. Introduzimos seis algoritmos, categorizados por normalização (normalizado ou não normalizado) e método de amostragem (baseado em vértice, aresta e wedge). Três algoritmos calculam CN normalizado com garantias de erro aditivo, enquanto os outros lidam com CN não normalizado com garantias de erro multiplicativo. Resultados experimentais demonstram que nossos algoritmos alcançam acelerações substanciais em relação aos métodos exatos, mantendo alta precisão

Abstract : Common Neighbors (CN) is a fundamental quantity in network analysis and data mining, underpinning various metrics and similarity measures. In this paper, we address the problem of approximately counting the number of common neighbors for all vertex pairs in a graph. Since exact computation scales with the size of the graph, it becomes computationally prohibitive for large-scale networks. To overcome this limitation, we propose efficient sampling-based algorithms that approximate CN with strong probabilistic guarantees. Building on results from VC-dimension theory, our algorithms obtain sample sizes that are independent of the size of the graph and depend only on its maximum degree, offering a practical and scalable solution for large-scale network analysis. We introduce six algorithms, categorized by normalization (normalized or unnormalized) and sampling method (vertex-, edge- and wedge-based). Three algorithms compute normalized CN with additive error guarantees, while the others handle unnormalized CN with multiplicative error guarantees. Experimental results demonstrate that our algorithms achieve substantial speedups over exact methods while maintaining high accuracy