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

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

Посредничество (betweenees) - это параметр, показывающий, сколько кратчайших путей проходит через узел. Эта характеристика отражает роль данного узла в установлении связей в сети. Узлы с наибольшим посредничеством играют главную роль в установлении связей между другими узлами в сети. Посредничество Ьт узла т определяется по формуле:

где В(i, j) - общее количество кратчайших путей между узлами i и j, В(i,т,j]) - количество кратчайших путей между узлами i и j, проходящих через узел т .

Эластичность сети

Свойство эластичности сетей относится к распределению расстояний между узлами при изъятии отдельных узлов (толерантность к атакам).

Эластичность сети зависит от ее связности, т.е. существовании путей между парами узлов. Если узел будет изъят из сети, типичная длина этих путей увеличится.

Albert R., Jeong H., Barabasi A. Error and attack tolerance of complex networks. Nature, 2000. - Vol. 406. - pp. 378-382.

При исследовании атак на вебсерверы изучался эффект изъятии узлов сети, представляющей собой подмножество веб-пространства из 326000 страниц и около 1,5 млрд. гиперссылок. Для этой сети были определены параметры входного и выходного распределения степеней:

где

и

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

Примеры вычисления харакетеристик сетей

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

Рассматриваемые далее шесть примеров сетей будем обозначать номерами № 1 - № 6 (рис. 1.1.3).

- Примеры простейших сетей: сеть № 5 - так называемый орграф (направленный граф), сеть № 6 - сеть с весами связей (указаны цифры на связях)

№5 № 6

Рис. 1.1.3 - Примеры простейших сетей: сеть № 5 - так называемый орграф (направленный граф), сеть № 6 - сеть с весами связей (указаны цифры на связях)

Матрицы смежности сетей, изображенных на рис. 4 приведены ниже:

Для сети № 5 матрица смежности А не симметрична. Элементы матрицы смежности А6 - это веса связей.

Распределение узлов по их степеням Р(к) приведено на рис. 1.1.4, где также приведена такая характеристика сетей, как среднее число связей на один узел:

которая вычисляется как отношение всех связей в сети к числу узлов и, одновременно, как среднее дискретной переменной кi с функцией распределения Р( кi).

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

Рассмотрим, например, узлы 2 и 3 сети № 4. Для узла № 2 жирными линиями обозначены вилки (их три) и треугольники (он один).

Как можно убедиться, для второго узла имеются три вилки и один треугольник, поэтому С2 = 1/3.

Для третьего узла три вилки и два треугольника -

Еще одна сеть представлена на рис. 1.1.4.

Варианты сети

Рис. 1.1.4 - Варианты сети

Коэффициент кластеризации всей сети вычисляется по формуле:

С - коэффициент кластеризации сети.

В табл. 1.1.1 приведены коэффициенты кластеризации для всех

узлов сетей №1, № 2, № 3 и № 4, а также коэффициент кластеризации всей сети С. На рис. 1.1.5. Представлено распределение узлов по степеням для сетей, изображенных на рис. 1.1.3.

Как видно, наибольший коэффициент кластеризации имеет сеть № 2, у нее, в среднем, наибольшее число соседей каждого узла соединены между собой. Наименьший коэффициент кластеризации имеет сеть № 3.

Таблица 1.1.1

Коэффициенты кластеризации

Сеть

С1

С2

Сз

С4

С5

С6

С7

№ 1

1/3

0

1

1

1

7/12

№ 2

2/3

1

1

1

2/3

10/12

№ 3

0

1/6

2/3

2/3

1/3

0

2/3

11/36

№ 4

0

1/3

2/3

2/3

1

2/3

8/15

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

где суммирование ведется по всем узлам.

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

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

Рис. 1.1.5. Распределение узлов по степеням для рассматриваемых сетей

Кроме определения коэффициента кластеризации всей сети (1.1.7) и (1.1.8) в литературе встречается еще одно, близкое, но не тождественно определение, иногда называемое транзитивностью - Т :

Т - транзитивность, характеристика, близкая к коэффициенту кластеризации.

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

Для сравнения ниже приведены значения коэффициента кластеризации и транзитивности для сетей № 1, № 2, № 3 и № 4 - Табл. 1.1.2.

Таблица 1.1.2.

Коэффициенты кластеризации

Еще одной важной характеристикой сетей является среднее минимальное расстояние между их узлами:

где 1 - наименьшее число шагов от узла 1 к узлу ]. При этом каждый шаг соответствует единичному расстоянию.

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

В случае арифметического среднего (1.1.11) наибольший вклад будут давать наиболее длинные пути (из наиболее коротких), в случае же гармонического среднего -наиболее короткие. Если в сети имеются изолированные узлы, добраться до которых невозможно и для которых естественно считать llj =°°, определение минимального среднего расстояния как арифметического среднего перестает быть информативным, поскольку даже при наличии одного такого изолированного узла l = = °° . В такой ситуации удобно пользоваться определением среднего минимального расстояния как среднего гармонического - 1 . Иногда величину обратную 1 обозначают E = 1 /1 и называют действенность (efficiency).

Наименьшее число шагов lj от узла i к узлу j может быть записано в виде матрицы SP (short path). Численные значения этой матрицы для сетей № 1 - № 6 равны:

