Longest shortest path between any two nodes of a graph

4
votes

I am trying to find two nodes that are furthest from each other in my Neo4j Database. For the purposes of my analysis, I am considering shortest distance between the two nodes as the distance between them. Therefore, the two nodes that are furthest will have longest shortest path between them. I am using the following syntax from Cypher to find the shortest node.

Given two nodes as shown in the Neo4j example documentation http://docs.neo4j.org/chunked/milestone/query-match.html#match-shortest-path, I can run the following Cypher query.

MATCH p = shortestPath((martin:Person)-[*..15]-(oliver:Person))
WHERE martin.name = 'Martin Sheen' AND oliver.name = 'Oliver Stone'
RETURN p

My database has over 1/2 million nodes. The brute force way will obviously take a long time. Is there any easy or faster way to get the two nodes?

[As an extra wrinkle .. the graph is weighted but this detail can be ignored.]

1
neo4jcypher
Are you looking for a single-source shortest path list, then trying to determine which of those is the longest? – Nicholas
Yes. My goal is to find two nodes, any nodes, that are far apart. To put in the context, I am still struggling to find cliques, as suggested by you in an earlier post. I am experimenting with partitioning the graph. To partition them effectively, I need two sufficiently far apart nodes to minimize chance that that they t belong to the same subgraph. PS - I have no formal education in graphs so I am trying to create some "make do" solution that are not perfect but get the work done. Appreciate you responding. – Anshul
Hi @Anshul, just wanted to ask how you solved the problem? – lmazgon
I could not find a way to solve it efficiently. Below stated points by R2-D2 and Peter were the best leads. Do let us know if you find something more efficient. – Anshul

1 Answers

5
votes

If I'm reading this correctly, you want all-pairs shortest path. This will give you a list with each node as a source and the shortest path to every other node. While it does do it by weight, you can simple use a weight of 1 for everything.

You'll have to implement this yourself in Java as Cypher doesn't have anything for this.