Invulnerability Analysis Under Attack Based On Hyperbolic Coordinate And Community Structure

In recent years, people pay much attention to the ability of complex networked system that can continue to provide core services under random failures or targeted attack. The researches of complex network’s invulnerability study the survivability of system based on network topology, and the analysis of the network’s invulnerability under the attack strategies can provide guidance for the optimization of network topology. Network in the hyperbolic geometry framework exhibits navigability, which provides a new perspective for the study of network invulnerability based on topology.Hyperbolic mapping algorithm is the important prerequisite of the application of hyperbolic geometry framework, it matches the real networks with their mirrors in hyperbolic space. The much the nodes’ hyperbolic coordinates match, the higher the mapping accuracy. To improve the hyperbolic mapping methods both in terms of accuracy and running time, firstly an index called CC(Community Closeness) is proposed to measure the adjacency relationship between the communities; then the community ordering algorithm based on CC is proposed to infer the adjacent relationships of communities on hyperbolic disk; finaly a novel Hyperbolic Mapping algorithm based on the Community Structure and its hierarchical organization(HMCS) and the Community-Sector assumption is proposed. Based on HMCS, a Hyperbolic Mapping algorithm based on Community Structure and its hierarchical structure with Angular Optimization(HMCSAO) is proposed, which improves the accuracy of the hyperbolic coordinates. The experiments show that the mapping accuracy of HMCSAO(2O(N)) is higher than the existing algorithms Hyper Map(3O(N)) and CHM(2O(N)). The accuracy of HMCS is slightly worse than that of the existing algorithms, however the time complexity is linear in sparse networks.Real networks exhibit community structure characteristic, the bridge nodes connecting different communities play important roles in the network topology and functions. By taking advantage of the navigability of the network in the hyperbolic geometry framework, a novel node Local Information Centrality(LIC) index based on hyperbolic coordinates is proposed. LIC measures the effect that a node has on the network survivability by the information flow through a node. The greater the LIC value of a node, it is considered more important for the network. The experiments show that bridge nodes in community network have higher LIC values in the network. Compared to Betweenness Centrality index, LIC has a lower computational complexity, and the failure of the nodes with high LIC value makes the network survivability decline faster.Based on the proposed index LIC, an attack strategy called NCLIC aiming at attacking bridge nodes is proposed. From the experiments, we find that NCLIC can fragment the network much faster than the attack strategy called NLIC that aiming at attacking nodes in the whole network, especially in Power network with obvious community structure. From the analysis of the community survivability, we find that when the percent of the attack nodes with high LIC value is small, the largest connected component size and the average inverse geodesic length value of the community decrease faster under NCLIC. As the percent of the attack nodes increases, the community is fragment under NLIC, and there has connected components exist under NCLIC. The analysis further indicates that the community structure exhibits the structural function in the network. When the network is attacked, the community that the attacked nodes in is greatly effected, while the rest component of the network is almost not effected. The targeted attacks according to community structure make the network survivability largely effected.