Abstract-SimRank har varit en kraftfull modell för att bedöma likheten av par av hörn i en graf. Det bygger på begreppet att två hörn liknar varandra om de refereras till liknande hörn. På grund av sin själv-referensitet, snabb SimRank beräkning på stora grafer innebär betydande utmaningar. Det state-of-the-art arbete [17] utnyttjar partiella summor memorering för beräkning SimRank i O (Kmn) tid på en graf med n hörn och m kanter, där K är antalet iterationer. Partiella summor memorering kan minska upprepade beräkningar genom caching en del av likhetssammanfattningar för senare återanvändning. Vi konstaterar dock att beräkningar av olika delbelopp kan ha dubbla redundanser. Dessutom, för en önskad noggrannhet, den befintliga SimRank modellen kräver K = logg C iterationer [17], där C är en dämpningsfaktor. En sådan geometrisk konvergensgrad är dock i praktiken långsam om en hög noggrannhet är önskvärd. I detta dokument tar vi itu med dessa luckor. (1) Vi föreslår en adaptiv klusterstrategi för att eliminera partiella summor redundans (dvs. dubbla beräkningar som sker i partiella summor), och utforma en effektiv algoritm för att påskynda beräkningen av SimRank till O (Kd n 2 ) tid, där d är typiskt mycket mindre än den genomsnittliga in-graden av en graf. (2) Vi presenterar också en ny uppfattning om SimRank som bygger på en differentialekvation och kan representeras som en exponentiell summa av övergångsmatriser, i motsats till den geometriska summan av den konventionella motsvarigheten. Detta leder till en ytterligare ökning av konvergensgraden för SimRank iterationer. (3) Med hjälp av verkliga och syntetiska data, verifierar vi empiriskt att vår strategi för partiella summor dela överträffar den mest kända algoritmen med upp till en storleksordning, och att vår reviderade uppfattning om SimRank ytterligare uppnår en 5X speedup på stora grafer samtidigt ganska bevara den relativa ordningen av ursprungliga SimRank poäng.
Nyligen, Yu et al. REF förbättrade ytterligare SimRank-beräkningen till O(kd ′ N 2 ) tid (med d ′ < d) genom finkornig memorisering.
Towards efficient SimRank computation on large networks
{'venue': '2013 IEEE 29th International Conference on Data Engineering (ICDE)', 'journal': '2013 IEEE 29th International Conference on Data Engineering (ICDE)', 'mag_field_of_study': ['Computer Science']}