Модели локальной мировой развивающейся сети
Динамические сети, которые меняются со временем

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

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

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

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

  П л о с а л ′ ( к я ) = П ′ ( я ∈ Л о с а л − Вт о г л г ) к я ∑ дж ∈ Л о с а л к я {\displaystyle P_{local}'(k_{i})=P'(i\in Локально-Мировой){\frac {k_{i}}{\sum _{j\in Локально}k_{i}^{}}}}

Где   и термин «Local-World» относится ко всем узлам, которые находятся в сфере интересов вновь добавленного узла в момент времени t. Таким образом, это можно переписать: П ′ ( я ∈ Л о с а л − Вт о г л г ) = М м 0 + т {\displaystyle P'(i\in Локальный мир)={\frac {M}{m_{0}+t^{}}}}

  П л о с а л ′ ( к я ) = М м 0 + т к я ∑ дж ∈ Л о с а л к я {\displaystyle P_{local}'(k_{i})={\frac {M_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}}

в то время как динамика такова:

  ∂ к я ∂ т = м М м 0 + т к я ∑ дж ∈ Л о с а л к я {\displaystyle {\frac {\partial k_{i}}{\partial t}}={\frac {mM_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}}

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

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

Случай А. Нижний предел М = м {\displaystyle М=м}

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

  ∂ к я ∂ т = м м 0 + т к я ∑ дж ∈ Л о с а л к я {\displaystyle {\frac {\partial k_{i}}{\partial t}}={\frac {m_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}}

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

Случай B Нижний предел М = м 0 + т {\displaystyle М=м_{0}+т}

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

  ∂ к я ∂ т = к я 2 т {\displaystyle {\frac {\partial k_{i}}{\partial t}}={\frac {k_{i}}{2t}}}

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

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

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

  П г л о б а л ( к я ) = к я ∑ дж к дж {\displaystyle P_{global}(k_{i})={\frac {k_{i}}{\sum _{j}k_{j}}}}

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

  П л о с а л ′ ( к я ) = П ′ ( я ∈ Л о с а л − Вт о г л г ) к дж ∑ дж ∈ Л о с а л к дж {\displaystyle P_{local}'(k_{i})=P'(i\in Локально-Мировой){\frac {k_{j}}{\sum _{j\in Локально}k_{j}^{}}}}

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

  П а л л ′ ( к я ) == δ к я ∑ дж к дж + ( 1 − δ ) П ′ ( я ∈ Л о с а л − Вт о г л г ) к я ∑ дж к дж {\displaystyle P_{all}'(k_{i})==\delta {\frac {k_{i}}{\sum _{j}k_{j}}}+(1-\delta )P'(i\in Локальный мир){\frac {k_{i}}{\sum _{j}k_{j}}}}

где — вероятность того, что новый узел обладает знаниями о глобальной сети. Подобно модели LW, модель NLW различает три случая локально-мирового выбора: δ {\displaystyle \дельта}

  м = М {\displaystyle м=М} ; и м ≪ М ≪ м 0 + т {\displaystyle м\лл М\лл м_{0}+т} М = м 0 + т {\displaystyle М=м_{0}+т}

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

Случай A Нижний предел М = м {\displaystyle М=м}

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

  ∂ к я ∂ т = δ к я + 2 ( 1 − δ ) м 2 т {\displaystyle {\frac {\partial k_{i}}{\partial t}}={\frac {\delta k_{i}+2(1-\delta )m}{2t}}}

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

Случай Б. м ≪ М ≪ м 0 + т {\displaystyle м\лл М\лл м_{0}+т}

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

  ∂ к я ∂ т = [ δ 2 − 1 + δ 1 − δ ] к я т {\displaystyle {\frac {\partial k_{i}}{\partial t}}=\left[{\frac {\delta }{2}}-{\frac {1+\delta }{1-\delta }}\right]{\frac {k_{i}}{t}}}

с предположением, что:  Как и в предыдущем случае, развивающаяся сеть имеет степенное распределение степеней, однако с большим показателем γ, который равен :  Можно заметить, что отношение является единственным параметром масштабно-свободного показателя новой модели. Таким образом, существенное улучшение модели происходит от введения , которое путем добавления или удаления узлов, обладающих информацией о глобальной сети, позволяет управлять топологической структурой сети. ∑ дж ∈ л о с а л к дж = ∑ дж ∈ л о с а л к дж = [ δ ⟨ к я ⟩ + ( 1 − δ ) м ] М {\displaystyle \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}
4 + δ + δ 2 2 − δ − δ 2 {\displaystyle {\frac {4+\delta +\delta ^{2}}{2-\delta -\delta ^{2}}}}
δ {\displaystyle \дельта} δ {\displaystyle \дельта}

Ссылки

  1. ^ Эрдеш, П. и А.Реньи (1961). Об эволюции случайных графов. Опубл. Математика. Инст. Хунг. акад. Наука, Том 5, стр.17-61
  2. ^ Альберт, Р. и А.Л.Барабаси (2000). Physical Review Letters, т.85, №24, стр.5234
  3. ^ Уоттс, Дж. Д. и Х. С. Строгац (1998). Коллективная динамика сетей «малого мира», Nature, т. 393, стр. 440-442
  4. ^ Сен, К. и Д.Г.Чжонг () Китайская физика B, т.18, №2, стр.383
  5. ^ Вэнь, Г., Чжан Дуань, Г. Чен Г. и Ся Гэн (2011). Physica A, т. 390, стр. 4012
  6. ^ Xuan, Q., Y.Li и T.Wu (2007). Physica A, Vol.378, p.561
  7. ^ Ли, X. и GRChen (2003). Physica A, т. 328, стр. 274

Источники

  • Бао, З. и И. Цао (2008). Журнал науки Чжэцзянского университета, том 9, № 10, стр. 1336
  • Lu, J., H.Leung и G.Chen (2004). Динамика непрерывных, дискретных и импульсных систем, Серия B: Приложения и алгоритмы, Том 11a, стр. 70
Взято с "https://en.wikipedia.org/w/index.php?title=Модели_локальной_эволюционной_сети_Мира&oldid=1264988253"