Надежность сложных сетей

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

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

Теория перколяции

Основная статья: Теория перколяции

В центре внимания устойчивости сложных сетей лежит реакция сети на удаление узлов или связей. Математическая модель такого процесса можно представить как обратный процесс перколяции. Теория перколяции моделирует процесс случайного размещения камешков на n-мерной решетке с вероятностью p и предсказывает внезапное образование одного большого кластера с критической вероятностью. $p_{c}$. В теории перколяции этот кластер называется перколяционным кластером. Это явление количественно выражается в теории перколяции с помощью ряда величин, например, среднего размера кластера. $\langle s\rangle$. Эта величина представляет собой средний размер всех конечных кластеров и определяется следующим уравнением.

${\begin{aligned}\langle s\rangle \sim \left|p-p_{c}\right|^{\gamma _{p}}\end{aligned}}$

Мы можем видеть, что средний размер кластера внезапно расходится вокруг критической вероятности, что указывает на формирование одного большого кластера. Также важно отметить, что показатель $\gamma _{p}$ универсален для всех решеток, а $p_{c}$ нет. Это важно, поскольку указывает на универсальное поведение фазового перехода в точке, зависящей от топологии. Проблему устойчивости в сложных сетях можно рассматривать как начиная с просачивающегося кластера и удаляя критическую часть камешков, чтобы кластер мог разрушиться. Аналогично образованию перколяционного кластера в теории перколяции, разрушение сложной сети происходит внезапно во время фазового перехода при удалении некоторой критической доли узлов.

Критический порог случайных сбоев

Математический вывод порога, при котором сложная сеть потеряет свой гигантский компонент , основан на критерии Моллоя-Рида .

${\begin{aligned}\kappa \equiv {\frac {\langle k^{2}\rangle }{\langle k\rangle }}>2\end{aligned}}$

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

${\begin{aligned}f_{c}=1-{\frac {1}{{\frac {\langle k^{2}\rangle }{\langle k\rangle }}-1}}\end{aligned}}$

Важным свойством этого открытия является то, что критический порог зависит только от первого и второго момента распределения степеней и действителен для произвольного распределения степеней.

Случайная сеть

Основная статья: модель Эрдеша – Реньи

С использованием $\langle k^{2}\rangle =\langle k\rangle (\langle k\rangle +1)$ для случайного графа Эрдеша – Реньи (ER) можно повторно выразить критическую точку для случайной сети.

${\begin{aligned}f_{c}^{ER}=1-{\frac {1}{\langle k\rangle }}\end{aligned}}$

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

Безмасштабная сеть

Основная статья: Безмасштабная сеть

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

${\begin{aligned}f_{c}&=1-{\frac {1}{\kappa -1}}\\\kappa &={\frac {\langle k^{2}\rangle }{\langle k\rangle }}=\left|{\frac {2-\gamma }{3-\gamma }}\right|A\\A&=K_{min},~\gamma >3\\A&=K_{max}^{3-\gamma }K_{min}^{\gamma -2},~3>\gamma >2\\A&=K_{max},~2>\gamma >1\\&where~K_{max}=K_{min}N^{\frac {1}{\gamma -1}}\end{aligned}}$

Для $\gamma >3$Критический порог зависит только от гаммы и минимальной степени, и в этом режиме сеть действует как случайная сеть, разрушающаяся при удалении конечной доли ее узлов. Для $\gamma <3$, $\kappa$ расходится в пределе, когда N стремится к бесконечности. В этом случае для больших безмасштабных сетей критический порог приближается к 1. По сути, это означает, что почти все узлы должны быть удалены, чтобы уничтожить гигантский компонент, а большие безмасштабные сети очень устойчивы к случайным сбоям. Этот вывод можно интуитивно понять, поразмыслив о неоднородности безмасштабных сетей и хабов в частности. Поскольку концентраторов относительно мало, вероятность их удаления из-за случайных сбоев с меньшей вероятностью, в то время как небольшие узлы низкого уровня с большей вероятностью будут удалены. Поскольку узлы низкой степени не имеют большого значения для соединения гигантского компонента, их удаление не имеет большого значения.

Целевые атаки на безмасштабные сети

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

${\begin{aligned}f_{c}^{\frac {2-\gamma }{1-\gamma }}=2+{\frac {2-\gamma }{3-\gamma }}K_{min}(f_{c}^{\frac {3-\gamma }{1-\gamma }}-1)\end{aligned}}$

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

Более подробную информацию об устойчивости сложных сетей к атакам можно найти на странице устойчивости к атакам .

Каскадные сбои

Основная статья: Каскадный отказ

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

Более подробную информацию о моделировании каскадных сбоев см. на странице модели глобальных каскадов .