A Personalized PageRank Fingerprint Framework for Seedless Graph Matching

Grafos são usados para modelar problemas e codificar relacionamentos entre entidades em vários contextos, abrangendo estudos que vão desde redes sociais até interações biológicas. Um problema clássico em teoria dos grafos envolve encontrar o mapeamento de vértices entre dois grafos que exibem maior similaridade. Esse problema é conhecido como emparelhamento de grafos, também referido como alinhamento de redes. O emparelhamento de grafos depende fortemente da estrutura da rede e surge em contextos diversos devido à importância de identificar estruturas semelhantes em redes. Nesta dissertação, apresenta-se uma nova framework que não requer sementes, usa representações baseadas em Personalized PageRank, e utiliza um algoritmo em rodadas para mapear gradualmente os nós. Em cada rodada, o algoritmo define pares de âncoras que irão aprimorar as representações dos nós para, então, decidir os emparelhamentos na rodada subsequente. Este trabalho formaliza a definição de uma nova representação de vértices com base no Personalized PageRank, bem como uma métrica de similaridade para comparar vértices usando essa representação introduzida. Os resultados de avaliação demonstram valores de acurácia de até 97% em média, considerando emparelhamentos corretos em pares de grafos que foram submetidos a um processo de edge sampling com uma probabilidade de remoção de aresta de 20% no modelo Barabási–Albert.