Research On Approximate Algorithm Of Inter - Zonal Center Based On Graph Feature

The research of complex networks has been involved in some fields, such as computer science, biological, physics, traffic and so on. The relation between complex network and human life becoming more and more closely. So complex network analysis is a hot spot of research. In analysis of complex network, measure the degree of every vertex’s importance is very important. For example, in terrorist organization by controlling the leader can control the entire terrorist organization and avoid some terrorist attacks of cases’ happen. To protect critical servers on the network to prevent it be attacked by virus or hacker, we need to achieve the critical vertices of the whole network. By isolating the source of infection, we can prevent the spread of infectious virus. According to human lethal proteins we can develop new drugs and so on. However, there are a lot of algorithms to measure of the importance of network vertices, but the most commonly used algorithms is the betweenness centrality algorithm and PageRank algorithm, the two algorithms have their own different application scenarios. In this thesis, we analyze the key vertices which was based on different algorithms on the web the position of these two algorithms to analyze the application scenarios, the betweenness centrality algorithm be used to find the important vertices in the whole network, PageRank be used to find the vertices which have high popularity in the inner of field.Now many applications need to find important vertices in the whole network, such as the application of the above example, it will use the betweeness centrality algorithm to find the key vertices. However, the time complexity of the algorithm is O(V*E), and the running time of betweenness centrality algorithm of a large-scale graph is longer. If we need to compute a network with millions of vertices, we need to ten months to complete the betweenness centrality algorithm. Therefore, when compute the large graphs’ betweenness centrality value, the algorithm is unavailable. So our goal of research is to reduce the running time of betweenness centrality algorithm, so that make the algorithm to be used.The study found that the current networks have the characteristics of power-law distribution and preferential attachment. Based on the characteristics of the graph, we proposed a approximation algorithm of betweenness centrality based on vertices weighted to reduce the computation time of the betweenness centrality algorithm, so that we can make the betwenness centrality algorithm in used. The ways of approximation algorithm of betweenness centrality based on vertices weighted to reduce the amount of calculation of the algorithm betweenness centrality is to select high-impact source vertices weighted, using the algorithm we can achieve the speedup of 25 on average, and the error rate of approximate results is less than 0.01%. So, the betweenness centrality approximation algorithm based on vertex weighted can guarantee the accuracy of approximate results and reduce the amount of computation significantly.