RELAÇÕES ENTRE O INCREMENTO DA CONECTIVIDADE ALGÉBRICA E A CONFIABILIDADE DE UMA REDE

Abstract

Algebraic connectivity is a widely discussed measure in the field of Spectral Graph Theory, since it is related to several graph invariants such as maximal cut, vertex connectivity, toughness, isoperimetric number, besides being associated, by several authors, within network robustness, among other approaches. Therefore, it is possible to find many papers in the literature which aim to increase algebraic connectivity through the insertion of new edges, or through the insertion of new vertices. On the other hand, the reliability of a network represents the faculty of a network to remain connected, either after the failure of one or a subset of its vertices and/or edges. Thus, reliability is a significant measure for several real applications in the field of networks analysis, such as transport networks, energy transmission and communication, since keeping all vertices connected is essential for the system’s operation. However, while algebraic connectivity and reliability have close concepts, the literature lacks approaches which relate them both, either with a theoretical-algebraic approach, but also regarding to real scenarios simulation. This work aims to evaluate the relations between these two measures through the insertion of new edges. Therefore, it is possible to study the impact of the increase in algebraic connectivity and reliability. In order to achieve this goal, a previous study is carried out regarding edges insertion strategies that already exist in the literature which aim at maximizing algebraic connectivity. Later, computational simulations are performed based on best strategies in order to analyze the variation of the network reliability according to the variation regarding algebraic connectivity.

A conectividade algébrica de um grafo é uma medida amplamente abordada na Teoria Espectral de Grafos, pois está relacionada com diversas invariantes do grafo como por exemplo, corte maximal, conectividade de vértices, toughness, número isoperimétrico, além de ser associada, por muitos autores, com a robustez da rede, dentre outras diversas abordagens. Por isso, podem ser encontrados diversos trabalhos na literatura que tem como objetivo o aumento da conectividade algébrica da rede, tanto através da inserção de novas arestas, como pela inserção de novos vértices. Por outro lado, a confiabilidade de uma rede representa a capacidade da rede permanecer conexa, seja após a falha de um ou de um subconjunto de seus vértices e/ou arestas. Desta forma, a confiabilidade é uma medida significativamente importante para diversos aplicações reais na análise de redes, como, por exemplo, redes de transporte, transmissão de energia e comunicação, cuja necessidade de manter todos seus vértices conectados é fundamental para o pleno funcionamento do sistema modelado pelo grafo. No entanto, embora a conectividade algébrica e a confiabilidade tenham conceitos próximos, a literatura carece de abordagens que relacione ambos, tanto do ponto de vista teórico-algébrico, como com relação à simulações em casos reais. Este trabalho tem como objetivo avaliar as relações entre estas duas medidas, através da inserção de arestas no grafo. Desta maneira, é possível estudar o impacto que o incremento no valor da conectividade algébrica gera na confiabilidade. Para isso, é realizado um estudo prévio a respeito das diversas estratégias de inserção de arestas existentes na literatura que objetivam a maximização da conectividade algébrica. Posteriormente, são realizadas simulações computacionais baseadas nas melhores estratégias a fim de analisar o comportamento da variação da confiabilidade da rede conforme a variação no valor da conectividade algébrica.