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

• Якушев, Андрей Владимирович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Якушев, Андрей Владимирович

Оглавление

Основные обозначения и сокращения

Введение

Глава 1. Принципы сбора и обработки больших объемов данных в социальных медиа

1.1. Модели информационных процессов в социальных медиа

1.2. Принципы сбора данных в Интернет

1.3. Обзор существующих систем сбора данных

1.4. Классификация задач сбора и обработки данных в социальных медиа

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

Глава 2. Математическое обеспечение сбора данных

2.1. Адаптивная процедура сбора данных

2.2. Тематический сбор данных в социальных медиа

2.3. Мониторинг социальных медиа

2.4. Репрезентативные выборки из графовых структур

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

Глава 3. Программное обеспечение сбора данных

3.1. Общая архитектура системы

3.2. Интеграция с платформой облачных вычислений СЬАУШЕ

3.3. Программная реализация системы сбора данных

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

Глава 4. Применение к исследованиям социальных медиа

4.1. Психологический портрет пользователей, вовлеченных в пропаганду наркотиков в социальных медиа

4.2. Анализ соответствия реальных и виртуальных связей пользователей сети Укота^е

4.3. Исследование процессов формирования пользовательских сообществ на основе общих интересов

4.4. Внедрение системы сбора данных в производственно-исследовательский веб-центр «Социодинамика»

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

Заключение

Список использованных источников

Основные обозначения и сокращения

СМ — социальные медиа;

ВОП — виртуальное общество пользователей;

ИП — информационный процесс;

AaaS — Application as a Service, приложение как сервис;

SaaS — Software as a Service, программное обеспечение как услуга;

API — Application Programming Interface;

URL — Uniform Resource Locator;

JSON — JavaScript Object Notation, нотация объектов языка JavaScript; XML — Extensible Markup Language, расширяемый язык разметки; БД — база данных;

СУБД — система управления базами данных;

CLAVIRE — CLoud Applications VIRtual Environment, виртуальная среда для облачных приложений;

МИТП — многопрофильная инструментально-технологическая платформа;

КП — композитное приложение;

WF — workflow, «поток работ»;

iPSE — Intelligent PSE, интеллектуальная PSE.

\

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение распределенной обработки больших объемов данных из социальных медиа»

Введение

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

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

Предметом исследования являются методы повышения эффективности систем сбора и обработки больших объемов данных из СМ.

1 Устанавливается оператором СМ.

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

Задачи исследования:

- обоснование требований к математическому и программному обеспечению сбора и обработки данных СМ на основе результатов аналитического обзора предметной области;

I

- разработка и исследование адаптивных методов повышения скорости обнаружения новых событий в СМ и построения репрезентативных выборок с учетом топологии связей ВОП;

- проектирование и программная реализация архитектуры распределенной программной среды для сбора и анализа данных из разнотипных СМ на основе концепции BigData;

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

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

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

Практическую ценность работы составляют:

- программная платформа для сбора данных из CM Livejournal, ВКонтакте, Twitter, с учетом актуального состояния их топологической структуры;

- набор композитных приложений для анализа ИП в СМ, доступный в облачной среде CLAVIRE (www.clavire.ru);

2 AaaS - Application as a Service, приложение как сервис

- система тематического сбора данных СМ в составе веб-ориентированного производственно-исследовательского центра «Социодинамика» (socio.escience.ifmo.ru).

На защиту выносятся:

- адаптивная процедура эффективного сбора данных в СМ на основе методов предсказания времени возникновения новых событий в СМ и построения репрезентативных выборок с учетом топологии связей ВОП;

- архитектура программной платформы для эффективного сбора и анализа данных большого объема СМ на основе модели AaaS облачных вычислений второго поколения.

Достоверность научных результатов и выводов обеспечивается обоснованностью применения математического аппарата, результатами тестирования алгоритмов и программного обеспечения, экспериментальными исследованиями на реальных приложениях, а также практическим внедрением (опытной эксплуатацией) разработанных программных средств.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (100 наименований) и 1 приложения; содержит 125 страниц текста, включая 33 рисунка и 5 таблиц.

Глава 1. Принципы сбора и обработки больших объемов

данных в социальных медиа

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

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

1.1. Модели информационных процессов в социальных медиа

