Research On K-step Betweenness Centrality Approximation Algorithm For Multidimensional Complex Networks

In recent years,with the development of the Internet and the expansion of complex networks,the structure of the network has evolved into a diversified and multi-dimensional coexistence trend.Therefore,it is of great significance and application value to study the multi-dimensional structure of complex networks.Most of the relevant research results of existing complex networks are all about single-dimensional networks and cannot be applied to multi-dimensional complex networks.The key node in the analysis of complex networks is an important research direction,and the betweenness centrality algorithm occupies an important position.Therefore,based on the original research results,this paper extends the betweenness centrality algorithm to a multidimensional complex network.This paper firstly redefines the betweenness centrality of the multidimensional network.Its calculation is to calculate the shortest path for the entire graph.In order to reduce the computational complexity,the K-step idea is adopted,but the shortest path on the single-dimension network cannot applicable to multidimensional networks,so we have given a series of definitions such as multidimensional K-step shortest paths,and the multidimensional K-step shortest path is a cross-dimension network.Traversing,on this basis,gives the K-step betweenness centrality of nodes in each dimension,thus further defining the centrality of the multi-dimensional K-step betweenness centrality.In order to facilitate the calculation,the degree of node on the multidimensional network was formalized.This paper considers reducing the computational complexity of the multidimensional K-step betweenness centrality algorithm from the perspective of reducing the repeated similarity calculation of the multi-dimensional K-step shortest path and the scale-free characteristics of the network.The multidimensional K-step betweenness centrality approximation algorithm is proposed.There are 3 stages: Firstly,the source node stage is selected according to the degree,and the node degree is approximately positively related to the betweenness centrality.Therefore,the x% node with a high degree of selection is used as the source node for traversal calculation;the second is the source node weightingprocess stage.The method of replacing the computational process of the low-degree node with the calculation process of the high-degree node is used to reduce the large number of repeated similarity calculations when calculating the multi-dimensional K-step betweenness centrality;the final step is the calculation phase of the multi-dimensional K-step betweenness centrality value,according to the previous step.The weights obtained determine how many times to repeat.On the one hand,the approximation of the algorithm is embodied in the K-step idea.On the other hand,it is reflected in the weighted processing phase of the source node in the second stage of the algorithm.The traversal times of the low-degree nodes are used as the weights of the high-number nodes.When the algorithm backtracks,the dependency value is used.Multiply the weights into the calculation of the multi-dimensional K-step betweenness centrality value.This paper experiments and analyzes the proposed multidimensional K-step betweenness centrality approximation algorithm on multiple real multidimensional networks.Based on the actual network,the applicable K-value and x-value are determined.The experimental results obtained by using the error evaluation index prove the algorithm.Under the premise of ensuring the accuracy of the importance of the nodes,the efficiency of the algorithm is improved.