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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

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

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

Аннотация

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

Ключевые слова: растущие сети, случайные графы предпочтительного связывания, моделирование

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

Введение

Удобным инструментом моделирования больших сетевых структур, к которым относятся, например, виртуальные сети пользователей Интернет, транспортные и информационно-телекоммуникационные сети, являются случайные графы, теория которых сегодня активно развивается. Особо следует выделить графы, предложенные А. Барабаши и Р. Альберт [1, 2], реализующие принцип предпочтительного связывания с линейным правилом предпочтения, когда вероятность присоединения новой вершины графа в процессе его генерации к какой-либо существующей вершине прямо пропорциональна степени связности этой вершины (чем больше степень, тем больше вероятность). Более широким классом случайных графов с предпочтительным связыванием являются графы с нелинейным правилом предпочтительного связывания (НППС) рассматриваемые, например, в работах В.Н. Задорожного и Е.Б. Юдина [3-6]. Оба класса графов выращиваются по механизму, сходному с механизмом роста моделируемых сетей. Выращенный случайный граф с предпочтительным связыванием имеет характеристики, близкие с характеристиками реальной сети, что позволяет использовать его в качестве адекватной модели, на которой можно проводить имитационные эксперименты по устойчивости этой сети к разрушению, атакам вирусов, по распространению информации в сети и т.д.

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

Постановка задачи

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

Одним из результатов исследований Крапивского-Реднера [8] является вывод о том, что степень связности вершины графа зависит от времени рождения данной вершины. Для описания этой зависимости вводится величина a - возраст вершины. Возраст a означает, что вершина была введена в момент времени t - a, где t - время, прошедшее с момента начала моделирования. Средняя степень вершины k в момент времени t, с учетом ограничений на метод генерации случайного графа у Крапивского-Реднера, определяется для a  t выражением:

k ~ (1 - a/t)-1/2. (1)

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

В работе В.Н. Задорожного и В.А. Бадрызлова [9] также найдена зависимость от t степени связности произвольно выделенной вершины (далее ВВ) случайного графа с линейным правилом предпочтительного связывания и случайным числом x ребер у новых вершин:

, (2)

где k0 - степень связности ВВ в момент ее генерации;

m - среднее число ребер, инцидентных вершине графа, появляющейся на очередном шаге генерации: m =M(x);

R0 - количество ребер в графе накануне генерации ВВ;

t - время, прошедшее с момента генерации ВВ графа (если ВВ входит в граф-затравку, то это время совпадает с общим временем моделирования).

По виду формулы (2) можно отметить, что чем больше величина R0 (а это соответствует тому, что ВВ выбрана в момент, когда граф уже приобрел значительные размеры), тем меньше средняя степень связности ВВ.

Граф, рассматриваемый в работе [9], выращивается из небольшого связного графа-затравки, имеющего произвольное число вершин и ребер.

Сопоставление моделей динамики степеней вершин случайного графа

Представленная ниже таблица 1 позволяет сопоставить обозначения параметров и результаты исследований авторов. Более раннюю по времени появления модель Крапивского-Реднера будем обозначать «модель 1», вторую модель - «модель 2».

Покажем также, что формула (1) является частным случаем формулы (2).

Отметим, что время t, используемое в формулах (1) и (2) имеет разный смысл. В формуле (1) это «абсолютное» время, ведущее отсчет от начала моделирования, а в формуле (2) t - это время, прошедшее с момента генерации ВВ.

Установим соответствие между временем, используемым в разных моделях. В модели 1 возраст вершины a = 5 означает, что эта вершина была введена на 5 шагов ранее по шкале «абсолютного» времени, а в модели 2 возраст (время жизни) вершины t = 5 означает, что с момента введения вершины уже прошло 5 шагов модельного времени. Поэтому можно установить соответствие обозначений:

a (модель 1) t (модель 2).

Таблица 1

Сравнение обозначений и результатов исследования авторов

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