Существует широкий спектр различных социальных медиа, которые набрали большую популярность в Интернете в последние годы. Выделяют семь типов социальных медиа: социальные сети (Вконтакте, Одноклассники), блоги (Livejournal) и микроблоги (Twitter), геосоциальные сервисы (Foursquare), фотохостинги (Instagramm) и видеохостинги (Youtube), сайты отзывов (Яндекс.Маркет), сайты знакомств(ЬоуеР1апе1:). Появление этих сервисов оказало огромное влияние как на развитие интернета, так и на способы взаимодействия между людьми. Социальные медиа зачастую отражают в себе некоторую часть структуры реального сообщества, и поэтому их изучение имеет большое значение для социальных наук. Изучение социальных медиа так же важно и для решения бизнес задач, поскольку позволяет создавать более точные рекомендательные и рекламные системы, служащие главным способом монетизации социальных медиа. Социальные медиа содержат разнородную информацию, такую как текстовые сообщения, фото/видео/аудио послания, геоинформацию. Но особенно важно наличие графовой структуры, возникающей благодаря наличию разного рода связей между элементами социальных медиа, что позволяет использовать методы анализа графов и коллаборативной фильтрации для решения различных задач.

Анализ социальных медиа позволяет решить целый ряд различных задач. Исследование принципов формирования связей между пользователями позволяет понять как сеть формируется и динамически изменяется во времени. Исследование топологических сообществ в сети - групп пользователей которые сильнее связаны друг с другом, чем с остальными пользователями, так же раскрывает структуру и функциональность сети. Особый интерес представляют задачи отслеживания, моделирования и предсказывания потока распространения информации по сети. Определение наиболее важных узлов в сети может так же помочь в исследовании задачи распространения информации в сети. Поиск различного рода аномалий или «недостойного поведения» (misbehaviour detection) в социальных медиа так же важен для многих практических задач.

Для описания информационных процессов, рассмотренных выше, используется математический аппарат комплексных сетей. Под комплексной сетью подразумевается граф с достаточно большим числом узлов различной природы (характеризуемых, в том числе многомерным кортежем признаков) и динамически изменяющимися связями; распределение признаков узлов и характеристик связей может быть описано вероятностной моделью (многомерным распределением). Каждое состояние комплексной сети представляется взвешенным неориентированным графом G, который определяется как совокупность (V, Е) конечного множества вершин V, dim(F) = N, и множества ребер Е, состоящего из неупорядоченных пар (и, v), где и, v е F и иФ\. Каждая вершина характеризуется своей степенью, т.е. числом инцидентных ей ребер.

Формализм комплексных сетей применим для описания различных многосвязных систем реального мира. Примерами комплексных сетей служат социальные сети (знакомств, соавторства ученых [1]), информационные (цитирования в научных статьях, ссылок WWW [2]), технологические (Интернет как сеть компьютеров, транспортные и электрические сети) и биологические (сети нейронов в мозге, взаимодействующих протеинов, генетические сети).

Основным отличием моделей комплексных сетей от других графовых структур является возможность их вероятностного описания. Данная возможность не ограничивается частотным определением вероятности, пригодным для сетей с очень большим количеством узлов, но формально позволяет ввести вероятностное пространство (Q,Bq,Pq) , включающее в себя следующие элементы [3].

1) Q - пространство элементарных событий. Пусть V, - множество всех вершин веса (типа) /, возможно, бесконечное, a El k - множество всевозможных графов-звеньев

инцидентных паре вершин, одна из которых имеет вес ' , а другая - к : Щ,к = {е = и еУ1>уеук }> тогда О = {у €¥¡,1 = \,...Ых\ееЕ1к1,к = \....Ых].

2) Вп - сигма-алгебра подмножеств О. Любой граф, содержащий вершины весов / = 1,..,АГ1 , может быть составлен из элементов множества О и соответственно рассмотрен как подмножество множества О.

3) Рп - сигма-аддитивная мера на множестве Г2 (вероятностная мера) отражает вероятностные закономерности формирования топологии комплексной сети. Рп(о) = р0 - вероятность того, что из всех возможных графов (элементов Вп) комплексная сеть изображается графом &

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

Использование вероятностного подхода позволяет изучать комплексные сети посредством аппарата статистической физики [4]. В настоящее время существует большое число различных подходов к описанию и моделированию комплексных сетей, использующих инструменты статистической физики [5]. Комплексные сети содержат огромное количество элементов и имеют сложную структуру, что и обусловливает эффективность вероятностного подхода к сети как совокупности микросостояний. В частности, оказывается эффективным непосредственное применение к комплексным сетям конструкций статистической физики [6] (статистические ансамбли, статистические суммы, средние по ансамблю и т.д.). Достоинством такого подхода является возможность дать описание в рамках единого формализма для различных классов моделей комплексных сетей, включая случайные графы (модели Эрдоша-Реньи [7]), модели скрытых переменных [8] и их обобщения [6].

