Estudo da variabilidade de medidas em redes complexas

Autor: Raquel da Silva Cabral
Přispěvatelé: Jaime Arturo Ramirez, Alejandro César Frery Orgambide, Osvaldo Anibal Rosso, Elizabeth Fialho Wanner, Frederico Gadelha Guimaraes, Lucas de Souza Batista
Jazyk: portugalština
Rok vydání: 2013
Předmět:
Zdroj: Repositório Institucional da UFMG
Universidade Federal de Minas Gerais (UFMG)
instacron:UFMG
Popis: As redes complexas podem modelar a estrutura e dinâmica de vários tipos de sistemas, sendo comum a caracterização dessas redes através de medidas. Neste trabalho, avalia-se a variabilidade de medidas de redes complexas quando as redes são submetidas a perturbações e, para isso, as perturbações são controladas e seus efeitos quantificados. Foram avaliadas as redes aleatórias, de mundo pequeno e livres de escala em relação às medidas grau do vértice, coeficiente de agrupamento local, betweenness centrality, comprimento dos caminhos mínimos e comprimento médio dos caminhos mínimos. Em tal análise, utilizou-se três quantificadores: a divergência de Kullback-Leibler, a distância de Jensen-Shannon e a distância de Hellinger. A sensibilidade das medidas foi analisada com respeito às seguintes perturbações: adição de arestas, remoção de arestas, religação de arestas e remoção de nós, todas elas aplicadas em diferentes intensidades. Adicionalmente, foram feitos testes de hipótese para verificação do comportamento da distribuição dos graus e identificar que perturbações e seus níveis levam à quebra dessa propriedade. Dentre as perturbações aplicadas, a religação de arestas causou menor variação nos quantificadores estocásticos. O grau do vértice não é alterado com esta perturbação, pois a religação preserva seus valores; enquanto que, o comprimento dos caminhos mínimos apresentou uma pequena variação nas redes aleatórias e de mundo pequeno e uma variação maior nas redes livres de escala. A adição e remoção de arestas atinge diretamente o comportamento das medidas locais, já que estas alteram sempre seus valores causando variações nos quantificadores estocásticos. Especificamente, as redes livres de escala são mais sensíveis a adição de arestas, já que os quantificadores atingiram os valores mais altos, 0.807 para no nível de perturbação 10% em redes com 10000 vértices. Em relação a sensibilidade dos quantificadores utilizados, a distância de Hellinger apresentou os maiores valores na maioria dos casos, seguida pela divergência de Kullback-Leibler e a distância de Jensen-Shannon. O coeficiente de agrupamento local não apresentou variação para as perturbações de arestas, assim pode-se dizer que essa medida é robusta ou insensível a estas perturbações. Além disso, foi realizada uma caracterização da estrutura de comunicação de redes de sensores sem fio usando redes complexas. Essa redes de sensores são uma tecnologia importante para coleta de dados em ambientes distribuídos e hostis.Entre os desafios, está a forma como os dados que elas coletam são transportados na rede, pois sua estrutura é bastante dinâmica.A topologia operacional desses dispositivos pode muitas vezes ser descrita por redes complexas.Foi avaliada a variação do comprimento dos caminhos mínimos, uma medida comumente empregada na caracterização de redes de sensores sem fio; foram consideradas quatro estratégias de propagação de dados que seguem os modelos: geométrico, aleatório, de mundo pequeno, livre de escala. A sensibilidade desta medida foi analisada em relação a perturbações: inserção e remoção de vértices na estratégia geométrica; e inserção, remoção e religação de arestas nos demais modelos. A avaliação foi realizada por meio da divergência de Kullback-Leibler normalizada e da distância Hellinger. Os resultados revelaram que as medidas avaliadas são influenciadas pelas perturbações. Tanto a adição como a remoção de vértices alteram o comprimento dos caminhos mínimos no modelo de propagação geométrico. A variabilidade dos quantificadores tem dependência com o nível de perturbação aplicado; eles aumentam quando o nível de perturbação aumenta, sendo a distância de Hellinger a mais sensível as perturbações. A remoção de nós teve um impacto maior sobre o comprimento dos caminhos mínimos comparada à adição de nós. Nas estratégias de propagação baseadas em redes complexas o comprimento do caminho mínimo é sensível à adição e remoção de arestas. A distância de Hellinger é consistente e significativamente maior do que a divergência Kullback-Leibler por um fator de, aproximadamente, dois, em todas as situações em que a adição da ligação e remoção são aplicadas. Complex networks are able to model the structure and dynamics of different types of systems. It has been shown that they can be characterized by certain measures. In this work, we evaluate the variability of complex networks measures face to perturbations and, for this purpose, we impose controlled perturbations and quantify their effect. We analyze the random, small-world and scale-free models, along with the vertex degree, local cluster coefficient, betweenness centrality, shortest path length and average shortest path length measures. We employ three quantifiers for the change of vector-valued measures: the Kullback-Leibler divergence, and the Jensen-Shannon and Hellinger distances. The sensitivity of these measures was analyzed with respect to the following perturbations: edge addition, removal, rewiring and node removal, all of them applied at different intensities. Additionally, hypotheses tests were performed to verify the behavior of the degree distribution to identify the intensity of the perturbations that leads to the breakdown of these properties. Among the perturbations applied, the rewiring of edges caused less variation in stochastic quantifiers. The degree of vertices is not changed with this perturbation because the rewiring preserves its values. The shortest paths length showed a small variation in random and small-world networks and a greater variation in scale-free networks. The edge addition and removal affects the behavior of local measures, since they always change their values causing variations in stochastics quantifiers. Specifically, the scale-free networks are more sensitive to edge addition, since the quantifiers have the highest values, 0.807 to the level of perturbation 10% in networks with 10.000. Regarding the sensitivity of quantifiers used, Hellinger distance showed the highest in most cases, followed by Kullback-Leibler divergence and the Jensen-Shannon distance. The local clustering coefficient did not change for the disruption of edges, so it can be said that this measure is robust or insensitive to these perturbations. Furthermore, we characterized the communication structure of wireless sensor networks as complex network. These sensor networks are an important technology for making distributed autonomous measures in hostile or inaccessible environments. Among the challenges they pose, the way data travel among them is a relevant issue since their structure is quite dynamic. The operational topology of such devices can be often described by complex networks. We assess the variation of the shortest paths, a measures commonly employed in the complex networks to characterize wireless sensor networks. Four data propagation strategies were considered: geometric, random, small-world, and scale-free models. The sensitivity of these measures was analyzed with respect to perturbations: insertion and removal of nodes in the geometric strategy; and insertion, removal and rewiring of links in the other models. The assessment was performed using the normalized Kullback-Leibler divergence and the Hellinger distance, both stemming from the Information Theory framework. The results reveal that the evaluated measures are influenced by these perturbations. Both the node addition and removal change the shortest path length in geometric strategy. The variability of the quantifiers is dependent on the level of disturbance applied, they increase when the level of perturbations increases, with the distance from the Hellinger more sensitive to perturbation. Node removal had a greater impact on the shortest paths length compared to node addition. In strategies based on complex networks the shortest path length is sensitive to the edges addition and removal. The Hellinger distance is significantly higher than the Kullback-Leibler divergence by a factor of about two, in all cases where edge addition and removal are applied.
Databáze: OpenAIRE
Externí odkaz: