About 12 years ago, some colleagues (Yehuda Koren and Chris Volinsky) and I proposed a technique for measuring proximity in quasi-random (social) networks, that

About 12 years ago, some colleagues (Yehuda Koren and Chris Volinsky) and I proposed a technique for measuring proximity in quasi-random (social) networks, that can handle out-of-memory databases, and more than two query nodes, also finds a visualizable subgraph that represents as much of the relationship as possible using dynamic programming. It is described here (includes some figures): http://web2.research.att.com/export/sites/att_labs/groups/infovis/res/legacy_papers/DBLP-conf-kdd-KorenNV06.pdf http://web2.research.att.com/export/sites/att_labs/groups/in... The proposed heuristic approximates the "cycle-free effective [electrical] conductance" between the query nodes. In this paper, we were able to use anonymized phone calls to confirm 6 degrees of separation. There used to be a live demo on an AT&T Labs website but it is not available now. There are published algorithms for all the phases of the proposed heuristic, but my recollection is that Yehuda found an efficient, robust implementation of k-disjoint-shortest-paths was not easy. This is an interesting problem, thank you for making your work available. (I do agree the HTML form placeholders that change rapidly but are ignored when you press the GO button are a little confusing; it took me a minute or two to figure out what was going on.)