Введение 2
2 Описание модели 4
2.1 Моделирование 4
3 Результаты 5
4 Доказательства 11
5 Заключение 23
6 Приложения 24
6.1 Приложение А 24
Список литературы 26
В чем сложность изучения массивных динамических графов и сетей? Есть множество параметров и свойств, которые делают каждую сеть уникальной. Ориентированность, связность, длины путей, распределение степеней вершин, количество ребер, количество вершин, диаметр, инвариантность масштаба, коэффициенты кластеризации, наличие "треугольников", двудольность и т.д., и т.д. [1]
К сожалению, работать с реальным объектом бывает сложно, энергозатратно, долго или дорого. В таком случае на помощь могут прийти модели, которые можно описать в строгих математических терминах и в них же сформулировать ожидаемое поведение графа. А уже хорошие математические модели могут подсказать, какими свойствами обладает реальный объект.
Есть множество хорошо изученных моделей графов. Вот несколько из них:
Модель G(n,p)
Зафиксируем количество вершин в графе. За это отвечает параметр n.С вероятностью p 2 (0,1) независимо для каждой пары вершин возникает ребро [2].
Модель G(n,|E|) или модель Эрдёша-Реньи.
Зафиксируем количество вершин и ребер в графе. За это отвечает параметры n и Е|. С равной вероятностью выбираем граф с данным числом вершин и ребер [2].
Модель Gn.
Первоначально у нас есть n вершин и нет ребер. В каждый момент времени т, берем G(n, Е), где Е = т и говорим, что это "моментальный снимок" эволюции графа. Другими словами, на момент времени т наш граф находится в таком состоянии [2].
При всех своих достоинствах, эти модели не подходят, например, для моделирования графов со степенным законом распределения, т.к. ребра появляются независимо, а нам требуется корреляция [3].
Что такое степенной закон распределения?
При степенном распределении доля вершин степени dпропорциональна 1/daдля некоторого фиксированного а > 0. Существует множество реальных примеров сетей со степенным законом распределения: Всемирная сеть WWW [4,5,6,7,8,9], сеть телефонных звонков [10, 11], цитирование в статьях [12], совместное употребление слов [13, 14], биологические обменные сети [15]. И все они представляют практический интерес.
Если граф ориентирован, параметры законов для входящих и исходящих степеней могут и не совпадать. Например, для узлов подсети университета Нотр-Дама (nd.edu) эти параметры равны 2.1 и 2.4, соответственно. А если рассматривать поисковую систему Altavista как граф, где вершины - это статические страницы в сети, а ребра - ссылки между этими страницами, можно обнаружить, что эти параметры - 2.1 и 2.7.
Как моделировать такие графы?
Например, некоторые графы типа "мир тесен" обладают данным свойством. Их основная идея в том, чтобы типичное расстояние между двумя произвольными вершинами было пропорционально логарифму от числа вершин. В качестве реализации этой идеи можно взять модель Уотса и Строгатса [16], модель Бармпутиса и Мюррея [17] или Монассона [18], Ньюмэна и Уотса [19].
Модель Уотса и Строгатса.
Первоначально у нас есть n вершин. Связываем каждую вершину со всеми соседями на расстоянии не более некоторого фиксированного к. Для каждого ребра с некоторой вероятностью pодин из кондов заменяется на случайную вершину.
Замечание. В данной модели необходимо следить за тем, чтобы не появлялись петли и двойные ребра.
Возникают вопросы: если не использовать "близость" между вершинами и не ограничивать расстояние, как ещё можно моделировать такие графы? Как контролировать параметры? Какими дополнительными свойствами они обладают? Настоящая дипломная работа, в том числе, посвящена решению этих задач.
В работе была рассмотрена модель, которую можно использовать для динамического моделирования массивных графов со степенным распределением при условии, что параметры для входящих и исходящих степеней совпадают или граф неориентирован, а параметр больше 2. Если 0 такой параметр, то для моделирования выбирается а = 1/(5 — 1). Также выявлена связь вероятности появления петель и оценок отклонения от среднего количества вершин с фиксированными степенями. С помощью этого исправлены ошибки, допущенные при доказательстве в оригинальной статье
Обозначим перспективы и существующие вопросы:
1. Распространяется ли результат на модели В, С, D из той же статьи?
2. Можно ли исключить петли и двойные ребра для построения социальных графов?
3. Можно ли улучшить оценку для ci;j;tпри а > 2 в предложении 8?
