Approximating Shortest Paths in Spatial Social Networks

Carlo Ratti and Christian Sommer
SocialCom 2012 - 4th ASE/IEEE International Conference on Social Computing (pp. 585-586)

We evaluate an algorithm that efficiently computes short paths in social networks by exploiting their spatial component. The main idea is very simple and builds upon Milgram's seminal social experiment, where target individuals were found by having participants forward, or route, messages towards the target. Motivated by the somewhat surprising success of this experiment, Kleinberg introduced a model for spatial social networks, wherein a procedure called greedy routing can be used to find short, but not necessarily shortest paths between any two individuals.

We extend Kleinberg's greedy routing procedure to explore k≥1 links at each routing step. Experimental evaluations on social networks obtained from real-world mobile and landline phone communication data demonstrate that such adaptations can efficiently compute accurate estimates for shortest-path distances.

@inproceedings{RS12,
 author    = {Carlo Ratti and Christian Sommer},
 title     = {Approximating Shortest Paths 
              in Spatial Social Networks},
 booktitle = {4th ASE/IEEE International Conference 
              on Social Computing (SocialCom)},
 year      = {2012},
 pages     = {585--586},
 url       = {http://dx.doi.org/10.1109/SocialCom-PASSAT.2012.132},
 doi       = {10.1109/SocialCom-PASSAT.2012.132},
}

Official version
Local version (104.0 KB)

Note

Unfortunately, due to page limitations, we were forced to drastically reduce the references. For example, we could not cite and discuss related work with similar experimental results, such as articles by Liben-Nowell et al. (PNAS 2005), Adamic and Adar (Social Networks 2005), or Thadakamalla et al. (PRE 2005).

For an accessible exposition on phenomena like the six degrees of separation and others, see e.g. the book Linked. Disclaimer: if you buy the book using this link I receive a few cents (which is not the reason why the above algorithm is also called greedy routing ;-)).

Home → Publications → Approximating Shortest Paths in Spatial Social Networks