Six degrees of Seperation

[rrfrey]

Hi. I'm trying to model something and haven't been able to find discussions about similar situations to study. Maybe I don't know enough terminology to realize that, so would appreciate anything that points me in the right direction.

The best way to describe my problem is "six degrees of seperation" where one person knows another person, who knows another person, and so on. Person A and Person N are seemingly unrelated, other than the 1:1 relationships of a large number of intermediate people in between.

My prototype solution involves a script that searches for the individual links and assigns "string IDs" to the individual person records. I can go into more detail, but I figure I'm either totally off base or working on something simple and just don't realize it.

I would appreciate anything that could point me in the right direction on this problem.

[Ender]

Sounds like fun.

One question: should we assume that if Bob knows Bill, that Bill also knows Bob, or are there cases where this wouldn't be true?

[rrfrey]

Yes, for this situation, all of the 1:1 people relationships are bidirectional. Bill knows bob and bob knows bill...

Thanks, Rodney

[Ender]

I think the solution to this is using scripts to build a multi-key for each degree of separation. Each successive degree of separation is then built from the previous list and all related person IDs.

In working this out, I came to another important question that may steer the design: If you are looking at the 3rd degree of separation, do you only want to see those people that are three relationships away, or do you want to see those people that are 3, 2, and 1 degrees away? I have worked out a solution to second choice (see attached.)

In my demo, I use a script to generate two join records in a Relationship table (one for each direction.) Then, once you select who your starting person is, you can progressively see all the people within N relationships away.

I suppose it is possible to make it show only those people N relationships away (omitting those closer than that,) but I'm not sure of the best approach. It seems like some kind of shortest-path algorithm might be needed, but then again, maybe there's away to simply filter them out using a multi-criteria relationship and another multi-key.

6degrees.fp7.zip

[rrfrey]

Wow. This is impressive and I can't thank you enough. The total end-to-end relationships are what I'm trying to track so this appears to do it (doesn't have to show a specific nth degree).

I appreciate the approach, mine had way more scripting and I needed another point of view. I'm looking forward to the next week (probably more) understanding your structure.

Again, many thanks.

Rodney Frey