Hardness Analysis and Empirical Studies of the Relations among Robustness, Topology and Flow in Dynamic Networks.

Abstract

Network robustness is the ability of a network to maintain performance after disruption, thus it is an important index for network designers to refer to. Every actual network has its own topology structure, flow magnitude (scale) and flow distribution. How the robustness relates to these factors still remains unresolved. To analyze the relations, we first established a robustness problem model, studied the hardness of a special case of the model, and generated a lot of representative network instances. We conducted experiments on these instances, deleting 5% to 50% edges on each instance and found that the robustness of a network has an approximate linearity to its structural entropy and flow entropy, when the correlation coefficient between the structure and flow is fixed. We also found that robustness is unlikely to have a relation to the flow scale and edge scale in our model. The empirical studies thus can provide a way of quickly estimating the robustness of real-world networks by using the regression coefficients we obtained during the experiments. We conducted computation on a real-world dataset and got favorable results, which exhibited the effectiveness of the estimation.