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

На правах рукописи

0031634^

БАЖЕНОВ Михаил Михайлович

РАЗРАБОТКА СПЕЦИАЛЬНОГО МАТЕМАТИЧЕСКОГО

И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЯВЛЕНИЯ ВЕБ-СООБЩЕСТВ В ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМАХ

Специальность- 05 13 11 - "Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

4 АИВ

Воронеж-2007

003163422

Работа выполнена в Воронежском государственном университете

Научный руководитель

доктор технических наук, профессор Сирота Александр Анатольевич

Официальные оппоненты

доктор технических наук, профессор Кравец Олег Яковлевич,

кандидат технических наук Соколов Александр Евгеньевич

Ведущая организация

Тамбовский государственный технический университет

Защита состоится 17 января 2008 г в Ю00 часов в конференц-зале на заседании диссертационного совета Д212 037 01 Воронежского государственного технического университета по адресу 394026 Воронеж, Московский просп, 14

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

Автореферат разослан {Я. декабря 2007 г

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Анализ существующих работ Флейка (G Flake), Лоуренса (S Lawience), Гайлса (С L Giles), Ямафуджи (N Imafuji) и Китсурегава (М Kitsuregawa), посвященных процессам самоорганизации в Интернет и идентификации (выявления и оценки) веб-сообществ в интересах информационного поиска, выявил незначительное число проведенных исследований При этом готовых и апробированных решений (способных непосредственно интегрироваться в существующие ИПС) еще практически не существует, что во многом связано с отсутствием достаточно проработанной теории и практики решения задач идентификации веб-сообществ и масштабностью требуемых исследований В известных работах, рассматривающих вопросы идентификации самоорганизованных веб-сообществ в сети Интернет, не учитываются также многие реалии современной Сети и, прежде всего существование "ложных" гиперссылочных связей, не характеризующих тематику веб-сообщества, но внешне удовлетворяющих всем предъявляемым критериям Подобные факторы вызывают появление так называемых страниц-шумов, фактически не соответствующих тематике Кроме того, имеет место постепенное вытеснение поверхностного Web динамическими ресурсами, что приводит к неадекватности результатов, полученных на основе реконструкций веб-графов, не учитывающих глубинный Web (т е ресурсы, генерируемые по запросу с помощью различных технологий) В то же время учет подобных факторов, как показывает анализ, позволяет существенно повысить как эффективность функционирования информационно-поисковых систем, так и сформировать соответствующие рекомендации для их пользователей

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

Работа выполнена в рамках научного направления Воронежского государственного университета - "Математическое моделирование, программное и информационное обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным исследованиям в естественных науках" и непосредственно связана с темой, имеющей номер государственной регистрации №0120 0405475

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

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

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 - в изданиях, рекомендованных ВАК РФ В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат в [1,3,11] - принципы идентификации веб-сообществ, результаты идентификации веб-сообществ и анализ закономерностей структуры Мобильного Интернета, [4,7] - анализ распределения гиперссылок, [5,6,8] - оценка эффективности потоковых методов идентификации веб-сообществ, [10] - алгоритм автоматической оценки качества веб-сообществ, [12,14,15] - многоэтапная процедура идентификации веб-сообществ и реализующие ее алгоритмы обработки информации, [13] - предложения по применению анализа гиперссылок для диагностики веб-сайтов

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, изложено состояние вопроса, сформулированы цели и задачи исследований, показаны научная новизна и практическая значимость полученных результатов, описан объект исследования Приведены основные положения, выносимые автором на защиту, сведения об апробации и использовании результатов работы

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

Современные подходы к идентификации веб-сообществ наиболее полно реализуются в методе ГЪО (Р1аке-Ьа\¥гепсе-011ез) В рамках этого метода (рис 1) используется модель веб-сообщества в виде подграфа веб-графа, отделенного от последнего минимальным сечением

Рис 2 демонстрирует один из способов поиска этого минимального сечения - представление веб-графа в виде транспортной .^-сети с последующим

нахождением максимального потока минимальной стоимости (ПМС) Математически поток из s в t представляет собой неотрицательную целую

функцию f, определенную на множестве ребер Е, которая подчиняется следующим условиям

О </(и,о) < с{и,и), где с(и,и) - пропускная способность ребра

Мшшмлтьное сечешге

Рис 1 Веб-граф и веб-сообщество

Рис 2 Транспортная э^сеть

Для каждой внутренней вершины и 51-сети, не равной 5 или I, выполняется следующее условие

для любых «б)- , где (н, и) - ребра, входящие в вершину и, (и,и„) — ребра, исходящие из вершины и

