Robustness Metrics For Complex Networks And Their Applications

The world consists of the complex networks.We are surrounded by networks in different types,such as the Internet,social networks,biological networks,transportation networks,and so on.In recent years,complex network analysis and mining has gradually become a research hotspot in academia and industry since it has helped us to understand and predict the rules and anomalies in complex systems.Among them,network robustness measures the ability of networks to maintain their structure and functions when attacked or disturbed.Measuring network robustness can not only detect complex network structural anomalies and track structural evolution,but also analyze the importance of network nodes and optimize network structural design.It is widely used in transportation planning,information diffusion,infectious disease prevention and control,network security and many other fields.At present,the existing network robustness measurements mainly include vertex connectivity,edge connectivity,algebraic connectivity,etc.However,they have many shortcomings.Firstly,their computational cost is very high.As such,they are difficult to measure the robustness of networks in large-scale and dynamic.Secondly,they are proposed only for connected networks.However,most of the real networks are unconnected.Thirdly,it is hard to apply for measuring robustness of weighted networks.In this thesis,we define new robustness metrics to measure network robustness of different types based on the method of spectrum analysis.They are not only computed in efficient,but also can be applied for measure robustness of unconnected,weighted,and dynamic networks.We also apply the new proposed metric to some applications,such as information diffusion monitoring,infectious disease prevention and control,and fraud telephone detection.The main contributions of this thesis are as follows:(1)We propose R-energy as a metric to evaluate the robustness of undirected and unweighted networks: Based on the normalized Laplacian matrix of an undirected network,we propose the network robustness metric R-energy via using the spectrum analysis method.R-energy has several good properties as follows:(1)It is related to the two-step commuting probability of all vertices.As such,it has a clear physical meaning.(2)Its computational cost is only O(|V | + |E|).As a result,it is more suitable for the cases of large-scale complex networks.(3)It can be used to measure the robustness of unconnected networks,which shows that it has more practical value.A large number of experiments are carried out to verify the good properties of this metric.The computation time of R-energy of a network with 30,000 vertices is at least 3 orders of magnitude lower than that of its algebraic connectivity.By analyzing the change of R-energy value of dynamic network,it is used for event detection and rule discovery in social network,which not only indicates that R-energy can be used to measure the robustness of dynamic network,but also indicates that the measure has a wide range of uses.(2)We propose WR-energy as a new metric for evaluating the robustness of the weighted and undirected networks: By using the method of spectrum analysis,we have found that R-energy can be further extended to measure the robustness of weighted and undirected networks.Based on this theoretical finding,we propose WR-energy to measure the robustness of weighted and undirected networks.WRenergy not only has low computational complexity,but also can measure the robustness of unconnected networks.Moreover,for evaluating the robustness of dynamic networks,we find a method to compute WR-energy in an incremental manner.We have conducted extensive experiments to verify the efficiency and effectiveness of WR-energy.The elapsed time is less than 120 seconds for computing WR-energy of a network with 5.9 million vertices and 33 million edges.For the task of event detection from dynamic social network,we have found that WR-energy is more useful than R-energy,which ignores weights of all edges.Furthermore,we track the changes of WR-energy for an offline network,which models offline interaction of the Telecom users.During the COVID-19 pandemic in Nanjing,July 2021,we verify the validity and rationality of the proposed robustness metric.(3)We propose DR-energy as a new metric for evaluating the robustness of the directed networks: The adjacency matrix of directed network is unsymmetric,so spectrum analysis of directed network becomes a difficulty.For directed networks,the normalized Laplacian matrix and its eigenvalues need further theoretical study.The robustness measurement of directed network cannot be defined directly by spectral analysis method.Based on the two-step commuting probabilities of vertices in a random walk,we define DR-energy as a robustness measurement of directed network.We have conducted extensive experiments to verify the efficiency and effectiveness of DR-energy.Furthermore,we model user interactions as a directed network for Telecom calls between users.We introduce the two-step limited communting probability,which captures the interaction pattern between two users,to distinguish the different interaction behaviors of scammers and normal users.Combining basic features,behavior features,and interaction features,we built a model for detecting the Telecom fraud via gradient boosting decision tree.This method significantly improves the prediction accuracy of telecom fraud identification model,and the experimental results effectively prove the rationality of DR-energy.To sum up,this thesis proposes robustness metrics for different types of networks,which are related to the two-step commuting probability of vertices in the network.They can not only efficiently measure the ability of the network to maintain its structure and function,but also have more good properties compared with existing network robustness metrics.Extensive experiments have conducted to verify the effectiveness,efficiency and application value of the metrics proposed in this thesis.The network robustness metrics proposed in this thesis not only has clear physical meaning,but also can effectively measure the robustness of various types of networks,such as unweighted undirected networks,weighted networks and directed networks.This metrics supports three detection findings of important events,important groups and important trend rules.The three problems of robustness measurement for unconnected networks,dynamic networks and large-scale networks are solved.