Эффективность использования конструкций статистической физики, в свою очередь, открывает возможности для обобщения на комплексные сети физических закономерностей, описывающих процессы в реальных физических системах с большим числом частиц [4]. Это позволяет получить описание макроскопических свойств сети в терминах типовых микросостояний, используя уже существующий формализм, эффективно ввести в рассмотрение макроскопические характеристики сети и установить взаимосвязи между ними. Следует отметить, что данное заключение справедливо только для равновесных сетей. Существующие модели сетей, находящихся в состоянии эволюции (например, модель Барабаши-Алберт [9]), не могут быть описаны в терминах равновесной статистической физики.

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

1) Модель случайного графа [10]. Простейшим примером такой сети является сеть, в которой фиксировано число вершин п и ребер т. Из всего множества пар вершин равномерно и случайно выбирается m пар и между ними проводится ребро. Для случайного графа распределение степеней вершин является пуассоновским.

2) Конфигурационная модель [4], в отличие от случайного графа, позволяет построить сеть с заданным законом распределения степеней.

3) Модель малого мира [11] - отдельный класс сетей, основанный на построении связей между ближайшими соседями.

4) Модель предпочтительного добавления (preferential attachment) [9]. Данная модель позволяет строить сети со степенным распределением; при этом его характеристики зависят от степени роста сети.

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

{V,E,f)i+x = Г(К, £,/),,

(F,£,/)i=0 =(К0>£0,/0). (1.1.1)

Эволюционный оператор Г может быть представлен как композиция нескольких различных операторов

м

Г=®Гт, (1.1.2)

»¡=1

каждый из которых соответствует определенной динамической компоненте эволюции

\ Р

сети. В общем случае это добавление новых вершин (оператор 1), удаление из сети

г г

вершин (оператор 2), добавление новых связей (оператор 3), разрушение существующих

связей (удаление ребер) (оператор В общем случае эти операторы некоммутативны. Соотношения (1.1.1) и (1.1.2) могут быть сведены к системе обыкновенных дифференциальных уравнений относительно макропараметров сети [6]. В общем случае вид операторов (1.1.2) и уравнений для макропараметров зависят от специфики конкретной предметной области.

Таким образом, описанные выше подходы позволяют анализировать и моделировать различные информационные процессы в социальных медиа. Однако для их идентификации необходимо знать топологию самой сети и характеристики ее узлов. Для получения этих данных непосредственно из социальных медиа используются технологии краулинга (см. раздел 1.2).

1.2. Принципы сбора данных в Интернет

Технологи сбора данных в социальных медиа основываются на методах краулинга. Поисковым роботом, или краулером (от слова to crawl - продвигаться), называется программный компонент, осуществляющий обход веб-страниц и занесение информации о них в базу данных. Поскольку априори список всех веб-страниц не известен, то поиск ссылок на новые страницы осуществляется на уже загруженных. Таким образом, краулинг представляет собой процесс обхода веб-графа. Целью работы краулера является сбор данных о как можно большем числе «качественных» веб-страницах. В зависимости от решаемой задачи термин «качественности» веб-страницы может быть сформулирован по-разному.

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

Рисунок 1.1. Обобщенный алгоритм работы краулера

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

загружаются данные из Интернет. Собранные данные сохраняются в базу данных, а так же из них извлекаются ссылки, ведущие на другие страницы. Полученные ссылки добавляются в очередь на загрузку, которая их сортирует исходя из их приоритета. На этом заканчивается текущая итерация работы краулера и начинается следующая. Краулер начинает работу с заданного набор начальных1ЖЬ и заканчивает работу при выполнении некоторого критерия, например при достижении базы данных определенного размера. Несмотря на простой алгоритм работы, к краулерам предъявляется множество требований, усложняющих как его архитектуру и реализацию, так и зачастую требует использования сложного математического аппарата.

Краулеры могут быть разделены на два основных вида: краулеры реального времени, позволяющие приступить к обработке информации сразу после ее сбора, и Ьа^Ь-краулеры, позволяющие приступить к анализу данных, только после сбора достаточно большого объема данных. Краулеры реального времени могут быть использованы при реализации систем мониторинга за процессами, происходящими в сети, и быстрого реагирования на них. Требование высокой скорости работы с данными приводит к тому, что краулеры реального времени работают преимущественно с оперативной памятью компьютера и данные обрабатываются независимо друг от друга. Ва1сЬ-краулеры осуществляют однотипные манипуляции сразу над целым массивом данных, а не обрабатывают их по отдельности. Этот тип архитектур позволяет создавать эффективные системы для работы с огромным объемом данных, но тем самым уменьшается время доступа к новой информации. Для работы с большими объемами данных данный тип краулеров активно использует эффективные алгоритмы работы с жесткими дисками, и, поскольку жесткие диски являются одним из наиболее медленных элементов современных компьютеров, при реализации ЬагсЬ-краулеров используют только операции чтения/сортировки/объединения хранимых на жестких дисках данных.

1.2.1. Требования, предъявляемые к системам сбора данных

К основным требованиям, предъявляемым к краулерам можно отнести следующие:

1) Вежливость. Требуется соблюдать накладываемые сервером правила, регулирующие частоту обращения и запрашиваемые ресурсы.

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

