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

• Бадрызлов Владимир Александрович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Бадрызлов Владимир Александрович

Введение

1 Моделирование растущих сетей с использованием случайных графов

1.1 Растущие сети как объект исследования

1.2 Моделирование сетей случайными графами

1.2.1 Случайные графы Эрдеша-Реньи

1.2.2 Графы Уотса-Строгатца и сети тесного мира

1.2.3 Графы Барабаши-Альберт и правило предпочтительного связывания

1.3 Разновидности случайных графов с предпочтительным связыванием

1.3.1 Ориентированный случайный граф с предпочтительным связыванием

1.3.2 Обобщенный граф с предпочтительным связыванием

1.3.3 Граф предпочтительного связывания с дополнительным качеством

1.3.4 Граф предпочтительного связывания с условно независимыми ребрами

1.3.5 Граф предпочтительного связывания с устареванием вершин

1.4 Случайные графы с нелинейным правилом предпочтительного связывания

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

2 Переходные процессы в случайных графах с пропорциональным правилом предпочтительного связывания

2.1 Асимптотически точная формула для расчета средних степеней связности вершин

2.2 Зависимость средних степеней связности вершин от времени в замкнутом виде

2.3 Сравнение полученных результатов с известными результатами

2.4 Анализ точности методов расчета средних степеней связности вершин

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

3 Переходные процессы в растущих случайных графах с нелинейным правилом предпочтительного связывания

3.1 Сетевые переходные процессы в растущих случайных графах

3.1.1 Рекуррентные формулы для расчета сетевых переходных процессов

3.1.2 Примеры расчета сетевых переходных процессов

3.2 Локальные переходные процессы в случайных графах

3.2.1 Рекуррентные формулы для расчета локальных переходных процессов

3.2.2 Алгоритм расчета средних степеней связности вершин

3.2.3 Упрощенный метод расчета средних степеней связности

3.3 Длительность переходных процессов и конечный финальный средний вес вершин

3.3.1 Длительность переходных процессов в графах Барабаши-Альберт

3.3.2 Исследование финального среднего веса вершин в известных классах случайных графов

3.3.3 Метод среднего поля для расчета финальных характеристик графов Барабаши-Альберт

3.3.4 Вывод выражений в замкнутом виде для расчета финальных характеристик случайных графов

3.3.5 Метод контроля погрешностей расчета переходных процессов

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

4 Программные средства генерации случайных графов и моделирования

растущих сетей

4.1 Средства генерации случайных графов с предпочтительным связыванием

4.1.1 Агентное моделирование

4.1.2 Базовый принцип генерации случайных графов

4.1.3 Алгоритм генерации случайных графов с пропорциональным правилом предпочтительного связывания

4.1.4 Генерация случайных графов с нелинейным правилом предпочтительного связывания

4.1.5 Общая схема имитационной модели

4.2 Имитационное моделирование с использованием программы генерации случайных графов

4.2.1 Выбор варианта выращивания случайных графов

4.2.2 Результаты имитационных экспериментов

4.3 Реализация разработанных методов в среде электронных таблиц

4.3.1 Расчет сетевых переходных процессов

4.3.2 Расчет распределения состояний выделенной вершины

4.3.3 Расчет финального среднего веса вершин графа

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

Заключение

Список условных обозначений, символов, сокращений

Список литературы

Приложение А Погрешности расчета средней степени связности ВВ

различными методами

Приложение Б Схема алгоритма расчета финального среднего веса вершин

графа

Приложение В 1ауа-код генерации графа Барабаши-Альберт с одним

ребром в приращении

Приложение Г Схема алгоритма генерации графа Барабаши-

Альберт

Приложение Д 1ауа-код генерации графа с ПППС со случайным числом

ребер в приращении

Приложение Е Свидетельства о государственной регистрации

программ

Приложение Ж Акты о внедрении результатов диссертации

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

Введение

