Complex networks can model the structure and dynamics of different types of systems. It has been shown that they are characterized by a set of 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 theoretical models (random, small-world and scale-free) and real networks (a collaboration network and a metabolic networks) along with the shortest path length, vertex degree, local cluster coefficient and betweenness centrality measures. In such analysis, we propose the use of three stochastic quantifiers: 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, edge removal, edge rewiring and node removal, all of them applied at different intensities. The results reveal that the evalu- * Corresponding author. Tel.:+55 8232141882 Email addresses: raquelcabral@gmail.com (Raquel S. Cabral), acfrery@gmail.com (Alejandro C. Frery), jramirez@ufmg.br (Jaime A. Ramírez) Preprint submitted to Physica A: Statistical Mechanics and its Applications July 31, 2014 arXiv:1407.7890v1 [physics.soc-ph] 29 Jul 2014 ated measures are influenced by these perturbations. Additionally, hypotheses tests were performed to verify the behavior of the degree distribution to identify the intensity of the perturbations that leads to break this property. Keywords: complex network, measures, stochastic distance, variability Complex networks are systems whose structure is irregular, complex and dynamically evolving in time [1] . In recent years, a number of measures have been developed to quantify the structure and behavior of such systems, which provide a framework that allows its characterization, analysis and modeling, reflecting different features of the network such as, connectivity, centrality, cycles, distances, among others. The choice of an appropriate measure for the characterization of a network is performed by evaluating its behavior, and depends mainly on three factors: (i) data availability, (ii) storage capacity and processing and (iii) interest in characterizing the behavior of the measures. In this procedure, the network is mapped into a feature vector [2] ; however, in many cases the mapping is not complete and does not accurately describe the network's real structure. In such cases, it is important to evaluate the performance of the measures when unexpected changes occur in the networks. For instance, what is the behavior of the measures if the network loses links or nodes? or, do these changes break the properties used to describe the network structure? To address such problems, it is necessary to compare different states of the network. In this work, we investigate the use of methods from the Information Theory, in particular the concept of Stochastic Quantifiers, as means to quantify the 2 changes. There are a few works that explore the use of stochastic measures to analyze the behavior of complex networks. Wang et al. [3] employed the concept of Entropy of the degree distribution to provide an amount of the network's heterogeneity, since that measure quantifies the diversity of the link distribution. They also studied the robustness of scale-free networks using the Entropy. A common practice to address the questions raised previously is to use samples of the network, instead of considering it entirely. This saves memory and processing time. Boas et al. [4] employed the Kullback-Leibler divergence to compare different states of the network and assessed the appropriateness of using network samples. However, this divergence can not be considered a distance since it is not commutative. We extend those results in two manners, namely, (i) we analyze the behavior of four measures applied to different theoretical network models and real networks, and (ii) we compare the sensitivity of three stochastic quantifiers with respect to several perturbations of the networks, including node removal. The study of the evolution of complex networks is an important issue due to their dynamic nature. Among the changes a network may be subjected to, we will consider node removal, edge addition, edge removal, and edge rewiring. Such perturbations describe common changes in practical situations as, for instance, the death of a node, the creation and the deletion of a connection, and both operations at once. Carpi et al. [5] proposed a new quantifier based on Information Theory for the analysis of the evolution of small-world dynamic networks. The 3 quantifier, a statistical complexity measure, is used to compute changes in the topological randomness for degree distribution of the network. It is obtained by the product of the normalized Shannon entropy and the normalized Jensen-Shannon distance. This quantifier requires the use of a probability distribution as a reference to compute the Jensen-Shannon distance. The authors used three reference distributions: Poisson, uniform and the distribution corresponding to the regular lattice. The analysis of perturbations in networks has also been studied with two practical purposes in mind: their vulnerability to attacks and the identification of elements whose failure lead to a breakdown. The vulnerability is associated with the decrease of network performance when structural changes occur; these can be caused by the random or directed removal of vertices, termed failure and attack, respectively. Measures related to this property are commonly defined in terms of the shortest path length and the size of the connected components of the graph. The main idea is to intentionally apply a sequence of failures (or attacks) to the network, and to observe its behavior [6] [7] [8] [9] [10] . In this context, many real networks have been studied. Pu et al. [11] studied the behavior of network controllability under vulnerability for net-  The breakdown phenomenon in networks refers to a type of cascade process, where the failure of a single or a few nodes may result in the collapse of their functionality. In networks with power distribution, for instance, the failure of a node requires that its load is redistributed to other nodes, causing a network overload and possibly other faults [14, 15] . Cabral et al. [16] presented the analysis of communication strategies in wireless sensor networks by means of analyzing the variation of the shortest path length measure in flooding, random, small-world, and scale-free networks. The variation of this measure was analyzed with respect to the insertion and removal of nodes in flooding; and with respect to insertion, removal and rewiring of links in the strategy based in complex networks. Stochastic quantifiers, namely the normalized Kullback-Leibler divergence and Hellinger distance were used to quantify the variation of the shortest paths. The goal of this work is to analyze the behavior of measures face to network perturbations. We propose the use of quantifiers based on information theoretic tools to perform this analysis. The complex network measures evaluated were shortest paths length, vertex degree, local cluster coefficient and betweenness centrality. The first one is calculated for each pair of nodes and the others are calculated for each network node. We compare the results, which are vector-valued measures, using of stochastic divergences between discrete probability distributions. In addition, we propose the use of  A complex network can be described as an undirected graph G = (V, E), where V = {v 1 , v 2 , . . . , v N } is the set of vertices (or nodes), and E = {e 1 , e 2 , . . . , e M | In this way, the problem addressed in this work can be stated as following: Problem 1. Let G be a class of complex networks, F = {f 1 , f 2 , . . . , f F } a vector of features of G, and Π = {π 1 , π 2 , . . . , π P } a set of graph perturbations. We are interested in the behavior of F applied to G before Π. In other words, we want to know how the perturbations under assessment change the intrinsic characteristics of the considered class of graphs To do this analysis we take elements of G, say g 1 , g 2 , . . . , g Z , and subject each to a series of perturbations. For example, g j is transformed into η 1,j = In this way, we have Π : G = (V, E) → 6 G = (V , E ), where V and E are the new sets of vertices and edges, defined according to the type of perturbation Π applied to G. In complex networks, four types of perturbations are very common and were applied in this methodology: • Edge addition π ae : an edge (v i , v j ) ∈ E is added on G, setting E = E ∪ (v i , v j ), i.e., π 1 : E = {e 1 , e 2 , . . . , e M } → E = {e 1 , e 2 , . . . , e m , e M +1 }. • Edge removal π re : an edge . . , e m−1 , e m , e m+1 , . . . , e M } → E = {e 1 , e m−1 , e m+1 , . . . , e M −1 }. In this case the graph may become disconnected. • Edge rewiring π we : two edges i.e., π 3 : E = {e 1 , e 2 , . . . , e M } → E = {e 1 , e i−1 , . . . , e M }. • Node removal π rv : a vertex v j ∈ V is removed from G, then V = V \ v j and E = E \ (v j , v i ), where v i are the vertices linked to v j , i.e., π 4 : and π 4 : E = {e 1 , e 2 , . . . , e M } → E = {e 1 , e 2 , . . . , e M −x }, where x is the number of edges which were linked to v j before the removal. We then study sample quantities (measures) of the perturbed samples and use the stochastic quantifiers to compare them. In this section, we focus on the description of the complex network measures, models and stochastic measures used to evaluate the effects of pertur-7 bations on networks. Figure 1 shows the steps to perform the analysis. Given the initial network g j , first we calculate the measures F and obtain, for instance, f k (g j ). We then apply the perturbation π i to g j , produce the network η ij = π i (g j ) and calculate the measures F for η ij and obtain, for instance, and H[f k (η ij )] in order to compare them with the stochastic quantifiers D. Stochastic quantifiers have been shown to exhibit good discriminatory properties in a number of problems [4, 5] .  The structural analysis or characterization of a network can be made with The measures chosen for the analysis are among the most used to characterize a large number of networks. They are also used as the basis for defining of other measures, moreover, they reflect important network features. They are defined as follows: Shortest path (i,j) , or geodesic path, is any path that connects the vertices i and j with minimal distance. This is a measure of the efficiency of information or mass transport on a network. Vertex degree κ i of a node i in a network is the number of edges incident to it, and is defined in terms of the adjacency matrix A N ×N as: The degree distribution p(κ) of a graph G is, probably, the most widespread topological characterization of graphs. It is defined as the probability that a node chosen uniformly at random has degree κ, i.e., the fraction of nodes in the graph with degree κ [1]. Local cluster coefficient C i , or transitivity, is a measure that characterizes grouping in complex networks. First introduced to unweighted graphs by Newman and Watts [18] , this measure can be defined as the number of the edges (denoted by ne i ) that connects neighbors of node i: where κ i (κ i − 1)/2 is the maximum number of edges in the sub-graph of neighbors of i. Betweenness centrality B u is a measure of a vertex's centrality in a network. It is equal to the number of shortest paths of the network that pass through that vertex v u , defined as: where σ(i, u, j) is the number of shortest paths between v i and v j that pass through v u , σ(i, j) is the total number of shortest paths between v i and v j . The first three measures are used to characterize the theoretical network models and the latter identifies important components in the network. We employ both theoretical models and real networks to study the effect of perturbations in complex networks. The theoretical models are widely used to describe real networks, specifically, Erdős Rényi's random model, Watts-Strogatz' small-world model, Barabási-Albert's scale-free model. The real-world networks are the metabolic and collaboration networks. The main characteristics of these networks are as follows. Random model G ER , in this model the probability to connect each pair of nodes is the same. The degree distribution of this model is a Poisson distribution: where c is the mean degree of network. There are two ways to build a random graph [19] : N nodes and exactly M links, and N nodes and the probability 0 < p c < 1 to connect each pair of nodes. In the first description, M links are uniformly distributed among the N (N − 1)/2 possibilities. In the second description, which is the one we adopted here, we start with a totally disconnected graph and then connect each pair of nodes with probability p c , so the probability of observing 0 ≤ κ ≤ N − 1 connections in each node follows a Binomial distribution with N −1 trials and probability of success p c , leading to c = (N −1)p c . Small-world model G W S , presents a high clustering coefficient and a small shortest path length, so it is a model between regular and random networks. The degree distribution of this model is: where κ ≥ c/2, c is the is the mean degree of network and p r is a probability of rewiring edges. If κ < c/2 then p(κ) = 0. There are several ways to build such network; in this work we use the Watts-Strogatz model. This model starts with a circular regular topology with N nodes, each one connected to the c/2 nearest neighbors in each direction (right or left in circular topology). Then, each link is randomly "rewired" with probability p r [20] . Scale-free model G BA , it displays a power law degree distribution The main feature of this topology is the presence of a few nodes with high degree, often called "hubs". To generate this topology we use the Barabási-Albert scale-free model that starts with a small number of nodes n 0 ≥ 2 with m 0 links, and in the next step a new node with m links is added to the network (with m ≤ n 0 ). The probability connection is linearly proportional to the node degree [21] . Metabolic networks Metabolic and physical processes that determine the physiological and biochemical properties of a cell can be described by Next section examines the stochastic measures used in this work, that is, the use of tools derived from information theory, specifically Kullback-Leibler divergence, and Jensen-Shannon and Hellinger distances. In probability theory and statistics, metrics, divergences and distances are popular measures for comparing different probability distributions. In 4. D(p, q) D(p, r)+D(r, q), triangle inequality for any other probability function r defined on the same probability space. A distance is not required to satisfy property 4 and a divergence is only required to satisfy properties 1 and 2 [25]. Assuming q(ξ) > 0 for every event ξ ∈ Ω, the Kullback-Leibler divergence is defined as: The Shannon Entropy S(p) of the distribution p is given by with the convention 0 ln 0 = 0. The Jensen-Shannon distance is defined as The Hellinger distance does not impose positivity on the probabilities; it is defined as In order to make the Kullback-Leibler divergence (an unbounded positive quantity) and the Hellinger distance (which is confined to the [0, 1] interval) comparable, in the remainder of this work we will use the normalized  This section presents a simulation study which evaluates the behavior of measures from complex network with respect to perturbations, i.e., we are interested in the behavior of F applied to G associated to Π. We take elements of G and subject each to a series of perturbations comparing different states of the networks with different quantifiers. The study presented here shows the application of the methodology outlined in Figure 1 , limited to the following scope: the theoretical models examined are the random, smallworld and scale-free, and real networks examined are collaboration networks and metabolic networks. The measures considered are the shortest paths length ( (i,j) ), vertex degree (κ i ), local cluster coefficient (C i ) and betweenness centrality (B i ), so F = { (i,j) , κ i , C i , B i }. The perturbations applied are the edge addition (π ae ), edge removal (π re ), edge rewiring (π we ) and node removal (π rv ), so Π = {π ae , π re , π we , π rv }. In addition, to evaluate the behavior of F, we use as quantifiers the Kullback-Leibler divergence (D KL ) and two distances: Jensen-Shannon (D JS ) and Hellinger (D H ). The simulation assumptions and parameters were: Theoretical model parameters: networks with N = {1000, 5000, 10000} vertices and average degree equal to c = 6 for the three models. The probability of connection (p c ) in the random model was 0.06, 0.012 and 0.0006 to 1000, 5000 and 10000 nodes, respectively. The nearest neighbors and probability rewiring in small-world models was three and p r = 0.3, respectively. The number of links added in each step in the scale-free model was m = 1. Real Network data: two real data were evaluated, namely: • The WIT database [26] provides descriptions for the metabolic networks of forty-three different organisms based on data for six archaea, thirty-two bacteria and five eukaryotes organisms. We analyzed the metabolic network of Escherichia coli, which has 778 nodes. The data were downloaded from Center for Complex Networks Research 1 , the graphs were those presented in Jeong et al. [22]. • In the Scientific Collaboration networks we examined the collabo- and of nodes (node removal). Histograms: for each network (theoretical and real), the normalized his- Simulation parameters: for each model network (theoretical and real) we generated 10 different networks and for each network 20 different perturbations were made. Each replication refers to a state of the network g j after a perturbation π i , denoted by η ij = π i (g j ). In this way we are able to present the mean results with symmetrical asymptotic confidence intervals at the 95% significance level. Computational resources: we performed our evaluation using the R plat-  Four measures were analyzed with stochastic quantifiers. The results are summarized in Table 1 (clustering coefficient C i ), Table 2 and Figure 3 (shortest paths length (i,j) ), Table 3 and Figure 4 (vertex degree κ i ), Table 4 and Figure 5 (betweenness centrality B i ). The Tables show the maximum values of the quantifiers for N = 10000 the level perturbation of 10%. The results for the cluster coefficient C i are not shown here for brevity. This measure did not exhibit changes with respect to edge perturbations and to node removal in scale-free model, thus, it can be considered robust or insensitive in these cases. This measure, when applied to random and small-world models, is slightly sensitive to node removal, being the Hellinger distance the one which varies most: in mean, 0.052 in the small-world for the most intense removal of nodes, as we can see in Table 1 . As presented in Figure 3 , the shortest paths ( (i,j) ) exhibit the same behavior in all models. All perturbations increase all the quantifiers, i.e., they render progres- Vertex degree (κ i ), as presented in Figure 4 , exhibits the same behavior in all models. Edge addition, edge removal and node removal increase all the quantifiers, i.e., they render progressively different graphs from the original one as the level of perturbation increases. Edge rewiring does not introduce any noticeable difference, cf. the last column of the three blocks. Observe that, the confidence intervals are larger for node removal in small-world (1000 vertices) and scale-free (1000 and 5000 vertices) models, however one can check an asymptotic behavior. Among the stochastic quantifiers, the most sensitive to the two types of perturbation which induce changes is the Hellinger distance Regarding the scale-free model, both measures vary strongly when small perturbations are applied, but the change tends to stabilize, i.e., it saturates, soon after, as we see in Figure 5 with N = {5000, 10000} vertices; as we see in Fig. 3(a) , the maximum D JS is 0.002 for the most intense addition of edges ( Table 2 ). The degree distribution is known for the models here considered, see equations (4), (5) and (6) for the random, small-world and scale-free models, respectively. It is, therefore, possible to apply hypothesis tests to check whether it changed or not and, if it changed, if the distribution was altered. To perform the tests we use networks with N = 1000. Two hypotheses were verified: 1. the degree distribution of the networks was preserved, i.e., H 0 : p g j (κ) = 23 p η ij (κ) for every κ, and 2. the degree was preserved, even if the distribution changed (first order property). We used the Kolmogorov-Smirnov test for the former and the Student's t test for the latter. The first hypothesis H 0 was rejected in both the random and scale-free models after the perturbations were applied. In the first model, when the level of perturbations increases, the p-values are close to zero, so H 0 was rejected whenever the perturbation is greater than 4%, see Table 5 . In the scale-free model, all p-values are smaller than 0.05 for all levels of perturbations. In particular, edge rewiring does not lead to the rejection of H 0 in the random model, as we observe in Figure 6 (a) (first line from down to top and third column from left to right). H 0 was not rejected in the three types of edge perturbations applied to the small-world model, since the all p-values are greater than 0.05 but, otherwise, the hypothesis is rejected for node removal. We may say that whenever H 0 is rejected, the perturbations has led to a breakdown of the degree distribution of the network. The Student's t test checks if the degree was preserved after the perturbations. As the Kolmogorov-Smirnov test showed that the degree distribution 24 G BA 0 0 0 0 0 0 0 0 0 0 0 0 G W S 100 100 100 100 100 100 100 100 100 0 0 0 G ER 100 30 0 100 25 0 100 100 100 100 35 0 was preserved only for small-world and random model, we apply the Student's t only to these models and to edge perturbations (where the number of nodes is the same). Figure 6 (b) shows the results in the small-world and random networks (top to bottom rows) and the three types of perturbation: edge addition, edge removal and edge rewiring (left to right columns), while Table 6 presents the percentage of rejected situations. In the small-world and random models, as the level of edge addition and removal increases the p-values are close to zero, the degrees was not preserved in perturbations greater than 3% for the first and 4% for the last. As expected, edge rewiring did not change the degree (all p-values greater than 0.05). Two real networks were analyzed with stochastic quantifiers: a metabolic and a collaboration network. The metabolic network was evaluated with respect to edge addition, edge removal and node removal. For brevity, we only show the results for the 10% π ae π re π we 1% 4% 10% 1% 4% 10% 1% 4% 10% G W S 100 0 0 100 0 0 100 100 100 G ER 100 0% 0 100 0 0 100 100 100 level of perturbation in Table 7 . These results show that the variation of quantifiers is very small, being the Hellinger and Jensen-Shannon distances the ones which varies most and least, respectively. Measures (i,j) and C i exhibit the same behavior: perturbations progressively increase the values of the quantifiers, and are more sensitive to edge addition; C i presents the highest value to edge addition. Measures κ i and B i behave alike. Edge addition increases the quantifiers at low levels of perturbation (1%) and then they tend to become constant as the level of perturbation increases; this perturbation, thus, induces a kind of saturation in the measures. Edge removal and node removal increase progressively but slightly the values of the quantifiers. The collaboration network was evaluated with respect to edge addition, edge removal and node removal. We observed that the intensity the perturbations did not affect the behavior of the measures degree (κ), betweenness (b) and shortest paths ( ), the values of the quantifiers are very small as can be seen in Table 8 . The cluster coefficient varies when the network was subjected to edge perturbations, the values of quantifiers increase progressively with increasing levels of perturbations. This behavior is due to the fact that 26 0.003 0.055 0.020 0.058 these networks are highly clustered.  The analysis of the variability of measures in complex networks provides important information. It gives an insight of the behavior of the network when it is perturbed, and it helps us in the design of appropriate solutions for many applications. In this paper, we used the Hellinger and Jensen-Shannon distances, and the normalized Kullback-Leibler divergence to compare different states of networks: samples from the random, small-world, scale-free, metabolic and collaboration networks. We performed four types of perturbations: addition, removal, rewiring of edges and removal nodes. We analyzed how path length, vertex degree, cluster coefficient and betweenness centrality change with respect to different levels of each perturbation. The results showed that the clustering coefficient is not sensitive to these perturbations in theoretical models, but is very sensitive in highly clustered networks. The other measures are sensitive to these changes and, in most situations, they alter their values accordingly to the intensity of the perturbation. Our analysis promotes the identification of the relationship between the strength of the perturbations and the change of the shortest path length. We applied hypothesis tests which allowed the identification of which perturbations lead to breakdowns in the degree distribution of the networks. The use of quantifiers that involve logarithms or ratios may not be a good choice for this kind of characterization, because the occurrence of zeros leads to numerical problems and, possibly, to incorrect interpretation of network changes. Acknowledgement
Cabral et al. REF measured the impact of random errors to real-world networks and generated graphs by means of stochastic quantifiers.
Variability Analysis of Complex Networks Measures based on Stochastic Distances
ArXiv
ArXiv
Mathematics Computer Science Physics