Research On Incremental Compuation Of Top-k Betweenness Centrality

Node betweenness centrality is an important indicator to measure the importance of nodes in complex networks;computing node betweenness centrality plays a key role in a wide range of applications such as social network analysis,traffic network governance,and network security management.Most of the traditional node betweenness centrality calculation methods only focus on small-scale and static graphs.However,in practical applications,the network is huge and dynamic characteristics.Therefore,how to calculate betweeenness centrality on such a network has attracted the attention of the research community.This paper studies the calculation methods of betweenness centrality and the Top-k node betweenness centrality in the dynamic graph,including the incremental calculation method of the node betweenness centrality for the dynamic graph,the top-k node approximate betweenness centrality calculation method for the static graph,and the top-k node for the dynamic graph.Calculation method of k-node approximate betweenness centrality.The main research contents of the thesis are as follows:(1)Incremental algorithm for calculating node betweenness centrality in dynamic graph.In order to accurately calculate the betweenness centrality of each node in the dynamic graph,an incremental algorithm is proposed based on the classic Brandes algorithm for static graphs.The algorithm uses incremental single-source shortest path calculation technology to maintain intermediate results and quickly calculate the betweenness centrality of change.Experimental results on the datasets such as Email-Eu-core,Facebook and bitcoin-alpha verify the efficiency of the proposed algorithm;compared with other algorithms,the proposed algorithm is about 10 times faster;in different sparsity and different scales In the figure,the speed of the proposed algorithm is more than 2 times faster than the traditional static algorithm.(2)Top-k node approximate betweenness centrality acquisition algorithm in static graph.In order to calculate the approximate betweenness centrality of Top-k nodes in a static network,this paper adopts sampling adaptive technology and proposes a method for calculating the approximate betweenness centrality.The algorithm divides the original one-way calculation of pivots into two-way simultaneous calculation of the front and rear axes,reducing the situation that some nodes are overestimated during the sampling process.By ensuring the accuracy of the approximate betweenness centrality of very few nodes,the Top-k nodes before approximate betweenness centrality ranking.The experimental results on the five datasets of CollegeMsg,p2p-Gnutella05/06,Soc-sign-bitcoinapla and Wiki-Vote show that the proposed algorithm is compared with other algorithms under the condition of ensuring the approximate betweenness centrality of the top Top-k node.The average calculation speed is increased by more than 2.4 times,and the average value of the sorting geometry is increased by more than 10 times.(3)Top-k node approximate betweenness centrality acquisition algorithm in dynamic graph.In order to calculate the approximate betweenness centrality of Top-k nodes in a dy-namic network,this paper adopts sampling adaptive technology and proposes an algorithm for maintaining the approximate betweenness centrality of Top-k nodes on a dynamic network.The algorithm dynamically updates the Top-k nodes by maintaining the sampling results,up-dating the number of front and rear pivots in real time,and sorting the approximate betweenness centrality.The experimental results in the five datasets of CollegeMsg,p2p-Gnutella05/06,Soc-sign-bitcoinapla and Wiki-Vote show that the proposed algorithm has an average speed increase of more than 10 times compared with other algorithms.