Актуальность темы исследования. Наука о сетях (Network science), сформировавшаяся в начале нынешнего века, решает широкий круг задач, связанных с изучением сетей, в частности, задач их анализа и идентификации, изучения процессов развития сетей и распространения информации по сетям, исследования устойчивости к разрушающим воздействиям и т.д. Одна из важнейших задач - это изучение и прогнозирование процессов роста сетей, поскольку задачей Network science является «изучение сетевых представлений физических, биологических и социальных явлений, ведущее к прогнозирующим моделям этих явлений» [125].

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

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

распространения в них информации, оценка скорости и стоимости распространения рекламы в социальных сетях и др.

Степень разработанности темы исследования. Впервые случайные графы были предложены в 1959-1960 гг. в работах П. Эрдеша (P. Erdos) и А. Реньи (A. Renyi) [115, 116]. Графы Эрдеша-Реньи - наиболее изученные случайные графы, но они практически не используются в моделировании растущих сетей, поскольку не отражают известные на сегодняшний день закономерности роста сетей. В 1998 году С. Строгатц (S. Strogatz) и Д. Уотс (D. Watts) [127, 128] предложили случайные графы, позже получившие их имя. Графы Уотса-Строгатца воспроизводят свойство «тесного мира», характерное для Интернета и ряда других реальных сетей, но строятся на фиксированном множестве вершин и поэтому не подходят для моделирования растущих сетей.

В работе А. Барабаши (A. Barabasi) и Р. Альберт (R. Albert) [102] было предложено в качестве модели Интернета использовать растущий случайный граф, строящийся по правилу предпочтительного связывания. Правило предпочтительного связывания предполагает, что новые вершины, появляющиеся в растущем графе, с большей вероятностью присоединяются к вершинам, имеющим большее значение функции предпочтения (вес). Для графов Барабаши -Альберт (далее графы БА) функция предпочтения имеет вид fk) = k, где k -степень связности вершины. Растущие случайные графы с функцией предпочтения вершин f(k) = k будем далее называть графами с пропорциональным правилом предпочтительного связывания (графами с ПППС). Графы БА и правило предпочтительного связывания легли в основу исследований ряда зарубежных ученых: B. Bollobas и O. Riordan [107, 108, 109, 110], M. Newman [124], J. Leskovec [121], S. Boccaletti и др. [106]. Среди российских исследователей, занимающихся случайными графами, можно выделить И.А. Евина [44, 45], В.Н. Задорожного [46-56, 130-132], В.Ф. Колчина [66], А.М. Райгородского [8284], Е.Б. Юдина [97-100].

Разнообразные аспекты моделирования социальных сетей рассмотрены в работах К.Г. Абрамова [1-4], Д.А. Губанова, Д.А. Новикова и А.Г. Чхартишвили [37-39], Ю.М. Монахова [77], В.М. Сазанова [86-87].

Среди исследований, связанных со случайными графами с предпочтительным связыванием, выделяются работы следующих авторов: B. Bollobas, С. Borgs, J. Chayes и O. Riordan [108], C. Cooper и A. Frieze [111, 112], G. Ergun и G.J .Rodgers [117], S. Dereich и P. Morters [113], P.L. Krapivsky и S. Redner [119, 120], Л.А. Прохоренкова и Е.А. Самосват [81]. В каждой из названных работ предлагаются классы случайных графов с различными правилами предпочтительного связывания. Например, возможен выбор наиболее предпочтительной вершины не только на основании ее степени связности, но и на основании некоторых дополнительных качеств, присущих вершинам, или выбор вершины на основании ее возраста (чем моложе, тем предпочтительнее) и т.д. С помощью этих графов авторы пытаются воспроизвести некоторые специфические особенности растущих сетей, не учитываемые в других графах. В работе В.Н. Задорожного [46] предложены случайные графы с нелинейным правилом предпочтительного связывания (далее графы с НППС). Для них решен ряд задач: найден метод расчета финальных распределений степеней связности (РСС) вершин, разработан алгоритм поиска финального среднего веса вершин, разработан метод калибровки генераторов графов с НППС, позволяющий строить графы с заданным РСС вершин, решен ряд других задач.

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

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