t («абсолютное» время, модель 1) R0 + t (t - время жизни ВВ, модель 2).

С учетом установленных соответствий обозначений времени в разных моделях, выполним подстановку обозначений модели 2 в формулу (1):

k ~ (1 - a/t)-1/2 (в обозначениях модели 1) (в обозначениях модели 2)

и далее выполним ряд преобразований:

= = = = (3)

Для графа, рассматриваемого в модели 1, как уже отмечалось, число ребер в приращении m = 1 и начальная степень генерируемой вершины k0 = 1. Подставляя в формулу (2), соответствующую модели 2, значения m = 1 и k0 = 1 получаем:

= (4)

В результате выполненных преобразований и подстановок установлено, что формулы (1) и (2), предложенные разными авторами, дают одинаковую зависимость степени связности вершины от времени в виде формул (3)-(4) для графа с одной начальной вершиной и последующим соединением новой вершины единственным ребром с уже имеющимися вершинами по линейному правилу предпочтительного связывания. Можно отметить, что формула (1) построена для графов, являющихся подклассом случайных графов, рассматриваемых в модели 2. Случайные графы модели 2 вырождаются в графы модели 1, если положить в них число вершин графа-затравки N = 1, число ребер R0 = 0 и полагать, что на каждом шаге выращивания графа число ребер в приращении m всегда равно 1.

Выводы и перспективы

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

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

1. Поиск закономерностей динамики роста вершины, вводимой в граф в произвольный момент времени с высокой степенью связности, сопоставимой со степенью связности ведущих вершин графа. Это позволяет моделировать процессы появления новых лидеров социальной сети _ включение в граф на каком либо шаге вершины с большой степенью связности имитирует появление в сети нового активного участника, более привлекательного, чем «старые» лидеры. Знание динамики роста такой вершины позволяет прогнозировать ее развитие.

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

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

Библиографический список

1. Barabбsi, A.-L. Albert, R. Emergence of scaling in random networks. Science 286. P. 509-512 (1999).

2. Введение в математическое моделирование транспортных потоков / А. В. Гасников [и др.]; под ред. А. В. Гасникова. - М. : МФТИ, 2010. - 362 с.

3. Задорожный, В. Н. Случайные графы с нелинейным правилом предпочтительного связывания /В. Н. Задорожный // Проблемы управления.

4. Zadorozhnyi, V., Yudin, E. Growing Network: Nonlinear Extension of the Barabasi-Albert Model. // Communications in Computer and Information Science. - 2014. - V. 487. - P. 432-439.

5. Юдин, Е. Б. Моделирование устойчивости Интернет в условиях распространении вирусов и случайных отказов элементов сети /Е. Б. Юдин // Омский научный вестник. - 2010. - № 1 (87). - С. 190-194.

6. Юдин, Е. Б. Генерация случайных графов предпочтительного связывания /Е. Б. Юдин // Омский научный вестник. - 2010. - № 2 (90). - С. 188-192.

7. Бадрызлов, В. А. Динамика роста степени связности вершин случайного графа /В. А. Бадрызлов //Информационные технологии и автоматизация управления: материалы VI Всерос. науч.-практ. конф. Студентов, аспирантов, работников образования и промышленности 9Омск 27-30 апр. 2015 г.) /Минобрнауки России, ОмГТУ, каф. АСОИУ. - Омск: Изд-во ОмГТУ, 2015. - С.107-115.

8. Krapivsky, P.L., Redner, S. Organization of growing random networks [Электронный ресурс]. - Режим доступа: http://physics.bu.edu/~redner/pubs/pdf/ organization.pdf (дата обращения 16.12.2014).

9. Задорожный, В. Н. Исследование динамики роста степени связности вершин случайного графа в моделях виртуальных сетей /В. Н. Задорожный, В. А. Бадрызлов //Омский научный вестник. - 2015. - №1 (137). - С.215-219.

Размещено на Allbest.ru