Соответственно в рамках представления рис 1, 2 веб-сообщество можно определить как подмножество вершин Се К таких, что для всех вершин иеС. и имеет множество ребер, соединяющих ее с вершинами в С, и практически не имеет ребер, соединяющих с вершинами в {V \ С)

кг тс а(г/,и)

Идентификация самоорганизованных веб-сообществ на основе модели веб-графа в виде транспортной БЬсети - это неразрешимая в общем случае задача, так как она относится к семейству №-полных задач разбиения на графах Поэтому в различных потоковых алгоритмах идентификации веб-сообществ всегда делаются допущения, позволяющие эффективно идентифицировать веб-сообщества (различными способами вводятся виртуальные исток 5 и сток I) Непосредственно сам поиск ПМС в потоковых методах, как правило, реализован на основе алгоритма Форда-Фалкерсона, существо которого состоит в наращивании потоков по аугментальным путям до тех пор, пока потенциал наращивания не будет исчерпан После нахождения минимального сечения ребра попавшие в него удаляются, а вершины, оставшиеся доступными из виртуального стокам, считаются членами веб-сообщества

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

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

Модель веб-графа необходима для более глубокого понимания процессов самоорганизации в Сети и исследования известных и предлагаемых алгоритмов выявления веб-сообществ Модель основана на идее хронологического возникновения веб-ресурсов При этом считается, что каждый новый появившийся ресурс (на »-том шаге) с определенными вероятностями р" > р" > > р" может поставить ссылку на уже существующие и/или получить обратную ссылку с существующих с вероятностями д" > > ><7^ В предложенной модели вероятность того, что при возникновении «-того узла он установит ссылку на /-й узел (из уже существующих) равна //' = С,,,,«//, а вероятность того, что он получит ссылку с 1-го узла равна ц" = С„Л,«/(«-/) Здесь С,„„ и С,м - нормировочные константы, зависящие только от исходных параметров V (заданного количества вершин в веб-графе) и (заданного среднего соотношения количества ребер Е к количеству вершин V) Для реализуемых в модели закономерностей вероятностей возникновения гиперссылок величины с„„ и См равны, поэтому они заменяются единой

С С

нормировочной константой С1 В итоге она принимает следующий

вид

С 4£™Г

