Study On Network Robustness Based On Generalized Mesh Robust Growth

In the age of mobile internet,more and more people live and work hardly without internet.Under this circumstances,people must pay a great attention to the internet security.And it is of great importance to construct an internet with higher robustness for people.Based on this application background we do some research in this paper.We cannot study network well without graph theory as a modeling tool.The current network model is mainly about complex network and regular network.In this paper,we choose mesh as the network model and promote the concept of mesh to GMs(Generalized Meshes),and explore its robustness.Based on the concept of network expansion,we propose an application scenarios of GMs—Robust Growth of GMs,which means the bigger GM can be obtained by stepwise adding a new node to the current GM,and we should make sure any GMs produced in this process with best robustness.Robustness index is used for capture the robustness of a network.In this paper we come up with a new heuristic algorithm Proximity—Growth to measure the robustness of GMs.The main work about this paper is as follows:? Start from the research background and significance of this topic,we introduce the research status at home and abroad in this area.Then we present the tool needed for the study and the popular network models and robustness indexes.? We explain the problem Robust Growth of GMs in detail,and propose a heuristic algorithm Proximity-Growth to solve the problem.Then we analysis the performance of the algorithm and give two variants of the algorithm.? We solved the problem of Robust Growth of GMs by the proposed heuristic algorithm and get an optimal growth sequence of GMs.After that,we choose and compute other four robustness indexes,algebraic connectivity,effective resistance,average edge betweenness and efficiency to get four corresponding optimal growth sequences.? By comparing and analyzing the different five optimal growth sequences,we find the heuristic algorithm we proposed performs well to measure the network robustness,especially in the computation time.? By comparing and analyzing the different four optimal growth sequences produced by the common robustness indexes mentioned above,we obtained the findings as follows:(1)The algebraic connectivity-optimal GMs deviate quickly from the proximity-optimal GMs,yielding a number of less robust GMs.This hints that the rationality of the algebraic connectivity as a measure of network robustness is still in doubt.(2)The effective resistance-optimal GMs and the average edge betweenness-optimal GMs are in line with the proximity-optimal GMs.This partly justifies the two quantities as metrics of network robustness.(3)The efficiency-optimal GMs deviate gradually from the proximity-optimal GMs,yielding some less robust GMs.This suggests the limited utility of the efficiency as a measure of network robustness.