In this experiment we show that is possible to find short social routes between cities without having global knowledge of the network structure
In our proposed distributed social search, we assume people have knowledge of the geographical locations of their friends (they know in which city they live). This way they forward the message to their friend who is geographically closest to the destination city. You can of course learn more about our method.
For comparision, we include the optimal search: the shortest path in the network can be obtained by doing a well known bfs. In short, it would be like if people forward copies of the message to all of their friends, until this flooding reaches the target. That's why the number of explored nodes is so big (it grows exponentially with the number of steps).
Names appearing in the chain are of course not real, see data and anonimization to find out about the applied procedure.