Andy Lewis-Pye

Finding short paths in small worlds. 

Abstract. While the problem of finding short paths in graphs has been extensively studied, the situation changes dramatically when one restricts to the case of graphs satisfying conditions like the small world property, common to most networks seen in nature.  I’ll discuss recent work in which my coauthors Huang, Li and Pan and I introduce the idemetric property, which formalises the idea that most nodes in a graph have similar distances between them, and which we suggest is likely to be satisfied by many small-world network models. As evidence for this claim, we have shown, for example, that the  Watts-Strogatz model is idemetric for a wide range of parameters.  For graphs with the idemetric property, it is easily observed that the all-pairs shortest path problem can be reduced to the single-source shortest path problem, so long as one is prepared to accept solutions which are of stretch close to 2 with high probability. So the suggestion is that this is a common property, giving rise to very efficient short path finding algorithms in contexts where O(n) preprocessing is permitted.