Medidas de conectividade baseadas em cortes de vértices para redes complexas

Abstract

Resumo: As redes complexas foram propostas para modelar qualquer sistema que possua várias partes discretas que interajam entre si. Devido a essa generalidade elas são aplicadas a diversas áreas do conhecimento. Em redes complexas existe a necessidade de utilizar diversas medidas para analisar as propriedades da rede sob diferentes aspectos. Neste trabalho apresentamos as medidas de conectividade baseadas em cortes de vértices aplicadas a redes complexas. Essas medidas identicam os nodos importantes em uma rede de acordo com a conectividade dos mesmos em relação aos demais nodos. Mostramos como calcular o valor da medida que chamamos de vértice-conectividade dos nodos. O valor da vértice-conectividade se comparado com outras medidas como grau de intermediação, grau de proximidade, excentricidade, grau e as medidas de conectividade baseadas em cortes de arestas. Foram realizadas simulações em redes sintéticas aleatórias e redes reais. As medidas foram também analisadas em casos extremos.

Abstract: Complex networks have been proposed to model any system with many discrete parts that interact with each other. Currently complex networks are applied to a wide range of research areas. Several measures are used to quantify properties of complex networks. In this dissertation we present connectivity measures based on vertex cuts applied to complex networks. These measures identify important nodes in a network according their connectivity. We show how to calculate the value of the measure that we call vertex-connectivity of the nodes. The value of vertex-connectivity is compared with other measures such as betweenness, closeness, eccentricity, degree and connectivity measures based on edges cuts. Simulations were performed on synthetic random graphs and real networks, which were also evaluated in extreme cases.