Удаление узла

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

Случайное удаление

Случайное удаление узла или нескольких узлов из сети означает, что удаление набора узлов происходит с определенной вероятностью. Вероятность удаления узла может следовать любому распределению; наиболее распространенным является предположение о равномерном распределении. Эффект удаления узла сильно зависит от топологии сети, поэтому он по-разному влияет на каждую эмпирическую сеть. ^[1]

Модель Эрдеша-Реньи

Влияние на связность сети измеряется диаметром сети (длиной самого длинного кратчайшего пути между двумя узлами). ^[2] Когда мы удаляем часть узлов f, диаметр сети монотонно увеличивается с увеличением f. Это связано с тем, что каждый узел имеет примерно одинаковую степень и, таким образом, вносит относительно одинаковый вклад в взаимосвязанность.

Модель Барабаши-Альберта

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

Случайное удаление из растущей сети

Когда удаление узла сочетается с другими процессами, топология сети может кардинально измениться. Чтобы проиллюстрировать это, рассмотрим модель BA. На каждом шаге добавляйте в сеть новый узел с m ссылками, а также удаляйте узел с вероятностью r. Это приводит к появлению разных сетей в зависимости от m и r. ^[3]

$r<1$ , Фаза без масштабирования : на этом этапе сеть продолжает расти, хотя темпы роста меньше из-за удаления узлов. Здесь распределение степеней остается степенным с коэффициентом $\gamma =3+{\frac {2r}{1-r}}$ .
$r=1$ , Экспоненциальная фаза : в этом случае удаление узлов и появление новых равны, поэтому сеть имеет постоянный размер. Сеть теряет свойство безмасштабности, распределение степеней превращается в растянутую экспоненту.
$r>1$ , Убывающая сеть : Скорость удаления превышает скорость роста, поэтому сеть сокращается и после конечных шагов исчезает.

Целенаправленное удаление

Когда целью является разрушение сети, гораздо разумнее нацеливаться на определенные узлы, а не удалять их равномерно случайным образом. Это происходит, например, когда кто-то борется с бактерией или хочет разрушить преступную сеть. Целенаправленное удаление может происходить в соответствии со многими стратегиями, наиболее эффективными из которых являются нацеливание на узлы самой высокой степени и нацеливание на узлы с наибольшей посреднической центральностью. ^[4] Эффективность стратегий можно измерить либо по тому, как изменяется диаметр сети, либо по тому, как изменяется размер крупнейших компонентов с течением времени удаления. ^[5]

Модель Эрдеша-Реньи

При удалении узлов, начиная с самого связного (узла с наивысшей степенью), диаметр модели Эрдеша-Реньи реагирует аналогично случайному удалению узлов. Это связано с тем, что модель довольно однородна, степени узлов близки друг к другу ( распределение степеней имеет резкий пик вокруг среднего значения), поэтому нацеливание на наиболее связанные узлы не сильно отличается от случайного выбора.

Модель Барабаши-Альберта

Диаметр модели BA резко увеличивается при удалении наиболее связанных узлов по сравнению со случаем случайного удаления. Диаметр увеличивается вдвое при удалении 5% узлов. Это связано с тем, что удаление концентраторов серьезно меняет топологию сети: большинство каналов удаляются, поэтому диаметр увеличивается.

Ссылки

^ Барабаши, А.-Л. СЕТЕВАЯ НАУКА, Издательство Кембриджского университета, 2015 г.
^ Альберт, Р.; Чон, Х.; Барабаши, А. Л. Ошибки и устойчивость к атакам сложных сетей, Рабочий документ, факультет физики, Университет Нотр-Дам, Нотр-Дам, IN 46556
^ Барабаши, А.-Л. СЕТЕВАЯ НАУКА, Издательство Кембриджского университета, 2015 г.
^ Джаханпур, Э.; Чен, X. Анализ производительности сложной сети и эвристические стратегии удаления узлов, Коммуникации в нелинейной науке и численном моделировании, том 18, выпуск 12, с. 3458-3468.
^ Не, Т.; Го, З.; Чжао, К.; Лу, З.-М. Новые стратегии атак на сложные сети, Physica A: Статистическая механика и ее приложения, том 424, 15 апреля 2015 г., страницы 248–253

[1] Барабаши, А.-Л. СЕТЕВАЯ НАУКА, Издательство Кембриджского университета, 2015 г.

[2] Альберт, Р.; Чон, Х.; Барабаши, А. Л. Ошибки и устойчивость к атакам сложных сетей, Рабочий документ, факультет физики, Университет Нотр-Дам, Нотр-Дам, IN 46556

[3] Барабаши, А.-Л. СЕТЕВАЯ НАУКА, Издательство Кембриджского университета, 2015 г.

[4] Джаханпур, Э.; Чен, X. Анализ производительности сложной сети и эвристические стратегии удаления узлов, Коммуникации в нелинейной науке и численном моделировании, том 18, выпуск 12, с. 3458-3468.

[5] Не, Т.; Го, З.; Чжао, К.; Лу, З.-М. Новые стратегии атак на сложные сети, Physica A: Статистическая механика и ее приложения, том 424, 15 апреля 2015 г., страницы 248–253

[1]

[2]

[3]

[4]

[5]