Для достижения поставленной цели в работе ставятся следующие задачи:

1. Исследование динамики формирования растущих сетей с использованием аналитических методов теории случайных графов с предпочтительным связыванием и метода имитационного моделирования.

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

3. Вывод асимптотически точных рекуррентных уравнений переходного процесса для РСС вершин графов с НППС и разработка основанного на этих уравнениях численного метода расчета переходного процесса для РСС.

4. Разработка численного метода расчета переходного процесса для распределения возможных состояний выделенной вершины в графе с НППС.

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

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

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

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

Научная новизна выполненной работы состоит в следующем:

1. В виде рекуррентного соотношения найдена зависимость от времени степени связности произвольной выделенной вершины графа с ПППС.

2. Установлена в замкнутом виде зависимость средней степени связности произвольной выделенной вершины графа с ПППС от возраста этой вершины. Найденная зависимость применима к более широкому кругу случайных графов, чем ранее полученные (A. L. Barabasi, R. Albert, 1999) аналогичные зависимости.

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

4. Предложен численный метод расчета распределений вероятностей состояний выделенных вершин в переходных процессах формирования графов с НППС.

5. Получен метод расчета финальных РСС вершин в графах с НППС, отличающийся от ранее предложенного метода (В.Н. Задорожный, 2010) выводом формул для контроля точности определения финального среднего веса вершин.

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

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

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

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

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

Положения и результаты, выносимые на защиту:

1. Рекуррентное выражение зависимости средней степени связности произвольно выделенной в графе с ПППС вершины от ее возраста.

2. Выраженная в замкнутом виде зависимость средней степени связности произвольно выделенной в графе с ПППС вершины от ее возраста.

3. Численный рекуррентный метод расчета зависимости РСС вершин графов с НППС от времени.

4. Численный рекуррентный метод для расчета зависимости распределения вероятностей состояний выделенной в графе с НППС вершины от ее возраста.

5. Метод расчета финальных РСС вершин графов с НППС с контролем точности определения финального среднего веса вершин.

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

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

International scientific and technical conference «Mechanical science and technology update», Омск, 2019 г., I Всероссийская с международным участием научно-практическая конференция студентов, аспирантов, работников образования и промышленности «Системы управления, информационные технологии и математическое моделирование», Омск, 2019 г., IX всероссийская научно-практическая конференция студентов, аспирантов, работников образования и промышленности «Информационные технологии и автоматизация управления», Омск, 2018 г.; международная IEEE конференция «2016 International Siberian Conference on Control and Communications (SIBCON)», Москва, 2016 г.; Седьмая всероссийская научно-практическая конференция «Имитационное моделирование. Теория и практика» (ИММОД-2015), Москва, 2015 г.; Всероссийская научно-техническая конференция «Россия молодая: передовые технологии - в промышленность», Омск, 2015 г.

Результаты исследований также были опубликованы в материалах нескольких конференций: Всероссийская научно-практическая конференция «Имитационное моделирование. Теория и практика» (ИММОД-2019, г. Екатеринбург и ИММОД-2017, г. Москва), XVIII международная конференция им. А.Ф. Терпугова «Информационные технологии и математическое моделирование», Саратов, 2019 г., Всероссийская научно-практическая конференция студентов, аспирантов, работников образования и промышленности «Информационные технологии и автоматизация управления», Омск (2019, 2018, 2017, 2015, 2013, 2012 гг.), Всероссийская научно-практическая конференция «Организационно-управленческие аспекты экономического развития предприятий и регионов», Омск, 2017 г.; V Всероссийская научно-техническая конференция с международным участием «Россия молодая: передовые технологии - в промышленность!», Омск, 2013 г.; Международная научно-практическая конференция «Проблемы экономики, организации и управления в России и в мире», Прага, 2013 г.; VIII международная научно-техническая конференция «Динамика систем, механизмов и машин», Омск, 2012 г.

