Algorytm SALSA

Stochastic Approach for Link-Structure Analysis (SALSA) to algorytm rankingu stron internetowych zaprojektowany przez R. Lempla i S. Morana w celu przypisania wysokich wyników stronom centralnym i autorytatywnym na podstawie liczby hiperłączy między nimi.

SALSA jest inspirowana dwoma innymi algorytmami rankingu opartymi na linkach, a mianowicie HITS i PageRank , w następujący sposób:

• podobnie jak HITS, algorytm przypisuje każdej stronie internetowej dwie oceny: ocenę centrum i ocenę autorytetu. Autorytet to strona, która jest znacznie bardziej adekwatna do danego tematu niż inne strony, podczas gdy hub to strona, która zawiera wiele linków do autorytetów;
• podobnie jak HITS, SALSA działa również na skupionym podgrafie , który jest zależny od tematu. Ten skoncentrowany podwykres uzyskuje się najpierw poprzez znalezienie zestawu stron najbardziej odpowiednich dla danego tematu (np. weź n pierwszych stron zwróconych przez algorytm wyszukiwania tekstowego), a następnie rozszerzenie tego zestawu o strony internetowe, które prowadzą bezpośrednio do niego i z strony, do których prowadzą bezpośrednie linki. Ze względu na ten proces selekcji wyniki centrum i autorytetu są zależne od tematu;
• podobnie jak PageRank, algorytm oblicza wyniki, symulując losowe przejście przez łańcuch Markowa reprezentujący wykres stron internetowych. SALSA współpracuje jednak z dwoma różnymi łańcuchami Markowa: łańcuchem centrów i łańcuchem organów. Jest to odejście od koncepcji HITS dotyczących centrów i władz opartych na wzajemnie wzmacniającej się relacji.

Nieruchomości

SALSA może być postrzegana jako ulepszenie HITS-ów.

Jest lżejszy obliczeniowo, ponieważ jego ranking jest równoważny z ważonym rankingiem stopni wejścia/wyjścia. Koszt obliczeniowy algorytmu jest kluczowym czynnikiem, ponieważ HITS i SALSA są obliczane w czasie zapytania i dlatego mogą znacząco wpłynąć na czas odpowiedzi wyszukiwarki. Należy to skontrastować z algorytmami niezależnymi od zapytań, takimi jak PageRank, które można obliczać w trybie offline.

SALSA jest mniej podatna na efekt Tightly Knit Community (TKC) niż HITS. TKC to struktura topologiczna w sieci WWW, która składa się z niewielkiego zestawu ściśle ze sobą powiązanych stron. , że obecność TKC w skoncentrowanym podgrafie negatywnie wpływa na wykrywanie znaczących autorytetów przez HITS.

Sieć społecznościowa Twitter używa algorytmu stylu SALSA do sugerowania kont do obserwowania.

•    Lempel R.; Moran S. (kwiecień 2001). „SALSA: podejście stochastyczne do analizy struktury powiązań”. Transakcje ACM w systemach informatycznych . 19 (2): 131–160. CiteSeerX 10.1.1.38.5859 . doi : 10.1145/382979.383041 . S2CID 9607841 .