Best solutions to 6 degrees of separation

From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check whether A and B have 6 degrees of separation. If I simply wanted to check whether B is within 6 degrees I could also limit my depth to 6.

I have heard however that there are better ways of doing this using bidirectional methods which involve some heuristics. I was wondering if someone could explain the most effective way of doing this and compare space and time complexity between the different approaches. Thanks!

And as a followup, what would be a good algorithm for finding the degree of separation between two arbitrary nodes A and B and the path between them?

• Wrong link? haha – IABP Apr 7 '14 at 6:36
• oops! anyway it sounds like shortest path problem (with uniform weights), if not sufficient dont know why not at moment – vzn Apr 7 '14 at 16:57
• And I should've mentioned...this is in fact a shorted path problem however the edges are unweighted so it is more or less a modification of some kind of breadth first search. – IABP Apr 7 '14 at 18:00

• You could potentially save space since you only need to store that part of the graph which is at distance $d/2$ from A or B (where $d$ is the distance from $A$ to $B$), whereas other algorithms require linear space. In practice, I suspect that almost all the graph would be at distance $d/2$ from A (at least for social networks and the like), so it's not clear that you will save anything. But this is an experimental question. – Yuval Filmus Apr 7 '14 at 1:49