3) Расширяемость. Требуется «легкость» добавления или изменения компонентов краулера. Например, изменение алгоритма влияющего на работу системы, поддержка нового формата данных или сетевого протокола передачи данных.

4) Устойчивость. Система должна стабильно обрабатывать разного рода сетевые ошибки, неизбежно возникающие при обмене данных с серверами. При остановке работы, краулер должен поддерживать восстановление работы с последней точки.

5) Производительность. Работа с большими объемами данных требует эффективного использования всех ресурсов машины.

6) Качество. Собранная краулером база данных документов должна удовлетворять требованиям клиентов системы. Например, при решении задач мониторинга сети, база данных должна содержать свежие копии страниц.

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

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

1.2.2. Политики обхода краулера

Проведение систем сбора данных регулируется рядом алгоритмов, называемых политиками обхода краулера. Можно выделить несколько типов политик краулеров [12]: политика выбора данных, политика повторного посещения узлов, а так же политика вежливости, определяющая интенсивность сбора данных с одного узла и политика параллелизации. Последние две политики больше относятся к особенностям построения архитектуры краулера, в то время как две первые влияют на выбор и порядок обхода узлов сети.

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

для краулера. Например, в сети Интернет содержится огромное количество дублирующих друг друга данных, политика выбора может определять такие данные исходя из ряда эвристик, и исключать дубликаты. Могут быть предложены различные метрики для оценки важности или качества страницы, как исходя из топологических признаков страницы, так и исходя из свойств URL. Примером топологического признака может быть знаменитая метрика оценки важности PageRank, предложенная создателями поисковой компании Google [13], которая оценивает предельную вероятность оказаться в заданной странице при случайных блужданиях. В современных промышленных поисковых системах и краулерах для реализации политик выбора узла используются методы машинного обучения, которые на базе признакового описания URL определяют его важность таким образом, чтобы общее качество получаемой базы данных было максимальным.

Сайты в сети Интернет имеют динамическую природу и в общем случае изменяются в случайные моменты времени. Одно из важных требований к базе данных веб-страниц является требование «свежести», заключающееся в том, чтобы сохраненные копии документов совпадали с текущими версиями в на сайтах. Политики повторного посещения определяют страницы и момент времени, в которых их требуется повторно посетить, чтобы свежесть базы данных была максимальной. Понятие свежести базы данных может быть математически формализовано несколькими способами. Наиболее распространенными в литературе являются метрика свежести, возраста и задержки [14]. При сборе данных из сети интернет предпочтительней использовать метрику свежести, показывающей долю страниц в базе данных в последней версии. А при сборе данных из новостных сайтов предпочтительней использовать метрику задержки, показывающей время между моментом изменения страница и моментом ее обнаружения. Эффективная реализация политики повторного посещения страниц особенно важна при реализации мониторинга данных.

1.2.3. Тематический сбор данных

Стоит выделить так называемые тематические краулеры (topic or focused crawlers) [15], которые ставят своей целью сбор данных о конкретной тематике. Примерами тематических краулеров могут быть системы по поиску домашних страниц ученых, людей с определенными интересами, сбор данных в определенном формате, например графический медиаконтент. При тематическом сборе данных, краулер определяет релевантность страницы заданной тематике исходя из анализа URL страницы, анализа другой страницы, содержащей ссылку на данную страницу, или же путем анализа самого содержимого на странице, после ее загрузки. При этом в качестве базы алгоритма

вычисляющего релевантность используются методы обучения без учителя (unsupervised learning) или методы частичного обучения (semi-supervised learning).

При тематическом сборе данных релевантность страницы определяется до момента ее загрузки, и на основе этого принимается решение о ее фильтрации. Это позволяет значительно уменьшить объемы обрабатываемых данных, однако для ряда тематических сборов данных релевантность может быть вычислена только исходя из анализа содержимого страницы.

