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

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

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

Существует ряд авторитетных международных конференций' по информационному поиску, посвященных, в том числе, обсуждению вопросов информационного поиска в сети Интернет. Это такие известные конференции как 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].

По сравнению с подобными крупномасштабными исследованиями, 1 выполненными в 2000 году [72], объём данных вырос с 20 — 50 до 167 терабайт для «поверхностного» Web. А если учесть, что «глубинный» Web по некоторым оценкам [73] обычно больше в 400−450 раз, то и его объём за 3 года увеличился в 3 раза. Если предположить сохранение подобной динамики, то в 2006 году объём накопленной информации составил порядка 270 000 терабайт.

Не стоит также забывать и о многократном росте количества пользователей Сети, особенно за счёт появления в их рядах людей, не имеющих компьютеров, но пользующихся Мобильным Интернетом (МИ). Их потенциальное число сегодня составляет более 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-сетях. Теория графов предоставляет достаточно адекватный математический' аппарат для решения подобных: задачМетодыи алгоритмы, теории графов, непосредственно применимы к Интернет, так как эта сеть может быть представлена? в виде гигантского. графа, где узлы — веб-страницы, а рёбра — гиперссылки. Проблемой при: идентификации веб-сообществ становится размер исследуемого графа, при котором он не поддается" ни полному, воспроизведениюни=обработке.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение1 результатов работьп Основные теоретические и практические результаты диссертационной* работы реализованы в виде специальной информационной системы исследования1 процессов самоорганизации в Сети. Система была использована для* анализа процессов самоорганизации воронежского сегмента Интернет, сети Воронежского госуниверситета и российской части Мобильного Интернета, а также в учебном процессе Воронежского госуниверситета при разработке учебных курсов «Информационно-поисковые системы» и «Корпоративные информационные системы», что подтверждается соответствующими актами внедрения. Результаты работы были использованы при выполнении гранта ООО «Яндекс» № 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. Предложена концептуальная модель эволюции веб-графа, модель имитации веб-графа и алгоритм генерации искусственных веб-графов — с контролируемыми параметрами. Предложенная модель имитации веб-графа позволила объяснить различие зависимостей ранг-частота для разных тематических веб-графов. Показано, что степень выпуклости на графиках зависит от параметра dotd предложенной модели, определяющего долю рёбер со старых вершин на новую. Доказано утверждение, позволяющее вычислить вероятность достижимости двух случайно выбранных узлов в веб-графе. Из него следует, что в реальной Сети такие узлы достижимы не менее чем в 13% случаев.

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

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

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

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

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