Vi studerar kraften i lokala informationsalgoritmer för optimeringsproblem på sociala och tekniska nätverk. Vi fokuserar på sekventiella algoritmer för vilka nätverket topologin initialt är okänd och avslöjas endast inom ett lokalt område av hörn som oåterkalleligen har lagts till i utdatauppsättningen. Det särskiljande draget i denna inställning är att lokaliseringen är nödvändig på grund av begränsningar i den nätinformation som är synlig för algoritmen, snarare än att den är önskvärd av effektivitets- eller parallelliseringsskäl. I detta avseende kan förändringar av nätverkets synlighet ha en betydande inverkan på algoritmkonstruktionen. Detta ramverk fångar situationer där optimatorn är en extern agent som inte har direkt tillgång till nätverksdata, utan snarare lär sig om grafstrukturen endast via (kostsamt) frågor. Till exempel, en användare kan vilja strategiskt hitta, och bilda anslutningar till, höggradiga noder i ett online socialt nätverk. En lämplig algoritm för detta sökproblem måste ta hänsyn till det faktum att strukturen på grafen inte är känd i förväg, och endast avslöjas lokalt som noder läggs till användarens uppsättning anslutningar. Med tanke på denna begränsade nätverkssynlighet, hur ska användaren välja vilka anslutningar som ska bildas? Denna fråga är relevant inte bara för optimizern, utan också för konstruktören av den sociala nätverksplattformen som måste bestämma hur mycket nättopologi som avslöjas för enskilda användare. Vi studerar en rad problem under denna modell av algoritmer med lokal information. Vi betraktar först det fall där den underliggande grafen är ett preferentiellt bilaganätverk, där vi visar att lokala informationsalgoritmer kan prestera förvånansvärt bra på olika uppgifter. Vi visar att man kan hitta noden av maximal grad i nätverket i ett polylogaritmiskt antal steg, med hjälp av en opportunistisk algoritm som gång på gång frågar den synliga noden av maximal grad. Detta tar upp en öppen fråga om Bollobás och Riordan om kraften hos lokala algoritmer på prioriterade bifogade grafer. Vi visar också att ett polylogaritmiskt antal frågor räcker för att hitta en väg mellan två noder i nätverket. Däremot kräver lokala informationsalgoritmer ett linjärt antal frågor för att lösa dessa problem på godtyckliga nätverk. Motiverade av problem som rekryterare ställs inför i online-nätverk, anser vi också nättäckning problem som att hitta en minimal dominerande uppsättning. För detta optimeringsproblem visar vi att om varje nod som läggs till i utdatauppsättningen avslöjar tillräcklig information om uppsättningens område, då är det möjligt att utforma randomiserade algoritmer för allmänna nätverk * borgs@microsoft. 1 som nästan motsvarar bästa möjliga approximationer även med full tillgång till grafstrukturen. Vi visar också att denna synlighetsnivå är nödvändig: det är omöjligt att uppnå en sublinjär approximation för allmänna grafer om mindre information avslöjas på varje fråga. Vi drar slutsatsen att en nätverksleverantörs beslut om hur mycket struktur som ska göras synlig för sina användare kan ha en betydande effekt på en användares förmåga att interagera strategiskt med nätverket.
I REF föreslås spårvägsalgoritmer för att hitta rotnoden och för att approximera flera andra egenskaper i en preferensgrafik.
The Power of Local Information in Social Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Physics']}