Развивающиеся сетевые модели локального мира

Развивающиеся сети — это динамические сети, которые меняются со временем. В каждый период $t$ к сети присоединяются новые узлы и ребра, а старые исчезают. Такое динамическое поведение характерно для большинства реальных сетей, независимо от их радиуса действия — глобального или локального. Однако сети различаются не только по своему радиусу действия, но и по топологической структуре. Можно выделить:

• Случайные сети
• Свободномасштабные сети
• Сети маленького мира
• Локальные сети

Одной из основных особенностей, позволяющей дифференцировать сети, является процесс их эволюции. В случайных сетях точки добавляются и удаляются из сети совершенно случайным образом (модель Эрдеша и Реньи ). Эволюция сетей свободного масштаба основана на преимущественном присоединении – узлы подключаются к узлам, которые уже имеют большое количество связей. В результате создаются хабы (узлы с наибольшим количеством ребер), а сети подчиняются степенному закону распределения ( модель Барабаши и Альберта) . ). Напротив, в маленьких мировых сетях нет хабов, а узлы довольно эгалитарны и локально группируются в более мелкие кластеры. Сети такого типа описываются моделью Уоттса и Строгаца (WS) . Все вышеупомянутые модели предполагают, что вновь добавленные точки содержат глобальную информацию обо всей сети. Однако в случае больших систем такие знания встречаются довольно редко. Это сильно ограничивает возможности узлов по выбору соединения. В результате решения о ссылках принимаются скорее в локальном мире, чем во всей сети. Сети, учитывающие эту локальность, называются сетями локального мира и впервые были описаны моделью Ли и Чена (2003). Модель локального мира была расширена, среди прочего, Гарденьесом и Морено (2004), Сеном и Чжонгом, Вен и др. или Сюань и др.

Мировая развивающаяся сетевая модель Ли и Чена (2003)

