Разработка специального математического и программного обеспечения выявления веб-сообществ в информационно-поисковых системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Баженов, Михаил Михайлович

• Баженов, Михаил Михайлович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Баженов, Михаил Михайлович

ВВЕДЕНИЕ.

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 Алгоритм автоматической численной оценки качества веб-сообществ

ВЫВОДЫ ПО ГЛАВЕ

3 ПРИНЦИПЫ ПОСТРОЕНИЯ АЛГОРИТМОВ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ ОБРАБОТКИ ИНФОРМАЦИИ В ИНТЕРЕСАХ ИССЛЕДОВАНИЯ ПРОЦЕССОВ САМООРГАНИЗАЦИИ В СЕТИ.

3.1 Общая структура разработанного программного комплекса для обработки данных при решении задачи информационного поиска и выявления веб-сообществ.

3.1.1 Программные модули, реконструирующие (или генерирующие) веб-граф.

3.1.2 Программные модули, преобразующие веб-граф.

3.1.3 Программные модули, обрабатывающие веб-граф.

3.1.4 Вспомогательные программные модули.

3.2 Используемые структуры данных.

3.2.1 Формат хранения данных веб-графа в файловой системе.

3.2.2 Размещение веб-графа в оперативной памяти.

3.3 Алгоритмы обработки веб-графа.

3.3.1 Алгоритм генерации искусственного веб-графа.

3.3.2 Алгоритм поиска максимального потока минимальной стоимости

3.3.3 Алгоритм поиска связанных компонент.

ВЫВОДЫ ПО ГЛАВЕ.ИЗ

4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ВЕБ-ГРАФА И ВЕБ-СООБЩЕСТВ.

4.1 Анализ алгоритмов идентификации веб-сообществ на основе метода FLG для различных типов веб-графов.

4.2 Результаты экспериментальных исследований при идентификации веб-сообществ на основе разработанной многоэтапной процедуры.

4.2.1 Оценка эффективности разработанной многоэтапной процедуры идентификации веб-сообществ.

4.2.2 Сравнительный анализ разработанной многоэтапной процедуры идентификации веб-сообществ и метода FLG.

4.3 Экспериментальные исследования алгоритма автоматической численной оценки качества веб-сообществ.

4.4 Исследование Мобильного Интернета.

4.5 Применение разработанных алгоритмов обработки информации в информационно-поисковых системах.

4.5.1 Уточнение результатов поиска.

4.5.2 Автоматическое пополнение и оценка веб-каталогов.

4.5.3 Интеграция в вертикальные информационно-поисковые системы

ВЫВОДЫ ПО ГЛАВЕ.

Введение диссертации (часть автореферата) на тему «Разработка специального математического и программного обеспечения выявления веб-сообществ в информационно-поисковых системах»

Самая фундаментальная и отличительная черта наступившего информационного века состоит в том, что почти вся информация стала цифровой. В конце концов, все библиотечные и печатные материалы будут отсканированы и сохранены в цифровом виде с возможностью свободного или контролируемого доступа.

Бурное развитие сетевых технологий, в том числе и сети Интернет (в дальнейшем Сети), способствуют значительному увеличению доступных информационных ресурсов и объемов передаваемой информации. На сегодняшний день каждый человек может внести свой вклад в формирование мировых информационных ресурсов Сети, что приводит к колоссальной динамике их роста. При сегодняшних объемах доступной в Сети информации решение задач информационного поиска становится не только приоритетным, но и жизненно необходимым для обеспечения своевременного доступа к интересующей информации. Накопленные к настоящему времени колоссальные объемы информации в совокупности с непрерывно увеличивающимися темпами ее роста определяют актуальность и значимость исследований в области информационного поиска.

