Networks of this type are peculiar in that relatively short paths exist between any two nodes.
In the case of Milgram's original small-world experiment, participants knew the location and occupation of the final recipient and could therefore forward messages based on those parameters.
[citation needed] Greedy routing will not readily work when there is no obvious reference base.
In such networks, trust is ensured by the fact that you only know underlying information about nodes with whom you are already a neighbor.
Given the assumption that these networks exhibit small world properties, often as the result of real-world or acquaintance relationships, it should be possible to recover an embedded Kleinberg small-world graph.
[citation needed] An important problem involved with this solution is the possibility of local minima.
In the above paper, the authors proposed a simulated annealing method where less-than-optimal swaps were made with a small probability.
Another possible metaheuristic optimization method is a tabu search, which adds a memory to the swap decision.
[citation needed] This method for constructing a reference base can also be adapted to distributed settings, where decisions can only be made at the level of individual nodes who have no knowledge of the overall network.
It turns out that the only modification necessary is in the method for selecting pairs of random nodes.
To give it the "small world" effect, a number of long range edges are added to the network that tend to favor nodes closer in distance rather than farther.
[1] It is easy to see that a greedy algorithm, without using the long range edges, can navigate from random vertices
By following the guaranteed connections to our neighbors, we can move one unit at a time in the direction of our destination.
is large and the "long range" edges end up staying very close; we simply do not take advantage of the weaker ties in this model.
[2] To reason why this is the case, if a circle of radius r is drawn around the initial node it will have nodal density
, long-range edges are evenly distributed over all distances, which is effective for letting us funnel to our final destination.
[citation needed] Some structured Peer-to-peer systems based on DHTs often are implementing variants of Kleinberg's Small-World topology to enable efficient routing within Peer-to-peer network with limited node degrees.