Список литературы диссертационного исследования кандидат наук Якушев, Андрей Владимирович, 2013 год

Список использованных источников

1. Redner S. How popular is your paper? An empirical study of the citation distribution // Eur. Phys. J. B-Condensed Matter Complex Syst. Springer, 1998. Vol. 4, № 2. P. 131— 134.

2. Broder A. et al. Graph structure in the Web // Comput. Networks. 2000. Vol. 33, № 1-6. P.309-320.

3. Болгова E.B. et al. Параллельные алгоритмы моделирования динамических процессов на комплексных сетях // Известия высших учебных заведений. Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2011. Vol. 54, № 10.

4. Newman М.Е J. The structure and function of complex networks.

5. Burda Z., Correia J.D., Krzywicki A. Statistical ensemble of scale-free random graphs. // Phys. Rev. E. Stat. Nonlin. Soft Matter Phys. 2001. Vol. 64, № 4 Pt 2. P. 046118.

6. Garlaschelli D., Loffredo M.I. Maximum likelihood: extracting unbiased information from complex networks. // Phys. Rev. E. Stat. Nonlin. Soft Matter Phys. 2008. Vol. 78, № 1 Pt 2.P. 015101.

7. Erdos P. On random graphs // Publ. Math. Debrecen. 1959.

8. Boguna M., Pastor-Satorras R. Class of correlated random networks with hidden variables // Phys. Rev. E (Statistical, Nonlinear, Soft Matter Physics). 2003. Vol. 68, № 3. P. 036112-036113.

9. Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Stat. Mech. complex networks. 2002. Vol. 74, № January. P. 48-97.

10. Bollobas B. Random graphs. Cambridge university press, 2001. Vol. 73.

11. Lodge D. Small World, an Academic Romance. 1984. Harmondsworth: Penguin, 1985.

12. Castillo C., Baeza-Yates R. Effective web crawling // ACM SIGIR Forum. 2005. № November 2004.

13. Page L. et al. The PageRank Citation Ranking: Bringing Order to the Web // World Wide Web Internet Web Inf. Syst. Technical report, Stanford Digital Library Technologies Project, 1998, 1998. Vol. 54, № 2. P. 1-17.

14. Sia K., Cho J., Cho H. Efficient monitoring algorithm for fast news alerts // Knowl. Data Eng.....2007.

15. Menczer F., Belew R.K. Adaptive Information Agents in Distributed Textual Environments // Proc. 2nd Int. Conf. Auton. Agents Agents98 / ed. Sycara K.P., Wooldridge M. ACM Press, 1998. P. 157-164.

16. Ipeirotis P.G., Agichtein E., Gravano L. To Search or to Crawl ? Towards a Query Optimizer for Text-Centric Tasks. 2006. P. 265-276.

17. Heydon A., Najork M. Mercator: A scalable, extensible web crawler // World Wide Web. 1999. Vol. 2, № 4. P. 219-229.

18. Singh S., Tyagi N. A Novel Architecture of Mercator: A Scalable, Extensible Web Crawler with Focused Web Crawler. 2013. Vol. 2, № June. P. 244-250.

19. Michael M. et al. Scale-up x Scale-out: A Case Study using Nutch/Lucene // 2007 ШЕЕ Int. Parallel Distrib. Process. Symp. Ieee, 2007. P. 1-8.

20. White T. Hadoop : The Definitive Guide // Online / ed. Array. Yahoo Press, 2010. Vol. 54. P. 258.

21. Boanjak M. et al. TwitterEcho: a distributed focused crawler to support open research with twitter data // Proc. 21st. 2012. P. 1233-1239.

22. Chau D.H. et al. Parallel crawling for online social networks // Proc. 16th Int. Conf. World Wide Web - WWW '07. New York, New York, USA: ACM Press, 2007. P. 1283.

23. Huang W. et al. Semantic Focused Crawling for Retrieving E-Commerce Information // J. Softw. 2009. Vol. 4, № 5. P. 436-443.

24. Ferrara E. Community structure discovery in Facebook // Int. J. Soc. Netw. Min. 2012. Vol. 1, № 1. P. 67.

25. Dave K., Lawrence S., Pennock D. Mining the peanut gallery: Opinion extraction and semantic classification of product reviews // Proc. 12th .... 2003.

26. Gjoka M. et al. Walking in Facebook: A Case Study of Unbiased Sampling of OSNs // INFOCOM 2010 Proc. IEEE. Ieee, 2010. Vol. 2, № October. P. 1-9.