Публикации. По теме диссертации опубликована 31 работа, в том числе 8 работ опубликованы в журналах, включенных в «Перечень рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук», две работы включены в международную систему научного цитирования Scopus. Получены два свидетельства о регистрации программ.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объем работы - 164 страницы машинописного текста. Работа содержит 31 рисунок, 7 таблиц, список литературы включает 133 наименования. Объем приложений - 21 страница.

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

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

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

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

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

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

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

1 Моделирование растущих сетей с использованием

случайных графов

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

1.1 Растущие сети как объект исследования

В современном мире человека окружает множество самых разнообразных сетей, например:

1. Технологические сети - Интернет, транспортные, телефонные и электрические сети.

2. Социальные сети, основанные как на телекоммуникационных технологиях, так и на обычных межличностных коммуникациях.

3. Информационные сети - сеть гиперссылок World Wide Web и сети научного цитирования.

4. Биологические сети, такие, как биохимические цепи, цепи взаимодействия протеинов, метаболические и нейронные сети.

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

[123] представлены на Рисунке 1.1. Как следует из этих данных, масштабы социальных сетей огромны, прямое изучение объектов таких размеров затруднено, эксперименты с самими сетями труднореализуемы. Наиболее плодотворным методом исследования в таком случае является метод моделирования, который позволяет строить адекватные модели реальных сетей, обладающих теми же основными свойствами, что и сами сети.

Facebook YouTube WhatsApp Facebook Messenger We С hat In stag ram QQ QZone Doujin j TikTok Sina Weibo

Рисунок 1.1 - Численность активных участников социальных сетей, млн человек, по состоянию на июль 2018 года

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

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

В качестве примера различий свойств растущих сетей рассмотрим два наиболее крупные объекта исследования: Интернет и социальные сети. Распределение степеней связности узлов - одна из самых важных характеристик сетей, определяющих их свойства. Исследования А. Барабаши и Р. Альберт [102], показали, что РСС узлов Интернета подчиняется степенному закону. Доля pk вершин, имеющих степень связности к:

Рк к = 1, 2, -

где с - некоторая константа.

Широко известно правило предпочтительного связывания в трактовке А. Барабаши и Р. Альберт. Оно означает, что новый объект сети с большей вероятностью соединяется с узлами, богатыми связями, чем с узлами, имеющими малое количество связей. Применение этого правила приводит к тому, что в сети образуются несколько узлов с очень высокой степенью связности и множество малосвязных узлов.

Для узлов социальной сети, в отличие от Интернета, может существовать некоторое верхнее ограничение на количество связей, которое одновременно способен поддерживать обычный человек [118]. Если какой-либо участник сети имеет множество связей, то необязательно все новые участники сети в соответствии с правилом предпочтительного связывания будут устанавливать контакты именно с этим человеком, так как он может быть просто закрыт от установления новых контактов. Это обстоятельство ведет к появлению РСС узлов с законом распределения, отличным от степенного закона. В таком РСС велика доля вершин со степенью связности, близкой к максимальному числу связей, которые может поддерживать отдельный участник [118].

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

1.2 Моделирование сетей случайными графами

Широко известные графы Эрдеша-Реньи, Уотса-Строгатца, Барабаши-Альберт знаменуют основные вехи в теории случайных графов. Предложенные правила построения этих графов в свое время стали новыми этапами в науке о сетях, а сами графы явились базой для построения многих других графов, развивающих базовые идеи. Так, со случайных графов Эрдеша -Реньи в принципе начинается теория случайных графов. Графы Уотса-Строгатца положили начало графам, обладающим высоким коэффициентом кластеризации, как у реальных социальных сетей. Графы Барабаши-Альберт впервые реализовали правило предпочтительного связывания, а также степенной закон РСС, свойственный узлам Интернета. На правиле предпочтительного связывания построены многие другие случайные графы, предложенные для моделирования сетей.

1.2.1 Случайные графы Эрдеша-Реньи

