Abstrakt. För att förklara individers förmåga att hitta korta vägar för att skicka meddelanden till en okänd destination, baserat endast på deras egen lokala syn på ett socialt nätverk (den lilla världen fenomen), Kleinberg (2000) föreslog en nätverksmodell baserad på en d-dimensionell lattice av storlek n förstärkt med k lång räckvidd riktade länkar per nod. Individers beteende modelleras av en girig algoritm som vidarebefordrar meddelandet till grannen av den nuvarande innehavaren, som är närmast destinationen. Den här algoritmen beräknar sökvägar av förväntad längd (log 2 n/k) mellan varje par noder. Andra topologier har föreslagits senare för att förbättra giriga algoritmprestanda. Men, Aspnes m.fl. (2002) visar att för en bred klass av långdistanslänkdistributioner är den förväntade längden på den väg som beräknas av denna algoritm alltid "log 2 n/(k 2 log log n)". Vi designar och analyserar en ny decentraliserad routingalgoritm, där noder konsulterar sina grannar i närheten, innan de bestämmer sig för vem som vidarebefordrar meddelandet. Vår algoritm använder liknande mängd beräkningsresurser som Kleinbergs giriga algoritm: det är lätt att implementera, besöker O`log 2 n/ log 2 (1 + k) ́nodes på förväntan och kräver endast  till (log 2 n/ log(1 + k))) bitar av minne -observera att [1] visar att alla decentraliserade algoritmer besöker minst  till (log 2 n/k) på förväntan. Vår algoritm beräknar dock en nästan optimal väg av förväntad längd O`log n(log log n) 2 / log 2 (1 + k) ́, mellan varje par av noder. Vår algoritm kan passa bättre vissa mänskliga sociala beteenden (såsom webbsurfning) och kan också ha framgångsrika program för peer-to-peer-nätverk där längden på den väg längs vilken filerna laddas ner, är en kritisk parameter för nätverkets prestanda.
Lebhar och Schabanel REF föreslår en routingalgoritm för endimensionell Kleinbergs modell, som besöker O(
Almost Optimal Decentralized Routing in Long-Range Contact Networks
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Computer Science']}