Содержание к диссертации
Введение
1 Модели и методы идентификации веб-сообществ 15
1.1 Основные задачи, решаемые современными информационно-поисковыми системами 15
1.2 Анализ гиперссылочной структуры Сети 23
1.2.1 Концентраторы (hubs) и авторитеты (authorities) 23
1.2.2 Цитируемость и степенной закон распределения гиперссылок 24
1.2.3 Анализ веб-графа на наличие организованных структур 26
1.2.4 Комплексные методы и алгоритмы учёта цитируемости: HITS и PageRank 30
1.3 Потоковые методы идентификации веб-сообществ 35
1.3.1 Метод FLG 36
1.3.2 Модифицированный поиск веб-сообществ на базе метода FLG с настраиваемыми ёмкостями рёбер 44
ВЫВОДЫ ПО ГЛАВЕ 53
2 Разработка моделей и совершенствование методов эффективной идентификации веб-сообществ 55
2.1 Модель имитации веб-графа и алгоритм машинной генерации искусственного веб-графа 55
2.1.1 Модель имитации веб-фафа на основе принципа хронологического возникновения ресурсов 56
2.1.2 Анализ искусственно сгенерированных веб-фафов и их применение для исследований Сети 66
2.2 Типизация веб-фафов и оценка достижимости узлов 71
2.2.1 Типизация веб-фафов 71
2.2.2 Оценка достижимости узлов 75
2.3 Многоэтапная процедура идентификации веб-сообществ на основе сильно связанных компонент и контентного анализа 78
2.4 Алгоритм автоматической численной оценки качества веб-сообществ84
Выводы по главе
3 Принципы построения алгоритмов и программного обеспечения для обработки информации в интересах исследования процессов самоорганизации в сети 92
3.1 Общая структура разработанного программного комплекса для обработки данных при решении задачи информационного поиска и выявления веб-сообществ 92
3.1.1 Программные модули, реконструирующие (или генерирующие) веб-граф 96
3.1.2 Программные модули, преобразующие веб-граф 98
3.1.3 Программные модули, обрабатывающие веб-граф 100
3.1.4 Вспомогательные программные модули 104
3.2 Используемые структуры данных 105
3.2.1 Формат хранения данных веб-графа в файловой системе 105
3.2.2 Размещение веб-графа в оперативной памяти 106
3.3 Алгоритмы обработки веб-графа 109
3.3.1 Алгоритм генерации искусственного веб-графа 109
3.3.2 Алгоритм поиска максимального потока минимальной стоимости ПО
3.3.3 Алгоритм поиска связанных компонент 112
ВЫВОДЫ ПО ГЛАВЕ 113
4 Экспериментальные исследования веб-графа и веб-сообществ 116
4.1 Анализ алгоритмов идентификации веб-сообществ на основе метода FLG для различных типов веб-графов 116
4.2 Результаты экспериментальных исследований при идентификации веб-сообществ на основе разработанной многоэтапной процедуры 119
4.2.1 Оценка эффективности разработанной многоэтапной процедуры идентификации веб-сообществ 119
4.2.2 Сравнительный анализ разработанной многоэтапной процедуры идентификации веб-сообществ и метода FLG 125
4.3 Экспериментальные исследования алгоритма автоматической численной оценки качества веб-сообществ 128
4.4 Исследование Мобильного Интернета 132
4.5 Применение разработанных алгоритмов обработки информации в информационно-поисковых системах 139
4.5.1 Уточнение результатов поиска 139
4.5.2 Автоматическое пополнение и оценка веб-каталогов 145
4.5.3 Интеграция в вертикальные информационно-поисковые системы 147
Выводы по главе 150
Заключение 153
Литература
- Концентраторы (hubs) и авторитеты (authorities)
- Модель имитации веб-фафа на основе принципа хронологического возникновения ресурсов
- Программные модули, реконструирующие (или генерирующие) веб-граф
- Результаты экспериментальных исследований при идентификации веб-сообществ на основе разработанной многоэтапной процедуры
Введение к работе
Самая фундаментальная и отличительная черта наступившего информационного века состоит в том, что почти вся информация стала цифровой. В конце концов, все библиотечные и печатные материалы будут отсканированы и сохранены в цифровом виде с возможностью свободного или контролируемого доступа.
Бурное развитие сетевых технологий, в том числе и сети Интернет (в дальнейшем Сети), способствуют значительному увеличению доступных информационных ресурсов и объемов передаваемой информации. На сегодняшний день каждый человек может внести свой вклад в формирование мировых информационных ресурсов Сети, что приводит к колоссальной динамике их роста. При сегодняшних объемах доступной в Сети информации решение задач информационного поиска становится не только приоритетным, но и жизненно необходимым для обеспечения своевременного доступа к интересующей информации. Накопленные к настоящему времени колоссальные объемы информации в совокупности с непрерывно увеличивающимися темпами ее роста определяют актуальность и значимость исследований в области информационного поиска.
Существует ряд авторитетных международных конференций по
информационному поиску, посвященных, в том числе, обсуждению вопросов
информационного поиска в сети Интернет. Это такие известные
конференции как TREC (), SIGIR (),
WWW Conference () и некоторые другие: CIKM
(), SIGMOD (), KDD
(). Высокий авторитет конференций TREC, SIGIR, WWW и участие в них ведущих исследовательских коллективов и разработчиков технологий информационного поиска во многом определяет
приоритетные направления исследований и задает общие принципы развития поисковых систем.
Кроме того, существует три российские конференции, заслуживающие
внимания: DIALOG-21 (), RCDL
() и РОМИП ().
Последние крупные исследования по оценке мировых информационных ресурсов и в том числе ресурсов сети Интернет проводились в 2000 и 2003 годах [72,73] и ожидаются в 2007. По данным за 2003 год суммарный объём веб-ресурсов составлял 92 017 терабайт, из них 167 терабайт принадлежало так называемому, "поверхностному" Интернет (surface Web) и 91 850 терабайт - "глубинному" Интернет (deep Web). Под "поверхностным" Интернет понимаются ресурсы, в основном в виде статичных страниц HTML, а под "глубинным" - те ресурсы которые, генерируются по запросу - т.е. это сайты, управляемые базами данных и активными языками разметки типа РНР и ASP. К этому гигантскому объёму информации в 2003 году имело доступ порядка 600 млн. человек [73].
По сравнению с подобными крупномасштабными исследованиями, выполненными в 2000 году [72], объём данных вырос с 20 - 50 до 167 терабайт для "поверхностного" Web. А если учесть, что "глубинный" Web по некоторым оценкам [73] обычно больше в 400-450 раз, то и его объём за 3 года увеличился в 3 раза. Если предположить сохранение подобной динамики, то в 2006 году объём накопленной информации составил порядка 270 000 терабайт.
Не стоит также забывать и о многократном росте количества пользователей Сети, особенно за счёт появления в их рядах людей, не имеющих компьютеров, но пользующихся Мобильным Интернетом (МИ). Их потенциальное число сегодня составляет более 2 млрд. человек, и есть уверенность, что это наложит свой отпечаток на дальнейшее развитие всемирной Сети.
7 Одной из задач, призванных решить проблему доступа к необходимой
информации при такой скорости роста Сети, является изучение
закономерностей в системе её гиперсвязей. Принято считать, что Сеть - это
распределенный гипертекст. Однако это не совсем так. Гипертекст обычно
подразумевает наличие концептуальной модели, которая накладывает
ограничения согласованности на данные и гиперсвязи. В Сети подобной
модели обычно не существует даже для тех её частей, которые находятся под
единым административным контролем.
Как показали многие исследования [79,84,86], структура гипертекстовых ссылок в Сети подчиняется степенному закону и законам Зипфа [82], что характерно для многих других структур, созданных человеком. При этом другие классические распределения, например распределение Пуассона, используемые для описания случайных сетей и графов, в данном случае не наблюдаются.
В современных информационно-поисковых системах (далее ИПС) Интернет данные закономерности не используются в достаточной мере, несмотря на то, что в ряде работ [78,79,83,87 и др.] исследуется возможность применения в информационном поиске уникальных свойств сети Интернет, не присущих другим коллекциям данных, для которых разрабатывалась и на которых апробировалась классическая теория поиска. Ключевым в подобных исследованиях является то, что Интернет есть не только "склад информации", но и динамически изменяющаяся неоднородная Сеть, в которой всё более явно проявляются процессы самоорганизации. Тем сложнее становится её анализ не только в качественном, но и в количественном отношении - число гиперссылок во много раз превышает число самих веб-ресурсов, количество которых, как было показано выше, уже измеряется миллиардами. Феномен самоорганизации в сети Интернет приводит к формированию всё более сложных структур - веб-сообществ, анализ которых потенциально может существенно улучшить эффективность
8 классического поиска. Подобные самоорганизованные структуры и являются
предметом исследования данной работы.
В литературе [70] даётся следующее неформализованное и наиболее общее определение понятия веб-сообщество: веб-сообщество - это множество веб-ресурсов, связанных общей тематикой. Соответственно, задача идентификации веб-сообществ представляет собой задачу выделения множества веб-ресурсов, связанных общей тематикой. В зависимости от конкретных требований к веб-сообществам (например, степень ссылочной связанности входящих в них веб-ресурсов) способы идентификации веб-сообществ могут существенно отличаться. В данной работе в основном рассматривается идентификация веб-сообществ на основе анализа ссылочной связанности веб-графа, что сводит задачу идентификации веб-сообществ к задаче нахождения веб-подграфа (часто с последующей обработкой). Решение задачи идентификации веб-сообществ имеет ряд важных практических приложений и может использоваться при разработке автоматических веб-порталов и рубрикаторов, поисковых систем направленного действия (так называемый вертикальный поиск), а также для расширения возможностей поисковых систем, основанных на текстовом поиске.
Первая модель идентификации веб-сообществ была предложена в работе 1998 г. Гибсона (D. Gibson), Клейнберга (J. Kleinberg) и Рахавана (Р. Raghavan) [70]. Она была основана на извлечении веб-сообществ с помощью алгоритма ранжирования в поисковых системах, получившего название HITS (Hyperlink-Induced Topic Search) [78]. Далее в 1999-2000 гг. несколько исследователей и, прежде всего, Рахаван обобщили полученные закономерности, наблюдаемые при самоорганизации в Сети, и предложили ряд моделей, описывающих структуру Интернет [59,80], в том числе и веб-сообщества. Первые работы, развивающие идею идентификации веб-сообществ как отдельное направление и использующие альтернативные
9 подходы (т.е. не основанные на HITS и т.п.), были опубликованы в 2000-2002
гг. Флэйком (G. Flake), Лоуренсом (S. Lawrence) и Гайлсом (С. L. Giles)
[65,67]. Позже, в 2002-2004 гг. японские исследователи Ямафуджи (N.
Imafuji) и Китсурегава (М. Kitsuregawa) провели подробный анализ работ
Флэйка и других, выявив их недостатки и предложив улучшенные методы по
идентификации веб-сообществ [74-76].
Задача идентификации самоорганизованных веб-сообществ в
большинстве работ так или иначе сводится к поиску максимального потока
минимальной стоимости в транспортных st-сетях. Теория графов
предоставляет достаточно адекватный математический аппарат для решения
подобных задач. Методы и алгоритмы теории графов непосредственно
применимы к Интернет, так как эта сеть может быть представлена в виде
гигантского графа, где узлы - веб-страницы, а рёбра - гиперссылки.
Проблемой при идентификации веб-сообществ становится размер
исследуемого графа, при котором он не поддается ни полному
воспроизведению, ни обработке.
Анализ существующих работ Флейка, Лоуренса, Гайлса, Ямафуджи и
Китсурегава, посвященных процессам самоорганизации в Интернет и
идентификации веб-сообществ в интересах информационного поиска, выявил
незначительное число проведённых исследований. При этом готовых и
апробированных решений (способных непосредственно интегрироваться в
существующие информационно-поисковые системы) ещё практически не
существует, что во многом связано с отсутствием достаточно проработанной
теории и практики решения задач идентификации веб-сообществ и
масштабностью требуемых исследований. В тоже время учёт подобных
факторов, как показывает анализ, выполненный в работах Д.Д. Козлова и
А.А. Беловой [29], позволяет существенно повысить как эффективность
функционирования информационно-поисковых систем, так и сформировать
соответствующие рекомендации для их пользователей.
10 В имеющихся публикациях, рассматривающих вопросы
идентификации самоорганизованных веб-сообществ в сети Интернет, не
учитываются многие реалии современной Сети и, прежде всего:
существование "ложных" гиперссылочных связей, не характеризующих
тематику веб-сообщества, но внешне удовлетворяющих всем предъявляемым
критериям. Подобные факторы вызывают появление так называемых
страниц-шумов, фактически не соответствующих тематике. Кроме того,
имеет место постепенное вытеснение поверхностного Web динамическими
ресурсами, что приводит к неадекватности результатов, полученных на
основе реконструкций веб-графов, не учитывающих глубинный Web (т.е.
ресурсы, генерируемые по запросу с помощью различных технологий с
применением баз данных).
Указанные факторы определяют актуальность темы диссертации, направленной на поиск эффективных решений задачи идентификации полноценных веб-сообществ.
Цели и задачи исследования. Целью диссертации является разработка моделей, алгоритмов и программных средств для выявления и оценки веб-сообществ в сети гипертекстовых ресурсов на основе комплексного учёта гиперсвязей и содержания веб-ресурсов в интересах повышения эффективности функционирования информационно-поисковых систем и анализа сетевых ресурсов.
В соответствии с указанной целью в работе поставлены и решены следующие основные задачи:
Анализ современных подходов к исследованию процессов самоорганизации в сети Интернет и идентификации самоорганизованных веб-сообществ.
Математическое моделирование веб-графов в интересах понимания процессов самоорганизации в Сети и анализа алгоритмов идентификации веб-сообществ.
Разработка алгоритмов идентификации и оценки самоорганизованных веб-сообществ, учитывающих современные тенденции в развитии Сети, в том числе и наличие ложных гиперсвязей.
Разработка программного обеспечения для проведения анализа структуры Сети, идентификации и оценки веб-сообществ.
Проведение экспериментальных исследований для проверки разработанных алгоритмов и моделей с выработкой рекомендаций по их практическому применению в информационно-поисковых системах.
Научная новизна. К основным результатам работы, отличающимся научной новизной, относятся:
Модель и алгоритм имитации искусственных веб-графов с контролируемыми параметрами, учитывающие эволюционное развитие Сети и неравномерное распределение гиперсвязей внутри веб-графа и обеспечивающие анализ свойств реального веб-графа, а также отработку технологий поиска тематически связанных веб-сообществ.
Многоэтапная процедура обработки информации для идентификации веб-сообществ и реализующий её комплексный алгоритм, отличающиеся учётом гиперссылочных связей в Сети совместно с проведением контентного анализа связанных документов и обеспечивающие идентификацию веб-сообществ с учётом ложных гиперссылочных связей и обнаруженных закономерностей в структуре Сети.
Алгоритм автоматической численной оценки качества веб-сообществ, отличающийся выявлением тематики веб-сообщества с использованием "зерновых" ресурсов и обеспечивающий снятие ограничений по размерам оцениваемых веб-сообществ и их количеству, свойственных методам экспертной оценки, а также сокращение вычислительных затрат за счёт предложенного механизма определения смыслового соответствия словоформ.
4. Структура и способы организации данных программного обеспечения,
реализующего полный цикл решения задач идентификации, анализа и оценки качества самоорганизованных веб-сообществ и отличающегося применением разработанных моделей и алгоритмов, ориентированных на работу с веб-графами с учётом выявленных закономерностей в структуре Сети.
5. Результаты экспериментальных исследований по идентификации веб-
сообществ в Интернет и Мобильном Интернет, позволяющие провести
оценку совокупного объёма ресурсов, их структуры, степени
самоорганизованности, темпов роста и дать количественную оценку
повышения точности поиска в современных информационно-поисковых
системах с помощью предложенных алгоритмов обработки информации.
Практическая значимость работы. Практическая значимость
диссертационной работы заключается в создании алгоритмов обработки
информации и программных средств для моделирования, идентификации и
исследования самоорганизованных веб-сообществ, способных
непосредственно интегрироваться в существующие ИПС и позволяющих улучшить точность и полноту получаемых с их помощью результатов, а также провести автоматическую рубрикацию веб-ресурсов и оценить уровень организации сегментов Сети для выработки дальнейших рекомендаций по их поисковой оптимизации.
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы реализованы в виде специальной информационной системы исследования процессов самоорганизации в Сети. Система была использована для анализа процессов самоорганизации воронежского сегмента Интернет, сети Воронежского госуниверситета и российской части Мобильного Интернета, а также в учебном процессе Воронежского госуниверситета при разработке учебных курсов "Информационно-поисковые системы" и "Корпоративные
13 информационные системы", что подтверждается соответствующими актами
внедрения. Результаты работы были использованы при выполнении гранта
ООО "Яндекс" №67-05/07.
Апробация работы. Основные положения и результаты работы обсуждались и получили одобрение на Международной научно-технической конференции "Кибернетика и технологии XXI века" (Воронеж, 2004, 2006); Всероссийской научной конференции "Научный сервис в сети Интернет" (Новороссийск, 2003, 2004, 2005); Региональной научно-методической конференции "Информатика: проблемы, методология, технологии" (Воронеж, 2004, 2005, 2006); Всероссийской научно-методической конференции "Телематика" (Санкт-Петербург, 2004, 2006); Всероссийской научной конференции "Электронные библиотеки" (Переславль-Залесский, 2007).
Публикации. Основные результаты диссертации опубликованы в 15 научных работах, из них 2 - в изданиях, рекомендованных ВАК РФ.
Объём и структура диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 97 наименований, и одного приложения. Основная часть работы изложена на 166 страницах, содержит 13 таблиц и 52 рисунка.
Содержание работы.
Первая глава посвящена подробному обзору существующих исследований по теме идентификации самоорганизованных веб-сообществ, в том числе затронуты общие тенденции процесса самоорганизации в Сети. Кратко рассмотрены основы информационного поиска и его применения в рамках исследуемой проблематики.
Во второй главе решается задача построения модели веб-графа, необходимой для понимания процессов самоорганизации в Сети, вводится типизация веб-графов. Обосновывается многоэтапная процедура идентификации веб-сообществ на основе комбинирования как информации о
14 гиперссылочной структуре Сети, так и о содержимом её ресурсов.
Разрабатывается алгоритм автоматической оценки качества веб-сообществ.
В третьей главе диссертационной работы приведено описание разработанного программного комплекса. Определены структуры данных, используемые для хранения веб-графов, и алгоритмы, реализующие предложенные модели и алгоритмы. Описаны UML-модели программного обеспечения, реализованного для решения основных и сопутствующих задач исследований.
В четвёртой главе диссертации основное внимание уделено практическим приложениям разработанных моделей и алгоритмов. Описываются результаты экспериментальных исследований по идентификации веб-сообществ в большом Интернете на основе предложенных во второй главе моделей и алгоритмов, реализованных в виде программных средств и структур данных. Отдельным разделом вынесено исследование Мобильного Интернета, имеющее самостоятельное значение. В заключительной части главы представлены предложения по практическому применению разработанных алгоритмов обработки информации и программных реализаций в интересах повышения эффективности функционирования информационно-поисковых систем как горизонтального, так и вертикального типов.
Автор выражает благодарность научному руководителю профессору Сироте А.А., научному консультанту доценту Сычёву А.В., а также всему коллективу кафедры информационных систем Воронежского госуниверситета за помощь при выполнении работы.
Концентраторы (hubs) и авторитеты (authorities)
Несмотря на децентрализованную структуру Сети в ней прослеживаются тенденции к самоорганизации. Одной из важнейших и базовых закономерностей гиперссылочных связей сети Интернет является наличие особых веб-страниц - концентраторов и авторитетов (рисунок 1.2) [78].
Под концентраторами мы будем понимать веб-страницы, которые накапливают в себе множество гиперссылок на другие веб-страницы, а под авторитетами - веб-страницы, на которые ссылается множество других веб-страниц.
Примером концентраторов могут служить такие крупные сайты-каталоги как Yahoo (wAvw.yahoo.com). Как правило, на каждом сайте есть страница с набором ссылок - такая страница тоже фактически концентратор. Авторитеты - это популярные или компетентные сайты с высоким показателем цитируемости. Примером может служить сайт РБК (www.rbc.ru), на который часто ссылаются новостные веб-сайты.
Наличие страниц-авторитетов в Сети определяет тот факт, что некоторые веб-ресурсы имеют существенно большее количество входящих ссылок, нежели другие. На первом этапе развития поисковых технологий этот фактор был напрямую задействован информационно-поисковыми системами. Они учитывали количество входящих ссылок на веб-ресурс и присваивали ему индекс по аналогии с библиографическим индексом -индекс цитируемости. Как правило, существовали некоторые ограничения, например, ссылки с "родительского" сайта веб-ресурса не учитывались (здесь под "родительским" понимается веб-сайт Сети, частью которого этот ресурс являлся). При формировании ответа на поисковой запрос страницы с большим индексом цитируемости считались более релевантными. На данный момент прямое применение такого подхода уже не является актуальным из-за появления так называемого ссылочного спама - ссылок, созданных исключительно для искусственного повышения индекса цитируемости сайта. Свой вклад здесь также внесли баннеро-обменные рекламные сети и всевозможные счётчики посещаемости.
В сети Интернет, как и во многих других сферах деятельности человека, действует степенной закон. Как правило, исследователи Сети иллюстрируют это принципом "богатый становится ещё богаче" [79] и объясняют следующим образом: Сеть растёт путём последовательного появления в ней новых веб-ресурсов, при этом уже существующие веб-ресурсы увеличивают количество входящих на них гиперссылок пропорционально росту Сети и количеству уже имеющихся у них входящих гиперссылок. Этот результат и выражается в виде степенного закона распределения гиперссылок. Особенно явно этот закон проявляет себя на входящих (in-degrees) гиперссылках (что было подтверждено и нашими экспериментами [11]) и формулируется следующим образом [59]:
Несмотря на выявленные закономерности, исследователи ещё весьма далеки от полного понимания процессов, управляющих ростом Сети. Ведь даже степенной закон в ней не является абсолютно устойчивым для всех типов веб-ресурсов. Например, распределение ссылок в домашних страницах университетов практически полностью отклоняется от степенного закона, следуя гораздо более равномерному распределению [88].
В работе [59] и некоторых других исследованиях приводится так называемая модель "Бабочка" (Bow Tie). Согласно этой модели все ресурсы Интернет примерно равномерно распределяются между 4-мя "типами" веб-ресурсов (см. рисунок 1.5). Важность этой модели заключается в том, что она была построена в рамках самого масштабного исследования, совместно проведённого исследовательскими центрами компаний IBM, Compaq и AltaVista, и опровергла несколько принципиальных гипотез, считавшихся до неё верными. В частности гипотезу о том, что, начав "путешествие" по сети Интернет с любой веб-страницы, можно за определённое конечное число переходов по гиперссылкам попасть на любую другую веб-страницу Интернет. Для использования в дальнейшем, приведём несколько определений из [25]. Определение 1.3. Ориентированный граф называется сильно связным, если для любой пары вершин каждая из них достижима из другой. Определение 1.4. Сильно связный подграф ориентированного графа называется зоной. Определение 1.5. Зона, максимальная относительно включения вершин, называется компонентой сильной связности (КСС, англ. SCC) или бикомпонентой. Модель включает в себя "ядро" (множество SCC), два "крыла" (множества IN, OUT), а также подмножество страниц Сети, не связанных с "Бабочкой". Ядро представляет собой набор тесно связанных ресурсов Сети, являясь центральной частью модели. Фактически это компонента сильной связанности в веб-графе.
Одно из "крыльев" (IN) представляет страницы, имеющие только входящие по направлению к ядру гиперссылки, другое "крыло" (OUT) -содержит только страницы с исходящими на них из ядра гиперссылками. Авторы модели предполагают, что в множество IN могут входить новые сайты, ещё не найденные пользователями и, соответственно, не имеющие ссылок на себя со значимых ресурсов из множества SCC. В множество OUT, по мнению авторов модели, входят корпоративные сайты, имеющие только внутренние ссылки.
Модель имитации веб-фафа на основе принципа хронологического возникновения ресурсов
Для целей исследования веб-графа и предварительного тестирования поисковых алгоритмов предлагается разработать модель, которая позволяет получать искусственный веб-граф с контролируемыми параметрами, имеющий схожие с реальным характеристики, не обращаясь непосредственно к самой сети Интернет.
Предлагаемая модель эволюции веб-графа основана на идее хронологического возникновения веб-ресурсов и отражает естественное поведение авторов этих ресурсов. На основе модели имитации, реализующей концептуальную модель, нам необходимо сгенерировать искусственный веб-граф, по своей структуре и характеристикам похожий на настоящий. Контролируемыми входными параметрами мы будем считать желаемое количество вершин V и соотношение среднего числа рёбер к числу вершин Ет% = —, которому стоит присваивать значения, характерные для естественных веб-графов (фактически это неявный способ задать среднее количество Е желаемых рёбер в графе).
В соответствии с идеей хронологического возникновения ресурсов в модели эволюции веб-графа, задавая изначально количество желаемых вершин V, мы подразумеваем, что веб-ресурсы в веб-графе появлялись в определённом порядке от 7-го до V -го. При этом каждый вновь появившийся ресурс (на и-том шаге) с определённой вероятностью может поставить ссылку на уже существующие и/или получить обратную ссылку с существующих. Рассмотрим эту ситуацию для ссылок с нового ресурса на уже существующие для некоторого и-го шага, предполагая, что уже существует (п-1) узел и они связаны между собой (см. рисунок 2.1).
Таким образом, для каждого п-го шага будем первоначально рассматривать только вероятности р"—рп установления ссылок с нового появившегося веб-узла на уже существующие (но не обратно). Запишем вероятности возникновения каждого ребра в этом направлении на этапе появления новых узлов от 2 до V: n = 2: p\ Таким образом, р" это вероятность того, что при возникновении п-того узла, он установит дугу на і-й узел из числа уже существующих. Соответственно, всегда іїп, так как это вероятность создания петли в графе, которая равна 0 в нашей модели и не имеет физического смысла в Сети.
Появление «-го веб-узла (А,Р2 - А,_І вероятности того, что он установит ссылки на уже существующие веб-узлы в веб-графе) Будем исходить из гипотезы, согласно которой каждый вновь возникший я-ый веб-ресурс поставит ссылку на более старый ресурс вероятнее, чем на более новый. Тогда: Р; Р: РІ, Р!=1-Р"О, (2.2) где РІ - вероятность того, что ссылок не будет установлено. Тем самым, мы отражаем в модели существование веб-ресурсов "авторитетов" в терминологии веб-графов. При таком подходе вероятность РІ становится функцией зависимой от 4-х параметров: р!=Р(,Ет,п,і),і = \,п-1,п = 2,У.
Предлагается записать вероятности, отвечающие условию (2.2) и реализующие предлагаемую модель формирования веб-графа, в следующем виде:
Здесь C„w - это нормировочная константа, зависящая только от входных параметров V и Eovg. В содержательном плане запись (2.3) означает, что авторитетность каждого более позднего ресурса уменьшается по сравнению с более ранним ресурсом из числа уже имеющихся. Следует отметить, что постулирование подобной закономерности присвоения вероятностей р", і = \,п-1 не является единственным. Возможно использование любого другого закона изменения, сохраняющего концепцию хронологического возникновения ресурсов и большей "авторитетности" ранее созданных ресурсов.
Программные модули, реконструирующие (или генерирующие) веб-граф
К данной группе относятся программные модули, результатом работы которых является веб-граф, получаемый с помощью реконструкции непосредственно из Сети или искусственным способом на основе моделирования.
Модуль WebGraphGenerator строит искусственный веб-граф по заданным параметрам V, Eavg и dM или загружает готовый, после чего проводит анализ некоторых характеристик построенного/загруженного веб-графа: Е вычисляет соотношение —; V вычисляет и сохраняет таблицы ранг входящих(исходящих) ссылок - частота; вычисляет и сохраняет таблицу расширенных характеристик узлов там, где указан идентификатор узла и количество входящих и исходящих ссылок.
Модули WEBcrawler и WAPcrawler из этой же группы представляют собой сетевых "пауков". Отличие этих двух модулей состоит только в ориентации на основной Интернет и Мобильный Интернет, обусловленной особенностями используемых в МИ типов данных. Для определённости мы рассмотрим только WEBcrawler.
Графический интерфейс WEBcrawler (сетевого паука) предельно упрощён, как и в большинстве других использующихся модулей. В основном отображение информации выполняется с использованием shell-оболочки. На рисунке 3.3 приведена UML диаграмма классов (class diagram) для разработанного сетевого паука
Основной класс CMain управляет работой сетевого паука, он создаёт экземпляры очереди {CQueue) и графа {CGraph). С началом извлечения веб-графа из Сети в очередь помещаются "стартовые" ресурсы. Для построения локального веб-графа ими являются "зерновые" ресурсы и ресурсы, ссылающиеся на них. Они получаются при помощи модуля InLinksCounter, описанного ниже. Основной класс обращается к очереди и получает от неё URL-адреса для закачки (стратегия, по которой выдаётся URL, определяется внутри экземпляра CQueue через переменную workMode), затем передаёт их в сетевой транспорт CTransport. Закаченные сетевым транспортом ресурсы передаются обратно основному классу, который посредством обработки их в классе CLinkExtractor, получает из них ссылки и добавляет их в очередь.
Параллельно с этим процессом, основной класс добавляет информацию о связанности ресурсов в экземпляр класса CGraph. Основной проблемой при работе сетевого паука является обеспечение его стабильности. Являясь просто модулем для построения веб-графа или частью полноценной ИПС, сетевой паук должен работать сутки, а иногда и месяцы с сильно различающимися и неповторяющимися данными. Как правило, рано или поздно находится веб-ресурс, на котором сетевой паук некорректно завершает работу. Для решения этой проблемы разработан механизм, позволяющий продолжить работу, игнорируя подобный ресурс. Позже такие проблемные ресурсы анализируются отдельно и в код паука добавляются обновления. Описанный подход свидетельствует о том, что разработка качественного сетевого паука без его экспериментального тестирования на больших объёмах реальных данных просто невозможна. Этот же вывод подтверждают разработчики крупных поисковых систем, например Google (http://www.google.com). Для обеспечения стабильности был предложен многоуровневый режим отладки, позволяющий выводить минимум дополнительной информации и проводить минимум дополнительных проверок (что в итоге повышает производительность), а также отслеживать каждый шаг программы, позволяя быстро выявить источник проблем.
Результаты экспериментальных исследований при идентификации веб-сообществ на основе разработанной многоэтапной процедуры
Ещё один алгоритм, эффективная реализация которого весьма важна для успешной работы программного обеспечения - это алгоритм, предназначенный для поиска связанных компонент в модуле SCCtarjan. В отличие от максимальных потоков, существует ряд алгоритмов, решающих эту задачу за время порядка 0(V + E). Здесь также стоит задача выбора подходящего алгоритма именно для разреженных графов. К сожалению, наиболее простой алгоритм, с линейным временем выполнения, принадлежащий Косарайю [37], в данном случае не является оптимальным. Предпочтительным оказалось использование более подходящего для разреженных графов, представленных в форме, отличной от матрицы смежности, алгоритма Тарьяна. Это объясняется тем, что последний использует только один проход по графу, поскольку не требует обращения для разреженных графов (в отличии от алгоритма Косарайю). Кроме того, при хранении графа в виде, отличном от матрицы смежности, потребуются дополнительные ресурсы, увеличивающие общую трудоёмкость. В абсолютном значении для разреженных графов скорость обоих алгоритмов равна СКУ+Е).
Реализованный алгоритм базировался на использовании двух закономерностей. Во-первых, поскольку вершины рассматриваются в обратном топологическом порядке, то при достижении конца рекурсивной функции (в приложении определена как recursiveSCC) для какой-либо вершины, известно, что уже не встретится ни одна вершина из той же связанной компоненты (в силу того, что все вершины, достижимые из этой вершины, уже обработаны). Во-вторых, обратные связи в дереве обеспечивают второй путь из одной вершины в другую и связывают между собой сильные компоненты.
Предложенная реализация алгоритма продемонстрировала достаточно высокое быстродействие, соответствующие результаты, отвечающие условиям поиска связанных компонент в веб-графе, приведены в таблице 3.2.
Выводы по главе
1. В рамках проведённых исследований разработан программный комплекс, обеспечивающий проведение полного цикла исследований при идентификации, анализе и оценке качества самоорганизованных веб 114 сообществ. Программный комплекс представляет собой набор модулей, которые можно разделить на группы по отношению к проводимым операциям над веб-графом. Данные группы объединяются по функциональному назначению и включают в себя модули реконструирующие, преобразующие и обрабатывающие веб-графы. Любой эксперимент, выполненный в соответствии с разработанными подходами, можно представить как последовательную цепочку применения модулей программного комплекса.
2. Описаны особенности реализованных в рамках программного комплекса алгоритмов обработки информации и использованных структур данных. Одним из основных принципов, используемых при разработке, являлся принцип масштабируемости, который позволил работать с реальными данными из Сети. Кроме того, использовалась унификация данных, позволяющая выходные данные одного модуля использовать как входные для другого. При этом все данные хранятся в открытых форматах, что повышает их переносимость и позволяет использовать стандартные средства для постобработки. Ряд программных модулей комплекса, не требующих выполнения сложных ресурсоёмких задач, реализован на языке Java, что делает их кроссплатформенными. В частности, модуль, реализующий алгоритм построения локального веб-графа, может выполняться в nix средах, которые наиболее предпочтительны для сетевых серверных приложений.
3. Получена оценка наиболее ресурсоёмких элементов программного комплекса на эффективность и масштабируемость. К ним относятся модули MaxFlowMinCut, SCCtarjan и FLGcommunity. Алгоритм идентификации связанных компонент (модуль SCCtarjan), в контексте разработанной многоэтапной процедуры идентификации веб-сообществ, показал свою масштабируемость, что позволяет использовать этот подход на разреженных веб-графах размером в десятки миллионов узлов. Алгоритм поиска максимального потока минимальной стоимости (модули MaxFlowMinCut и FLGcommunity) менее масштабируем и использование его за пределами локальных веб-графов глубины три и более с большими пропускными способностями рёбер может быть весьма ограничено.
В целом разработка и отладка программного комплекса заняла существенную часть времени, необходимого для исследований по теме диссертации. Всего было написано около 20 000 строк на C/C++, 11 000 строк на Java и до 40 сложных SQL-скриптов.
