Contracting Weighted Graph With Top-K-Centroid Clustering For Better Diameter Approximation

The graph diameter is a fundamental but very important attribute of the graph.It represents the length of the longest of the shortest distances between vertices in the connected graph.Because of the high computational time complexity of traditional single-machine shortest path algorithm,alongside the larger amount of information,the existing algorithms for sequential computing are facing great challenges in terms of time efficiency.One of the solution is to use parallel and approximate computation,assigning the computation task to multiple processors and sacrificing precision to get a lower computational time complexity,which can improve the efficiency of the graph diameter calculation.Recently,related parallel graph diameter approximate algorithms have also been successively proposed.The graph contraction based algorithm with Random-K-Centroid clustering(RK-CC)obtains O(log3n)-approximate diameter with a low computational time complexity.However,it can not obtain a deterministic output result for the same input,which brings troubles to the analysis of the same data for multiple results.Moreover,when selecting the centers to contraction the graph and calculate the approximate diameter,the influence of the vertex on the diameter is neglected,which lead to the problem of large approximate diameter error.The graph contraction based algorithm with RK-CC still needs improvement.This paper firstly analyzes the graph contraction based algorithm with RK-CC,finding that the method of randomly selecting the centers will lead to the uncertainty of the result and the large approximate diameter error.We analyze the causes of approximate diameter error in the graph contraction:(1)the centers increase the distance of the shortest path between the vertices of the original graph during the growing and contraction of the clusters set;(2)when using diameter approximate function,the radius of the clusters constructed by the centers will cause unnecessary errors.Therefore,we believe that the approximate diameter error of the graph contraction based algorithm can be reduced by selecting the appropriate centers.In order to have a determine approximate diameter result with the effective efficiency and higher precision in graph contraction based algorithm,combing with the characteristic of the cluster grow in the graph contraction,we use the 1-hop information of vertex design a centrality measurement function limcluc to measure vertex' growing efficiency and the ability of reducing approximate diameter error in the graph contraction based algorithm.After the measurement of vertexes'centralities,according to the Top-K centrality selection strategy,K vertices are selected as the centers from high to low according to their centralities in each round of center selection.We proposed a graph contraction based algorithm with Top-K-Centroid clustering(TK-CC),so that the graph contraction based algorithm can provide a deterministic output and obtain a lower approximate diameter error with the appropriate centrality measurement function.Secondly,in the graph contraction based algorithm with TK-CC,the gathering centers will result in low cluster grow efficiency in the road networks.Therefore,we designed the relaxed Top-K centrality selection strategy,which use vertex's 1-hop information to relax the gathering centers,and then select the Top-K centrality vertexes as centers after the relaxation.We proposed the graph contraction based algorithm with relaxed Top-K-Centroid clustering(rTK-CC),which can improve the efficiency of cluster grow in the road networks,and maintaining the corresponding low approximated diameter error at the same time.Finally,we experimented on real large-scale networks data sets.The results verify that the TK-CC proposed in this paper can not only provide a certain output,but also reduce the approximate diameter error when the centrality measurement function is selected appropriately.Among the functions with TK-CC,our proposed centrality measurement function limcluc has almost the best approximate rate and lower approximate diameter error than RK-CC,which reduce at most 24.7%approximate rate and 95%mean absolute error.It obtained good cluster growing efficiency in all functions with TK-CC,and by comparing with RK-CC,it reduced up to 15.9%execution time in social networks,and increase 32.5%execution time at most in road networks.In the road networks,rTK-CC improved the cluster growing efficiency at most 21.7%comparing with TK-CC.It can effectively reduce the execution time when the scale of quotient graph is small,in the meantime maintaining the precise and stability of approximate diameter to TK-CC.