Разработка специального математического и программного обеспечения выявления веб-сообществ в информационно-поисковых системах

• Автор: Баженов, Михаил Михайлович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Воронеж
• Количество страниц: 172 с. : ил.

1 МОДЕЛИ И МЕТОДЫ ИДЕНТИФИКАЦИИ ВЕБ-СООБЩЕСТВ

1.1 Основные задачи, решаемые современными информационнопоисковыми системами

1.2 Анализ гиперссылочной структуры Сети

1.2.1 Концентраторы (hubs) и авторитеты (authorities)

1.2.2 Цитируемость и степенной закон распределения гиперссылок

1.2.3 Анализ веб-графа на наличие организованных структур

1.2.4 Комплексные методы и алгоритмы учёта цитируемости: HITS и

PageRank

1.3 Потоковые методы идентификации веб-сообществ

1.3.1 Метод FLG

1.3.2 Модифицированный поиск веб-сообществ на базе метода FLG с

настраиваемыми ёмкостями рёбер
ВЫВОДЫ ПО ГЛАВЕ
2 РАЗРАБОТКА МОДЕЛЕЙ И СОВЕРШЕНСТВОВАНИЕ МЕТОДОВ ЭФФЕКТИВНОЙ ИДЕНТИФИКАЦИИ ВЕБ-СООБЩЕСТВ
2.1 Модель имитации веб-графа и алгоритм машинной генерации искусственного веб-графа
2.1.1 Модель имитации веб-графа на основе принципа хронологического
возникновения ресурсов
2.1.2 Анализ искусственно сгенерированных веб-графов и их
применение для исследований Сети
2.2 Типизация веб-графов и оценка достижимости узлов
2.2.1 Типизация веб-графов
2.2.2 Оценка достижимости узлов
2.3 Многоэтапная процедура идентификации веб-сообществ на основе сильно связанных компонент и контентного анализа
2.4 Алгоритм автоматической численной оценки качества веб-сообществ84
ВЫВОДЫ ПО ГЛАВЕ

3 ПРИНЦИПЫ ПОСТРОЕНИЯ АЛГОРИТМОВ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ ОБРАБОТКИ ИНФОРМАЦИИ В ИНТЕРЕСАХ ИССЛЕДОВАНИЯ ПРОЦЕССОВ САМООРГАНИЗАЦИИ В СЕТИ
3.1 Общая структура разработанного программного комплекса для
обработки данных при решении задачи информационного поиска и выявления веб-сообществ
3 Л. 1 Программные модули, реконструирующие (или генерирующие)
веб-граф
ЗЛ.2 Программные модули, преобразующие веб-граф
ЗЛ.З Программные модули, обрабатывающие веб-граф
3 Л .4 Вспомогательные программные модули
3.2 Используемые структуры данных
3.2.1 Формат хранения данных веб-графа в файловой системе
3.2.2 Размещение веб-графа в оперативной памяти
3.3 Алгоритмы обработки веб-графа
3.3.1 Алгоритм генерации искусственного веб-графа
3.3.2 Алгоритм поиска максимального потока минимальной стоимости
3.3.3 Алгоритм поиска связанных компонент
ВЫВОДЫ ПО ГЛАВЕ
4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ВЕБ-ГРАФА И ВЕБСООБЩЕСТВ
4.1 Анализ алгоритмов идентификации веб-сообществ на основе метода РЬО для различных типов веб-графов
4.2 Результаты экспериментальных исследований при идентификации вебсообществ на основе разработанной многоэтапной процедуры
4.2.1 Оценка эффективности разработанной многоэтапной процедуры
идентификации веб-сообществ
4.2.2 Сравнительный анализ разработанной многоэтапной процедуры
идентификации веб-сообществ и метода ИХ}
4.3 Экспериментальные исследования алгоритма автоматической численной оценки качества веб-сообществ
4.4 Исследование Мобильного Интернета
4.5 Применение разработанных алгоритмов обработки информации в
информационно-поисковых системах
4.5.1 Уточнение результатов поиска

4.5.2 Автоматическое пополнение и оценка веб-каталогов
4.5.3 Интеграция в вертикальные информационно-поисковые системы
ВЫВОДЫ ПО ГЛАВЕ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ
Алгоритм генерации искусственного веб-графа
Алгоритм поиска максимального потока минимальной стоимости методом Форда-Фалкерсона
Алгоритм проверки достижимости одного узла из другого
Алгоритм поиска связанных компонент

Далее полученные ранги узлов rt используются для назначения ёмкостей рёбер. Назначаются адаптивный рейтинг концентраторов h'0 vi
~ п'
адаптивный рейтинг авторитетов %. :
И = r.h а' =г а п
ц h o, ■> Ц а v,
Первоначально рейтинг концентраторов и авторитетов лежит в пределах значений 0<ИЦ ,ац <1 и не пригоден для ёмкостей рёбер, так как их значения должны лежать в области целых положительных чисел.
Следовательно, rh и га ключевые факторы в использовании оригинальных рейтингов концентраторов и авторитетов для наилучшего назначения ёмкостей рёбер. В первую очередь определяется максимальное значение адаптивного рейтинга концентраторов и авторитетов. Как указывалось ранее (рисунок 1.10), у нас присутствует один финальный скачок, т.е. если ёмкости рёбер превысили определённое значение, всё узлы графа попадают в члены веб-сообщества. Для примера, представленного на рисунке 1.10, финальный скачок происходит при ёмкости рёбер равной 22. Авторы [76] предлагают использовать значение ёмкости, при котором происходит финальный скачок, как максимальное значение. Оценка эффективности при таком назначении ёмкостей приведена в [76].
Авторы [76] резюмируют процедуру поиска максимального потока с изменяющимися ёмкостями рёбер на основе HITS следующим образом.
1. На входе S = juS|,uS2 uSi j как множество “зерновых” узлов.
2. Извлечь подграф в пределах глубины 2 около каждой ц е S.
3. Посчитать векторы концентраторов и авторитетов Н и А.
4. Построить локальный граф G(V,E), аналогично соответствующему
решению в [67].