This project was realized by
Juan C Higuera C
Francisco J Ordoñez A
Kevin N Ramos G
This project was presented for the course Statistical Mechanics of the National University of Colombia.
Based on the biases found in the analytical analysis of the Preferential Attacthment algorithm, it is proposed to expand the robustness studies against cascading failures of geodesic communication for networks with representative topologies: small world and scale-free. This by means of an algorithm which we validate theoretically and computationally that allows to sample the assembly of networks with maximum entropy given a average distribution of degree as a ligature. In this robustness study we pay special emphasis on the possibility that the entropy of the distribution of some nodal parameter allows us to account for the differences in robustness.
The scale-free degree distribution and the small world characteristic are the most studied connectivity properties of networks, in particular because of their wide presence in a variety of complex systems. For this reason with Erdos-Renyi networks have been the most studyed type of networks. In the study of scale-free networks the barabasi-albert algorithm have been a standart, but ¿this algorithm generates networks that really are representative of the ensemble of scale-free networks? Some previous results (see [1]) suggest that this is not the case. In order to avoid this problem in a general way, its posible to use the Maximum Entropy Principle (MaxEnt), which allow us to generate ensembles of random networks that fullfill some restrictions, in particular the restriction of have a scale-free distribution.
1. Analytically develop by means of non-equilibrium statistical mechanics tools, the process of evolution of networks known as preferential attachment in order to find conditions for the networks generated by this model that limit its sample of the set of scale-free networks.
2. Analytically develop the canonical ensemble for networks imposing the average degree sequence as a constraint, from the partition function calculate the free energy and finally, using the free energy, calculate the components of the average adjacency matrix for this ensemble.
3. Establish in the Python language the algorithms that will be used for the study of robustness and entropy, that is, the algorithms to generate Watts-Strogatz, Barabási-Albert and Maximum Entropy networks; the cascade failure algorithms and those necessary to calculate the Shannon entropy for different distributions of nodal parameters of the network.
4. Sample the ensemble of scale-free networks using the previously programmed maximum entropy algorithm, from this sample calculate the average adjacency matrix and compare with the average adjacency matrix calculated from the canonical ensemble.
5. Carry out comparisons of robustness against cascade failures for networks generated by the Watts-Strogatz, Barabási-Albert and Maximum Entropy algorithms. Evaluating the possibility that the entropy with respect to some parameter of the network accounts for the differences in robustness.
Using some statistical mechanics tecniques and approximations, we obtain that the distribution of the degree in networks generated from the prefferential attacthment algorithm, has a exponent between 2 and 3, this being a bias of the algorithm to sample the ensemble of scale-free networks.
Using the Maximum Entropy Principle, the definition of Free Energy and derivatives of Free Energy, we calcule numerically the mean adjacency matrix of the ensemble of random networks with in average certain degree sequence extracted from a scale-free degree distribution.
Figure 1. Average adjacency matrix calculated numerically
Was established twelve functions, that contains all the code neccesary to reproduce this work. This functions are pareto-cumm-probabilities, Degree-Sec-Generator, maxent-generator, graph-entropys, remove-hubs-load, edge-remove-hub-load, remove-aleatory, edge-remove-aleatory, hub-cascade-failure, edge-hub-cascade-failure, aleatory-cascade-failure and edge-aleatory-cascade-failure. Its possible found all this functions in the folder Functions in this repository.
Using the generator of maximum entropy networks, we generate 300 networks, obtain their adjacency matrix and averaged them.
Figure 2. Average adjacency matrix obtained from the generator of maximum entropy networks. The colorbar are proportional to the probability of two nodes are connected
If we compare the numerically and simulated mean adjacency matrix obtain for a row of this matrices:
Figure 3. 90 row of the simulated and numerically adjacency matrices.
and the difference between the two matrix:
Figure 4. Differente between de numercally and simulated mean adjacency matrix
Finally we calculate the entropy of some topological node properties
Figure 5. Entropys of the distribution of differents nodal centrality measures.
and injuried the networks with four type of attacks. Node hub attack, Edge hub attack, Node aleatory attack and Edge aleatory attactk. The results its presented below:
Figure 6. Node hub attack
Figure 7. Node aleatory attack
Figure 8. Edge hub attack
Figure 9. Edge aleatory attack
1. Some robustness properties of networks generated by the Albert-Barabasi algorithm aren´t representative of the robustness properties of scale-free networks. In particular the Albert-Barabasi networks are more hub-centric than the scale-free networks of the ensemble.
2. The robustness but fragility propertie of Albert-Barabasi networks also are found in the maximum entropy scale free networks, but this networks are less robust to aleatory attacks and more robust to hub-centric attactks than the Albert-Barabasi networks.
3. The Watts-Strogatz network are the most robust to hub-centric attacks of the nodes, followed by the maximum entropy scale-free networks. To aleatory node attacks the pattern was de opossite, with the Albert-Barabasi networks as the most robust and the Watts-Strogatz the most fragile.
4. The robustness behavior against random attacks on links follows the same pattern as for random attacks on nodes. But in the case of hub-centric edge attacks the behaviour change, neither Watts-Strogatz or Albert-Barabasi was the most robust for this type of attack.
5. The entropy of nodal centrality measures has two patterns, in the case of local centrality (degree) more entropy correlate with more robustness to aleatory attacks, but in the case of global centrality (Betweenness, Closeness, Load and Eigenvector) more entropy correlate with more robustness to hub attacks.