Heurísticas espectrais aplicadas à análise de confiabilidade de grafos

Resumen

Grafos são objetos matemáticos que permitem modelar uma vasta gama de aplicações reais. Um exemplo disso diz respeito à modelagem de uma rede de telecomunicações por grafos, o que permite investigar a sua robustez a partir da análise do impacto do desenho topológico utilizando diferentes medidas de robustez. Dado um grafo simples conexo G que modela uma rede, definimos a sua confiabilidade como a probabilidade de G permanecer conexo após a remoção arbitrária de alguns de seus vértices e/ou arestas com probabilidade independente de remoção 1 − p. Desde Moore & Shannon, o estudo da confiabilidade tem focado na confiabilidade de aresta, onde supõe-se que os vértices são perfeitamente confiáveis e as arestas são passíveis de remoção. A partir de Goldschmidt, parte da literatura se volta para o estudo da confiabilidade de vértice, onde supõe-se que as arestas são perfeitamente confiáveis e os vértices são passíveis de remoção. Em ambos os casos, determinar a confiabilidade de um grafo G, considerando todos os possíveis cenários de remoção de vértices ou arestas, corresponde a um problema NP-Difícil. No caso da confiabilidade de vértice de G, o polinômio de confiabilidade de vértice, RN (G, p), é definido por: RN (G, p) = ∑ Sr(G)pr(1− p)n−r, sendo Sr(G) correspondente ao número de subgrafos induzidos conexos de G que contêm, exatamente, r vértices e p é a probabilidade complementar de remoção de um vértice. Além disso, dada a complexidade, encontrar o polinômio de confiabilidade de vértice de G e de todos os supergrafos de G gerados pela inserção de uma única aresta é inviável na prática para muitas das redes reais de interesse. Logo, a identificação de alguma alteração topológica para o incremento da confiabilidade de muitos grafos é efetuada por meio de heurísticas ou simulações, ambas tendo por base propriedades topológicas e invariantes do grafo.