Research On Graph Mining Algorithm And Technology For Important Nodes

In real life,there are colorful complex systems,such as air transportation system,sea transportation system,etc.In order to better study the characteristics of various complex systems,we artificially abstract complex systems into a network structure that is easy to understand and remember,which is a complex network.In the network structure of complex networks,there are usually some nodes which are vital to maintain the integrity of network structure and function.Once these important nodes are attacked,the network will suffer devastating damage.Based on this,the work of this thesis will revolve around two points.One is how to mine the important nodes in the network,and the other is how to optimize the robustness of the network.For the first work of this thesis,the main contribution is that the Graph neural network algorithm is applied to node mining for the first time,and a Weighted Graph Autocoding method(WGA)is proposed to mine the important nodes in the network.The process of WGA method for mining important nodes is as follows: first,the network model is constructed,the weight matrix of the network model is used as the input,and the weight matrix is reconstructed by the autoencoder;second,the coding loss and reconstruction loss of the weight matrix are calculated,so as to calculate the overall loss;then,the eigenvectors of each node are output,and the importance of this node is evaluated by the sum of Euclidean distances between the eigenvectors of nodes and those of other nodes,and the ranking sequence of the importance of nodes is obtained;finally,the Proportion of Noncritical Nodes(PNN)index is used to evaluate the node importance ranking sequence obtained by the WGA method.As a contrast experiment,this thesis also uses Node2 vec algorithm,degree centrality index,intermediate centrality index,Page Rank algorithm,DIL(degree value and the importance of lines)method and NL(neighbor nodes and the importance of lines)method to mine the important nodes in the network,and obtains the corresponding PNN results.Finally,the reliability of the important nodes mined by WGA method is analyzed in the real situation.The second work in this thesis can be seen as an extension of the first work,and the main contribution is that the evaluation index of network robustness is redefined by combining the Gini coefficient,and an edge-adding method based on greedy and dynamic programming is proposed to optimize the robustness of the network.The specific optimization process is as follows: first,the top 20% of the most important node's neighbor nodes are selected to form the set H,and 30% of the nodes in H are randomly selected to form the candidate edge set,the candidate edge set is removed from the original network to obtain the network model requiring robust optimization;second,the Gini coefficient index is analyzed,and the increment of the Gini coefficient is obtained,the larger the increment of the Gini coefficient is,the better the network robustness optimization method is;finally,the greedy algorithm and dynamic programming algorithm are used to optimize the network by selecting edges from the candidate edge set under the condition of limiting the number of edges added or the capacity of edges added,so that the Gini coefficient of the whole network grows the fastest.As a contrast,this thesis selects the method of adding edges between the nodes with the maximum degree value and the method of adding edges between nodes with the maximum dielectric value to optimize the robustness of the network.