Cálculo de resistência efetiva eficiente e comprovadamente eficaz em grandes grafos: Uma abordagem baseada em índice

A resistência efetiva (ER) é uma métrica fundamental para medir semelhanças de nós em um grafo e encontra aplicações em vários domínios, incluindo agrupamento de grafos, sistemas de recomendação, previsão de link e redes neurais gráficas. O algoritmo de ponta para calcular a resistência efetiva depende de uma técnica de marco, que envolve selecionar um nó que é fácil de alcançar por todos os outros nós como um marco. O desempenho dessa técnica depende fortemente do nó marco escolhido. No entanto, em muitos grafos da vida real, não é sempre possível encontrar um nó marco facilmente acessível, o que pode prejudicar significativamente a eficiência do algoritmo. Para superar esse problema, propomos uma nova técnica de múltiplos marcos que envolve selecionar um conjunto de nós marco V l de forma que os outros nós no grafo possam facilmente alcançar qualquer um dos nós marco em V l. Especificamente, primeiro propomos várias novas fórmulas para calcular ER com múltiplos marcos, utilizando o conceito de complemento de Schur. Essas novas fórmulas nos permitem pré-computar e manter várias matrizes de pequeno tamanho relacionadas a V l como um índice compacto. Com essa poderosa técnica de índice, demonstramos que tanto consultas ER de par único quanto de origem única podem ser respondidas de forma eficiente usando uma amostragem de passeio aleatório V l absorvida ou técnica de empurrar V l absorvida recentemente desenvolvida. Uma análise teórica abrangente mostra que todos os algoritmos baseados em índice propostos alcançam garantias de desempenho comprováveis para consultas ER de par único e de origem única. Experimentos extensivos em 5 conjuntos de dados da vida real demonstram a alta eficiência de nossas técnicas de índice baseadas em múltiplos marcos. Por exemplo, nossos algoritmos, com um tamanho de índice de 1,5 GB, podem ser até 4 ordens de magnitude mais rápidos do que os algoritmos de ponta, mantendo a mesma precisão em uma grande rede viária.