Материал: Теория сетевых войн. Живучесть атакуемых сетей. учеб. пособие. Остапенко А.Г., Калашников А.О

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

= ( ) ∑ , (1.2)

где сумма учитывает все пары узлов. Эта характеристика отражает эффективность сети при пересылке информации между узлами (предполагается, что эффективность в пересылке информации между двумя узлами i и j обратно пропорциональна расстоянию между ними).

Обратная величина глобальной эффективности — среднее

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

1.2.5. Коэффициент кластерности

Д. Уаттс (D. Watts) и С. Строгатц (S. Strogatz) в 1998 году определили такой параметр сетей, как коэффициент кластерности [69], который соответствует уровню связности узлов в сети. Этот коэффициент характеризует тенденцию к

16

образованию групп взаимосвязанных узлов, так называемых клик (clique). Кроме того, для конкретного узла коэффициент кластерности показывает, сколько ближайших соседей данного узла являются также ближайшими соседями друг для друга.

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

то количество ребер между ними составляло бы ( −1),

т.е. это число, которое соответствует максимально возможному количеству ребер, которыми могли бы соединяться ближайшие соседи выбранного узла. Отношение реального количества ребер, которые соединяют ближайших соседей данного узла, к максимально возможному (такому, при котором все ближайшие соседи данного узла были бы соединены непосредственно друг с другом) называется коэффициентом кластерности узла i – C(i) . Естественно, эта величина не превышает единицы.

Существует еще один способ вычисления коэффициента кластерности (транзитивности), базирующийся на такой формуле:

3-цикл определяется при этом как множество трех узлов с ребрами между каждой парой узлов. Связная 3-компонента — множество, состоящее из трех узлов, в котором каждый узел достижим из другого узла, непосредственно или опосредованно. Таким образом, в 3-компоненте центральный узел должен быть инцидентен двум другим. Множитель 3 введен из учета вариантов различных 3-компонент для каждого

17

3-цикла, этот множитель обеспечивает выполнение неравенства 0 C 1 . Тогда мы получаем:

где −элементы матрицы смежности А, соответствующей сети, сумма берется по всем компонентам различных узлов i, j и k только один раз.

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

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

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

Рассмотренный ниже феномен «малых миров» непосредственно связан с уровнем кластерности сети.

1.2.6. Посредничество

Значение узла для сети тем больше, чем в большем количестве путей он задействован. Поэтому, полагая, что обмен данными происходит по кратчайшим путям между двумя вершинами, можно измерить количественно значение узла с точки зрения посредничества (betweenness), определяемого количеством кратчайших путей, проходящих

18

через узел. Эта характеристика отражает роль данного узла в установлении связей в сети. Узлы с наибольшим посредничеством играют главную роль в установлении связей между другими узлами в сети. Посредничество bm узла m определяется по формуле:

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

посредничества.

Преобладание центрального узла будет равно 0 для клики и 1 для звезды, в которой центральный узел входит во все пути.

1.2.7. Эластичность и уязвимость сети

Противоположные свойства эластичности и уязвимости сетей относятся к распределению расстояний между узлами при изъятии отдельных узлов. Эластичность сети зависит от ее связности, т.е. существовании путей между парами узлов. Если узел будет изъят из сети, типичная длина этих путей увеличится. Если этот процесс продолжать достаточно долго, сеть перестанет быть связной. Р. Альберт (Reka Albert) из

19

университета штата Пенсильвания (США) при исследовании атак на интернет-серверы изучала эффекты, возникающие при изъятии узла из сети, представляющей собой подмножество

WWW из 326000 страниц [57].

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

Один из способов найти критичные компоненты сети — поиск самых уязвимых узлов [64]. Если производительность сети связана с ее глобальной эффективностью, уязвимость узла может быть определена как спад производительности в случае

где Е— глобальная эффективность исходной сети, а Ei — глобальная эффективность после удаления узла i и всех смежных ему ребер.

Упорядоченное распределение узлов относительно их уязвимостей связано со структурой всей сети. Таким образом, наиболее уязвимый узел занимает наивысшую позицию в сетевой иерархии. Мера уязвимости сети — максимальная уязвимость среди всех ее узлов:

1.2.8.Коэффициент элитарности

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

20