Навігація
Головна
ПОСЛУГИ
Авторизація/Реєстрація
Реклама на сайті
 
Головна arrow Інформатика arrow Моделирование сложных сетей
< Попередня   ЗМІСТ   Наступна >

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

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

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

  • - входная степень узла - количество ребер графа, которые входят в узел;
  • - выходная степень узла - количество ребер графа, которые выходят из узла;
  • - расстояние от одного узла до других;
  • - эксцентричность (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.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Банківська справа
БЖД
Бухоблік та Аудит
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Нерухомість
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
РПС
Соціологія
Статистика
Страхова справа
Техніка
Товарознавство
Туризм
Філософія
Фінанси
Інші