Research On The Computing Method Of Metric Backbone In The Graph

The analysis of graph data has always been one of the hot topics.The analysis of graph data plays an important role in many fields,including betweeness centrality,community discovery.At present,the main method of graph can be divided into two ways,one is the original map data,and the other is the metric backbone of the original graph.Instead of the analysis of the original map,the metric backbone has greatly efficient.This paper focuses on computing the backbone of the graph.The specific content is as follows.Firstly,the existing algorithm OSME deletes the first-order semi-metric edge and finds the triangle in the graph,there is a problem that the same triangle is repeatedly searched,which influence the efficiency.A new algorithm BSME is proposed to find triangles.The basic idea is that when traversing to a vertex u,it obtains a list of contiguous points greater than the u number firstly,and then finds the intersection of each element in the contiguous list with the vertex u successively.The intersection element,adjacent list element,and vertex u constitute a triangle.The BSME algorithm avoids the problem that the same triangle is repeatedly searched and improves the efficiency of the OSME.Secondly,when the existing algorithm CURE determines whether an edge(u,v)is a metric edge,if the degree of a vertex u becomes larger,the number of edges that need to be determined starting from the vertex u also tends to become larger.In this case,multiple BFSs need to be performed from the vertex u to find an alternative indirect path for each edge,resulting in an inefficient algorithm.In this regard,a new algorithm TURE is proposed to improve the efficiency of existing algorithms.The basic idea is to sort the vertices in descending order by their degrees,and then calculate the top-k Index.When a given edge(u,v)is to be processed,the shortest path from u to v is searched from the top-k Index instead of the BFS search.If the top-k Index does not contain the shortest path from u to v,it is processed by the algorithm CURE to improve the efficiency of the algorithm.Finally,the effectiveness of the proposed method is verified by experiments.