close

Вход

Забыли?

вход по аккаунту

?

Топология и устойчивость локально-мировых сетей.

код для вставкиСкачать
Программные продукты и системы
№ 4, 2009 г.
ТОПОЛОГИЯ И УСТОЙЧИВОСТЬ ЛОКАЛЬНО-МИРОВЫХ СЕТЕЙ
Б.Р. Гаджиев, д.ф.-м.н.; Е.Ю. Гибина; Т.Б. Прогулова, к.т.н.; Д.П. Щетинина
(Международный университет природы, общества и человека, г. Дубна, gadjiev@uni-dubna.ru)
Исследованы топология и устойчивость локально-мировых сетей. Рассмотрены различные стратегии формирования локального мира. Определены распределения степеней и характер корреляций в рассматриваемых сетях. Обсуждается устойчивость локально-мировых сетей к случайным отказам и направленным атакам.
Ключевые слова: сложные сети, масштабно-инвариантные сети, локально-мировые сети, степенное распределение, коррелированные сети, случайные отказы, направленные атаки, устойчивость сетей.
Общая теория систем начинается с определения системы как комплекса взаимодействующих
компонентов, формирующих организованное целое. Такое определение естественным образом
приводит к удобному и эффективному моделированию самых разнообразных систем (физических,
как природных, так и искусственных, биологических, социальных) на языке теории графов (сетей),
когда компоненты суть вершины, а их взаимодействия – связывающие эти вершины ребра.
В последнее десятилетие теория сложных сетей проявила себя как один из универсальных методов исследования сложных систем. Сети – всѐ
вокруг нас, и мы сами как индивидуумы являемся
элементами сети социальных отношений различных видов, а как биологические системы – результатом сети биохимических реакций. Сети могут
быть материальными объектами в евклидовом
пространстве (энергетические сети, Интернет, автомагистрали, метро или нейронные сети) или же
объектами, определенными в абстрактном пространстве (WWW, сети знакомств или сотрудничества между людьми).
Существенные достижения в исследовании
сложных сетей обусловлены несколькими обстоятельствами. Во-первых, компьютеризация сбора
данных во всех сферах привела к появлению
больших БД по топологии разнообразных сетей
реального мира. Во-вторых, расширившиеся вычислительные возможности позволили изучать сети, содержащие миллионы вершин, и исследовать
аспекты, которые не могли быть рассмотрены
прежде. В-третьих, медленное, но значимое стирание границ между дисциплинами открыло исследователям из разных предметных областей
доступ к разнообразным БД, что позволило обнаружить универсальные свойства сложных сетей.
Изучение структуры сетей реального мира показало, что сложные сети разделяются по форме
распределения степеней на случайные (сети Эрдеша–Реньи), мало-мировые (сети Ваттса–Строгатца) и масштабно-инвариантные (сети Барабаси–Альберт (БА)) [1]. Масштабно-инвариантные
сети характеризуются распределением степеней,
которое
подчиняется
степенному
закону
– показатель степени. В отличие
p(k )~ k , где
от случайных и мало-мировых масштабно-инвариантные сети имеют сильно неоднородную струк-
туру. Анализ топологии сетей реального мира показал, что многие из искусственных систем характеризуются степенным распределением.
Для объяснения феномена масштабно-инвариантных сетей БА была предложена модель растущих сетей, ставшая в теории сложных сетей базовой. В основе БА-модели лежат два механизма:
рост и предпочтительное присоединение, а именно, сети растут за счет добавления новых вершин;
вновь поступившая в сеть вершина соединяется с
вершинами, уже присутствующими в сети, в соответствии с принципом предпочтительного присоединения (то есть вероятность соединения с вершиной i пропорциональна ее степени ki:
(k i ) k i / k j ). Модель БА приводит к сети,
j
распределение степеней которой подчиняется степенному закону p(k ) 2m2k 3 . Несмотря на то,
что БА-модель объясняет основные особенности
большей части сетей реального мира (степенной
характер распределения степеней, динамику роста
степеней отдельных узлов и т.д.), строго фиксированное значение показателя =3 является существенным недостатком модели. Так, анализ сетей
реального мира показал, что значение показателя
3 [1, 2]. Очевидно, что эта особенстепени 1
ность связана с присутствием дополнительных
механизмов роста сетей. Обобщенная модель
предполагает следующие механизмы роста сети.
1. Добавление ребер: с вероятностью r
(0 r 1) в сеть добавляется m новых ребер, для каждого из которых одна из вершин выбирается случайным образом, а другая – с вероятностью
(k i ) k i / k j .
j
2. Добавление вершин: с вероятностью 1–r в
сеть поступает новая вершина, которая соединяется с вершинами, уже присутствующими в сети,
m ребрами опять-таки в соответствии с принципом предпочтительного присоединения.
Несколько позже был предложен еще целый
набор дополнительных механизмов, которые могут затрагивать как собственно процесс роста (пересвязывание ребер, слияние узлов и т.д.), так и
принцип предпочтительного присоединения (нелинейное предпочтительное присоединение, ускоренный рост, старение узлов и т.д.) [1, 2]. Иссле51
Программные продукты и системы
дования показали, что все эти механизмы приводят к сетям с нарушенной масштабно-инвариантной топологией.
При дальнейшем изучении сетей реального
мира выявилось, что может нарушаться и принцип
глобального действия предпочтительного присоединения. Так, исследования Международной торговой сети (WTW) показали, что при росте сети
механизм предпочтительного присоединения действует, но не глобально, а локально [3]. Последнее
означает, что при добавлении в сеть новой вершины она может соединиться только с вершинами
некоторой подсети (например, не с произвольными торговыми организациями, а с расположенными в определенном регионе). Такую подсеть в
дальнейшем и будем называть локальным миром
добавляемой вершины.
В данной работе представлены результаты исследования локально-мировых сетей.
Модели формирования
растущих локально-мировых сетей
Определим алгоритм формирования растущих
локально-мировых сетей как дальнейшее обобщение модели масштабно-инвариантой сети БА. При
таком подходе процесс формирования локальномировой растущей сети можно описать следующим образом.
1. Рост. Генерация сети начинается с небольшого числа m0 изолированных узлов, в каждый
момент t к сети добавляется новый узел, который
должен быть связан с уже существующими вершинами m ребрами.
2. Локальное предпочтительное присоединение. В каждый момент t перед соединением нового узла с m узлами, уже присутствующими в сети,
формируется локальный мир. Ребра добавляются
между новой вершиной и m вершинами локального мира. Таким образом, вероятность связывания
некоторого узла i локального мира с новым узлом
ki
M
отобразим как local (i)
.
m0 t
k
j local j
3. Формирование локального мира.
Правило 1. Локальный мир образуют случайно выбранная вершина i и ее 1-й, 2-й, …, n-й соседи (то есть вершины, расстояние до которых от i-й
вершины меньше либо равно n); n фиксированное
и является параметром модели. Фактически n
представляет собой радиус локального мира.
Правило 2. M узлов локального мира выбираются в сети случайным образом. Здесь M фиксированное и является параметром модели.
Анализ топологии и характера корреляций
локально-мировых сетей
Основной топологической характеристикой
графа G является распределение степеней p(k),
52
№ 4, 2009 г.
где p(k) определяется как вероятность того, что
случайно выбранная вершина имеет степень k,
или, что эквивалентно, как доля вершин графа,
имеющих степень k.
Характер корреляций степеней вершин сети
удобно анализировать с помощью функции
K nn (k ) , определяющей зависимость средней степени ближайших соседей вершины от ее степени
k [4]. Средняя степень ближайших соседей вершины степени k определяется как K nn k
k P k k . Здесь P k k
– вероятность того,
k
что ребро, выходящее из вершины степени k, наEkk
правлено к вершине степени k . P k k
,
kN k
где N k – число вершин степени k; Ekk – симметричная матрица, элементы которой равны количеству ребер между вершинами степени k и k для
k k и удвоенному числу ребер, связывающих
вершины одной и той же степени ( k k ). Если
зависимость K nn (k ) – монотонно растущая функция, сеть является ассортативной (преимущественно соединены вершины, имеющие близкие
степени); если K nn (k ) – монотонно убывающая
функция, сеть дисассортативна (вершины малой
степени в основном связаны с вершинами большой степени и наоборот). Если K nn (k ) не зависит
от k, сеть некоррелированная.
В соответствии с описанными алгоритмами
сгенерированы локально-мировые сети при различных способах формирования локального мира.
Были построены распределения степеней, и для
выявления наличия и характера корреляций в сети
вычислены зависимости средней степени ближайших соседей вершины от ее степени K nn (k ) .
На рисунке 1 приведены графики распределений степеней вершин сгенерированных локальномировых сетей, во всех трех случаях m m0 3 и
размер сети N ~104 . На рисунках 1а и 1b показано,
соответственно, распределение степеней для сетей, сгенерированных по правилу 1 при n=1 (локальный мир сформирован случайно выбранной
вершиной и ее первыми соседями) и при n=2
(вершина и ее первые и вторые соседи). На рисунке 1с представлено распределение степеней для
сети со случайным выбором локального мира
(правило 2) при M=3.
Значения показателей степени определялись
с помощью метода максимального правдоподобия
и равны 4.9 и 4.5 для распределений a, b соответственно. Как известно, значения >3 характерны
для сетей с суперхабами, то есть практически все
вершины сети оказываются связанными с одной
или несколькими вершинами, имеющими очень
большую степень [1]. Такие сети имеют резко вы-
Программные продукты и системы
№ 4, 2009 г.
1
0,1
1
0,1
P
P
P
1
0,1
0,01
a
0,001
0,01
b
0,01
c
0,001
0,001
0,0001
0,0001
0,00001
0,00001
0,0001
1
10
100
1000
10000 100000
1
10
100
k
1000 10000 100000
0,00001
k
a
1
k
10
b
100
c
Формирование локального мира в соответствии
с правилом 1 при n=1
с правилом 1 при n=2
с правилом 2 при M=m=3
Рис. 1. Распределение степеней P(k) для локально-мировых сетей, m=m0=3, N=10 000
раженный дисассортативный характер. Действительно, зависимости K nn (k ) для сгенерированных
сетей, представленные на рисунках 2a и 2b, имеют
убывающий характер, то есть дисассортативны.
На рисунке 1с показано, что локально-мировая сеть при случайном выборе локального мира и
при M=m=3 характеризуется экспоненциальным
распределением степеней. Соответствующая этой
сети зависимость K nn (k ) (рис. 2c) имеет растущий характер, следовательно, эта сеть является
ассортативной.
Анализ локально-мировых сетей, сгенерированных в соответствии с правилом 1, показал, что
при увеличении радиуса локального мира n топология сети практически не меняется. В таких сетях
всегда присутствуют суперхабы, и эти сети всегда
дисассортативны.
Более гибкую структуру имеют сети со случайным выбором локального мира. На рисунке 3
представлено распределение степеней для такой
сети при M>>m. Размер сети N~104, m=m0=3,
M=500. Сеть имеет масштабно-инвариантный характер,
=2.9. Соответствующая зависимость
K nn (k ) показывает, что сеть некоррелированная.
Таким образом, с ростом M происходит фазовый
переход с изменением топологии сети от экспоненциальной к масштабно-инвариантной. Одно-
временно это сопровождается изменением характера корреляций: сети трансформируются от ассортативных к некоррелированным.
Исследование устойчивости локально-мировых
сетей к случайным отказам
и направленным атакам
Обсудим топологические аспекты устойчивости сложных сетей. Рассмотрим произвольный
связанный граф с N вершинами. Предположим,
что из графа удаляется доля вершин p. Необходимо выяснить, является ли полученный подграф
связным, чтобы определить, как связность подграфа зависит от доли удаленных вершин p. Оказывается, для широкого класса сетей существует
порог pc N , такой, что при p pc N подграф
будет оставаться связным, тогда как при p pc N
происходит его расщепление.
Для анализа устойчивости принято рассматривать два типа воздействий на сети: случайные
отказы узлов и направленные атаки на узлы. В
первом случае в сети случайным образом удаляются часть вершин p. Во втором из сети удаляются вершины со степенью, большей некоторой заданной степени kcutof . Далее строятся зависимости доли вершин сети, принадлежащих наибольшей связной компоненте, от доли удаленных вер100
1000
10
Knn
Knn
Knn
1000
1
1
1
100
k
a
10000
1
100
k
10000
1
1
k 10
b
100
c
Формирование локального мира в соответствии
с правилом 1 при n=1
с правилом 1 при n=2
с правилом 2 при M=m=3
Рис. 2. Зависимость K nn (k ) для локально-мировых сетей, m=m0=3, N=10 000
53
Программные продукты и системы
№ 4, 2009 г.
P
1
1
0,1
0,8
0,01
a
0,0001
0,00001
1
a
10
k
100
1000
распределение степеней P(k)
Knn
100
b
10
доля вершин, принадлежащих самой
большой компоненте
0,6
0,001
1
0,4
0,2
0,8
0
0
0,01
0,02
0,03
0,04
0,6
0,4
0,2
0
0
0,2
0,4
0,6
0,8
доля удаленных вершин
1
b
1
10
k
100
1000
зависимость Knn (k)
Рис. 3. Топология локально-мировой сети,
сгенерированной в соответствии с правилом 2
при m=m0=3, N=10 000, M=500
шин (при изменениях p и kcutof соответственно).
Определяется порог – значение доли удаленных
вершин, при котором сеть рассыпается [5].
На рисунке 4 приведены результаты исследования устойчивости сетей к направленным атакам
для различных способов формирования локальномировых сетей. Для сравнения на рисунке приведены также результаты анализа устойчивости к
направленным атакам для аналогичной сети БА.
Видно, что наиболее устойчивыми к направленным атакам являются локально-мировые сети
со случайным выбором локального мира при
M=m=3, при этом пороговое значение pc=0.57.
Наименее устойчивыми в этом случае будут локально-мировые сети, в которых локальный мир
формируется по принципу соседства. Они имеют
очень малые пороговые значения pc=0.02, pc=0.03
соответственно, являясь более неустойчивыми по
отношению к направленным атакам. Это непосредственно связано с топологией данных сетей.
Результаты устойчивости рассматриваемых
сетей к случайным отказам показывают, что сети,
сгенерированные в соответствии с описанными
правилами, ведут себя практически одинаково.
Пороговое значение pc=0.9, что означает достаточно большую устойчивость этих сетей к такого
рода воздействиям.
Подводя итог, можно отметить, что в статье
рассмотрены различные механизмы формирования локально-мировых сетей, предложены соответствующие алгоритмы для их генерации, проведены исследования топологии, характера корреляций и устойчивости этих сетей к случайным отказам и направленным атакам.
Кроме того, показано: если локальный мир
формируется соседями случайно выбранного узла,
54
формирование локального мира в соответствии с
правилом 1 при n=1
в соответствии с правилом 1 при n=2
в соответствии с правилом 2 при M = m =3
модель БА
Рис. 4. Устойчивость к направленным атакам
это приводит к сети с суперхабами, которые дисассортативны и наименее устойчивы к направленным атакам. Сети со случайным выбором локального мира имеют более гибкую структуру.
Если размер локального мира совпадает с числом
ребер, поступающих в сеть на каждом временном
шаге, сеть имеет экспоненциальную топологию. С
увеличением размера локального мира происходит топологический фазовый переход, в результате которого топология сети становится масштабно-инвариантной. Сети с экспоненциальной топологией оказываются наиболее устойчивыми к направленным атакам.
По отношению к случайным отказам все рассмотренные сети ведут себя практически одинаково устойчиво.
Таким образом, масштабно-инвариантные сети уязвимы к направленным атакам и достаточно
устойчивы к случайным отказам.
Необходимо подчеркнуть, что важнейшими
примерами локально-мировых сетей являются Интернет и WTW.
Литература
1. Albert R., Barabási A.-L. Statistical Mechanics of
Complex Networks // Rev. Mod. Phys. 2002. Vol. 74, pp. 43–97.
2. Boccaletti S., Latora V., Morena Y., Chavez M. Complex
networks: Structure and dynamics // Physics Reports. 2006. Vol.
424, pp. 175–308.
3. Li X., Jin Yu Ying, Chen G. Complexity and
Synchronization of the World trade Web // Physica A. Vol. 328, pp.
287–296.
4. Pastor-Satorras R., Vespignani A. Evolution and Structure
of the Internet: a statistical physics approach. – Cambridge
University Press, 2004.
5. Гаджиев Б.Р., Прогулова Т.Б., Щетинина Д.П. Статическая устойчивость ассортативных и дисассортативных сетей
/ Математика. Компьютер. Образование: сб. научн. тр. Т. 2; под
ред. Г.Ю. Ризниченко. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика», 2007. С 22–29.
Документ
Категория
Без категории
Просмотров
6
Размер файла
2 053 Кб
Теги
локального, мировые, сетей, устойчивость, топология
1/--страниц
Пожаловаться на содержимое документа