Алгоритм САЛЬСА
Стохастический подход к анализу структуры ссылок (SALSA) ранжирования веб-страниц, — это алгоритм разработанный Р. Лемпелем и С. Мораном для присвоения высоких оценок центральным и авторитетным веб-страницам на основе количества гиперссылок между ними. [1]
Происхождение
[ редактировать ]SALSA вдохновлена двумя другими алгоритмами ранжирования на основе ссылок, а именно HITS и PageRank , следующим образом:
- Как и HITS, алгоритм присваивает каждой веб-странице две оценки: оценку хаба и оценку авторитета. Авторитетный ресурс — это страница, которая значительно более актуальна для данной темы, чем другие страницы, тогда как хаб — это страница, содержащая множество ссылок на авторитетные источники;
- Как и HITS, SALSA также работает с конкретным подграфом , зависящим от темы. Этот сфокусированный подграф получается путем нахождения набора страниц, наиболее соответствующих заданной теме (например, берутся первые n страниц, возвращаемых алгоритмом текстового поиска), а затем дополнения этого набора веб-страницами, которые ссылаются непосредственно на него, и страницы, на которые есть прямые ссылки из него. Из-за этого процесса выбора оценки центра и авторитета зависят от темы;
- Как и PageRank, алгоритм вычисляет баллы, моделируя случайное блуждание по цепи Маркова , которая представляет собой граф веб-страниц. Однако SALSA работает с двумя разными цепями Маркова: цепочкой узлов и цепочкой авторитетов. Это отход от представлений HITS о центрах и органах власти, основанных на взаимоусиливающих отношениях.
Характеристики
[ редактировать ]САЛЬСА можно рассматривать как усовершенствованную версию HITS.
Он легче в вычислительном отношении, поскольку его рейтинг эквивалентен взвешенному ранжированию степеней входа/выхода. Вычислительные затраты алгоритма являются решающим фактором, поскольку HITS и SALSA вычисляются во время запроса и, следовательно, могут существенно повлиять на время ответа поисковой системы. Это следует противопоставить алгоритмам, не зависящим от запроса, таким как PageRank, которые можно вычислять в автономном режиме.
SALSA менее уязвима к эффекту «Сплоченного сообщества» (TKC), чем HITS. TKC — это топологическая структура в сети, состоящая из небольшого набора тесно взаимосвязанных страниц. присутствие TKC в сфокусированном подграфе Известно, что отрицательно влияет на выявление значимых авторитетов с помощью HITS.
Социальная сеть Twitter использует алгоритм в стиле SALSA, чтобы предлагать учетные записи, на которые можно подписаться. [2]
Ссылки
[ редактировать ]- ^ Ван, Цзыян. «Улучшенные алгоритмы ранжирования веб-страниц на основе ссылок» (PDF) . cs.nyu.edu . Нью-Йоркский университет, факультет компьютерных наук . Проверено 7 августа 2023 г.
- ^ Панкадж Гупта, Ашиш Гоэл, Джимми Лин, Аниш Шарма, Донг Ван и Реза Босаг Заде WTF: Система «за кем следить» в Твиттере , Материалы 22-й международной конференции по Всемирной паутине
- Лемпель, Р.; Моран С. (апрель 2001 г.). «SALSA: стохастический подход к анализу структуры связей». Транзакции ACM в информационных системах . 19 (2): 131–160. CiteSeerX 10.1.1.38.5859 . дои : 10.1145/382979.383041 . S2CID 9607841 .