Research On Calculation Method Of Vertex Eccentricity Over Large Graphs

Graph is a non-linear data structure,which can be used to represent a lot of complex data in the real world,such as real maps,neural networks,social networks,etc.Eccentricity can be used to measure the importance of nodes in the graph.The eccentricity of a node in a graph is defined as the length of a longest shortest path starting at that node.Knowing the eccentricity of a vertex is helpful for analyzing other features of the graph,such as the centrality,radius and diameter of the graph.This paper studies the problem of high cost of index construction in existing eccentricity solving algorithms,and the research contents are as follows.Firstly,the paper proposes index construction strategy and corresponding algorithm based on subgraph partitioning.Different from the existing methods to build an index on a global graph,the basic idea of the method in this paper is that K nodes are selected at first,and then all nodes in the graph are extended outward with K points as the center until all nodes in the graph are covered.Then,disjoint subgraphs centered on K points can be obtained.For each subgraph,an index based on the central node is constructed as the pruning condition when calculating the eccentricity.Secondly,based on the idea of subgraph partition,this paper proposes the corresponding eccentricity algorithm Ecc Comp.In this algorithm,the partial eccentricity range of node x to be calculated for each subgraph is first obtained by dividing the reference node index constructed by subgraph.Then,pruning is performed based on the index to calculate the eccentricity within a smaller range.The algorithm reduces the average search cost to some extent and improves the computational efficiency.Furthermore,the paper proposes a single path node merging strategy and a reference node index optimization strategy,which further reduces the index size and improves the efficiency of eccentricity calculation.Finally,experiments are carried out on multiple real data sets.Experimental results verify the efficiency of the proposed algorithm in terms of the total time of eccentricity calculation,the average search length of reference node index and the size of reference node index.