Отметим, что матрица (5) (для направленной сети) содержит бесконечные элементы, например l21 (5) = ∞ (сравните с l21 (4) = 1). Это, конечно, означает (см. рис. сети № 5), что от узла 2 невозможно дойти до узла 1.

В сети с весами при подсчете lij каждый шаг по связи умножается на ее вес, так что суммируется не просто число шагов (связей), а их веса. Именно с этим связано то, что кратчайший путь в сети № 6 между узлами 3 и 4 включает в себя два шага с весами 4 и 1, а не один шаг с весом 1.

Средние значения кратчайших путей (1.1.11) для рассматриваемых сетей равны:

Гармоническое среднее:

Еще одной важной характеристикой сети является так называемое посредничество (betweenness). В таблице 1.1.3 приведены численные значения посредничества для всех узлов сетей № 1 - № 6.

Таблица. 1.1.3.

Значения посредничества для сетей № 1 - № 6.

№ сети

Узел

B1

B2

Вз

В4

В5

В6

1

4

0

0

0

2

1

0

0

1

3

0

10

4/3

2

4/3

4/3

4

0

6

2

0

2

5

0

2

0

0

0

6

0

6

0

0

8

Напомним, что при вычислении посредничества в сети с весом, кратчайший путь рассчитывается с учетом веса связей.

Кроме основной характеристики сети -распределения степени узлов по связям - Р(к), см. рис. 1.1.2 вводится также распределение концов связей - Рпп (к):

Это распределение называют также распределением степеней ближайших соседей (degree distribution of thenearest neighbor), откуда и берется обозначение Pnn (к). На простом примере сети № 1 легко убедиться, что (1.1.13) действительно дает распределение концов связей. Для сети №1 имеем восемь концов, т.е. вероятность попадания одного конца связи на узел равна 1/8 . У узла 1 одна связь,

поэтому

У каждого узлов 3 и 4 - 2/8, т.е.

2•2/8=1/2,

таким образом

и для узла 1 - 31/8, т.е.

С другой стороны эти же значения сразу получаются из (1.1.13), например, для первого узла

и аналогично для других.

Качественно выражение для

(1.1.13) можно пояснить так. Вероятность попадания случайно выбранной связи на узлы с к связями пропорционально числу всех связей таких узлов

где N - полное число узлов в сети. С учетом того, что

Нормировочная константа равна 1 / ^ к} , откуда и следует (1.1.13).

Распределение

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

Для некоррелированной сети знание распределения концов Рпп (к) позволяет найти вероятность соединения узлов со степенями

Т.к. вероятность того, что связь "воткнется" в узел со степенью к равна

вероятность того, что одновременно она "воткнется" и в связь со степенью к равна произведению

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

Первые соседи узла, в свою очередь, имеют своих соседей, которых логично назвать вторыми ближайшими к исходному узлу соседями. Если первый сосед имеет степень к , то у него к — 1 соседей (одна из связей "ушла" к исходному узлу).

Число первых соседей со степенью к для всех узлов равно

поэтому число всех вторых соседей равно:

Отношение среднего числа вторых соседей к первым:

называют коэффициентом ветвления (branching coefficient), он характеризует степень "размножения" связей по мере удаления от узла.

B -коэффициент ветвления

Коэффициент ветвления можно получить и из таких соображений. Вероятность Рпп (к ) можно трактовать как вероятность 0 (к — 1) того, что связь от некоторого выбранного узла А войдет в узел В с к — 1 связями, так, что узел В будет иметь в сумме к связей:

Тогда среднее число выходящих из узла В связей (без учета связи с узлом А ) равно:

Последнее равенство справедливо при

Зная коэффициент ветвления В (1.1.18) легко вычислить среднее число следующих (третьих, четвертых и т.д.) соседей:

Выражение для среднего числа m — ных соседей позволяет получить ответ на очень важный вопрос -существует ли в сети так называемый гигантский кластер (Giant Connected Cluster или Giant Connected Component).

GC - Giant Cluster -гигантский кластер

Т.е. существует ли сети кластер (связанная между собой часть узлов), включающая в себя число узлов порядка всего числа узлов в сети. При вычислении все более дальних и дальних соседей (т >> 1) согласно (1.1.22) возможны два сценария - при

и при

Во втором случае (предполагается, что N >> 1) из (1.1.21) следует:

а строгое равенство, конечно, имеет место в пределе N ®¥ . Из (1.1.23) сразу же следует, что при г2 > г, т.е. при

в сети существует бесконечный кластер.

Неравенство (1.1.24) называется критерий Моллоя-Рида, его часто записываю в таком виде

Критерий Моллоя-Рида

Таким образом, согласно (1.1.25) гигантский кластер существует, если число вторых соседей больше чем среднее число выходящих из узла связей.

Существование гигантского кластера означает также, что выбирая как угодно удаленные друг от друга узлы мы с ненулевой вероятностью сможем пройти по сети от одного узла к другому. Именно поэтому о тех значениях параметров, при которых (^к2^ достигает значения 2^к}, говорят как о

пороге протекания. Значение порога протекания рс при этом равна:

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