Estimated Diameter

The diameter of a graph is the worst-case length of a shortest path between any pair of vertices in a graph. It is the farthest distance to travel, to get from one vertex to another, if you always take the shortest path. Finding the diameter requires calculating (the lengths of) all shortest paths, which can be quite slow.

This algorithm uses a simple heuristic to estimate the diameter. rather than calculating the distance from each vertex to every other vertex, it selects K vertices randomly, where K is a user-provided parameter. It calculates the distances from each of these K vertices to all other vertices. So, instead of calculating V*(V-1) distances, this algorithm only calculates K*(V-1) distances. The higher the value of K, the greater the likelihood of hitting the actual longest shortest path.

The current version only computes unweighted distances.

This algorithm query employs a subquery called max_BFS_depth. Both queries are needed to run the algorithm.

Specifications

tg_estimate_diameter (SET<STRING> v_type, SET<STRING> e_type, INT seed_set_length,
  BOOL print_accum = TRUE, STRING file_path = "", BOOL display = FALSE)
Characteristic Value

Result

Returns the estimated value for the diameter of the graph

Input Parameters

  • SET<STRING> v_type: Names of vertex types to use

  • SET<STRING> e_type: Names of edge types to use

  • INT seed_set_length: The number (K) of random seed vertices to use

  • BOOL print_accum: If True, output JSON to standard output

  • STRING file_path: If not empty, write output to this file.

Result Size

one integer

Time Complexity

O(k*E), E = number of edges, k = number of seed vertices

Graph Types

Directed