I detta dokument studerar vi ungefärliga landmärkesbaserade metoder för point-to-point avståndsberäkning i mycket stora nätverk. Dessa metoder innebär att välja en delmängd av noder som landmärken och beräkna offline avstånden från varje nod i grafen till dessa landmärken. Vid körning, när avståndet mellan ett par noder behövs, kan det uppskattas snabbt genom att kombinera de förberäknade avstånden. Vi bevisar att välja den optimala uppsättningen av landmärken är ett NP-hård problem, och därmed heuristiska lösningar måste användas. Vi utforskar därför teoretiska insikter för att ta fram en mängd enkla metoder som skalar sig väl i mycket stora nätverk. Effektiviteten av de föreslagna teknikerna testas experimentellt med hjälp av fem verkliga grafer med miljontals kanter. Medan teoretiska gränser stöder påståendet att slumpmässiga landmärken fungerar bra i praktiken, visar vårt omfattande experiment att smarta landmärken val kan ge dramatiskt mer korrekta resultat: för en given målnoggrannhet, våra metoder kräver så mycket som 250 gånger mindre utrymme än att välja landmärken på måfå. Dessutom visar vi att vid en mycket liten precisionsförlust är våra tekniker flera storleksordningar snabbare än de senaste exakta metoderna. Slutligen studerar vi en tillämpning av våra metoder på den sociala sökuppgiften i stora grafer.
Arbetet REF undersöker att hitta den optimala uppsättningen landmärken.
Fast shortest path distance estimation in large networks
{'venue': 'CIKM', 'journal': None, 'mag_field_of_study': ['Computer Science']}