Estudo da variabilidade de medidas em redes complexas

Abstract

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.