Удаление узла — это процедура удаления узла из сети , при которой узел выбирается случайным образом или напрямую. Удаление узла используется для проверки надежности и устойчивости сетей к атакам . Понимание того, как сеть изменяется в ответ на удаление узла, имеет решающее значение для многих эмпирических сетей. Применение варьируется во многих областях, включая взлом Всемирной паутины путем удаления маршрутизатора, устранение эпидемий или борьбу с преступными организациями.
Случайное удаление узла или нескольких узлов из сети означает, что удаление набора узлов происходит с определенной вероятностью. Вероятность удаления узла может следовать любому распределению; наиболее распространенным является предположение о равномерном распределении. Эффект удаления узла сильно зависит от топологии сети, поэтому он влияет на каждую эмпирическую сеть по-разному. [1]
Влияние на связанность сети измеряется диаметром сети (длиной самого длинного кратчайшего пути между двумя узлами). [2] Когда мы удаляем долю f узлов, диаметр сети монотонно увеличивается с f. Это связано с тем, что каждый узел имеет примерно одинаковую степень и, таким образом, вносит относительно одинаковый вклад во взаимосвязанность.
Эффект в безмасштабной сети сильно отличается от того, что происходит в случайных сетях. При увеличении f диаметр остается неизменным даже при уровне ошибки 5%. Эта надежность обусловлена наличием концентраторов в сети. Пока концентраторы не работают со сбоями, взаимосвязь сети остается нетронутой.
Когда удаление узла сочетается с другими процессами, топология сети может резко измениться. Чтобы проиллюстрировать это, рассмотрим модель BA. На каждом шаге добавляйте в сеть новый узел с m связями, а также удаляйте узел с вероятностью r. Это приводит к различным сетям в зависимости от m и r. [3]
Когда цель состоит в том, чтобы разрушить сеть, имеет смысл нацеливаться на определенные узлы, а не удалять их случайным образом. Это тот случай, например, когда кто-то борется с бактерией или хочет ликвидировать криминальную сеть. Целевое удаление может происходить в соответствии со многими стратегиями, наиболее эффективными из которых являются нацеливание на узлы наивысшей степени и нацеливание на узлы с наивысшей промежуточной центральностью. [4] Эффективность стратегии может быть измерена либо по тому, как изменяется диаметр сети, либо по тому, как изменяется размер самых больших компонентов в течение периодов удаления. [5]