Теория случайных графов стала развиваться с конца 50-х годов XX века. Ее основоположниками считают П. Эрдеша и А. Реньи [115, 116], которые предложили модель для описания реальных сетей в виде случайного графа.

Случайные графы Эрдеша-Реньи образуются следующим образом:

- фиксируют N вершин графа;

- любую пару вершин случайно, с равной вероятностью р, связывают ребром.

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

Эрдеша-Реньи не воспроизводят РСС узлов Интернета по степенному закону, выявленное в ходе исследования Интернета. РСС графа Эрдеша-Реньи соответствует закону Пуассона - доля рк вершин графа с N вершинами и вероятностью р образования ребра, имеющих степень связности к, определяется законом [44]:

)к

к!

Рк ~ в-PN (Р^-, к = 1, 2, ...

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

Список литературы диссертационного исследования кандидат наук Бадрызлов Владимир Александрович, 2020 год

// // //

//

p[i]=p[i-1]+pow(rang,1.1);

p[i]=p[i-1]+log(rang);

p[i]=p[i-1]+1/rang;

p[i]=p[i-1]+rang;

p[i]=p[i-1]+1;

}

}

double sum rang=p[number]; for (int j=0; j<=number; j=j+1){ p[j]=p[j]/sum_rang;

}

//Закончено формирование массива вероятностей присоединения к вершинам

//собираются степени вершин

// функция 1/х //

//в p[i] нарастающим итогом

//конец цикла

//в переменной sum rang накоплена сумма степеней вершин (сумма весов для НППС) //цикл, в котором накапливаются вероятности вершин

//Определяется количество ребер в приращении // int v=people.size();

// int r=uniform discr(1,v);

// int r=2;

int r=uniform discr(1,5);

//

int r=reber();

//можно выбирать случайное число вершин для присоединения //можно выбирать в интервале от 1 до общего числа вершин в графе //присоединяется 2 вершины

//случайным образом определяется число вершин г от 1 до 5 //для присоединения к существующим

//число ребер определяется произвольной функцией геЬег

//Добавляется новая вершина add people();

int last number=people.size()-1; age.add(step);

age.set(last number, 0); stepen.add(O); stepen.set(last number, r);

//добавляется новая вершина Ь //определяется номер этой последней вершины //в коллекцию добавляется новый элемент //соответствующий добавленной вершине //время жизни добавленной вершины = 0 //в коллекцию добавляется новый элемент //степень добавленной вершины = г

//Добавленная вершина со степенью r связывается с существующими по правилу предпочтения Agent b=people.get(last number); //агент b - последний в списке

