Алгоритм HITS

Этот алгоритм впервые описал Джон Клейнберг (Jon Kleinberg) в своей статье “Авторитетные источники в гипертекстовой среде” (“Authoritative Sources in a Hyperlinked Environment” (1998)). В алгоритме HITS (Hyperlink Induced Topic Distillation) authority-страницы и хабы взаимно определяют вес друг друга. Значимость authority-страницы рассчитывается как сумма весов хабов, указывающих на нее, а вес хаба, в свою очередь, - как сумма значений авторитетности authority-страниц, ссылки на которые он содержит.

В алгоритме используются следующие обозначения. S - множество страниц, для которых рассчитываются веса хабов и authority, n – количество страниц в множестве. H - подмножество S, содержащее страницы в роли хабов, и A - подмножество S со страницами в роли authority. Поскольку любая страница может одновременно играть и роль хаба, и роль authority, множества A и H перекрываются. Для каждой страницы j в роли хаба F(j) является количеством исходящих ссылок. Для каждой страницы i в роли authority B(i) - количество входящих ссылок. Вектор значений authority с размерностью n обозначается буквой a, а вектор значений хабов - h. Таким образом расчет весов хабов и authority принимает следующий вид:

Процесс расчета производится итеративно.Изначально все веса имеют значение 1. Алгоритм начинается с перерасчета весов по формуле, указанной выше, после чего векторы нормализуются. Эта итерация повторяется до тех пор пока векторы a и h не сойдутся.

Алгоритм HITS, к сожалению, не лишен недостатков. К примеру, сама идея взаимного влияния хабов и authority-страниц создает следующую ситуацию. Представим себе хаб, который ссылается на несколько authority-страниц (хаб B на рисунке ниже), и несколько хабов, указывающих на одну authority-страницу (A). Если количество authority-страниц, на которые указывает В, больше, чем количество хабов, ссылающихся на А, то алгоритм HITS распределит весь вес авторитетности между authority-страницами в правой части рисунка, и назначит authority-странице А вес практически равный нулю.

Причиной этого явления является то, что хаб В уже на первой итерации получит большой вес от многочисленных authority-страниц и немедленно распределит его обратно между страницами, ссылки на которые он содержит. В тоже самое время хабы слева получат малый вес (вес одной лишь страницы А, поделенный между всеми ими) и в ответ назначат А также низкий вес, хотя очевидно, что страница А должна быть намного авторитетнее страниц справа.

Источники

• Kleinberg, J. May 1997, ‘Authoritative sources in a hyperlinked environment’. Technical Report RJ 10076, IBM,. Available at http://citeseer.ist.psu.edu/article/kleinberg98authoritative.html

Share elsewhere