Модель начинается с набора небольшого количества узлов. $m_{0}$ и небольшое количество ребер $e_{0}$. Есть M узлов, которые были выбраны случайным образом из всей глобальной сети, так что они составляют так называемый «локальный мир» для новых приходящих узлов. Таким образом, каждый новый узел с m ребрами соединяется только с m существующими узлами из своего локального мира и не связывается с узлами, находящимися в глобальной системе (основное отличие от модели BA). В таком случае вероятность соединения может быть определена как:

 $P_{local}'(k_{i})=P'(i\in Local-World){\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

Где $P'(i\in Local-World)={\frac {M}{m_{0}+t^{}}}$ а термин «локальный мир» относится ко всем узлам, которые представляют интерес для вновь добавленного узла в момент времени t. Таким образом, его можно переписать:

 $P_{local}'(k_{i})={\frac {M_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

а динамика такая:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {mM_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

В каждый момент времени t верно, что $m\leqslant M\leqslant m_{0}+t$, так что возможны два угловых решения: $M=m$ и $M=m_{0}+t$.

Рис.1. Сравнение распределения степеней в логарифмическом масштабе для случая нижней границы с M = m = 3 и развивающейся сети локального мира с M = 4 и m = 3. Сети имеют N = 10 000. На вставке показано лог-линейный масштаб тех же кривых

Случай A. Нижний ограниченный предел $M=m$

Новый узел соединяется только с узлами из первоначально выбранного локального мира M. Это указывает на то, что в процессе роста сети выбор предпочтительного подключения (PA) неэффективен. Случай идентичен безмасштабной модели BA, в которой сеть растет без PA. Скорость изменения степени i-го узла можно записать следующим образом:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {m_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

Таким образом, вышеизложенное доказывает, что в решении нижней границы сеть имеет экспоненциально затухающее распределение степеней: $P(k)\sim e^{-k/m}$(Рис.1)

Случай B Нижний ограниченный предел $M=m_{0}+t$

В этом случае локальный мир ведет себя так же, как и глобальная сеть. Оно развивается во времени. Следовательно, модель LW можно сравнить с безмасштабной моделью Барабаси – Альберта, а скорость изменения степени «i-го» узла можно выразить как:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {k_{i}}{2t}}$

Это равенство указывает на то, что в решении верхней границы модель LW следует распределению степеней степенного закона: $P(k)\sim 2m^{2}/k^{3}$ (рис. 2)
Следовательно, из A и B можно обнаружить, что среди угловых решений модель Ли и Чена представляет собой переход распределения степеней между экспоненциальным и степенным законом (рис.3).

Новая сетевая модель развития локального мира Сена и Чжуна (2009 г.)

Модель является расширением модели LM в том смысле, что она делит узлы на те, которые имеют информацию о глобальной сети, и на те, которые ее не имеют. Чтобы контролировать эту диверсификацию, параметр $\delta$ вводится. Позволять $\delta$ – отношение количества узлов, получающих информацию о глобальной сети, к общему числу узлов. Потому что $\delta$ это соотношение, должно быть так $\delta \in \left[0,1\right]$. Когда $\delta =0$ нет узлов, владеющих глобальной информацией, и модель NLW сводится к модели локальной сети. По очереди, $\delta =1$ означает, что каждый узел обладает глобальной информацией о сети, что делает модель NLW идентичной модели BA.
Модель NWL начинается так же, как и LW – имеется набор из небольшого количества узлов m_0 и небольшого количества ребер. $e_{0}$. Есть M узлов, которые были выбраны случайным образом из всей глобальной сети и создали «локальный мир» для новых узлов. Однако в модели NLW каждый новый узел с m ребрами может подключаться к глобальной или локальной системе. Решение зависит от полученной информации. Если новый узел получает информацию обо всей сети, вероятность того, что он будет соединен с узлом i, зависит от степени ki этого узла, так что:

 $P_{global}(k_{i})={\frac {k_{i}}{\sum _{j}k_{j}}}$

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

 $P_{local}'(k_{i})=P'(i\in Local-World){\frac {k_{j}}{\sum _{j\in Local}k_{j}^{}}}$

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

 $P_{all}'(k_{i})==\delta {\frac {k_{i}}{\sum _{j}k_{j}}}+(1-\delta )P'(i\in Local-World){\frac {k_{i}}{\sum _{j}k_{j}}}$

где $\delta$ — это вероятность того, что новый узел обладает знаниями о глобальной сети.Подобно модели LW, модель NLW различает три случая выбора локального мира:

 $m=M$; $m\ll M\ll m_{0}+t$ и $M=m_{0}+t$

Случай верхней границы (Случай C) такой же, как и в модели локального мира.

Случай A Нижний ограниченный предел $M=m$

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

 ${\frac {\partial k_{i}}{\partial t}}={\frac {\delta k_{i}+2(1-\delta )m}{2t}}$

с предположением, что: $\sum _{j\in local}k_{j}=M\left\langle k_{i}\right\rangle =m\left\langle k_{i}\right\rangle \approx mk_{i}$
В этом случае распределение степеней сетей соответствует распределению малой мощности, а показатель степени безмасштабной сети $(\sigma )$ равно $1+{\frac {\delta }{2}}$ так что первоначальное предположение о малых $\delta$указывает на то, что показатель низкой мощности сети достигает высокого значения.

Случай Б. $m\ll M\ll m_{0}+t$

Во времени t существуют $m_{0}+t$ узлы. Если новый приходящий узел не имеет информации о глобальной сети, он свяжется с i узлом в локальной системе с вероятностью $M=m_{0}+t$. Таким образом, динамику можно записать следующим образом:

 ${\frac {\partial k_{i}}{\partial t}}=\left[{\frac {\delta }{2}}-{\frac {1+\delta }{1-\delta }}\right]{\frac {k_{i}}{t}}$

с предположением, что: $\sum _{j\in local}k{j}=\sum _{j\in local}k_{j}=\left[\delta \left\langle k_{i}\right\rangle +(1-\delta )m\right]M$
Как и в предыдущем случае, развивающаяся сеть имеет степенное распределение степеней, однако с большим показателем γ, который равен: ${\frac {4+\delta +\delta ^{2}}{2-\delta -\delta ^{2}}}$
Можно заметить, что $\delta$ соотношение является единственным параметром безмасштабного показателя новой модели. Таким образом, существенное улучшение модели происходит за счет введения $\delta$, который путем добавления или удаления узлов, владеющих информацией о глобальной сети, позволяет управлять топологической структурой сети.

Источники

• Бао З. и Ю. Цао (2008). Журнал науки Чжэцзянского университета A, том 9, № 10, с. 1336
• Лу Дж., Х.Люнг и Г.Чен (2004). Динамика непрерывных, дискретных и импульсных систем. Серия B: Приложения и алгоритмы, Том 11а, с. 70