Abstrakt. Under det senaste årtiondet har PageRank blivit allt viktigare i ett brett spektrum av applikationer och domäner, ända sedan det först visade sig vara effektivt för att bestämma nod betydelse i stora grafer (och var en banbrytande idé bakom Googles sökmotor). I distribuerad dator ensam, PageRank vektorer, eller mer allmänt slumpmässiga gång baserade mängder har använts för flera olika program som sträcker sig från att bestämma viktiga noder, lastbalansering, sökning, och identifiera konnektivitet strukturer. Förvånansvärt nog har det dock varit lite arbete med att utforma bevisligen effektiva fullt distribuerade algoritmer för beräkning av PageRank. Svårigheten är att traditionella matris-vektor multiplikation stil iterativa metoder kanske inte alltid anpassa sig väl till den distribuerade inställningen på grund av kommunikations bandbredd begränsningar och konvergens hastigheter. I detta papper presenterar vi snabba slumpmässiga gång-baserade distribuerade algoritmer för beräkning PageRank i allmänna grafer och visar starka gränser på den runda komplexiteten. Vi presenterar först en algoritm som tar O(log n/ på) rundor med hög sannolikhet på någon graf (riktad eller oriktad), där n är nätverksstorleken och  till är den återställningsannolikhet som används i PageRank beräkning (vanligtvis  till är en fast konstant). Vi presenterar sedan en snabbare algoritm som tar O( н log n/ på) rundor i oriktade grafer. Båda ovanstående algoritmer är skalbara, eftersom varje nodprocess och skickar endast litet (polylogaritmiskt i n, nätverksstorleken) antal bitar per runda och därmed fungerar i CONGEST distribuerade datormodellen. För riktade grafer presenterar vi en algoritm som har en körtid av O( log n/ på), men det kräver ett polynom antal bitar för att bearbetas och skickas per nod i en runda. Såvitt vi vet är dessa de första fullt distribuerade algoritmerna för beräkning av PageRank vektorer med påvisbart effektiv körtid.
I REF härleds distribuerade algoritmer för beräkning av PageRank vektorer med O( 1 α log n) rundor för alla 0 < α < 1 med hög sannolikhet.
Fast Distributed PageRank Computation
{'venue': 'Theoretical Computer Science, Volume 561, Pages 113-121, 2015', 'journal': None, 'mag_field_of_study': ['Computer Science']}