Наличие экспертных оценок
В Веб содержится огромное количество экспертных оценок, как явных, так и неявных, которые могут быть использованы для обучения и настройки методов поиска.
Например, явная информация о тематической направленности ресурсов содержится в тематических каталогах — как в глобальных типа Yahoo! или List.Ru, так и в небольших персональных подборках ссылок на ресурсы по определенной теме.
Важным источником экспертных оценок в Веб являются гипертекстовые ссылки. Поскольку большинство ссылок создается вручную, то гипертекстовая ссылка часто отражает мнение создателя о цитируемом ресурсе. Пытаться характеризовать это мнение можно разными способами — например, путем анализа текста ссылки или в ее окружении.
Естественной моделью представления Веб является ориентированный граф, в котором вершины соответствуют страницам, а ребра — соединяющим страницы гиперссылкам. В рамках этой модели задача анализа структуры связей между страницами — это задача анализа структуры графа.
Информацию о структуре графа Веб можно использовать при решении многих связанных с Веб задач: при теоретическом анализе поведения алгоритмов, использующих информацию о ссылках; для оптимизации вычислительной эффективности методов работы с графом — например, сжатие графа Веб; при исследовании развития Веб с социологической точки зрения и т.д. [26].
Отметим лишь некоторые известные свойства Веб, которые активно используются в методах информационного поиска:
Входящие и исходящие ссылки. Несколькими независимыми исследователями [16,77] было показано, что распределение полустепеней захода и исхода вершин графа Веб подчиняется степенному закону, т.е. вероятность того, что соответствующая степень вершины равна
пропорциональна
(для входящих ссылок
, а для исходящих —
). Этот факт, например, неявно используется в алгоритмах, использующих информацию о цитировании для оценки «авторитетности» ресурсов (см. раздел 4).
Общая структура графа. Веб — это не просто месиво из случайных ссылок. Так, более 90% страниц в Веб относятся к одной компоненте связности, в которой можно выделить четыре примерно одинаковые по размеру части [26] (см. рис. 1). Ядро этой компоненты связности составляет компонента сильной связности (КСС), где для любой пары документов существует путь от первого документа ко второму. К ней примыкают части ИСТОК и СТОК, в которых для любой страницы существует путь соответственно «в» или «из» КСС, но не наоборот. Отметим, что ИСТОК и СТОК могут быть связаны путями в обход КСС. Остальные страницы относятся к так называемым «отросткам» (tendrils), для них не существует пути, соединяющего их с КСС.
Прямым следствием этого наблюдения является, например, ограничение сверху на количество страниц Веб, которые можно посетить, начав с некоторой выбранной страницы и переходя по обнаруженным ссылкам.
Повторяемость структурных шаблонов. При рассмотрении небольших подграфов Веб также можно выделить нетривиальные, но часто встречающиеся структуры. Например, такой структурой являются
-кланы (
-clans), т.е. графы из
вершин, где между любыми двумя вершинами существует путь длины
[51].
Другой часто встречающийся вид подграфов — полные двудольные подграфы
, т.е. графы из
вершин, в которых каждая из множества
вершин ссылается на каждую из
. При разумных значениях
и
такие подграфы (например
) можно интерпретировать как ядро некоторого сообщества [77].
Эти наблюдения очень важны для использующих структуру графа Веб алгоритмов, которые обсуждаются далее (см. раздел 4.1).
#128308; Как выбрать наставника? Особенности и алгоритм работы моей структуры.