27. Болгова E.B. АВТОМАТИЗАЦИЯ ПРОЦЕССА РАЗРАБОТКИ ВИРТУАЛЬНЫХ ЛАБОРАТОРИЙ НА ОСНОВЕ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ: Дис. канд. техн. наук: 05.13.06. 2012.

28. Князьков К.В. Технология разработки композитных приложений с использованием предметно-ориентированных программных модулей: Дис. канд. техн. наук: 05.13.11. 2012. Р. 170.

29. Pinkerton В. Finding what people want: Experiences with the WebCrawler // Proc. Second Int. World Wide Web Conf. Chicago, 1994. Vol. 94. P. 17-20.

30. Eiron N., McCurley K.S. Analysis of anchor text for web search // Proc. 26th Annu. Int. ACM SIGIR Conf. Res. Dev. informaion Retr. SIGIR 03. ACM Press, 2003. P. 459.

31. Smirnov I. Overview of Stemming Algorithms // Mech. Transl. DePaul University, 2008.

32. Zhao Y. et al. Ontology Classification for Semantic-Web-Based Software Engineering. 2009. Vol. 2, №4. P. 303-317.

33. Manning C.D., Raghavan P., Schütze H. Introduction to Information Retrieval // 2008 / ed. McGraw-Hill. Cambridge University Press, 2008. Vol. 1, № c. P. 496.

34. Soucy P., Mineau G.W. Beyond TFIDF Weighting for Text Categorization in the Vector Space Model//Corpus. Citeseer, 2005. Vol. 19, № l.P. 1130-1135.

35. Boyack K., Newman D., Duhon R. Clustering more than two million biomedical publications: Comparing the accuracies of nine text-based similarity approaches // PLoS One. 2011. Vol. 6, № 3.

36. Robertson S. et al. Simple BM25 Extension to Multiple Weighted Fields. 2004.

37. Митягин С .А. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ НАРКОТИЗАЦИИ НАСЕЛЕНИЯ НА ОСНОВЕ КОМПЛЕКСНЫХ СЕТЕЙ: Дис. канд. техн. наук: 05.13.18. 2012.

38. Cho J., Garcia-molina Н. Synchronizing a database to Improve Freshness. 2000. P. 1-30.

39. Cho J., Garcia-Molina H. Effective page refresh policies for Web crawlers // ACM Trans. Database Syst. 2003. Vol. 28, № 4. P. 390^26.

40. Cho J., Garcia-Molina H. Estimating frequency of change // ACM Trans. Internet Technol. 2003. Vol. 3, № 3. P. 256-290.

41. Arlitt M.F., Wfizpnson C.L. Internet Web Servers : Workload Characterization and Performance Implications. 1997. Vol. 5, № 5.

42. Brewington B.E., Cybenko G. Keeping up with the changing Web // Computer (Long. Beach. Calif). IEEE Computer Society Press, 2000. Vol. 33, № 5. P. 52-58.

43. Neyman J., Pearson E.S. Sufficient statistics and uniformly most powerful tests of statistical hypotheses. // Stat. Res. Mem. 1936. Vol. 1. P. 113-137.

44. Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics // Language (Baltim). Prentice Hall, 2000.

45. Manning C.D., Raghavan P. An Introduction to Information Retrieval // Online / ed. Salas A.C.-B.E. Cambridge University Press, 2009.

46. Mahalanobis P.C. On the generalized distance in statistics // Proc. Natl. Inst. Sei. 1936. Vol. 2. P. 49-55.

47. Steinbach M., Karypis G., Kumar V. A Comparison of Document Clustering Techniques // KDD Work, text Min. / ed. Grobelnik M„ Mladenic D., Milic-Frayling N. Ieee, 2000. Vol. 400, № X. P. 1-2.

48. Tarpey T. A Parametric k-Means Algorithm. // Comput. Stat. 2007. Vol. 22, № 1. P. 7189.

49. Ding С., He X. K-means Clustering via Principal Component Analysis // Twentyfirst Int. Conf. Mach. Learn. ICML 04 / ed: Brodley C.E. ACM Press, 2004. Vol. CI, № 2. P. 29.

50. Maiya A., Berger-Wolf T. Benefits of bias: Towards better characterization of network sampling//Proc. 17th ACM SIGKDD ....2011. P. 105-113.

51. Kurant M., Markopoulou A., Thiran P. On the bias of BFS (Breadth First Search) // Teletraffic Congr. ITC 2010 22nd Int. IEEE, 2010. P. 9.

