Самоорганизация в сети Веб

Информационно-поисковые системы. Сычев А.В.
Регулярность в распределении гиперссылок
Исследования показали, что гиперссылки в сети Веб не подчиняются модели независимой случайной генерации. В первом приближении вероятность появления новой ссылки у страницы подчиняется степенному закону:
где k - количество исходящих или входящих гиперссылок, aисх = 2.45, aвх = 2.1.

Информационно-поисковые системы. Сычев А.В.
Модель предпочтительного прикрепления
Вновь возникающий узел веб-графа устанавливает соединения с уже существующими узлами не равновероятно, но с большей вероятностью с узлами, имеющими большое количество связей.
“Победителям достается все”.

Информационно-поисковые системы. Сычев А.В.
Модель предпочтительного прикрепления

Информационно-поисковые системы. Сычев А.В.
Модель предпочтительного прикрепления

Информационно-поисковые системы. Сычев А.В.
Модель веб-графа “бабочка”

Информационно-поисковые системы. Сычев А.В.
Модель “бабочка”
В 1999 г. Было проведено исследование структуры веб-графа, содержащего около 200 млн. узлов. В результате исследования было обнаружено центральное сильной связное ядро (SCC), подграф, содержащий только направленные ссылки на ядро (IN), подграф, содержащий только направленные ссылки из ядра (OUT), относительно изолированные “отростки”, связанные с одной из трех крупных компонент, названных выше. Имелись также полностью изолированные компоненты, не имевшие связей с названными выше компонентами.

Информационно-поисковые системы. Сычев А.В.
Веб-сообщества
Неформально веб-сообщество определяется как подграф веб-графа, в котором плотность внутренних связей превышает плотность внешних связей.
Формальное определение: Веб-сообщество есть подмножество вершин , таких, что для всех вершин , v имеет множество рёбер, соединяющих её с вершинами в C и практически не имеет рёбер, соединяющих с вершинами в (V \ C) .
Данная задача является NP-полной.

Информационно-поисковые системы. Сычев А.В.
“Зерновые” веб-ресурсы
Тем не менее, если исходить из факта существования одного или более “зерновых” веб-ресурсов и использовать систематические закономерности в структуре веб-графа, задача может быть сформулирована в виде, который позволяет эффективно идентифицировать веб-сообщества. Под “зерновым” понимают веб-ресурс (веб-страницу), который является признанным авторитетом в тематической области идентифицируемого веб-сообщества и однозначно ему принадлежит.

Информационно-поисковые системы. Сычев А.В.
Веб-сообщества
Решение задачи о поиске веб-сообщества сводится к задаче поиска минимально сечения для потока в сети.

Информационно-поисковые системы. Сычев А.В.
Направленное извлечение сообщества и построение графа
(a) виртуальный исток; (b) вершины зерновых веб-сайтов; (c) вершины веб-сайтов на расстоянии одной ссылки в глубину от любого зернового сайта; (d) ссылки на сайты не из (b) или (c); (e) вершина виртуального стока.

Информационно-поисковые системы. Сычев А.В.
Начиная с зерновых веб-страниц (b), находятся все страницы, которые ссылаются или на которые ссылается зерновое подмножество страниц.
Исходящие ссылки извлекаются при анализе HTML-кода страницы.
Входящие ссылки находятся путём запроса к поисковому сервису, который поддерживает модификатор “link”.
Направленное извлечение сообщества и построение графа

Информационно-поисковые системы. Сычев А.В.
Как только URL из множества (c) идентифицированы, их HTML скачиваются и все исходящие ссылки запоминаются. Некоторые из этих исходящих ссылок могут ссылаться на страницы уже посещённые (такие как ссылки из (с) на (c) и (c) на (b)); тем не менее, большинство исходящих ссылок из (c) ведут на ещё не скаченные страницы (из множества (d)). Страницы, составляющие множество (d) фактически являются эффективно очищенной составной вершиной стока, т.к. каждая из них ссылается на вершину виртуального стока.
Направленное извлечение сообщества и построение графа

Информационно-поисковые системы. Сычев А.В.
Алгоритм для выделения веб-сообществ (Flake-Lawrence-Giles )

Информационно-поисковые системы. Сычев А.В.
Альтернативные подходы к поиску веб-сообществ
На основе классического алгоритма HITS
На основе HITS с использованием неглавных собственных векторов
На основе комбинированного HITS и латентно-семантического анализа
На основе комбинирования анализа гиперссылок с помощью SALSA и анализа текста с помощью tf-idf метрики.

Информационно-поисковые системы. Сычев А.В.
Литература
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J.Wiener. “Graph structure in the Web: Experiments and models”. In WWW9, pp. 309–320, Amsterdam, May 2000. Elsevier Science.
S. Chakrabarti “Mining the Web. Discovering Knowledge from Hypertext” Data. Morgan Kaufmann Publishers, 2003.
G. W. Flake, S. R. Lawrence, C. L. Giles, and F. M. Coetzee. Self-Organization and Identification of Web Communities. IEEE Computer, 35(3), 66–71, 2002
N. Imafuji and M. Kitsuregawa, "Finding a web community by maximum flow algorithm with hits score based capacity." In 8th International Conference on Database Systems for Advanced Applications, pp. 101–106, 2003.