Vi föreslår en ny skalbar algoritm som kan beräkna Personalized PageRank (PPR) mycket snabbt. Kraftmetoden är en toppmodern algoritm för att beräkna exakt PPR, men det kräver många iterationer. Att minska antalet iterationer är alltså den största utmaningen. Vi uppnår detta genom att utnyttja grafstrukturer i webbgrafer och sociala nätverk. Konvergensen av vår algoritm är mycket snabb. I själva verket kräver det upp till 7,5 gånger färre iterationer än Power-metoden och är upp till fem gånger snabbare i den faktiska beräkningstiden. Såvitt vi vet är detta första gången att använda grafstrukturer explicit för att lösa PPR snabbt. Våra bidrag kan sammanfattas enligt följande. 1. Vad är det för fel på dig? Vi tillhandahåller en algoritm för att beräkna en träd sönderdelning, som är mer effektiv och skalbar än någon tidigare algoritm. 2. Utgångspunkten är följande: Med ovanstående algoritm kan vi få en core-tree sönderdelning av alla webbgrafer och sociala nätverk. Detta gör att vi kan bryta ner en webbgraf och ett socialt nätverk i (1) kärnan, som beter sig som en expander graf, och (2) en liten trädbredd graf, som beter sig som ett träd i en algoritmisk betydelse. 3. Vad är det som händer? Vi tillämpar en direkt metod för den lilla trädbredd grafen för att konstruera en LU nedbrytning. 4. Vad är det som händer? Vi bygger på LU nedbrytningen och använder den som preconditoner, vi tillämpar GMRES metod (en state-of-theart avancerad iterativ metod) för att beräkna PPR för hela webbgrafer och sociala nätverk.
Maehara m.fl. I REF föreslås en iterationsbaserad metod som beräknar exakt PPV genom att utnyttja grafstrukturer.
Computing Personalized PageRank Quickly by Exploiting Graph Structures
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}