Существует ряд авторитетных международных конференций по информационному поиску, посвященных, в том числе, обсуждению вопросов информационного поиска в сети Интернет. Это такие известные конференции как TREC (http://trec.nist.gov), SIGIR (http://www.sigir.org), WWW Conference (http://www2006.org) и некоторые другие: CIKM (http://www.cikm.org), SIGMOD (http://www.sigmod.org), KDD (http://www.acm.org/sigs/sigkdd/). Высокий авторитет конференций TREC, SIGIR, WWW и участие в них ведущих исследовательских коллективов и разработчиков технологий информационного поиска во многом определяет приоритетные направления исследований и задает общие принципы развития поисковых систем.

Кроме того, существует три российские конференции, заслуживающие внимания: DIALOG-21 (http://www.dialog-21.ru), RCDL http://www.rcdl2006.uniyar.ac.ru) и РОМИП (http://romip.narod.ru).

Последние крупные исследования по оценке мировых информационных ресурсов и в том числе ресурсов сети Интернет проводились в 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 ООО терабайт.

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

Одной из задач, призванных решить проблему доступа к необходимой информации при такой скорости роста Сети, является изучение закономерностей в системе её гиперсвязей. Принято считать, что Сеть - это распределенный гипертекст. Однако это не совсем так. Гипертекст обычно подразумевает наличие концептуальной модели, которая накладывает ограничения согласованности на данные и гиперсвязи. В Сети подобной модели обычно не существует даже для тех её частей, которые находятся под единым административным контролем.

Как показали многие исследования [79,84,86], структура гипертекстовых ссылок в Сети подчиняется степенному закону и законам Зипфа [82], что характерно для многих других структур, созданных человеком. При этом другие классические распределения, например распределение Пуассона, используемые для описания случайных сетей и графов, в данном случае не наблюдаются.

В современных информационно-поисковых системах (далее ИПС) Интернет данные закономерности не используются в достаточной мере, несмотря на то, что в ряде работ [78,79,83,87 и др.] исследуется возможность применения в информационном поиске уникальных свойств сети Интернет, не присущих другим коллекциям данных, для которых разрабатывалась и на которых апробировалась классическая теория поиска. Ключевым в подобных исследованиях является то, что Интернет есть не только "склад информации", но и динамически изменяющаяся неоднородная Сеть, в которой всё более явно проявляются процессы самоорганизации. Тем сложнее становится её анализ не только в качественном, но и в количественном отношении - число гиперссылок во много раз превышает число самих веб-ресурсов, количество которых, как было показано выше, уже измеряется миллиардами. Феномен самоорганизации в сети Интернет приводит к формированию всё более сложных структур - веб-сообществ, анализ которых потенциально может существенно улучшить эффективность классического поиска. Подобные самоорганизованные структуры и являются предметом исследования данной работы.

В литературе [70] даётся следующее неформализованное и наиболее общее определение понятия веб-сообщество: веб-сообщество - это множество веб-ресурсов, связанных общей тематикой. Соответственно, задача идентификации веб-сообществ представляет собой задачу выделения множества веб-ресурсов, связанных общей тематикой. В зависимости от конкретных требований к веб-сообществам (например, степень ссылочной связанности входящих в них веб-ресурсов) способы идентификации веб-сообществ могут существенно отличаться. В данной работе в основном рассматривается идентификация веб-сообществ на основе анализа ссылочной связанности веб-графа, что сводит задачу идентификации веб-сообществ к задаче нахождения веб-подграфа (часто с последующей обработкой). Решение задачи идентификации веб-сообществ имеет ряд важных практических приложений и может использоваться при разработке автоматических веб-порталов и рубрикаторов, поисковых систем направленного действия (так называемый вертикальный поиск), а также для расширения возможностей поисковых систем, основанных на текстовом поиске.

Первая модель идентификации веб-сообществ была предложена в работе 1998 г. Гибсона (D. Gibson), Клейнберга (J. Kleinberg) и Рахавана (Р. Raghavan) [70]. Она была основана на извлечении веб-сообществ с помощью алгоритма ранжирования в поисковых системах, получившего название HITS (Hyperlink-Induced Topic Search) [78]. Далее в 1999-2000 гг. несколько исследователей и, прежде всего, Рахаван обобщили полученные закономерности, наблюдаемые при самоорганизации в Сети, и предложили ряд моделей, описывающих структуру Интернет [59,80], в том числе и веб-сообщества. Первые работы, развивающие идею идентификации веб-сообществ как отдельное направление и использующие альтернативные подходы (т.е. не основанные на HITS и т.п.), были опубликованы в 2000-2002 гг. Флэйком (G. Flake), Лоуренсом (S. Lawrence) и Гайлсом (С. L. Giles) [65,67]. Позже, в 2002-2004 гг. японские исследователи Ямафуджи (N. Imafuji) и Китсурегава (М. Kitsuregawa) провели подробный анализ работ Флэйка и других, выявив их недостатки и предложив улучшенные методы по идентификации веб-сообществ [74-76].

Задача идентификации самоорганизованных веб-сообществ в большинстве работ так или иначе сводится к поиску максимального потока минимальной стоимости в транспортных st-сетях. Теория графов предоставляет достаточно адекватный математический аппарат для решения подобных задач. Методы и алгоритмы теории графов непосредственно применимы к Интернет, так как эта сеть может быть представлена в виде гигантского графа, где узлы - веб-страницы, а рёбра - гиперссылки. Проблемой при идентификации веб-сообществ становится размер исследуемого графа, при котором он не поддается ни полному воспроизведению, ни обработке.

Анализ существующих работ Флейка, Лоуренса, Гайлса, Ямафуджи и Китсурегава, посвященных процессам самоорганизации в Интернет и идентификации веб-сообществ в интересах информационного поиска, выявил незначительное число проведённых исследований. При этом готовых и апробированных решений (способных непосредственно интегрироваться в существующие информационно-поисковые системы) ещё практически не существует, что во многом связано с отсутствием достаточно проработанной теории и практики решения задач идентификации веб-сообществ и масштабностью требуемых исследований. В тоже время учёт подобных факторов, как показывает анализ, выполненный в работах Д.Д. Козлова и А.А. Беловой [29], позволяет существенно повысить как эффективность функционирования информационно-поисковых систем, так и сформировать соответствующие рекомендации для их пользователей.

В имеющихся публикациях, рассматривающих вопросы идентификации самоорганизованных веб-сообществ в сети Интернет, не учитываются многие реалии современной Сети и, прежде всего: существование "ложных" гиперссылочных связей, не характеризующих тематику веб-сообщества, но внешне удовлетворяющих всем предъявляемым критериям. Подобные факторы вызывают появление так называемых страниц-шумов, фактически не соответствующих тематике. Кроме того, имеет место постепенное вытеснение поверхностного Web динамическими ресурсами, что приводит к неадекватности результатов, полученных на основе реконструкций веб-графов, не учитывающих глубинный Web (т.е. ресурсы, генерируемые по запросу с помощью различных технологий с применением баз данных).

Указанные факторы определяют актуальность темы диссертации, направленной на поиск эффективных решений задачи идентификации полноценных веб-сообществ.

Цели и задачи исследования. Целью диссертации является разработка моделей, алгоритмов и программных средств для выявления и оценки веб-сообществ в сети гипертекстовых ресурсов на основе комплексного учёта гиперсвязей и содержания веб-ресурсов в интересах повышения эффективности функционирования информационно-поисковых систем и анализа сетевых ресурсов.

В соответствии с указанной целью в работе поставлены и решены следующие основные задачи:

1. Анализ современных подходов к исследованию процессов самоорганизации в сети Интернет и идентификации самоорганизованных веб-сообществ.

2. Математическое моделирование веб-графов в интересах понимания процессов самоорганизации в Сети и анализа алгоритмов идентификации веб-сообществ.

3. Разработка алгоритмов идентификации и оценки самоорганизованных веб-сообществ, учитывающих современные тенденции в развитии Сети, в том числе и наличие ложных гиперсвязей.

4. Разработка программного обеспечения для проведения анализа структуры Сети, идентификации и оценки веб-сообществ.

5. Проведение экспериментальных исследований для проверки разработанных алгоритмов и моделей с выработкой рекомендаций по их практическому применению в информационно-поисковых системах.

Научная новизна. К основным результатам работы, отличающимся научной новизной, относятся:

1. Модель и алгоритм имитации искусственных веб-графов с контролируемыми параметрами, учитывающие эволюционное развитие Сети и неравномерное распределение гиперсвязей внутри веб-графа и обеспечивающие анализ свойств реального веб-графа, а также отработку технологий поиска тематически связанных веб-сообществ.

2. Многоэтапная процедура обработки информации для идентификации веб-сообществ и реализующий её комплексный алгоритм, отличающиеся учётом гиперссылочных связей в Сети совместно с проведением контентного анализа связанных документов и обеспечивающие идентификацию веб-сообществ с учётом ложных гиперссылочных связей и обнаруженных закономерностей в структуре Сети.

3. Алгоритм автоматической численной оценки качества веб-сообществ, отличающийся выявлением тематики веб-сообщества с использованием "зерновых" ресурсов и обеспечивающий снятие ограничений по размерам оцениваемых веб-сообществ и их количеству, свойственных методам экспертной оценки, а также сокращение вычислительных затрат за счёт предложенного механизма определения смыслового соответствия словоформ.

4. Структура и способы организации данных программного обеспечения, реализующего полный цикл решения задач идентификации, анализа и оценки качества самоорганизованных веб-сообществ и отличающегося применением разработанных моделей и алгоритмов, ориентированных на работу с веб-графами с учётом выявленных закономерностей в структуре Сети.

5. Результаты экспериментальных исследований по идентификации веб-сообществ в Интернет и Мобильном Интернет, позволяющие провести оценку совокупного объёма ресурсов, их структуры, степени самоорганизованности, темпов роста и дать количественную оценку повышения точности поиска в современных информационно-поисковых системах с помощью предложенных алгоритмов обработки информации.

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы реализованы в виде специальной информационной системы исследования процессов самоорганизации в Сети. Система была использована для анализа процессов самоорганизации воронежского сегмента Интернет, сети Воронежского госуниверситета и российской части Мобильного Интернета, а также в учебном процессе Воронежского госуниверситета при разработке учебных курсов "Информационно-поисковые системы" и "Корпоративные информационные системы", что подтверждается соответствующими актами внедрения. Результаты работы были использованы при выполнении гранта ООО "Яндекс" №67-05/07.

Апробация работы. Основные положения и результаты работы обсуждались и получили одобрение на Международной научно-технической конференции "Кибернетика и технологии XXI века" (Воронеж, 2004, 2006); Всероссийской научной конференции "Научный сервис в сети Интернет" (Новороссийск, 2003, 2004, 2005); Региональной научно-методической конференции "Информатика: проблемы, методология, технологии" (Воронеж, 2004, 2005, 2006); Всероссийской научно-методической конференции "Телематика" (Санкт-Петербург, 2004, 2006); Всероссийской научной конференции "Электронные библиотеки" (Переславль-Залесский, 2007).

Публикации. Основные результаты диссертации опубликованы в 15 научных работах, из них 2 - в изданиях, рекомендованных ВАК РФ.

Объём и структура диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 97 наименований, и одного приложения. Основная часть работы изложена на 166 страницах, содержит 13 таблиц и 52 рисунка.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Баженов, Михаил Михайлович

Выводы по главе

1. Проведено обобщение и уточнение известных результатов в части экспериментальных исследований поведения потоковых методов идентификации веб-сообществ на различных типах веб-графов, к которым приводят разные стратегии их реконструкции. Из полученных результатов следует, что на полных веб-графах коэффициент ёмкости пропускных способностей рёбер не влияет на количество идентифицируемых членов веб-сообщества для алгоритмов, реализованных на основе метода FLG. На частичных веб-графах такая зависимость присутствует и имеет скачкообразный характер, что подтверждает результаты в ряде известных работ. Это позволяет сделать вывод о том, что эти эксперименты проводились авторами на частичных веб-графах.

2. Анализ полученных результатов по использованию известного метода FLG для идентификации веб-сообществ показал, что ядро реализующего его алгоритма - алгоритм поиска максимального потока минимальной стоимости, имеет существенные ограничения по масштабируемости как в направлении увеличения локального веб-графа, так и при больших пропускных способностях рёбер. Это, наряду с уменьшающейся актуальностью такого подхода в целом из-за существенного влияния "ложных" и информационных гиперссылок, ограничивает его использование для идентификации реальных веб-сообществ.

3. Результаты экспериментов по идентификации самоорганизованных веб-сообществ на основе разработанной многоэтапной процедуры, учитывающей как ссылочную структуру, так и содержимое документов, показали достаточно высокую эффективность этого подхода, показав точность около 77% при 97% полноты поиска. Проведена оценка зависимости качества идентификации веб-сообществ от выбираемого числа ключевых слов, отображающих тематику веб-сообщества. Даны возможные объяснения закономерности ухудшения качества идентифицированных веб-сообществ при росте числа ключевых слов, вытекающие из законов Зипфа.

4. Предложенный алгоритм автоматической численной оценки веб-сообществ показал адекватные результаты в сравнении с результатами экспертной оценки. Разработанный в контексте этого алгоритма подход по нормализации словоформ показал удовлетворительные результаты в экспериментах, несмотря на принципиальное отсутствие учёта семантики и правил словообразования. В целом данный алгоритм может рассматриваться в качестве альтернативы методам экспертной оценки при обработке большого количества оцениваемых веб-сообществ за минимальное время, а также для оценки уже существующих тематических каталогов на соответствие документов основной тематике.

5. Выполнено исследование Мобильного Интернета и дана оценка динамики его роста за период исследований. Показана схожесть основных закономерностей формирования МИ с большим Интернет и проведён ряд экспериментов по идентификации веб-сообществ на веб-графе МИ. Сделан вывод о неразвитости МИ и дан прогноз его будущего развития в виде быстрого слияния с большим Интернетом.

6. Рассмотрены вопросы практического применения разработанных алгоритмов обработки информации и программных реализаций в интересах повышения эффективности поиска в Сети. Предложены и даны оценки эффективности возможностям применения алгоритмов, основанных на идентификации веб-сообществ, для создания уточняющих модулей ИПС, для автоматической рубрикации и/или оценки качества существующих веб-каталогов, а также для автоматизации части функций вертикальных ИПС.

Заключение

В ходе выполнения диссертационной работы поставлены и решены следующие задачи: проанализированы современные подходы к исследованию процессов самоорганизации в сети Интернет и к идентификации самоорганизованных веб-сообществ; разработана концептуальная модель веб-графа, реализующая идею хронологического возникновения ресурсов, и модель имитации искусственного веб-графа; разработана многоэтапная процедура идентификации самоорганизованных веб-сообществ, учитывающая современную структуру Сети; разработан алгоритм автоматической численной оценки качества веб-сообществ; разработан комплекс программ, реализующий как предложенные, так и уже известные подходы к идентификации веб-сообществ; проведены экспериментальные исследования предложенных моделей и алгоритмов, и их сравнение с существующими подходами; внесены предложения и даны оценки эффективности по применению результатов исследований в современных информационно-поисковых системах.

На основе проведенных исследований можно сделать следующие выводы:

1. Проведено обобщение известных результатов и дальнейшее их развитие в части исследования поведения потоковых методов идентификации веб-сообществ на различных типах графов, к которым приводят разные стратегии реконструкции веб-графа. Из полученных результатов следует, что на полных веб-графах коэффициент ёмкости пропускных способностей рёбер не влияет на количество идентифицируемых членов веб-сообщества для метода FLG и производных от него потоковых подходов. На частичных веб-графах такая зависимость присутствует и имеет скачкообразный характер. На основе этих данных введена типизация веб-графов.

2. Предложена концептуальная модель эволюции веб-графа, модель имитации веб-графа и алгоритм генерации искусственных веб-графов с контролируемыми параметрами. Предложенная модель имитации веб-графа позволила объяснить различие зависимостей ранг-частота для разных тематических веб-графов. Показано, что степень выпуклости на графиках зависит от параметра dM предложенной модели, определяющего долю рёбер со старых вершин на новую. Доказано утверждение, позволяющее вычислить вероятность достижимости двух случайно выбранных узлов в веб-графе. Из него следует, что в реальной Сети такие узлы достижимы не менее чем в 13% случаев.

3. Разработана многоэтапная процедура идентификации веб-сообществ, основанная на использовании информации о связях в веб-графе и анализе содержимого самих документов. Благодаря изначальной локализации только части веб-графа, последний, наиболее ресурсоёмкий этап анализа содержимого веб-ресурсов выполняется для наиболее вероятных кандидатов на члены веб-сообщества. Результаты экспериментов по идентификации различных самоорганизованных веб-сообществ на основе разработанной многоэтапной процедуры показали её высокую эффективность применительно к современной Сети.

4. Разработан алгоритм автоматической численной оценки качества идентифицированных веб-сообществ для любого метода идентификации, имеющего несколько членов со 100%-й принадлежностью к веб-сообществу. Алгоритм показал достаточно хорошие результаты в сравнении с экспертной оценкой при определении качества веб-сообществ. Разработанный в контексте этого алгоритма подход по нормализации словоформ показал удовлетворительные результаты в экспериментах, несмотря на принципиальное отсутствие учёта семантики и словообразования. В целом алгоритм может рассматриваться как альтернатива экспертной оценки при обработке большого количества оцениваемых веб-сообществ, а также для оценки уже существующих тематических каталогов на соответствие документов выбранной тематике.

5. В рамках проведённых исследований реализован программный комплекс, предназначенный для идентификации, анализа и оценки качества самоорганизованных веб-сообществ. Любой эксперимент, реализующий разработанные подходы, можно представить UML диаграммой последовательностей действий из цепочки модулей программного комплекса. Описаны особенности реализованных алгоритмов комплекса и использованных структур данных. Получена оценка наиболее ресурсоёмких элементов программного комплекса на эффективность и масштабируемость. Обеспеченный уровень масштабируемости позволил работать с реальными данными из Сети. Кроме того, использовалась унификация данных, позволяющая выходные данные одного модуля использовать как входные для другого. При этом все данные хранятся в открытых форматах, что повышает их переносимость и позволяет использовать стандартные средства для постобработки.

6. Исследован Мобильный Интернет и дана оценка динамики его роста за период исследований. Показана схожесть МИ с большим Интернет и проведён ряд экспериментов по идентификации веб-сообществ на веб-графе МИ. Экспериментальные исследования по идентификации самоорганизованных веб-сообществ в МИ показали, что с одной стороны такие сообщества в МИ есть, с другой - они мало организованны (но не малочисленны) и относятся к специфическим для МИ тематикам (сообщества любителей какой-либо модели или производителя телефона, сообщества бесплатного мобильного контента и т.п.). Из общих тематик пока более всего развиты новостные сообщества и информационные сервисы о погоде, курсах валют и акций. Таким образом сделано заключение о слабой развитости МИ и дан прогноз его развития в виде быстрого слияния с большим Интернетом.

7. Рассмотрены вопросы практического применения разработанных алгоритмов обработки информации и программных реализаций в интересах повышения эффективности поиска в Сети. Разработаны предложения и даны оценки эффективности по их использованию для решения следующих задач: уточнения результата поиска, автоматического пополнения веб-каталогов и автоматизации ряда функций вертикальных информационно-поисковых систем. Определены принципы интеграции предложенных программных средств в существующие структурные схемы информационно-поисковых систем.

Список литературы диссертационного исследования кандидат технических наук Баженов, Михаил Михайлович, 2007 год

1. Аветисян, Р. Д. Теоретические основы информатики / Р. Д. Аветисян, Д. О. Аветисян. - М.: Российск. гос. гуманит. ун-т, 1997. - 168 с.

2. Агеев, М. С. Экспериментальные алгоритмы поиска/классификации и сравнение с «basic line» / М. С. Агеев, Б. В. Добров, Н. В. Лукашевич, А. В. Сидоров // Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004). Пущино, 2004. - С. 62-89.

3. Айзеке, С. Dynamic HTML / С. Айзеке. СПб.: BHV-Санкт-Петербург, 1998.-496 с.

4. Баженов, М. М. Автоматическая оценка качества алгоритма идентификации Веб-сообществ / М. М. Баженов, А. В. Сычёв // Кибернетика и высокие технологии 21 века: 7 Международ, науч.-техн. конф., 16-18 мая 2006. Воронеж, 2006. - Т. 2. - С. 696-706.

5. Баженов, М. М. Анализ веб-графа мобильного рунета / М. М. Баженов, А. В. Сычёв // Информатика : проблемы, методология, технологии: материалы 6-ой международ, науч.-метод. конф., Воронеж, 9-10 февр. 2006. Воронеж, 2006. - С. 541-543.

6. Баженов, М. М. Анализ задачи идентификации самоорганизованных Web-сообществ / М. М. Баженов, А. В. Сычев // Информатика: проблемы, методология, технологии: Материалы 4-ей регион, науч.-метод. конф., 3-4 февр. 2004. С. 20-22.

7. Баженов, М. М. Идентификация веб-сообществ в глобальной сети WAP-ресурсов / М. М. Баженов, А. В. Сычёв // Информационные технологии, 2006.-№6.-С. 38-44.

8. Баженов, М. М. Исследование веб-графа МИ / М. М. Баженов, А. В. Сычёв // Информационные технологии моделирования и управления: науч.-техн. журн. 2006. - Вып. 2(27). - С. 230-238.

9. Баженов, М. М. Модель выявления "идеологов" веб-сообщества истратегия оптимизации индексирования / М. М. Баженов // Информатика: проблемы, методология, технологии : материалы 5-ой регион, науч.-метод. конф., Воронеж, 8-9 февр. 2005. Ч. 1. - С. 32-34.

10. О.Баженов, М. М. Об одном подходе к исследованию структуры Веб-графа /

11. З.Баженов, М.М. Опыт выявления Web-сообществ на примере сайтов ВГУ и Воронежа / М. М. Баженов, А. В. Сычев // Научный сервис в сети ИНТЕРНЕТ: Тр. Всерос. науч. конф, Новороссийск, 22-27 сент. 2003. С. 145-146.

12. Вебер, Д. Технология Java в подлиннике / Д. Вебер. СПб.: BHV-Санкт-Петербург, 1998. - 1104 с.

13. Вирт, Н. Алгоритмы + структуры данных = программы / Н. Вирт. М.: Мир, 1985.-406 с.

14. Горев, А. Эффективная работа с СУБД / А. Горев, Р. Ахаян, С. Макашарипов. СПб.: Питер, 1997. - 704 с.

15. Грабер М. Справочное руководство по SQL / М. Грабер, Изд-во ЛОРИ, 1997.-292 с.

16. Грабер, М. Введение в SQL / М. Грабер. Изд-во ЛОРИ, 1996 - 375 с.

17. Джамса, К. Программирование в Web для профессионалов / К. Джамса, С. Лалани, С. Уикли; пер. с англ. А. И. Панасюк. Мн.: Попурри, 1997. -632 с.

18. Джейсон, М. JavaScript: основы программирование / М. Джейсон. К.: Издательская группа BHV, 1997. - 512 с.

19. Евстигнеев, В. А. Графы в программировании: обработка, визуализация и применение / В. А. Евстигнеев, В. Н. Касьянов. СПб.: BHV-Санкт-Петербург, 2003.-1104 с.

20. Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев. М.: Наука, 1985. - 352 с.

21. Евстигнеев, В. А. Теория графов: алгоритмы обработки бесконтурных графов / В. А. Евстигнеев, В. Н. Касьянов. Новосибирск: Наука, 1998. -385 с.27.3олотов, С. Протоколы Internet / С. Золотов. СПб.: BHV-Санкт-Петербург, 1998.-304 с.

22. Информационные технологии и программирование: Межвузовский сборник статей. М.: МГИУ, 2003. - Вып. 2 (7). - 62 с.

23. Корн, Г. Справочник по математике для научных работников и инженеров / Г. Корн, Т. Корн. М.: Наука, 1968. - 720 с.

24. Кудрявцев, JI. Д. Курс математического анализа / JI. Д. Кудрявцев. М.: Высш. школа, 1981. - Т. 1.

25. Кульба, В. В. Модифицированные функциональные графы как аппарат моделирования сложных динамических систем / В. В. Кульба, В. М. Назаретов, И. П. Чухров. М.: Институт проблем управления, 1995. - 576 с.

26. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. -М. :Мир, 1981.-323 с.

27. Поисковая система Google Электронный ресурс. Режим доступа : http://www.google.com

28. Поисковая система Yandex Электронный ресурс. Режим доступа : http://www.yandex.ru

29. Рудин, У. Основы математического анализа / У. Рудин. М.: Мир, 1976. -320 с.

30. Седжвик, Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах / Р. Седжвик. СПб.: ДиаСофтЮП, 2003. - 480 с.

31. Солтон, Дж. Динамические библиотечно-поисковые системы / Дж. Солтон; пер. с англ. В. Р. Хисамутдинова. М.: Мир, 1979. - 557 с.

32. Статистические и информационно-аналитические исследования состояния и основных тенденций развития инфраструктуры российского сегмента Интернета Электронный ресурс. Выпуск 1. - Режим доступа : http://stat.nic.ru

33. Статистические и информационно-аналитические исследования состояния и основных тенденций развития инфраструктуры российского сегмента

34. Интернета по итогам 2005 года. Электронный ресурс. Выпуск 4. -Режим доступа : http://stat.nic.ru

35. Статистические и информационно-аналитические исследования состояния и основных тенденций развития инфраструктуры российского сегмента Интернета. Хостинг через призму DNS. Электронный ресурс. Выпуск 2. - Режим доступа : http://stat.nic.ru

36. Сычев, А. В. Применение методов анализа сети гиперссылок для оценки и диагностики веб-сайтов / А. В. Сычев, М. М. Баженов // Телематика'2004 : тр. 11 Всерос. науч.-метод. конф., Санкт-Петербург, 7-10 июня 2004. Т. 1.-С. 231-232.

37. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.: Мир, 1977. - 208 с.

38. Уинкуп, С. Microsoft SQL Server 6.5 в подлиннике / С. Уинкуп. СПб.: BHV-Санкт-Петербург, 1998. - 896 с.

39. Харари, Ф. Теория графов IФ. Харари. -М.: Мир, 1973.-301 с. 48.Челкак, С. И. Элементарное построение асимптотик некоторых сумм

40. Электронный ресурс. / С. И. Челкак, В. М. Чистяков // Интернет-журнал СПбГПУ, Математика и естествознание в ВУЗе. сентябрь 2001 - февраль 2002. - №2. - Режим доступа :http://www.spbstu.ru/public/mv/N002/ChistiakovChelkak/Chechi.pdf

41. Щепин, Б! В. Теория интерполяции Электронный ресурс. / Е. В. Щепин. -СУНЦ МГУ, 2006. Режим доступа : www.mi.ras.ru/~scepin/summation.pdf

42. Adler, М. Towards compressing web graphs / M. Adler, M. Mitzenmacher // In Proceedings of the IEEE data compression conference (DCC). March 2001.

43. Albert, R. Diameter of the World Wide Web / R. Albert, H. Jeong, A.-L. Barabasi // Nature. 1999. - 401. - pages 130-131.

44. Bharat, K. Improved Algorithms for Topic Distillation in a Hyperlinked Environment / K. Bharat, M. Henzinger // In Proc. ACM SIGIR'98. 1998.

45. Bharat, K. When Experts Agree: Using Non-Affiliated Experts to Rank Popular Topics / K. Bharat, G. A. Mihaila // In Proc. 10th WWW Conference. 2001.

46. Bianchini, M. Inside PageRank / M. Bianchini, M. Gori, F. Scarselli // ACM Transactions on Internet Technology. 2005. - Vol. 5. - No. 1. - pages 92-128.

47. Borodin, A. Link Analysis Ranking: Algorithms, Theory, and Experiments / A. Borodin, G. O. Roberts, J. S. Rosenthal, P. Tsaparas // ACM Transactions on Internet Technology. -2005. Vol. 5. - No. 1. - pages 231-297.

48. Brewington, В. E. How dynamic is the web? / В. E. Brewington, G. Cybenko // In Proc. 9th WWW Conference. 2000.

49. Brian, A. Does "authority" mean quality? Predicting expert quality ratings of web documents / A. Brian, T. Loren, H. Will // Proc. of the SIGIR'00. 2000. -pages 296-303.

50. Brin, S. The anatomy of a large scale hypertextual web search engine / S. Brin, L. Page // In Proc. 7th WWW. 1998.

51. Callan, J. P. The INQUERY Retrieval System / J.P. Callan, W.B. Croft, S.M. Harding // Proceedings of DEXA, 3rd International Conference on Databaseand Expert Systems Applications. Springer Verlag, New York, 1992. - pages 78-93.

52. Debajyoti, M. An Approach to Confidence Based Page Ranking for User Oriented Web Search / M. Debajyoti, G. Debasis, R. S. Sanasam // SIGMOD Record. 2003. - Vol. 32. - No. 2

53. Dempster, A. P. Maximum likelihood from incomplete data via the EM algorithm / A. P. Dempster, N. M. Laird, D. B. Rubin // J. R. Statist. Soc. B. -1977.-39.-pages 185-197.

54. Dill, S. Self-Similarity In the Web / S. Dill, R. Kumar, K. S. Mccurley, S. Rajagopalan, D. Sivakumar, A. Tomkins // ACM Transactions on Internet Technology. 2002. - Vol. 2. - No. 3. - pages 205-223.

55. Flake, G. Efficient identification of web communities / G. Flake, S. Lawrence, C. L. Giles // In 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2000. - pages 150-160.

56. Flake, G. Graph clustering and mining cut trees / G. Flake, R. Tarjan, K. Tsioutsiouliklis // Internet Mathematics. 2004. - 1(3). - pages 355-378.

57. Flake, G. W. Self-Organization and Identification of Web Communities / G. W. Flake, S. R. Lawrence, C. L. Giles, F. M. Coetzee // IEEE Computer. 2002. -35(3).-pages 66-71.

58. Gelbukh, A. Zipf and Heaps Laws' Coefficients Depend on Language / A. Gelbukh, S. Grigori // Proc. CICLing-2001, Conference on Intelligent Text Processing and Computational Linguistics, February 18-24, 2001. Springer-Verlag. - pages 332-335.

59. George, K. Zipf, The Psychobiology of Language, Houghton-Mifflin / K. George. New York, NY, 1935.

60. Gibson, D. Inferring web communities from link topology / D. Gibson, J. Kleinberg, P. Raghavan // In Proc. 9th ACM Conf. on Hypertext and Hypermedia. -1998.

61. How Much Information? Электронный ресурс. / Peter Lyman [и др.]. -2000. Режим доступа : http://www.sims.berkeley.edu/research/projects/how-much-info/internet.html

62. Kleinberg, J. M. Authoritative sources in a hyperlinked environment / J. M. Kleinberg // Journal of the ACM. 1999. - 46(5). - pages 604-632.

63. Kleinberg, J. The structure of the Web / J. Kleinberg, S. Lawrence // Science. -2001.-vol 294.-pages 1849-1850.

64. Kumar, R. Trawling the Web for emerging cyber-communities / R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins // In Proceedings of the 8th International World Wide Web Conference. 1999. - pages 1481-1493.

65. Lawrence, S. Context in Web Search / S. Lawrence // IEEE Data Engineering Bulletin. 2000. - Vol. 23. - pages 25-32.

66. Li, W. Random texts exhibit Zipf s-law-like word frequency distribution / W. Li // IEEE Transactions on Information Theory. 1992. - 38. - pages 18421845.

67. Miller, J.C. Modifications of Kleinberg's HITS AlgorithmUsing Matrix Exponentiation and Web Log Records / J. C. Miller, G. Rae, F. Schaefer // SIGIR'01, NewOrleans, Louisiana, USA, September 9-12, 2001.

68. Newman. Power laws, Pareto distributions and Zipf s law / Newman, Mej // Contemporary Physics. 2005. - vol. 46, Issue 5. - pages 323-351.

69. Ng, A. Y. Link Analysis, Eigenvectors and Stability Электронный ресурс. / A. Y. Ng, A. X. Zheng, M. I. Jordan // In Proc. of the IJCAT01. -2001.-Режим доступа: http://ai.stanford.edu/~ang/papers/ijcai01-linkanalysis.pdf

70. Page, L. The PageRank Citation Ranking: Bringing Order to the Web Электронный ресурс. / L. Page, S. Brin, R. Motwani, T. Winograd. Режим доступа: http://dbpubs.stanford.edu:8090/pub/l999-66

71. Pennock, D. M. Winners Don't Take All: A Model of Web Link Accumulation / D. M. Pennock, C. L. Giles, G. W. Flake, S. Lawrence, E. Glover // Technical Report 2000-164. NEC Re-search Institute, Princeton, NJ. - 2000.

72. Salton, G. Extended Boolean information retrieval / G. Salton, E. A. Fox, H. Wu // Commun. ACM 26. 1983. - pages 1022-1036.

73. Salton, G. Introduction to modern information retrieval / G. Salton, M. J. McGill. New York, NY, USA : McGraw-Hill, 1986. - pages 400.

74. Salton, G. Term-Weighting Approaches / G. Salton, C. Buckley // Automatic Text Retrieval. Information Processing and Management. 1988. - 24, 5. -pages 513-523.

75. Salton, G. Term-weighting approaches in automatic text retrieval / G. Salton, C. Buckley // Information Processing & Management. 1988. - 24(5). - pages 513-523.

76. Shivakumar, N. Finding Near-Replicas of Documents on the Web

77. Электронный ресурс. / N. Shivakumar, H. Garcia-Molina // Proc. of the WebDB'99. 1999. - Режим доступа : http://dbpubs.stanford.edu-.8090/pub/1998-31

78. Toyoda, M. Creating a Web Community Chart for Navigating Related Communities / M. Toyoda, M. Kitsuregawa // In Proc. Hypertext 2001.-2001. -pages 103-112.

79. Toyoda, M. Extracting Evolution of Web Communities from a Series of Web Archives / M. Toyoda, M. Kitsuregawa // HT'03, Nottingham, United Kingdom (ACM). August 26-30,2003

80. Uniform Resource Identifiers (URI): Generic Syntax Электронный ресурс. / Т. Berners-Lee, R. Fielding, U. C. Irvine, L. Masinter // Network Working Group. 1998. - Режим доступа : http://rfc.net/rfc2396.html

81. Van Rijsbergen, C. J. Information Retrieval, 2nd edition / C. J. Van Rijsbergen. Dept. of Computer Science, University of Glasgow. - Newton MA, USA : Butterworth-Heinemann, 1979. - 208 pages.