52. Leskovec J., Kleinberg J., Faloutsos C. Graph evolution: Densification and shrinking diameters // ACM Trans. Knowl. Discov. Data. 2007. Vol. 1, № 1.

53. Leskovec J., Kleinberg J., Faloutsos C. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations // Phys. Rev. / ed. Grossman R., Bayardo R., Bennett K.P. ACM, 2005. Vol. 10, № 3. P. 177-187.

54. Stutzbach D. et al. On unbiased sampling for unstructured peer-to-peer networks // Proc. 6th ACM SIGCOMM Internet Meas. - IMC '06. New York, New York, USA: ACM Press, 2006. P. 27.

55. Rasti A.H. et al. Evaluating Sampling Techniques for Large Dynamic Graphs. 2008. Vol. 1, № September.

56. Ahmed N.K., Neville J., Kompella R. Reconsidering the foundations of network sampling //Proc. WIN. 2010.

57. Kullback S., Leibler R.A. On information and sufficiency // Ann. Math. Stat. JSTOR, 1951. Vol. 22, № 1. P. 79-86.

58. Lammel R. Google's MapReduce programming model — Revisited // Sci. Comput. Program. 2008. Vol. 70, № 1. P. 1-30.

59. White T. abynbgkfu // Online / ed. Array. Yahoo Press, 2010. Vol. 54. P. 258.

60. Lammel R. Google's MapReduce programming model — Revisited // Sci. Comput. Program. 2008. Vol. 70, № 1. P. 1-30.

61. V Knyazkov K. et al. CLAVIRE: e-Science infrastructure for data-driven computing // J. Comput. Sci. Elsevier, 2012. Vol. 3, № 6. P. 504-510.

62. Hunt P. et al. ZooKeeper: wait-free coordination for internet-scale systems // Proc. 2010 ....2010. Vol. 8.

63. McClellan M.T., Minker J., Knuth D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching // Math. Comput. 1974. Vol. 28, № 128. P. 1175.

64. Harris Z.S. Distributional structure. // Word. 1954. Vol. 10, № 23. P. 146-162.

65. DALEY D.J., KENDALL D.G. EPIDEMICS AND RUMOURS. // Nature. 1964. Vol. 204. P. 1118.

66. Agar M. Agents in Living Color: Towards Emic Agent-Based Models // J. Artif. Soc. Soc. Simul. 2005. Vol. 8, № 1. P. http://jasss.soc.surrey.ac.Uk/8/l/4.html.

67. Beenstock M., Rahav G. Immunity and Susceptibility in Illicit Drug Initiation in Israel // J. Quant. Criminol. Springer, 2004. Vol. 20, № 2. P. 117-142.

68. Gallos L.K. et al. Collective behavior in the spatial spreading of obesity // Sci. Rep. 2012. Vol. 2.

69. Bernardes D.F., Latapy M., Tarissan F. Relevance of SIR model for real-world spreading phenomena: experiments on a large-scale P2P system // Proc. 2012 Int. Conf. Adv. Soc. Networks Anal. Min. (ASONAM 2012). 2012. P. 327-334.

70. Iribarren J.L., Moro E. Impact of human activity patterns on the dynamics of information diffusion. // Phys. Rev. Lett. 2009. Vol. 103, № 3. P. 038702.

71. Onnela J.-P. et al. Structure and tie strengths in mobile communication networks. // Proc. Natl. Acad. Sci. U. S. A. 2007. Vol. 104, № 18. P. 7332-7336.

72. Scott J. Social network analysis: developments, advances, and prospects // Soc. Netw. Anal. Min. 2011. Vol. 1, № 1. P. 21-26.

73. Fisher R. On the interpretation of X2 from contingency tables, and the calculation of P // J. R. Stat. Soc. 1922. Vol. 85, № 1. P. 87-94.

74. Agresti A. [A Survey of Exact Inference for Contingency Tables]: Rejoinder // Stat. Sci. 1992. Vol. 7, № l.P. 173-177.

75. Benjamini Y., Yekutieli D. The control of the false discovery rate in multiple testing under dependency // Ann. Stat. JSTOR, 2001. Vol. 29, № 4. P. 1165-1188.

76. Benjamini Y., Hochberg Y. Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing // J. R. Stat. Soc. Ser. B. 1995. Vol. 57, № 1. P. 289-300.

77. Kantardzic M. Data Mining: Concepts, Models, Methods, and Algorithms, Second Edition //J. Comput. Inf. Sci. Eng. 2005. Vol. 5, № December. P. 394-395.

78. Everitt B.S., Landau S., Leese M. Cluster Analysis // Qual. Quant. / ed. Tinsley H.E.A., Brown S.D. Arnold, 2001. Vol. 33, № 1. P. 508-100.

