Vi analyserar egenskaperna hos Small-World nätverk, där länkar är mycket mer benägna att ansluta "grannar noder" än avlägsna noder. I synnerhet ger vår analys nya resultat för Kleinbergs Small-World-modell och dess förlängningar. Kleinberg lägger till ett antal riktade slumpmässiga långdistanslänkar till ett n × n lattice-nätverk (vertiker som noder till ett rutnät, oriktade kanter mellan två angränsande noder). Länkar har en icke-uniform distribution som gynnar båge att stänga noder över mer avlägsna. Han visar att följande fenomen uppstår: mellan två noder en väg med förväntad längd O(log 2 n) kan hittas med hjälp av en enkel girig algoritm som inte har någon global kunskap om långdistanslänkar. Vi visar att Kleinbergs analys är tight: hans algoritm uppnår  och 2 n leveranstid. Dessutom visar vi att den förväntade diametern på grafen är  på (log n), en log n faktor mindre. Vi utvidgar också våra resultat till den allmänna kdimensionella modellen. Våra diameterresultat utökar det traditionella arbetet på diametern på slumpmässiga grafer som till stor del fokuserar på jämnt fördelade bågar. Med hjälp av lite ytterligare kunskap om grafen, visar vi att vi kan hitta kortare vägar: med förväntad längd O(log 3/2 n) i ba- Slutligen föreslår vi en allmän strategi för att analysera en bredare klass av slumpmässiga grafer med icke-uniforma kant sannolikheter. På så sätt visar vi förväntade resultat (log n) i diameter för rutnät med högre dimensioner, samt inställningar med mindre enhetliga basstrukturer: där länkar kan saknas, där sannolikheten kan variera vid olika noder, eller där rutnätsrelaterade faktorer (t.ex. Användning av lattice avstånd) har en svagare roll eller avfärdas, och begränsningar (såsom enhetlig grad fördelning) är avslappnad.
I REF visar Martel och Nguyen att den förväntade diametern för ett d-dimensionellt Kleinberg-nätverk är O(log n).
Analyzing Kleinberg's (and other) small-world Models
{'venue': "PODC '04", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}