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

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

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

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ БОЛЬШИХ ОБЪЕМОВ ДАННЫХ ИЗ СОЦИАЛЬНЫХ МЕДИА

Специальность: 05.13.11 —Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

14 НОЯ 2013

005538306

Санкт-Петербург — 2013

005538306

Работа выполнена на кафедре компьютерных технологий и в НИИ Наукоемких компьютерных технологий Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (НИУ ИТМО).

Научный руководитель: Бухановский Александр Валерьевич

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

Официальные оппоненты: Афанасьев Александр Петрович

доктор физико-математических наук, профессор,

Учреждение российской академии наук Институт проблем передачи информации РАН

Муромцев Дмитрий Ильич кандидат технических наук, доцент, СПб НИУ ИТМО

Ведущая организация: Национальный исследовательский университет

«Высшая школа экономики»

Защита состоится 28 ноября 2013 г. в 15 часов 30 минут на заседании диссертационного совета Д212.227.06 в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан 28 октября 2013 г.

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

Ученый секретарь диссертационного совета, кандидат физико-математических наук ¿X) Лобанов И. С.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4

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

Внедрение результатов работы. Результаты работы использованы при выполнении следующих НИОКР: «Создание высокотехнологичного производства комплексных решений в области предметно-ориентированных облачных вычислений для нужд науки, промышленности, бизнеса и социальной сферы» в рамках реализации постановления Правительства РФ № 218, «Распределенные экстренные вычисления для под держки принятия решений в критических ситуациях» в рамках реализации постановления Правительства РФ № 220, «Разработка веб-ориентированного производственно-исследовательского центра в области социодинамики и ее приложений» в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 гг.».

Апробация работы. Полученные результаты обсуждались на международных и всероссийских научных конференциях, семинарах и совещаниях, включая XIV Всероссийскую объединенную научную конференцию «Интернет и современное общество» (Санкт-Петербург, 2011), XI Всероссийскую конференцию «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011), Международную научно-практическую конференцию молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (Амстердам, 2012), Международную научно-практическую конференцию молодых ученых и специалистов «International School of Computational Science» (Барселона, 2013), XX Всероссийскую научно-методическую конференцию «Телематика'2013» (Санкт-Петербург, 2013), XVI Всероссийскую объединенную научную конференцию «Интернет и современное общество» (Санкт-Петербург, 2013), Международную конференцию «Инженерия Знаний и Семантического Веба "KESW-2013"» (Санкт-Петербург, 2013).

Публикации. По материалам диссертации опубликовано 12 печатных работ, в том числе 7 - в изданиях из перечня ВАК, а также 1 свидетельство о регистрации программы для ЭВМ.

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

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

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

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

Первая глава содержит аналитический обзор предметной области: рассматриваются особенности различных СМ, принципы и технологии BigData, а также методические основы описания топологических свойств ВОП.

В настоящее время традиционно выделяется семь типов СМ: социальные сети (ВКонтакге, Одноклассники), блоги (Livejoumal) и микроблоги (Twitter), геосоциальные сервисы (Foursquare), фотохостинги (Instagramm) и видеохос-тинги (Youtube), сайты отзывов (Яндекс.Маркет), сайты знакомств (LovePIanet). Эти СМ содержат разнородную информацию, такую как текстовые сообщения, фото/видео/ауциопослания, геоинформация. Однако все они характеризуются графовой (топологической) структурой, возникающей за счет разного рода связей между элементами СМ (участниками, документами, страницами), на основе которой могут эволюционировать различные информационные процессы.

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

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

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

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

Рис. 1. Задачи, решаемые при сборе данных из СМ (прямоугольники), и способы их решения (восьмиугольники)

