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

что гиперссылки в сети Веб не подчиняются модели независимой

случайной генерации. В первом приближении вероятность появления новой ссылки у страницы подчиняется степенному закону:

где k - количество исходящих или входящих гиперссылок, aисх = 2.45, aвх = 2.1.

веб-графа устанавливает соединения с уже существующими узлами не равновероятно,

но с большей вероятностью с узлами, имеющими большое количество связей.
“Победителям достается все”.

проведено исследование структуры веб-графа, содержащего около 200 млн. узлов.

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

веб-графа, в котором плотность внутренних связей превышает плотность внешних

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

исходить из факта существования одного или более “зерновых” веб-ресурсов

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

сводится к задаче поиска минимально сечения для потока в

сети.

графа
(a) виртуальный исток; (b) вершины зерновых веб-сайтов; (c) вершины

веб-сайтов на расстоянии одной ссылки в глубину от любого зернового сайта; (d) ссылки на сайты не из (b) или (c); (e) вершина виртуального стока.

находятся все страницы, которые ссылаются или на которые ссылается

зерновое подмножество страниц.
Исходящие ссылки извлекаются при анализе HTML-кода страницы.
Входящие ссылки находятся путём запроса к поисковому сервису, который поддерживает модификатор “link”.

Направленное извлечение сообщества и построение графа

(c) идентифицированы, их HTML скачиваются и все исходящие ссылки

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

Направленное извлечение сообщества и построение графа

основе классического алгоритма HITS
На основе HITS с использованием неглавных

собственных векторов
На основе комбинированного HITS и латентно-семантического анализа
На основе комбинирования анализа гиперссылок с помощью SALSA и анализа текста с помощью tf-idf метрики.

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.