Computer eccentricity of a given node in a neo4j graph

Neo4j Graph Platform
,
1

I am trying to compute the eccentricity of an enormous graph (hundreds of millions of nodes). The graph is stored in Neo4j, and given the size of the graph, my approach is to compute the eccentricity of n randomly selected nodes as an approximation of the eccentricity of the graph itself.

I did not find any documentation on Neo4j website for this specific purpose, and the only related source I found is on this old fork, which may not be applicable on the latest version of neo4j.

I started with the following query.

  MATCH (root)
    WHERE elementId(root) = '...'
    CALL apoc.path.spanningTree(
      root,
      {
        bfs: false,
        maxLevel: 500,
        relationshipFilter: '>',
        uniqueness: 'NODE_GLOBAL'
      }
    )
    YIELD path
    WITH path
    ORDER BY length(path) DESC
    LIMIT 1
    RETURN [node IN nodes(path) | elementId(node)] AS nodeElementIds

This query returns the path, and the nodes in the path are all unique. However, regardless of how much I increase the value of maxLevel it still finds a path from any given node at that depth. Certainly my graph would not have such a long path for every node. (I also tried omitting the maxLevel, the query never ended after having waited ~1h.)

I wonder if I am missing something in the above query, or if there is a better/built-in method for computing eccentricity in neo4j.