Характеристики сложных сетей

Параметры узлов сети

Для отдельных узлов выделяют следующие параметры:

• - входная степень узла - количество ребер графа, которые входят в узел;
• - выходная степень узла - количество ребер графа, которые выходят из узла;
• - расстояние от одного узла до других;
• - эксцентричность (eccentricity) - наибольшее из минимальных расстояний от данного узла до других;
• - посредничество (betweenness), показывающее, сколько кратчайших путей проходит через данный

узел;

- центральность - общее количество связей данного узла по отношению к другим.

Распределение степеней узлов

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

Существует несколько актуальных задач исследования сложных сетей, среди которых можно выделить следующие основные:

• • определение клик в сети. Клики - это подгруппы или кластеры, в которых узлы связаны между собой сильнее, чем с членами других клик;
• • выделение компонент (частей сети), которые не связаны между собой, узлы которых связаны внутри этих компонент;
• • нахождение блоков и перемычек. Узел называется перемычкой, если при его изъятии сеть распадается на несвязанные части;
• • выделение группировок - групп эквивалентных узлов (которые имеют максимально похожие профили связей).

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

ER - сеть Эрдеша-Реньи, так называемый случайный граф

SF - сеть scale free, безмасштабная сеть

Для больших (N"1) сетей со случайной структурой одной из самых важных характеристик является

функция распределения Р(к) по степеням узлов. Наибольшая часть реальных СЫ похожи (близки) к следующим трем:

1. Случайная сеть или сеть Эрдеша-Реньи (ЕR)

Таким образом, в случае сети

функция распределения есть функция Пуассона.

2. Сеть с экспоненциальным распределением

3. Сеть со степенным распределением (Scale-Free) P(к) = k~r /ζ(γ ) ~ к γ где дзета-функция Римана.

В двойном логарифмическом масштабе эти распределения имеют вид, представленный на рис. 1.1.2.

Рис. 1.1.2 - Плотности распределения Р(к) в двойном логарифмическом масштабе: а - распределение Пуассона (сеть ЕЕ); б - экспоненциальное распределение; в – степенное распределение

Сеть Эрдеша-Реньи можно построить, распределив случайным образом М связей между N узлами. Тогда с одной стороны (к) = 2М / N, а с другой (к) = пМ, где т -

вероятность соединения узлов. При N→ ∞ и т →∞ распределение степени узлов является Пуассоновым.

К сетям со степенным распределением относятся сетями Барабаши-Альберта (ВА), для

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

Существуют процедуры построения сетей иного типа, когда к упорядоченной структуре добавляются случайные связи. Наиболее известный пример такой сети - так называемая сеть малого мира (Small World - SW).

Barabäsi A.L., Albert R. Emergence of scaling in random networks. Science, 1999. - Vol. 286 (5439): 509-512.