CENTRALIDADE DE ARESTAS: APLICAÇÕES NO PROBLEMA DA ÁRVORE MÍNIMA DE STEINER E RELAÇÕES COM A CENTRALIDADE DE VÉRTICES.

Abstract

In the study of Graph Theory, centrality analysis has been a fundamental tool for understanding the importance of vertices within network structures. In 2001, Girvan and Newman [2001] proposed the study of edge centrality through the concept of edge betweenness centrality. In this work, we explore two potential applications of edge centrality, considering both edge betweenness centrality and edge closeness centrality, which is defined later. The first application investigates the frequency with which the most central edges are associated with the most central vertices in a graph according to their respective centrality measures. Initially, we use the betweenness measure as a starting point for the analysis. As a result, we identify particular characteristics in balanced double broom graphs. Based on this finding, we study the association between the most central edges and the most central vertices in balanced double broom graphs according to their respective betweenness and closeness centrality measures. The second application proposes two new variations of the KMB heuristic, one of the most widely used methods to solve the Minimum Steiner Tree Problem, utilizing the concept of edge closeness centrality. These variations were computationally tested on graphs from the SteinLib repository to compare their performances with each other and against the original KMB heuristic.

No estudo da Teoria dos Grafos, a análise de centralidade tem sido uma ferramenta fundamental para compreender a importância de vértices nas estruturas de rede. Em 2001, Girvan e Newman [2001] propuseram o estudo da centralidade de arestas, através do conceito de centralidade de intermediação de arestas. Neste trabalho estudamos duas potencialidades da centralidade de arestas, considerando tanto a centralidade de intermediação de arestas como também a centralidade de proximidade de arestas, posteriormente definida. A primeira trata-se de uma investigação sobre a frequência em que as arestas mais centrais estão associadas aos vértices mais centrais em um grafo de acordo com suas respectivas medidas de centralidade. Inicialmente, utilizamos a medida de intermediação como ponto de partida para análise. Como resultado, identificamos particularidades em grafos do tipo vassoura dupla equilibrada. A partir desse resultado, estudamos a associação entre as arestas mais centrais e os vértices mais centrais em grafos vassoura dupla equilibrada de acordo com suas respectivas medidas de centralidade de intermediação e de proximidade. A segunda potencialidade é uma proposta de duas novas variações da heurística KMB, um dos métodos mais utilizados para resolver o Problema da Árvore de Steiner Mínima, utilizando o conceito de centralidade de proximidade de arestas. Essas variações foram testadas computacionalmente em grafos do repositório SteinLib, com o intuito de comparar seus desempenhos entre si e em relação à heurística KMB original.