Мониторинг СМ позволяет оперативно получать сведения о новых событиях в ВОП. В зависимости от API СМ данная задача может быть решена двумя принципиально различными методами: загрузка новых событий и поиск новых событий в системе. Некоторые СМ, например Twitter, позволяют подписаться на поток всех новых сообщений; мониторинг проводится по мере поступления данных. Другой подход заключается в том, что новые сообщения необходимо выявлять в СМ, для чего краулером загружается информация о различных элементах сети и осуществляется поиск новых событий путем сравнения с предыдущим состоянием. Однако из-за ограничения частоты доступа и большого объема элементов СМ прямое решение этой задачи неэффективно. Как следствие, оптимизация данного подхода заключается в прогнозировании изменений в СМ с перераспределением квот на доступ к данным при использовании для этого априорных знаний об активности пользователей.

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

Аналитический обзор показал, что для эффективного решения задач мониторинга и построения репрезентативных выборок требуются априорные знания о структуре и свойствах ВОП СМ, которые возможно получить только на основе уже накопленных данных. Как следствие, в дальнейших исследованиях все три задачи рассматриваются в совокупности. Несмотря на то, что мониторинг СМ может быть ориентирован на отслеживание достаточно редких событий, его реализация требует обработки уже накопленных данных по всему ВОП. Потому для создания инструментов работы с данными СМ целесообразно использовать концепцию и технологии Big Data. Благодаря этому можно строить систему сбора данных, абстрагируясь от решения задач, связанных с распределенными вычислениями и хранением данных на низком уровне, тем самым обеспечивая универсальность разработанных методов, технологий и программных средств для СМ с различной топологией и назначением.

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

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

Композитные приложения в облаке, доступные э модели АааЗ ретроспективных состояний СМ

Рис. 2. Общая схема адаптивной процедуры эффективного сбора данных в СМ

Управление процессом краулинга осуществляется путем распределения квот доступа и формирования политики обхода топологии СМ. С точки зрения мониторинга состояния ВОП в текущий момент времени I, целью управления является наиболее быстрое обнаружение новых событий в СМ. Для формализации этого понятия используется функция задержки, которая по сути равна времени между появлением события в СМ и его обнаружением. Если в узле СМ произошли события в моменты времени £2> ■■■ и к этому узлу обращались в моменты времени а1( а2, ...ат, значение функции задержки для события будет равно £)(£;) = а,- — £:;, где а; - минимальное значение, удовлетворяющее условию С; < . Функция задержки для узла СМ будет равна сумме задержек для всех его событий.

