Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Wrong link? haha –  IABP Apr 7 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 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 at 18:00
add comment

1 Answer 1

up vote 8 down vote accepted

You could possibly save some space using a "meet in the middle" approach. Make a list of all nodes at distance at most 3 from A, and another list of all nodes at distance at most 3 from B. If the lists intersect, then A and B are at distance at most 6. In the fact, it is enough to construct one of the lists and then generate the other list, testing whether each element belongs to the first list.

To determine whether the lists intersect, you have two options: either sort the first list, or put it into a hash table. The second uses more space but it's faster. (You will need counterparts of these, a balanced binary tree or a hash table, to generate the lists in the first place.)

Practically speaking, you would apply the following optimization: first determine all nodes at distance 1 from A and all nodes at distance 1 from B, and check whether the lists intersect. Then check all nodes at distance 2 from A against all nodes at distance 1 from B. Then check all nodes at distance 2 from A against all nodes at distance 2 from B. And so on. If the distance is less than 6, then you potentially save a lot of time and space.

share|improve this answer
    
This is a good answer, but now I'm wondering, what if I modify the problem such that its any arbitrary degrees of separation and I have to find the number of degrees and a path. –  IABP Apr 6 at 20:43
    
You do the same thing, increasing the distance until the two lists intersect. While generating the lists, you also maintain one path for every reachable vertex. –  Yuval Filmus Apr 6 at 23:05
    
I see how it works but now I am wondering how this saves time and space over a simple breadth first search from A to B. It seems to me that I would have to look through as much data. Could you be more specific over what the complexities of the two are? Thank you, you've helped a lot. –  IABP Apr 7 at 1:13
1  
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 at 1:49
1  
@KeirSimmons distance is linear. Number of nodes can be exponential compared to distance. –  Taemyr Apr 7 at 9:14
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.