1 2К(Г + 1)1п(К + 1)-((' + 1)2 Соответственно, модель искусственного веб-графа описывается матрицей со случайными элементами

0 = 0п1ц+0м=\еп\\ + \\еш

где

п

0, с вероятностью (1 - Р1К„ —)

I

п '

1, с вероятностью Рпт —

I

п

0, с вероятностью (1 - Рм-)

П — 1

п

1, с вероятностью Р,м--

п-1

/ = 1,2, ,/?-1

Здесь величина Рт =С4 х(1-</„,.,), Р,м=С,.хс1м, а - управляющий параметр, представляющий собой долю ссылок со старых узлов обратно на новый Введение данного параметра удобно с точки зрения управления конфигурацией модели Параметр с!м фактически позволяет увеличивать или уменьшать долю ссылок со старых ресурсов на вновь появившийся (в ущерб обратным ссылкам)

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

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

Предложено и доказано утверждение о достижимости между двумя случайно выбранными веб-узлами в веб-графе

Утверждение. Если в ориентированном веб-графе случайно выбрать две вершины и и V, то вероятность того, что существует ориентированный путь из

и в V удовлетворяет неравенству р(и-»у)>--Ц-где N - общее число

Ы'

вершин в веб-графе, К - число вершин, входящих в компоненту сильной связанности (КСС) веб-графа, Ь - число вершин, имеющих дуги на вершины в КСС, но не обратно, М - число вершин, имеющих дуги с вершин из КСС, но не обратно

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

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

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

1---1 Выбор зерновых ресурсов 1 1-,-. 1-----^ Построение локального * . "" ееб графа

р--—-1 Укрупнение КСС до доменных 1 учппо Г 1 ' ---1—Извлечение свяэанньх ■ _________ компонент

^-1—--^ Автоматическая численная Г~ оценка качества веб сообщества ¡----- Ранжирование списка узлов < ~ Г" г учетом ппрпга входа ~ - 1 - ~

Рис 3 Диаграмма компонентов для многоэтапной процедуры идентификации веб-сообшеств

На рис 3 приведена диаграмма компонентов, описывающая основные составляющие предлагаемой многоэтапной процедуры идентификации веб-сообществ, а на рис 4 - диаграмма деятельности реализующего ее общего алгоритма обработки информации

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

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

Выбрать подмножество Э зерновых ресурсов

Построить локапьный веб граф

Извлечь все связанные компоненты локального веб графа выбрать из них КОС

[ не все ресурсы из Э

попали в КСС }

[ все ресурсы из Б пугали & КСС 1

Укрупнить узлы тпаечме в КСС до доменных узлов

Провести численную оцеику порученного списка доменоз

Р<^нжировать список на основе численнои оценки содержания узлов

Установить порог принятия решения для отнесения узла к веб сообществу

Показать веб сообщество в соответствии с устансв^енным порогом

Рис 4 Диаграмма деятельности для алгоритма, реализующего многоэтапную процедуру идентификации веб-сообществ

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

характеризующих тематику веб-сообщества На рис 5 приведена запись алгоритма в виде диаграммы деятельности Полученные оценки для каждого веб-ресурса на заключительной стадии алгоритма сравниваются с порогом Ра, который является порогом принятия решения о включении ресурса в веб-сообщество Порог Р„ подбирается в зависимости от требований к сообществу и фактически, являясь управляющим параметром, позволяет выбирать баланс между полнотой (в том числе размером) и точностью (фактически качеством) веб-сообщества

1

Задать количество клю <евых слов I отражающих тематику веб ресурса

Составить списки ключевых слов для каиздого зернового ресурса

| Сформировать общий список ключевых слов тематики веб сообщества | путрм объединения списков ключевык спов "зерновых ресурсов

Составить списки ключевых слов для каждой веб страницы веб сообщества

Для каодои веб страницы сравнить её список с общим списком тематики количество совпадении нормировать на 1

I Ранжировать веб страницы веб сообщества | в соответствии с полученной сценкой

1

идентификация веб-сообщества ]

[оценка веб|сообщества]

Удалить из списка веб страницы с оценкой нюке заданного порога ^

Рис 5 Диаграмма деятельности для алгоритма автоматической численной оценки качества веб-сообщества

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

формуле =]где 0<СЧ <1 - оценка смыслового соответствия слов 1 и j, DM - максимальное по длине слово из / иу

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

Третья глава посвящена описанию реализации разработанных моделей и алгоритмов в виде комплекса программ, обеспечивающего выполнение полного цикла обработки информации в соответствии с подходом, предложенным во 2 главе Описаны предлагаемые структуры данных, используемые для хранения веб-графов Даны UML-модели программного обеспечения, реализованного для решения основных и сопутствующих задач исследований

Структура разработанного программного комплекса представлена на рис 6 Используемые в ней программные модули сгруппированы по назначению реконструирующие/генерирующие веб-граф, преобразующие веб-граф и идентифицирующие веб-сообщество Здесь модули WEBcrawler и WAPcrawler представляют собой сетевых "пауков" для большого и мобильного Интернета соответственно, выполняющих реконструкцию веб-графов из Сети Модуль InLinksCounter получает все входящие ссылки на заданный узел, используя открытый публичный интерфейс Yandex XML к ИПС Яндекс Модуль WebGraphGenerator строит искусственный веб-граф и/или проводит его анализ Модуль DomamGraph укрупняет веб-граф до доменов, а модуль WeightGraph создает на основе орграфа граф с назначенными весами ребер Модуль CutGraph создает частичный веб-граф на основе входного полного веб-графа Модуль FLGcommumty идентифицирует веб-сообщества на основе метода FLG, вычисляя максимальный поток минимальной стоимости при помощи модуля MaxFlowMinCut Модуль SCCtarjan разбивает граф на связанные компоненты Модуль Community Quality проводит автоматическую численную оценку качества веб-сообщества

Задачи решаются комплексом в режиме реального времени и используют свободно доступные технологии и интерфейсы взаимодействия с внешними системами Программные решения реализованы на языках Java и С++

Любой эксперимент, проведенный в интересах исследования сетевых ресурсов, реализует последовательность выполнения указанных программных модулей На рис 7 показана UML-диаграмма последовательности действий (Sequence diagram), реализующая описанную выше многоэтапную процедуру

идентификации веб-сообществ с применением программных модулей, представленных на рис 6

Рис 6 Структура разработанного программного комплекса

Структуры данных, используемые в разработанном пакете программ, выбирались из соображения их унификации Результат работы одного инструмента из пакета совместим с входными данными другого

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

(например, опПпе-процедура реконструкции веб-графа) изначально невозможно знать итоговое число вершин и ребер в графе.

^(.¡пквСоигЛег!

\л/ЕВсг?^1ег ! ЗСС*апап 1 1 ОотатЗгаоЬ Соттит^СЮа

1 ' ^

список узлов ;

43

•локальный веб-граф ■

Л : ^

■ гигантская КОС

¡доменный ееб-граф

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

В наиболее ресурсоёмких модулях, где размер веб-графа может оказаться критичным фактором, реализованы комбинации из наиболее эффективных алгоритмов и способов представления графов. В частности самой ресурсоёмкой частью многоэтапной процедуры идентификации веб-сообществ в плане вычислений является поиск КСС, что потребовало эффективной реализации алгоритма поиска связанных компонент (с учётом специфики - разреженности веб-графов). Реализованный алгоритм представляет собой алгоритм Тарьяна с хранением веб-графа в виде структуры Вирта и базируется на использовании двух закономерностей. Во-первых, поскольку вершины рассматриваются в обратном топологическом порядке, то при достижении конца специальной рекурсивной функции для какой-либо вершины известно, что уже не встретится ни одна вершина из той же связанной компоненты (в силу того, что все вершины, достижимые из этой вершины, уже обработаны). Во-вторых, обратные связи в дереве обеспечивают второй путь из одной вершины в другую и связывают между собой сильные компоненты. В отличии от наиболее распространённого для таких задач алгоритма Косарайю, реализованный алгоритм делает только один проход по веб-графу (поскольку не требует обращения матрицы), в абсолютном значении для разреженных графов скорость обоих алгоритмов в наихудшем случае равна 0(У + Е), но на практике алгоритм Тарьяна часто даёт существенное превосходство. Благодаря этому удалось добиться линейного времени выполнения и расходования оперативной памяти при поиске связанных компонент, что, в свою очередь, позволяет программно обрабатывать веб-графы размером в десятки миллионов узлов.

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

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

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

В примере рис 8 для "библиотечного" веб-сообщества и порога Р„ = 0 2 были получены значения точности 77% и полноты 97%, причем погрешность в точности была обусловлена добавлением в веб-сообщество ложных членов При этом практически ни одного действительного члена не было пропущено Предложенный подход также показал отсутствие одного из главных недостатков, присущего потоковому методу РЬв, - малочисленности идентифицируемых членов веб-сообщества, что требует выполнения нескольких итераций при идентификации веб-сообщества методом РЬО Причем на полном веб-графе, в отличии от частичного, дополнительные итерации зачастую уже не могут увеличить веб-сообщество и исправить тем самым ситуацию В свою очередь, предложенная автором многоэтапная процедура позволяет путем варьирования значения порога вхождения расширять веб-сообщество за счет уменьшения точности результата идентификации, что придает ей больше гибкости в сравнении с методом ИЬО и рядом его известных модификаций

Разработанный алгоритм численной оценки качества веб-сообщества применялся также и независимо - для оценки "библиотечного'' веб-сообщества, полученного методом РЬО Из построенного локального веб-графа глубины 3

Зависимость точности и полноты от порога РО

Точность Полнота |

Порог Ре

Рис 8 График точность-полнота на основе экспертной оценки качества веб-сообщества

(307 641 вершина и 889 248 узлов) было получено веб-сообщество численностью в 19 членов. При оценке полученного веб-сообщества был также проведён анализ влияния управляющего параметра и, (отвечающего за число ключевых слов, представляющих тематику веб-ресурса) на точность итоговой оценки и было установлено, что с увеличением числа учитываемых слов, характеризующих каждый документ, точность падает, что удалось объяснить на основе законов Зипфа.

Проведено исследование российского сегмента Мобильного Интернета (МИ) и получена динамика его роста за определённый период (рис. 9). В связи с малым объёмом (по сравнению с большим Интернет) на первом этапе исследований (рис. 9, июнь 2005г.) удалось получить частичный веб-граф МИ глубины 3 и практически убедиться в существовании в нём компоненты сильной связанности.

Рост МИ

200 000 150 000 100 000 50 000

о

□ Июнь 2005г. I s февраль 2006Г

Длина пути по гиперссылкам

Рис. 9. Объёмы роста Мобильного Интернет (зона ЯУ)

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

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

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

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

Даны ожидаемые оценки прироста эффективности ИПС -доуточнения —»—послеуточнения | на основе реализации в них

дополнительных процедур __, обработки информации, реализующих предлагаемый подход к выявлению и авто-

Результат уточчения на примере 5 запросов

1,00 0,90

2 о,эз

ю 0,70 5 0,63 £ о.ээ

о 0,40

7 0,30 о

£ 0,2О 0,10 0,00

матической оценке веб- сообществ. В частности, в ходе

экспериментов показано, что ,_,-,_, применение предлагаемых

1 2 3 4 5 алгоритмов обработки инфор-

Номерзапроса мации и программных средств

Рис. 10. Сравнение результатов обычного и для идентификации веб-уточнённого поиска для 5 различных сообществ при их испо-запросов на примере ИПС Яндекс льзовании в современных оте-

чественных ИПС горизонтального типа для уточнения результатов поиска дает увеличение точности ответов на информационный запрос уже на первой странице в среднем в 2-3 раза. В целом на первых 5 страницах точность повышается с 0.44 до 0.65, при этом получаемый прирост качества поиска, как это видно на рис. 10, сильно разнится от тематики конкретного запроса. Для ИПС вертикального типа показано, что предложенная автоматизация подбора индексируемых ресурсов тематики позволяет дополнительно существенно (до 2-х порядков) сократить время обновления ресурсов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2 Разработана многоэтапная процедура идентификации

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

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

2 Баженов М М Идентификация веб-сообществ на основе сильно связанных компонент и контентного анализа /ММ Баженов // Вестник Воронежского государственного университета Сер Системный анализ и информационные технологии 2006 -Вып 1.-С 13-19

Статьи и материалы конференций

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

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

5 Баженов М М Анализ задачи идентификации самоорганизованных \Veb-сообществ / ММ Баженов, А В Сычев // Информатика проблемы,

методология, технологии материалы 4-ой регион науч -метод конф Воронеж, 2004 -С 20-22

6 Баженов ММ Об одном подходе к исследованию структуры Веб-графа/ ММ Баженов, А В Сычев // Новые технологии в образовании- сб тр Воронеж ВГТТУ, 2004. - Вып. 8 -С 3-10

7. Баженов М М Силовой закон для распределения ссылок на примере веб-ресурсов ВГУ и Воронежа /ММ Баженов, А В Сычев // Научный сервис в сети ИНТЕРНЕТ: труды всерос науч конф Новороссийск, 2004 - С 201-202

8 Баженов М М Решение задач о максимальном потоке методом Форда-Фалкерсона в контексте исследования структуры гипертекстового графа /ММ Баженов, А В Сычев // Кибернетика и технологии XXI века V междунар науч-техн. конф Воронеж, 2004 -С 111-116.

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

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

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

12 Сычев А В Идентификация веб-сообществ тематических ресурсов на основе выявления компонент сильной связности и частотного анализа текста / А В. Сычев, М М Баженов // Телематика'2006 труды 13 всерос науч -метод конф СПб.,2006 -Т2 -С 292-294

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

14 Сычев А В. Автоматическое пополнение веб-каталога на основе идентификации веб-сообществ с последующей фильтрацией документов по контенту / А В. Сычев, М М Баженов // Интернет-математика 2007 сб работ участников конкурса - Екатеринбург, 2007. - С. 200-210.

15 Сычёв А В О проблеме выбора зерновых ресурсов в задаче автоматического пополнения каталога веб-ресурсов на основе выявления компонент сильной связанности с последующей контентной фильтрацией / А В Сычёв, ММ Баженов // Электронные библиотеки перспективные методы и технологии, электронные коллекции : труды 9 всерос науч конф ЯСВЬ'2007 Переславль-Залесский, 2007.-С 156-165

Подписано в печать 10.12 2007 Формат 60x84/16 Бумага для множительных аппаратов. Уел печ л 1,0. Тираж 100 экз Заказ №

ГОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп , 14

ВВЕДЕНИЕ.

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

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.