В общем виде при решении задачи распределения квот доступа требуется распределить М обращений между .¿V элементами СМ и рассчитать время обращения таким образом, чтобы минимизировать функцию задержки исходя из активности пользователей. Данная задача решается путем разбиения на две подзадачи: определение числа суточных обращений ш, к узлу сети и определение времени суток, в которое необходимо совершить [тг] обращений к узлу. Результаты анализа экспериментальных данных показали, что для моделирования появления в течение дня новых событий допустимо использовать однородный пуассоновский процесс. В этом случае минимум ожидаемого значения функции задержки достигается при распределении ежедневных квот между узлами пропорционально корню квадратному из их частоты обновления т.1 = ку[Хь где к удовлетворяет условию = М. Использование этой модели для определения квот обращения к платформе Ыуе-Доигпа1 позволило выявлять новые сообщения на 13 % быстрее, по сравнению с равномерным распределением квот между блогами.

Для определения времени обращения к узлу используется модель периодического неоднородного пуассоновского процесса, которая позволяет

учесть суточную ритмику активности пользователей. Активность каждого узла СМ характеризуется 24-мерным вектором описывающим распределение событий в течение суток. Минимум ожидаемого значения функции задержки будет достигаться, если совершать т обращений к узлу в моменты времени а1( аг,... ат, которые являются квантилями распределения вероятности т.е. для любого / = 0,..., т. выполняется Л(0 йЬ = /1(0 <И. Проверка работоспособности модели на данных 1луе.к>игпа1 продемонстрировала снижение задержки на 14 %, что в совокупности с предыдущей моделью обеспечивает повышение эффективности на 25 % (рис. 3; учитываются: 1 - частота обновления и время суток, 2 - частота обновления, 3 -время суток; 4 - частота обновления и время суток не учитываются).

1.2

X

ч:

я 1.0

ж

а.

Я 0.8

1.0.6

0.4

2.0

2.5 3.0 3.5 4.0 4.5 5.0

Среднее число обращений к блогу за сутки

Рис. 3. Задержка обнаружения новых событий в зависимости от частоты обращений

Число новых записей за сутки

Рис. 4. Задержка обнаружения событий в зависимости от частоты обновления

Отметим, что учет эффекта суточной ритмики для часто обновляющихся блогов позволяет достичь 30 %-ного повышения скорости обнаружения новых сообщений (рис. 4; время суток: 1 -не учитывается, 2 - учитывается).

Формирование политики обхода топологии СМ определяется требованиями к репрезентативности выборки узлов, исходя из свойств ВОП в целом. Одним из характерных показателей репрезентативности является корректное воспроизведение степеней вершин сети СМ. Анализ показал, что большинство методов обхода СМ (обход в ширину - ВР8 и случайные блуждания -Капёоп^аЦс) выдают смещенную выборку, в которой преобладают узлы с высокой степенью. Потому в рамках данной процедуры реализована политика обхода на основе алгоритма Метрополиса-Гастингса (МНЯ\\0, выполняющего случайное блуждание по графу заданной топологии с возвращением, при котором посещенные узлы сети выкидываются из выборки с вероятностью, зависящей от их степени. Вероятности перехода между двумя совпадающими или соединенными ребром вершинами графа V и IV определяются ^-тт(1, если IV соединена ребром с V

— ^ лIV'

1— Еу^рРС^.у), если IV совпадает с V где ку - степень вершины.

как: Р(у, и/)

На рис. 5(a) сравниваются различные способы обхода СМ ВКонтакте, в качестве исходной выборки использовались данные о первых 100 ООО пользователях, зарегистрированных в этой сети (1 - BFS, 2 - MHRW, 3 -Random Walk). Отметим что алгоритм MHRW позволяет получить несмещенные выборки и в случае стратификации данных.

Отдельной задачей является формирование политики обхода, позволяющей найти топологические сообщества в ВОП, в которых находятся заданные узлы. Для этого используется метод PFS, обеспечивающий выборку узлов с наибольшим локальным коэффициентом кластеризации (JIKK). Метод PFS основан на методе обхода в ширину графа (BFS), но вместо обычной очереди используется приоритетная, где приоритетом узла является число ведущих к нему найденных ссылок. В качестве следующего посещаемого узла из очереди выбирается вершина с максимальным числом входящих ссылок. На рис. 5(6) по данным СМ ВКонтакте показано, как в зависимости от размера выборки в ней отличается распределение J1KK от распределения во всей сети СМ (/ - BFS, 2 - MHRW, 3 - PFS). В качестве меры близости между распределениями используется мера Кульбака-Лейблера - DKL(j),q) =

ZexPWlnffi.

(а) (б)

Рис. 5. Сравнение методов обхода сети: а - распределение степеней вершин выборок; б -расстояние Кульбака-Лейблера между распределениями ЛКК для выборок и для всей сети

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

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

- «вежливость», т.е. соблюдение квот на загрузку данных, устанавливаемых операторами СМ;

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

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

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

Для реализации такой архитектуры краулера в части работы с данными использована модель распределенных вычислений MapReduce, поддерживаемая фреймворком Apache Hadoop. На ее основе реализуется batch-краулер, который за одну итерацию обрабатывает большое число URL, что позволяет эффективно работать с большим объемом данных, но увеличивает время доступа к вновь полученным данным. Модули краулера вызываются последовательно друг за другом, но каждый отдельный модуль может выполняться параллельно на нескольких вычислительных ресурсах. Работа краулера представляет собой итерационный процесс. На каждой итерации краулер обрабатывает фиксированное число страниц, которое является входным параметром системы. Данные хранятся в сегментах, отвечающих определенным итерациям работы краулера. Одна из особенностей предложенной архитектуры заключается в том, что модули краулера реализованы либо на базе фреймворка Apache Hadoop, либо как отдельные приложения, в зависимости от того, необходимо ли им агрегировать все имеющиеся данные. Например, построение списка всех собранных URL основано на анализе всех сегментов базы данных, поэтому реализовано на базе Hadoop. В то же время извлечение данных из скачанных веб-страниц не требует агрегации по всем сегментам базы данных, поэтому реализовано вне кластера Hadoop. При такой архитектуре необходимы координация и синхронизация между кластером Apache Hadoop и отдельными вычислительными ресурсами, что решается посредством использования библиотеки Apache ZooKeeper, на базе которой возможно реализовать механизмы распределенных блокировок. Для организации вычислительного процесса в целях уточнения параметров планирования работы краулера используется модель AaaS, реализованная на основе облачной платформы второго поколения CLAVIRE. Вычисления организуются в виде композитных приложений, каждое из которых содержит источники данных (подключаемые через интерфейс API Apache Hadoop) и собственно вычислительные модули, осуществляющие их обработку.

Модуль загрузки реализован как самостоятельное приложение, способное работать на независимых вычислительных ресурсах, что позволяет более эффективно использовать сетевой канал. Получая на вход список URL, модуль загружает соответствующие им веб-страницы. Можно работать с несколькими СМ независимо, поэтому для каждого сервиса модуль загрузки представляет собой отдельный процесс. Загруженные веб-страницы и извлеченные данные копируются в новые сегменты баз данных, хранимых на кластере Hadoop. Для сериализации данных используется библиотека Google Protobuf. Для повышения производительности данные архивируются с помощью библиотеки Google Snappy.

Управление работой краулера производится путем распределения квот доступа и выработки политики обхода в соответствии с топологией СМ. В результате формируется список новых URL. По тематическому словарю выполняется фильтрация релевантных запросам клиента данных и формируется список новых URL. Сам модуль политик обхода реализован на базе Hadoop, в случае необходимости он может использовать внешние расчетные модули из облака CLAVIRE. Система поддерживает нескольких различных политик обхода, которые выполняются параллельно и независимо друг от друга. В результате формируется несколько списков URL, объединенных в очередь URL. Это позволяет распределить сетевой канал между несколькими клиентами системы, не превысив квоту на загрузку данных из СМ. Для некоторых политик обхода сети на вычислительном ресурсе запускается копия загрузчика данных, функционирующего независимо от основного загрузчика и адаптирующего список посещаемых URL в зависимости от только что загруженных данных, не обращаясь к ретроспективе.

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

Четвертая глава посвящена апробации разработанной программной платформы на базе прикладных исследований данных, собранных из CM LiveJournal, ВКонтакте и Twitter.

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

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

Были собраны данные о случайным образом выбранных 100 ООО поль- i зователях Live Journal, из которых 16 553 были отмечены как интересующиеся темой наркотиков. Были собраны данные об интересах каждого пользователя - ключевых словах, которые характеризуют интересующие его темы. С помощью теста Фишера и процедуры коррекции значимости при множественных сравнениях Хохберга и Бенджамини были определены интересы группы пользователей, встречавшиеся чаще, чем во всей совокупности. Благодаря этому был составлен психологический потрет интересующихся темой наркотиков пользователей. После экспертной кластеризации интересов выявлено, что пользователи, пишущие о наркотиках в LiveJournal, также интересуются русской рок-музыкой, нетрадиционной медициной, НЛО, буддизмом, йогой и различными оккультными практиками (рис. 6).

20

§10 с

5 0

^ Частота степени вершины, х

Рис. 6. Результаты анализа процессов распространения наркокультуры в СМ: а-темы, привлекшие внимание пользователей, интересующихся и не интересующихся наркотиками; б - гистограмма степеней вершин сети на логарифмических осях. Аппроксимация распределения степенным законом с а = 1.54

На основе выявленных значимых интересов был построен байесовский классификатор, который позволил выявить 3586 пользователей со схожими интересами, которые потенциально могут интересоваться наркокультурой, несмотря на отсутствие у них текстов, связанных с темой наркотиков. Если провести аналогию с распространением заболеваний, то пользователи могут быть поделены на три группы «инфицированные», «восприимчивые» и «иммунные» с точки зрения пропаганды наркотиков.

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

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

Одна из важных особенностей социальных сетей - наличие топологических сообществ, т.е. групп пользователей, у которых много связей друг с другом и мало с остальными пользователями. В СМ сообщества объединяют узлы сети на основе общего признака: интереса, проживания, работы. Поиск сообществ в социальных сетях осложняется большим объемом анализируемых сетей, с которыми большинство методов не позволяют работать. Для поиска сообществ был использован метод 1п(ЪМар, основанный на принципах теории информации и моделирования случайных блужданий по сети. Алгоритм группирует вершины графа таким образом, чтобы минимизировать длину описания пути случайного блуждания в графе, измеряемую числом битов, необходимым для описания каждой вершины пути случайного блуждания. На рис. 7 представлен профиль сообществ пользователей сети ВКонтакте, характеризуемый совместным распределением проводимости и размера сообщества. Функция проводимости равна отношению числа ребер, лежащих вне сообщества, к числу ребер, лежащих внутри сообщества. Метод (пГоМар показал наличие в сети большого количества небольших и слабовыраженных сообществ, а также отдельных ярко выраженных и более крупных сообществ.

Проанализировав различные атрибуты пользователей из одного сообщества, возможно отыскать общие темы интересов всего сообщества. Для обнаружения общих атрибутов используются методы поиска ассоциативных правил. Анализ интересов пользователей Ыуе.[оигпа1 выявил ряд тем, которые сплотили вокруг себя участников сети: инвестирование финансов или трейдинг, национализм, флирт и пр. Для сети ВКонтакте было обнаружено, что сообщества в большинстве своем сформированы исходя из места обучения.

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

5 10 20 40 Размер сообщества

Рис. 7. Совместное распределение проводимости и размера сообщества

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

Топологический признак знакомства пользователей основан на коэффициенте Жаккара (принимает значения из интервала [0, 1]), который показывает, как много общих знакомых у двух пользователей. Если расчетное значение коэффициента Жаккара больше порогового, пользователи считаются знако- | мыми в реальном мире. Пороговое значение вычисляется на основе обучающей выборки пользователей, о которых известно, что они знакомы в жизни; в данном исследовании оно соответствует медиане распределения (рис. 8; I -для знакомых друг с другом пользователей, 2 - класс неизвестных связей, 3 -пороговое значение признака знакомства пользователей). Обучающая выборка отражает связи между пользователями, которые учились вместе в одной школе или университете; коэффициент Жаккара в ней имеет распределение, близкое к логнормальному. На основе трех выделенных признаков можно объяснить 85 % связей в сети ВКонтакте: обучение в одной школе объясняет 14 % связей, в одном университете — 32 %, а большое число общих друзей -39 %. Оставшиеся 15 % связей не могут быть классифицированы на основании используемых критериев, однако какая-то их часть может относиться к ' пользователям, знакомым в реальном мире.

Рис. 8. Гистограмма значений Рис. 9. Интенсивность обсуждения различ-

коэффициента Жаккара ных тем в 1дуе.1оигпа1

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

вать критерии сбора или анализа данных из социальных сетей, например, задать словарь ключевых слов для сбора данных. По завершении работы пользователю будут доступны для загрузки собранные краулером тематические данные. На рис. 9 приведен пример изменения интенсивности обсуждения различных тем в сети LiveJournal в 2013 г. (1 - тема миграции, 2 - тема подростковых самоубийств, 5 - тема электронного правительства).

Заключение

В результате выполнения диссертационной работы:

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

- спроектирована архитектура распределенной программной среды для сбора и анализа данных из разнотипных СМ на основе сопряжения концепции BigData и облачной модели AaaS; выполнена ее программная реализация с использованием фреймворка Apache Hadoop и облачной платформы CLAVIRE;

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

Публикации по теме диссертационной работы

1. Yakushev А. V, Boukhanovsky А. V, Sloot RM.A. Topic crawler for social networks monitoring // Proc. of the 4th Conf. on Knowledge Engineering and Semantic Web (KESW-2013). Communications in Computer and Information Science. Berlin, Heidelberg: Springer, 2013. Vol. 394. P. 214-227. [Входит в перечень ВАК].

2. Якушев А.В., Дейкстра Л. Й., Митягин С. А. Распределенный краулер для социальных сетей на основе модели Map/Reduce // Информационно-измерительные и управляющие системы. 2012. № 11. С. 47-53 [Входит в перечень ВАК].

3. Якушев А.В., Митягин С.А., Бухановский А.В. Имитационное моделирование наркотизации населения по данным мониторинга социальных сетей // Современные исследования социальных проблем. 2012. №2(10). С. 133-151 [Входит в перечень ВАК].

4. Якушев А.В., Митягин С.А., Бухановский А.В., Захаров Ю.Н. Исследование социальных сетей в задаче моделирования наркотизации населения и противодействия незаконному обороту наркотиков // Вестн. Санкт-Петербургского университета МВД России. 2012. № 4. С. 107-111 [Входит в перечень ВАК].

5. Иванов С. В., Болгова Е. В., Каширин В. В., Якушев А. В., Чугунов А. В., Бухановский А. В. Web-ориентированный производственно-

17

исследовательский центр «Социодинамика» // Изв. вузов. Приборостроение. 2011. № 10. С. 65-71 [Входит в перечень ВАК].

6. Чугунов A.B., Бершадская Л.А., Якушев A.B., Болгова Е.В., Биккулов A.C. Социальные сети и социометрические исследования: теоретические основания и практика использования автоматизированного инструментария изучения виртуальных сообществ // Информационные ресурсы России. 2012. № 4. С. 19-24 [Входит в перечень ВАК].

7. Бершадская Л.А., Биккулов A.C., Болгова Е.В., Чугунов A.B., Якушев A.B. Социометрические исследования в социальных сетях как инструментарий социологии и политологии // Современные проблемы науки и образования. 2012. № 4 (Электронный журнал). URL: http://www.science-education.ru/104-6901 [Входит в перечень ВАК].

8. Митягин С.А., Якушев A.B., Бухановский A.B. Исследование социальных сетей интернет на предмет выявления сопутствующих интересов лиц, склонных к наркомании // Международный научно-исследовательский журнал. 2012. № 6-1. С. 59-64.

9. Иванов С. В., Болгова Е. В., Каширгт В. В., Якушев А. В., Чугунов А. В., Бухановский А. В., Слоот П.М.А. Веб-ориентированный центр в области социодинамики: концепция и принципиальная архитектура // Тр. XIV Всеросс. объединенной конф. «Интернет и современное общество» (IMS-2011). СПб, 2011. С. 75-80.

10. Якушев A.B. Эффективный мониторинг социальных сетей // XX Всероссийская научно-методическая конференция «Телематика'2013». СПб, 2013. С. 264-265.

11. Якушев A.B., Бухановский A.B. Знакомы ли «друзья» в сети Vkontakte в личной жизни? // Тр. XVI Всеросс.объединенной конф. «Интернет и современное общество» (IMS-2013). СПб, 2013. С. 110-115.

12. Программная система «SD/Crawler» интеллектуального сбора и анализа данных в социальных сетях / А. Якушев, С. Митягин, А. Бухановский, Р. Sloot. Св-во о гос. регистрации программы для ЭВМ №2012617951 от 03.09.2012 г.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики ФГБОУ ВПО «НИУ ИТМО»

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

04201451250

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

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ БОЛЬШИХ ОБЪЕМОВ ДАННЫХ ИЗ СОЦИАЛЬНЫХ МЕДИА

Специальность: 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н. Бухановский А.В.

Санкт-Петербург — 2013

Оглавление

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

Введение...............................................................................................................................5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение......................................................................................................................117

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

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

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

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

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

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]. Это позволяет получить описание макроскопических свойств сети в терминах типовых микросостояний, ис