for (int k=1; k<=r; k=k+1){ //цикл по количеству вершин для присоединения

double random value=uniform(); //генерируется случайное число от 0 до 1

int agent number connect=0; //задается номер вершины 0 для соединения

for (int i=0; i<=number; i=i+1){ //цикл по общему числу вершин

if (random value>=0 && random value<p[0] && (i==0)){ //если это 0-вершина

Agent a=people.get(0); //создается вершина a (агент)а для соединения

int stepen a=stepen.get(0); //задается степень вершины a, которая хранится в коллекции stepen

a.connectTo(b); //новую вершину соединяем с 0 вершиной

stepen.set(0,stepen a+1);

break;

//в коллекции stepen степень вершины увеличивается на 1 //выходим из цикла перебора вершин

}

else if (random value>p[0] && i==0){

}

else if (random value>p[i-1] && random value<= agent number connect=i;

Agent a=people.get(agent number connect); int stepen a=stepen.get(agent number conne

a.connectTo(b);

stepen.set(agent number connect,stepen a+1 break;

else if (random value>p[i-1] && random value<p Agent a=people.get(number);

int stepen a=stepen.get(number); //

a.connectTo(b);

stepen.set(number,stepen a+1); //

break;

}

}

else {

}

}

}

//Закончилось добавление новой вершины

р[±] && (11=0 || 11=питЬег)){

//задается номер вершины i для присоединения //создается вершина а (агент)для соединения с^; //задается степень вершины а,

//которая хранится в коллекции stepen //новую вершину соединяем с i вершиной ); //в коллекции stepen степень вершины i увеличивается на 1 //выходим из цикла перебора вершин

[1] && (1==питЬег)){

//вершина для присоединения последняя задается степень вершины a, которая хранится в коллекции stepen

//новую вершину соединяем с последней вершиной в коллекции stepen степень последней вершины увеличивается на 1 //выходим из цикла перебора вершин

//конец цикла перебора вершин

//конец цикла по числу присоединяемых вершин

Приложение Е

(обязательное)

Свидетельства о государственной регистрации программ

Регистрация в ФИПС

Регистрация в ОФЭРНиО

_

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное тсударствениос бюджетное научное упреждение

ИНСТИТУТ УПРАВЛЕНИЯ ОБРАЗОВАНИЕМ РОССИЙСКОЙ АКАДЕМИИ

ОБРАЗОВАНИЯ

ОБЪЕДИНЕННЫЙ ФОНД ОЛГКТРОННЫХ РЕСУРСОВ "НАУКА И ОБРАЗОВАНИЕ'

(основан • 1941 году)

СВИДЕТЕЛЬСТВО О РЕГИСТРАЦИИ ЭЛЕКТРОННОГО РЕСУРСА

№>23177 __

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

I енерання случайного I рафа с нредиочппельным связыванием V.!

Дата регистрации: 03 окт ября 2017 годя Автор: Бадрмтлов В.А.

Организация-разработчик ФГБОУ ВО «Омский государственный

технический уннпереитет»

Приложение Ж (обязательное) Акты о внедрении результатов диссертации

1Лксиомя

ООО «Аксиома-Софт Консалтинг»

117105, г. Москва, Варшавское ш.. дом 37А, стр. 2, тгаж 4, пом. 25 ИНН 7734693658. ОГРН 1137746023359 Тел. [phone], факс *7 [phone] МсхЭахютг^оК.ги www.axioma-soft.ru

АКТ О ВНЕДРЕНИИ

результатов диссертационной работы В.А. Бадрызлова «Методы моделирования, анализа и прогнозирования динамики развития растущих

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

При внедрении результатов диссертации получен следующий технический эффект:

- повышена степень обоснованности выбора площадок для продвижения рекламной и маркетинговой информации в социальных сетях;

- сокращено время принятия решений о запуске рекламных проектов;

- скорректирован алгоритм работы менеджеров по рекламе.

сетей»

ООО «Аксиома-Софт Консалтинг»

ИНН/КПП: 7734693658 / 772401001 Юридический адрес: 117105. г. Москва, Варшавское ш., дом 37А. стр. 2, этаж 4. пом. 25 Тел. [phone]

Генеральный директор ООО «Аксиома-Софт Консалтинг»

Козий С .Л.

м.п.

о внедрении результатов диссертационной работы Бадрызлова Владимира Александровича, выполненной в Федеральном государственном бюджетном образовательном учреждении высшего образования «Омский государственный технический университет» (ОмГТУ), представленной на соискание ученой степени кандидата технических наук

Комиссия в составе:

Председатель:

Николаев C.B. начальник службы сбыта, маркетинга и ВЭС, АО «Высокие технологии»;

Члены комиссии:

Раат H.A. - главный специалист по маркетингу службы сбыта, маркетинга и ВЭС, АО «Высокие технологии»;

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

и представитель Федерального государственного бюджетного образовательного учреждения высшего образования «Омский государственный технический университет» (ОмГТУ), аспирант Бадрызлов В.А. составили настоящий акт о том. что в период с 25.05.2020 по 05.06.2020 г. были проведены испытания программных средств и численных методов, разработанных Бадрызловым В.А. и представленных им в диссертационной работе. Обоснованность технических решений, расчетов и методов, предложенных автором, подтверждена полученными на имя Бадрызлова В.А. следующими охранными документами:

-свидетельство №2020614746 от 24.04.2020 г. о регистрации программы для ЭВМ «Генерация случайных графов с предпочтительным связыванием» в Федеральной службе по интеллектуальной собствснности (Роспатент);

свидетельство №23177 от 03.11.2017 г. о регистрации в ОФЭРНиО электронного ресурса «Генерация случайного графа с предпочтительным связыванием v.l».

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

С гранима I m 2

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

- снижение затрат времени по построению прогнозов развития сети контрагентов с использованием численных методов в сравнении с применяемыми методами на 28%;

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

Алгоритмы, разработанные в диссертации, использованы для модернизации программного обеспечения компании.

Акт выдан для представления в диссертационный совет.

От АО «Высокие технологии»

— Л

Председатель комисс C.B. Николаев

Члены комиссии

Н.А. Раат

И.Н. Матросов

От ОмГТУ

В.А. Бадрызлов

1'граница 2 ИЗ 2

Министерство науки и высшею образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования «Омский государственный технический университет»

УТВЕРЖДАЮ

Проректор по Омского юсу, технического

« ¿С "»

АКТ

о внедрении результатов диссертационной раооты «Методы моделирования, анализа и прогнозирования динамики развития растущих сетей» Бадрызлова Владимира Александровича

Комиссия в составе: председатель комиссии

члены комиссии

Соломин Вячеслав Юрьевич, начальник отдела корпоративных средств массовой информации ОмГТУ, Фефелов Василий Федорович, начальник НИЧ ОмГГУ. Никифорова Ангелина Юрьевна, начальник отдела организации НИР студентов и молодых ученых ОмГТУ

составили настоящий акт о следующем.

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

1. Залорожный В Н., Бадрызлов В.А. Переходные процессы в растущих сетях с нелинейным правилом предпо'ггительного связывания /I Омский научный вестник. -2016.-№1(145). -С.95-99.

2. Бадрызлов В. А. Имитационное моделирование социальной сети на основе ретроспективных данных II Восьмая всероссийская научно-практическая конференция по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2017): Труды конф., 18-20 окт. 2017 г. — Т.1. —М.: ИПУ РАН. 2017.-С.326-331.

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

Председатель комиссии

Начальник отдела корпоративных средств массовой информации ОмГТУ

/4п

1гны комиссии:

Начальник НИЧ ОмГТУ

Начальник отдела организации НИР студентов и молодых ученых ОмГТУ

В.Ю. Соломин В.Ф. Фефелов А.Ю. Никифорова

Министерство науки и высшею образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования «Омский государственный технический университет»

УТВЕРЖДАЮ

Проректор поучебной работе / Омского государственного

с технического университета, д.т.н

£ -4 I'/ ' V '. > 1 Л

» . | г '/-I О.В. Кронотин

АКТ

о внедрении результатов диссертационной работы Бадрызлова Владимира Александровича в учебный процесс ОмГТУ

Комиссия в составе:

председатель комиссии - Макаров В.В., к.т.н.. декан факультета информационных

технологий и компьютерных систем; члены комиссии - Бояркин Г.Н., д.э.н.. зав. кафедрой «Математические

методы и информационные технологии в экономике», - Стариков В.И.. к.т.н.. доцент кафедры «Математические методы и информационные технологии в экономике» составили настоящий акт о следующем:

Результаты диссертационной работы В.А. Бадрьшова используются при изучении дисциплины «Имитационное моделирование» студентами факультета информационных технологий и компьютерных систем направлений подготовки 09.03.03 «Прикладная информатика» Программа «Генерация случайного графа с предпочтительным связыванием у.1» применяется при проведении лабораторных работ по указанной дисциплине дчя исследования процессов формирования растущих социальных сетей и исследования процессов распространения информации в них.

Председатель комиссии

к.т.н., декан факультета информационных

технологии и компьютерных систем

Члены комиссии:

д.э.н.. зав. кафедрой «Математические методы и информационные технологии в экономике»

к.т.н.. доцент кафедры «Математические методы и информационные технологии в экономике»