124:
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
137:
The
Kleinberg model of a network is effective at demonstrating the effectiveness of greedy small world routing. The model uses an n x n grid of nodes to represent a network, where each node is connected with an undirected edge to its neighbors. To give it the "small world" effect, a number of long
58:
routing. This sort of routing depends on a relative reference point by which any node in the path can choose the next node it believes is closest to the destination. That is, there must be something to be greedy about. For example, this could be geographic location, IP address, etc. In the case of
46:. Networks of this type are peculiar in that relatively short paths exist between any two nodes. Determining these paths, however, can be a difficult problem from the perspective of an individual routing node in the network if no further information is known about the network as a whole.
109:. This can occur if nodes are in a situation that is optimal only considering a local neighborhood, while ignoring the possibility of a higher optimality resulting from swaps with distant nodes. In the above paper, the authors proposed a
341:, the long range edges are uniformly connected at random which means the long range edges are "too random" to be used efficiently for decentralized search. Kleinberg has shown that the optimal clustering coefficient for this model is
505:
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.
94:
networks. 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
121:, which adds a memory to the swap decision. In its most simplistic form, a limited history of past swaps is remembered so that they will be excluded from the list of possible swapping nodes.
79:
networks are a particular example of this problem. In such networks, trust is ensured by the fact that you only know underlying information about nodes with whom you are already a neighbor.
295:
time. By following the guaranteed connections to our neighbors, we can move one unit at a time in the direction of our destination. This is also the case when the clustering component
476:, meaning the probability of the original node having a weak tie with any node a given distance away is effectively independent of distance. Therefore, it is concluded that with
82:
One solution in this case, is to impose some sort of artificial addressing on the nodes in such a way that this addressing can be effectively used by greedy routing methods. A
264:
412:
206:
138:
range edges are added to the network that tend to favor nodes closer in distance rather than farther. When adding edges, the probability of connecting some random vertex
474:
439:
293:
500:
365:
339:
113:
method where less-than-optimal swaps were made with a small probability. This probability was proportional to the value of making the switches. Another possible
414:
where n is the number of nodes in the circular area. As this circle gets expanded further out, the number of nodes in the given area increases proportional to
313:
226:
156:
63:, participants knew the location and occupation of the final recipient and could therefore forward messages based on those parameters.
315:
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. When
502:, long-range edges are evenly distributed over all distances, which is effective for letting us funnel to our final destination.
83:
98:
small-world graph. This is accomplished by selecting random pairs of nodes and potentially swapping them based on an
370:
To reason why this is the case, if a circle of radius r is drawn around the initial node it will have nodal density
552:
71:
Greedy routing will not readily work when there is no obvious reference base. This can occur, for example, in
661:
60:
634:
589:
527:
243:
521:
373:
110:
43:
161:
99:
75:
where information about the destination's location in the underlying network is not available.
615:
607:
444:
597:
237:
91:
76:
55:
417:
54:
Nearly every solution to the problem of routing in small world involves the application of
269:
125:
nodes. In a distributed setting, this is done by having each node periodically send out a
102:
that minimizes the product of all the distances between any given node and its neighbors.
72:
39:
479:
344:
318:
593:
515:
298:
211:
141:
31:
655:
114:
95:
106:
17:
126:
118:
441:
as the probability of having a random link with any node remains proportional
611:
619:
553:"Networks, Crowds, and Markets: Reasoning about a Highly Connected World"
240:, without using the long range edges, can navigate from random vertices
524: – Graph where most nodes are reachable in a small number of steps
105:
An important problem involved with this solution is the possibility of
87:
602:
577:
518: – Social structure made up of a set of social actors
532:
Pages displaying short descriptions of redirect targets
530: – Method of generating random small-world graphs
482:
447:
420:
376:
347:
321:
301:
272:
246:
214:
164:
144:
129:
terminating at a node to be considered for swapping.
494:
468:
433:
406:
359:
333:
307:
287:
258:
220:
200:
150:
27:Routing methods for networks with short node paths
635:"Symphony: Distributed Hashing in a Small World"
158:to another random vertex w is proportional to
8:
90:discusses how this can be accomplished in
601:
481:
460:
451:
446:
425:
419:
395:
380:
375:
346:
320:
300:
271:
245:
213:
192:
168:
163:
143:
61:Milgram's original small-world experiment
543:
367:, or an inverse square distribution.
232:Greedy routing in the Kleinberg model
7:
25:
576:Kleinberg, Jon M. (August 2000).
401:
385:
282:
276:
259:{\displaystyle v\rightarrow w}
250:
189:
176:
1:
578:"Navigation in a small world"
407:{\displaystyle n/(\pi r^{2})}
67:Constructing a reference base
633:Manku, Gurmeet Singh Manku.
228:is the clustering exponent.
201:{\displaystyle 1/d(v,w)^{q}}
678:
236:It is easy to see that a
117:optimization method is a
469:{\displaystyle 1/r^{2}}
496:
470:
435:
408:
361:
335:
309:
289:
260:
222:
202:
152:
86:by a developer of the
497:
471:
436:
434:{\displaystyle r^{2}}
409:
362:
336:
310:
290:
261:
223:
203:
153:
528:Watts-Strogatz model
480:
445:
418:
374:
345:
319:
299:
288:{\displaystyle O(n)}
270:
244:
212:
162:
142:
44:small-world networks
594:2000Natur.406..845K
522:Small-world network
495:{\displaystyle q=2}
360:{\displaystyle q=2}
334:{\displaystyle q=0}
133:The Kleinberg model
111:simulated annealing
36:small-world routing
18:Small world routing
492:
466:
431:
404:
357:
331:
305:
285:
256:
218:
198:
148:
100:objective function
308:{\displaystyle q}
221:{\displaystyle q}
151:{\displaystyle v}
16:(Redirected from
669:
646:
645:
639:
630:
624:
623:
605:
603:10.1038/35022643
573:
567:
566:
564:
562:
557:
551:Kleinberg, Jon.
548:
533:
501:
499:
498:
493:
475:
473:
472:
467:
465:
464:
455:
440:
438:
437:
432:
430:
429:
413:
411:
410:
405:
400:
399:
384:
366:
364:
363:
358:
340:
338:
337:
332:
314:
312:
311:
306:
294:
292:
291:
286:
265:
263:
262:
257:
238:greedy algorithm
227:
225:
224:
219:
207:
205:
204:
199:
197:
196:
172:
157:
155:
154:
149:
92:friend to friend
77:Friend-to-friend
73:overlay networks
21:
677:
676:
672:
671:
670:
668:
667:
666:
652:
651:
650:
649:
637:
632:
631:
627:
575:
574:
570:
560:
558:
555:
550:
549:
545:
540:
531:
512:
478:
477:
456:
443:
442:
421:
416:
415:
391:
372:
371:
343:
342:
317:
316:
297:
296:
268:
267:
266:on the grid in
242:
241:
234:
210:
209:
188:
160:
159:
140:
139:
135:
88:Freenet Project
69:
52:
40:routing methods
28:
23:
22:
15:
12:
11:
5:
675:
673:
665:
664:
662:Network theory
654:
653:
648:
647:
625:
568:
542:
541:
539:
536:
535:
534:
525:
519:
516:Social network
511:
508:
491:
488:
485:
463:
459:
454:
450:
428:
424:
403:
398:
394:
390:
387:
383:
379:
356:
353:
350:
330:
327:
324:
304:
284:
281:
278:
275:
255:
252:
249:
233:
230:
217:
195:
191:
187:
184:
181:
178:
175:
171:
167:
147:
134:
131:
68:
65:
51:
50:Greedy routing
48:
32:network theory
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
674:
663:
660:
659:
657:
643:
636:
629:
626:
621:
617:
613:
609:
604:
599:
595:
591:
588:(6798): 845.
587:
583:
579:
572:
569:
554:
547:
544:
537:
529:
526:
523:
520:
517:
514:
513:
509:
507:
503:
489:
486:
483:
461:
457:
452:
448:
426:
422:
396:
392:
388:
381:
377:
368:
354:
351:
348:
328:
325:
322:
302:
279:
273:
253:
247:
239:
231:
229:
215:
193:
185:
182:
179:
173:
169:
165:
145:
132:
130:
128:
127:random walker
122:
120:
116:
115:metaheuristic
112:
108:
103:
101:
97:
93:
89:
85:
80:
78:
74:
66:
64:
62:
57:
49:
47:
45:
41:
37:
33:
19:
641:
628:
585:
581:
571:
559:. Retrieved
546:
504:
369:
235:
136:
123:
107:local minima
104:
81:
70:
53:
35:
29:
119:tabu search
642:usenix.org
538:References
84:2005 paper
38:refers to
612:1476-4687
389:π
251:→
96:Kleinberg
656:Category
620:10972276
510:See also
208:, where
590:Bibcode
618:
610:
582:Nature
561:10 May
56:greedy
638:(PDF)
556:(PDF)
616:PMID
608:ISSN
563:2011
42:for
598:doi
586:406
30:In
658::
640:.
614:.
606:.
596:.
584:.
580:.
34:,
644:.
622:.
600::
592::
565:.
490:2
487:=
484:q
462:2
458:r
453:/
449:1
427:2
423:r
402:)
397:2
393:r
386:(
382:/
378:n
355:2
352:=
349:q
329:0
326:=
323:q
303:q
283:)
280:n
277:(
274:O
254:w
248:v
216:q
194:q
190:)
186:w
183:,
180:v
177:(
174:d
170:/
166:1
146:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.