79. Choi S., Cha S., Tappert C.C. A Survey of Binary Similarity and Distance Measures // J. Syst. Cybern. Informatics. 2010. Vol. 8, № 1. P. 43-48.

80. Pinto C., Mendes Lopes A., Machado J.A. A review of power laws in real life phenomena // Commun. Nonlinear Sci. Numer. Simul. Elsevier, 2012. Vol. 17, № 9. P. 3558-3578.

81. Newman M.E.J. Power laws, Pareto distributions and Zipf s law // Contemp. Phys. Taylor & Francis, 2005. Vol. 46, № 5. P. 323-351.

82. Clauset A., Shalizi C. Power-law distributions in empirical data // Arxiv Prepr. arxiv0706.1062. 2007.

83. Stumpf М.Р.Н., Wiuf С., May R.M. Subnets of scale-free networks are not scale-free: sampling properties of networks. // Proc. Natl. Acad. Sei. U. S. A. 2005. Vol. 102, № 12. P.4221-4224.

84. Swamynathan G. et al. Do Social Networks Improve e-Commerce ? A Study on Social Marketplaces // Methodology. Acm, 2008. Vol. 1. P. 1-6.

85. Mcpherson M., Smith-lovin L„ Cook J.M. В IRDS OF A F EATHER: Homophily in Social Networks. 2001.

86. Liben-Nowell D., Kleinberg J. The link-prediction problem for social networks II... Am. Soc.....2007. № November 2003. P. 556-559.

87. Якушев A.B. Д.Л.Й. РАСПРЕДЕЛЕННЫЙ КРАУЛЕР ДЛЯ СОЦИАЛЬНЫХ СЕТЕЙ НА ОСНОВЕ МОДЕЛИ MAP/REDUCE // ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫЕ И УПРАВЛЯЮЩИЕ СИСТЕМЫ. Издательство" Радиотехника"(Москва), 2012. Vol. 10, № 11. Р. 47-53.

88. Singhai А. Modern information retrieval: A brief overview // Bull. IEEE Comput. Soc. Tech. Comm. DATA Eng. 2001. P. 1-9.

89. Hasan M. AI et al. Link prediction using supervised learning // SDM'06 Work. Link .... 2006.

90. Shalizi C.R., Thomas A.C. Homophily and Contagion Are Generically Confounded in Observational Social Network Studies. // Sociol. Methods Res. 2011. Vol. 40, № 2. P. 211-239.

91. Rosvall M., Axelsson D., Bergstrom C.T. The map equation // Eur. Phys. J. Spec. Top. 2010. Vol. 178, № l.P. 13-23.

92. Rosvall M., Bergstrom C.T. Maps of random walks on complex networks reveal community structure. // Proc. Natl. Acad. Sei. U. S. A. 2008. Vol. 105, № 4. P. 11181123.

93. Ceglar A., Roddick J.F. Association Mining. 2006. Vol. 38, № 2.

94. Liu B. Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data // Comput. Knowl. Technol. (Academic .... Springer Berlin Heidelberg, 2011. P. 527-603,81-83.

95. Kiran R.U., Reddy P.K. Improved approaches to mine rare association rules in transactional databases // Proc. Fourth SIGMOD PhD Work. Innov. Database Res. -IDAR '10. New York, New York, USA: ACM Press, 2010. P. 19-24.

96. Mika P. Social Networks and the Semantic Web // Web Intell. 2004.

97. Бухановский A.B., Ковальчук C.B., Марьин C.B. Интеллектуальные высокопроизводительные программные комплексы моделирования сложных систем: концепция, архитектура и примеры реализации // Известия вузов. Приборостроение. 2009. Vol. 52, № 10. Р. 5-24.

98. Newman M.E.J. The structure and function of complex networks.

Q)

99. Афанасьев А.П., Волошинов В.В., Посыпкин М.А. С.О.В. Объединение высокоуровневых вычислительных ресурсов в распределённой среде // Распределенные вычисления и Грид-технологии в науке и образовании Труды 4-й междунар. конф. (Дубна, 28 июня - 3 июля, 2010 г.). 2010. Р. 290-296.

100. АФАНАСЬЕВ А. П., ВОЛОШИНОВ В. В., ПОСЫПКИН М. А., СИГАЛ И. X. Х.Д.А. Программный комплекс для решения задач дискретной оптимизации на распределенных вычислительных системах // Сб. трудов ИСА РАН. 2006. Vol. 25. Р. 5-17.