PERCOLATION CONTROLED IN LARGE-SCALE NETWORK

Full Text

Введение. Большие (сложные) сети характеризуются не просто большим числом узлов, топологией и свойствами каждого узла. В больших сетях на первый план выходят исследования их совокупных свойств и ряд вытекающих из них статистических феноменов в частности: - статистические характеристики случайных операционных сред, образованных сетью, - пути, проложенные в сетях по выбранным критериям качества, - образование кластеров узлов (объектов), связанных по определенным условиям, - статистические распределения узлов, связей, кластеров и трафиков. Один из развиваемых подходов к исследованию больших сетей связан с моделью «протекания» по их ребрам информационного трафика, безопасного информационного трафика, транспортного трафика, потоков обслуживания и т.п. Теория перколяции решает задачи анализа больших сетей в рамках этой модели. Название возникло в связи с тем, что ряд первых работ в этом направлении был посвящен процессам просачивания (протекания) жидкостей или газов через случайную пористую среду [1-2]. Постановка задачи теории перколяции следующая. Имеется решетка из связей или матрица, случайная часть ячеек которых K - «черная», проводящая поток, а остальная часть - «белая», не проводящая поток. Необходимо найти минимальную концентрацию «черных» ячеек, при которой имеется сквозной путь по черным связям через всю матрицу в заданном направлении, иными словами, такую концентрацию Кп, при которой вся матрица в целом проводит. При достижении проводимости свойства такой сети качественно и скачком меняются: образуется безопасный путь ( или он разрушается), возникает (или затухает) эпидемия, воссоздается разрушенная социальная сеть, возникает пробка в дорожном движении и т.п. Концентрация К -это доля черных узлов при случайно-однородном заполнении решетки или матрицы является вероятностью наличия черного объекта в ячейке матрицы [3]. Поэтому далее в подрисуночных подписях вместе с выражением «вероятность наличия объекта в ячейке матрицы» употребляется более краткое выражение «доля примеси или концентрация». Для начала примем, что вероятность нахождения объекта в ячейке матрицы является величиной постоянной по всей матрице. В дальнейшем мы откажемся от этого предположения в пользу более общего. Таким образом, случайная матрица - модель случайной операционной среды большой сети: либо информационно - вычислительной, либо сети обслуживания, либо социальной. При этом имитируется в общем случае ячеистая топология сети, хотя имитация формы и размеров ячейки топологии реальной сети не требуется. Главное, что наша модель имитирует связность узлов - объектов сети. Объекты сети связаны по определенным условиям, если соприкасаются сторонами квадрата ячейки матрицы, в которых они находятся. По мере роста концентрации «черных» в матрице образуются и растут кластеры связанных «черных» объектов - узлов. Статистическое моделирование на таких случайных матрицах позволяет обнаружить и исследовать статистический феномен порога перколяции как «пробоя» матрицы проводящим перколяционным кластером при достижении вероятности нахождения объекта в ячейке значения Кп [1]. «Инфокоммуникационные технологии» Том 11, № 1, 2013 54 Мостовой Я.А. Применительно к задаче исследования больших безопасных сетей рассматриваемых объектов использование порога стохастической перколяции для определения потребного числа объектов в сети для ее «пробоя» приводит к их избыточному количеству, как показано в [6]. Там же исследован другой статистический феномен больших сетей - наличие устойчивого (робастного) значения вероятности нахождения в ячейке матрицы объекта, при котором число образовавшихся кластеров на матрице имеет максимум. При дальнейшем увеличении этой вероятности кластеры объектов растут, сливаются, и их суммарное число падает. Значение концентрации - вероятности наличия объекта в ячейке матрицы для этой точки составляет ~ 0,25, что более чем в два раза меньше, чем для стохастической перколяции. При таком значении концентрации стохастическая перколяция отсутствует. Однако в матрице, моделирующей случайную среду передачи, уже в этом случае будут отсутствовать пустые строки и столбцы, и это означает, что покрытие заданной зоны обслуживания будет проведено. Дальнейшего снижения концентрации числа объектов с заданными свойствами в сети, необходимого для реализации требуемых функций, можно достичь, используя двухфазную операцию создания программируемого перколяционного пути сети для чего нами вводится понятие управляемой перколяции. Результаты статистического моделирования больших сетей на квадратных матрицах Теория перколяции отвечат на вопрос: «Какова должна быть вероятность нахождения НС в ячейке К, чтобы возник перколяционный кластер, соединяющий верхнюю и нижнюю часть матрицы?» Эта теория дает метод моделирования важных прикладных задач, так как описывает широкий класс явлений, которые называются критическими и характеризуются движением потока через случайную среду. При этом переход от рассмотрения узлов и связей в решетках в классической постановке теории перколяции к рассмотрению смежных областей обслуживания, имитируемых соприкасающимися ребрами смежных ячеек матрицы, в рассматриваемых задачах является предпочтительным. Теория перколяции позволяет определить порог перколяции, уровень вероятности или концентрации Кп, при которой наступает перколяция, и имеет много точных аналитических результатов, но основной используемый ею метод - числен ное статистическое моделирование на решетках или деревьях [1; 3]. Нами рассматривались матрицы размером 30*30, 50*50, 100*100, 1000*1000, ячейки которых заполнялись случайным образом сначала с учетом равновероятностного распределения объектов по ячейкам. В дальнейшем будут рассмотрены и модальные законы распределения объектов по ячейкам матрицы. Математические эксперименты заключались в построении серии случайных матриц для каждого значения К - вероятности наличия объекта в ячейке матрицы с дальнейшим распознаванием каждого получившегося кластера и определением численных характеристик полученного распределения случайных кластеров по выбранным параметрам. В результате статистической обработки результатов математических экспериментов нами были определены пороги перколяции для различных размеров матрицы при равновероятном появлении объекта в каждой ее ячейке. Зависимость порога перколяции от размера матрицы представлена на рис. 1. Из графика видно, что при увеличении размера матрицы диапазон значений порога перко-ляции сужается, и при бесконечном росте размера матрицы можно ожидать, что перколяция будет возникать идеальным скачком - ступенчато [1]. В теории перколяции часто стремятся рассматривать бесконечную (очень большую по размерам) матрицу, однако в нашем случае, в соответствии с постановкой задачи, необходимо рассматривать матрицы конечных размеров. При этом возникает задача оценки влияния размеров матрицы на точность полученных результатов. Согласно рис. 1 можно определить диапазон значений порога перколяции для матрицы 50*50, который равен 0,5...0,65. При этом теоретическое значение для бесконечной матрицы равно 0,593 [1]. Перкопядия, -1М0 Концентрация % Рис. 1. Зависимость порога перколяции от вероятности наличия объекта в ячейке (концентрации) для различных размеров матрицы По полученным случайным матрицам были распознаны алгоритмом Хошена-Коппельмана [1; 3; 6] все кластеры, определены их статистические характеристики и построены графики. «Инфокоммуникационные технологии» Том 11, № 1, 2013 Мостовой Я.А. 55 36.3, А О л 0.2 0.4 К а) 0.6 0.8 ,0.65, К б) J>.6_ Рис. 2. Зависимость среднего размера кластера от концентрации (а) и зависимость среднего нормированного пути управляемой перколяции от концентрации (б) Визуализация ряда из полученных матриц будет приведена на рис. 5. Все возникшие кластеры окрашивались разными цветами, что в черно-белой интерпретации отображается разной интенсивностью серого и черного цвета. На данных матрицах отображены кратчайшие пути в направлении перколяции, проходящие через статистически образовавшиеся кластеры, и реализованные путем дополнения их минимальным количеством объектов, что необходимо для рассмотрения двухфазных операций и введения понятия «управляемой перколяции». На рис. 2а приведена зависимость среднего размера кластера матрицы от вероятности наличия объекта в ячейке - концентрации. По этому графику видно, что концентрации меньшей чем 0,5 соответствует небольшое значение среднего размера кластера, а при вероятности наличия объекта в ячейке больше, чем порог перколяции, функция возрастает стремительно. Это объясняется тем, что при малых вероятностях наличия объектов в ячейке матрица заполнена большим количеством кластеров маленького размера, а при значениях этой вероятности близких и больших, чем порог перколяции, эти маленькие кластеры объединяются с перколяционным кластером, который стремительно увеличивается. Зависимость среднего числа образовавшихся кластеров на матрице от вероятности наличия объекта в ячейке - концентрации K отражена на рис. 3. По мере увеличения этой вероятности в диапазоне 0,1 ...0,3 матрица заполняется объектами и число кластеров растет. Максимальное значение среднего количества кластеров достигается при вероятности наличия объекта в ячейке равной ~ 0,25. При этом в матрице присутствует большое число кластеров небольших размеров. После этой точки при добавлении новых объек тов с увеличением концентрации они начинают более активно присоединяться к уже образованным кластерам, происходит слияние кластеров и рост их размеров со снижением общего количества кластеров. На рис. 3 видна также зависимость числа кластеров от размеров матрицы, однако нормирование этих результатов по площади матрицы L2 избавляет от этой зависимости. Физические соображения подсказывают, что начиная с определенной величины матрицы от размера матрицы не должны зависеть размеры кластеров, измеряемые числом образующих кластер ячеек, расстояния между кластерами. В то же время количество кластеров, образовавшихся на матрице при определенной концентрации, зависит от площади матрицы L2, где L - размер матрицы, измеряемый числом ячеек строки. Длины путей на матрице, например длина пути перколяции зависят от размера матрицы L. От влияния размеров матрицы на результаты статистического моделирования можно избавиться, если их пронормировать путем деления соответственно на L и L2. Статистические исследования на матрицах различных размеров показали статистическую устойчивость нормированных подобным образом характеристик распределения кластеров и их независимость от размера матрицы. Полученные результаты позволяют гарантированно оценивать порог перколяции на квадратной матрице значением 0,65; что дает число объектов в перколяционном кластере 0,65 L2, где L2 - число ячеек в матрице. Однако такое количество объектов в перколя-ционном кластере будет явно избыточным для больших сетей, в которых ищется минимальная длина пути перколяции, так как структура перко-ляционного кластера достаточно ветвиста и рыхла [1; 3]. «Инфокоммуникационные технологии» Том 11, № 1, 2013 56 Мостовой Я.А. Л К l0.65j Л К .0.65, а) б) Рис. 3. Зависимость среднего числа кластеров от вероятности наличия объекта в ячейке для матрицы а) 50*50 и 100*100; б) нормированное по размеру матрицы среднее число кластеров Точка максимума на кривой рис. 3 со значением вероятности нахождения объекта в ячейке матрицы равным ~0,25 дает среднее максимальное количество кластеров. Средний размер кластера в этом случае имеет значение около 2 (см. рис. 2). Использование точки максимального среднего числа кластеров при определении необходимого числа объектов в требуемой зоне обслуживания позволяет более чем в два раза снизить потребное их число для выполнения выбранного геометрического критерия покрытия зоны обслуживания при некоторых постановках задач. Этот результат тем более важен, если учесть [6] замечательное свойство вероятности наличия объекта в ячейке равной ~0,25. Данное значение мало изменяется для модальных законов распределения по матрице вероятности нахождения объекта в ячейке (при сохранении средней по матрице вероятности наличия объекта в ячейке). Управляемая перколяция. Двухфазные операции в больших сетях Большинство прикладных задач анализа и исчисления путей в больших сетях связаны с минимизацией длины пути - числа узлов сети, входящих в искомый маршрут. В рассмотренном случае стохастической перколяции искомый путь получается случайным образом при повышении концентрации объектов с заданными свойствами в сети. Дальнейшего снижения потребной концентрации объектов и, следовательно, необходимого их количества для реализации перколя-ции зоны обслуживания сети можно достичь, если сначала создать опорную систему распределенных случайным образом объектов при сравнительно малой их концентрации, а затем на втором этапе операции в межкластерные интервалы «стохастической опоры» ввести управляемым образом ограниченное количество дополнительных объектов так, чтобы они совместно с имеющимися стохастическими кластерами образовали бы сплошной перколя-ционный путь минимальной длины в заданном направлении. В данном случае мы можем говорить о программируемой, или управляемой, перколяции в отличие от классической стохастической перколяции. При этом очевидно, что доставка и установка каждого дополнительного объекта с требуемыми характеристиками в определенное место зоны обслуживания большой сети (матрицы зоны обслуживания) - операция гораздо более дорогая, чем операция по созданию каждого объекта в случайной группе объектов «стохастической основы». Таким образом, увеличивая концентрацию объектов в стохастической основе большой сети, можно уменьшить необходимое для создания кратчайшего перколяционного пути число дополнительных управляемых объектов и наоборот. Учитывая различную в общем случае стоимость объектов первого рода, распределенных статистически, и объектов второго рода, внедряемых в определенные места зоны обслуживания для достижения искусственной управляемой перколяции с минимальной длиной пути, можно найти концентрацию объектов, при которой общие расходы на создание кратчайшего пути управляемой перколяции будет иметь минимум. Этот минимум расходов должен быть меньше расходов на создание чисто стохастического перколяционного кластера (K = Кп) или расходов на создание полностью управляемой перколяции заданной зоны обслуживания без стохастической основы (К = 0). «Инфокоммуникационные технологии» Том 11, № 1, 2013 Мостовой Я.А. 57 Для подтверждения высказанных соображений было проведено статистическое моделирование подобной двухфазной операции. Сначала было определено минимальное число дополнительно вводимых объектов в межкластерные интервалы для создания совместно с имеющимися кластерами кратчайшего сквозного перколяционного пути в заданном направлении. Среднее число таких добавленных объектов, как функция концентрации K, было определено путем статистического моделирования на большом количестве случайных матриц. При этом в каждой полученной случайным образом матрице варьировалось также и положение начальной точки пути программируемой перколяции на основании матрицы. На рис 4а)приведены средние числа добавленных объектов для получения программируемой J0Q 100 \ 1 1 1 80 “ \ _ DK(K) 60 - \ dk(K) 40 -'чч \ lQ, 20 0 1 1 ''-^L - 0 0.2 0.4 0.6 0.8 Л К ,0.65, управляемой перколяции в заданном направлении для матриц различных размеров. На рис. 4б) данные зависимости нормированы по размеру матрицы. После чего они совпали. Из рис. 4 видно, что с увеличением концентрации число добавленных объектов для образования минимального пути управляемой перколяции падает. С другой стороны, извилистость этого пути и стало быть его длина растут за счет использования все большего числа «попутных кластеров», вплоть до значения порога перколяции Кп ~ 0,6. На рис. 2б) приведена подсчитанная по результатам статистического моделирования средняя нормированная длина минимального пути управляемой перколяции, полученная сочетанием объектов стохастически образованных кластеров и добавленных «управляемых» объектов, закрыва- Л К L0.6 а) б) Рис. 4. Зависимость среднего числа добавленных объектов для обеспечения управляемой перколяции от вероятности наличия объекта в ячейке: а) для матриц размером 50 х 50 и 100х100; б) та же зависимость, нормированная по размеру матрицы ющих межкластерные интервалы, в соответствии с алгоритмом минимизации общего пути. Приведенная зависимость нормирована по размеру матрицы путем деления средней длины кратчайшего пути управляемой перколяции на L . В нормированном виде число добавленных ячеек и длина пути управляемой перколяции практически не зависят от размера матрицы начиная с L = 20-30. На рис. 5 приведена визуализация нескольких матриц различного размера для различных значений вероятности наличия объекта в ячейке. Там же приведены пути управляемой перколяции. На рис. 5а)-г) виден рост извилистости пути управляемой перколяции с ростом вероятности нахождения объекта в ячейке матрицы. Разработанный алгоритм, определяющий минимальное число добавленных объектов к существующим на матрице случайным кластерам для получения кратчайшего пути перколяции и визуализи рующий полученный путь на матрице, получил название «Молния». Минимальной длине пути управляемой перколяции соответствует значение концентрации стохастической основы равное нулю, при этом само значение пути управляемой перколяции равно L. Максимальное значение пути управляемой перколяции соответствует концентрации стохастической основы порога перко-ляции, при этом стохастический перколяционный кластер в этот момент обладает максимальной извилистостью, а число добавленных объектов равно нулю. Оптимизация двухфазных операций в больших сетях Обозначим стоимость каждого из распределенных случайным образом объектов а, а стоимость одного объекта, устанавливаемого в определенное место большой сети, - в (К). Тогда суммарная стоимость двухфазной операции Р будет: «Инфокоммуникационные технологии» Том 11, № 1, 2013 58 Мостовой Я.А. а) К = 0,1. Матрица 30x30, число добавленных объектов-21 б) К = 0,4. Матрица 30x30, число добавленных объектов - 5 в) К = 0,25. Малица 100x100, число добавленных г) К= 0,25. Матрица 100x100, число добавленных объектов-45 объектов 19 Рис. 5. Визуализация кластеров на матрице при указанной вероятности наличия объекта в ячейке и различных размерах матрицы. Число добавленных объектов относится к отмеченному кратчайшему пути управляемой перколяции через стохастически образованные кластеры Р = a KxL2 + в (К) p(K)xL . Здесь первое слагаемое - стоимость стохастической основы, а К^2 - число распределенных случайным образом объектов первого рода в стохастической основе. Второе слагаемое - это стоимость добавленных для формирования кратчайшего управляемого перколяционного пути через стохастически образованные кластеры объектов второго рода, а р(К)^ - количество этих добавленных объектов, определенных по результатам статистического моделирования и приведенных в нормированной зависимости на рис. 4б). Функция в (К) отражает зависимость стоимости создания и установки каждого внедряемого в сеть объекта от концентрации стохастической основы. Чем больше размер «межкластерных дыр», в которые надо устанавливать дополнительные объекты для создания сквозного минимального перколяционного пути через существующие стохастические кластеры, тем дороже будет стоить установка каждого из них. Поэтому для малых значений концентрации К объектов стохастической основы, сопровождаемых наличием протяженных межкластерных интервалов, стоимость одного дополнительного объекта (второго рода) будет больше, и с ростом К стоимость таких объектов будет уменьшаться. В общем случае эту зависимость можно представить в виде «Инфокоммуникационные технологии» Том 11, № 1, 2013 Мостовой Я.А. 59 в (К) ~ 0охр (K)xL . С другой стороны, экспериментально подтвержденное увеличение извилистости управляемого перколяционного пути с ростом концентрации К связано с увеличением доли объектов из случайных попутных кластеров в направлении перколяции при прокладке кратчайшего пути. Это означает также, что дополнительные объекты чаще перемежаются объектами стохастической основы. Это должно приводить к меньшим трудностям в установке очередного дополнительного объекта в заданное место сети. Мерой извилистости управляемого перколяционного пути может служить относительное увеличение длины пути перколяции по сравнению с кратчайшим путем - размером матрицы рис. 2б. Тогда окончательно 0 (К) - в 0Хф(К^/ДК) . Подставляя значение в (К) в выражение для суммарных затрат, получим Р = а ^L2 + в0Хф(К)2 х L2/^) . Значения а и в 0 зависят от множества факторов, характерных для конкретных характеристик решаемой задачи в конкретной сети. Поэтому целесообразно затраты на проведение двухфазной операции оценивать как функцию отношения стоимостей дополнительных объектов и объектов стохастической основы. Рассмотрим относительную стоимость двухфазной операции, нормированной по стоимости реализации чисто стохастической перколяции. Разделим левую и правую часть полученного уравнения на Рп = а ^xL2, учитывая, что для концентрации порога перколяции Кп - 0,6 значение ф(Кп) - 0. Тогда Ротн = Р/Рп = 1,7 К + 1,7 00хф(К)2/а р(К) = = 1,7 [К + R ф(К)2/ Р(К)], где R = в0/а - отношение стоимости дополнительного объекта к стоимости объекта стохастической основы. Зависимость относительной стоимости двухфазной операции от концентрации распределенных случайным образом объектов статистической основы приведены на рис. 6а)-б) для различных значений отношения R стоимости добавляемого объекта к стоимости объекта стохастической основы. Анализ полученных зависимостей показывает, что при двухфазных операциях в больших сетях при незначительном увеличении стоимости до- Л а) К L0.6 б) А6, л в) Л г) К .0,6, Рис. 6. Зависимости относительных затрат на проведение двухфазной операции от концентрации объектов стохастической основы при различных отношениях R стоимости дополнительных объектов и стоимости объектов стохастической основы: a) R = 1; б) R = 1,5; в), R = 2; г) R = 2,5 «Инфокоммуникационные технологии» Том 11, № 1, 2013 60 Мостовой Я.А. полнительных объектов, используемых для создания кратчайшего пути управляемой перколяции, относительно стоимости объектов стохастической основы оптимальное значение концентрации с точки зрения минимизации суммарных затрат составляет ~ 0,25. Это значение концентрации соответствует максимальному числу кластеров стохастической основы. В [6] рассмотрена концепция создания больших распределенных кластеров наноспутников (НС). В рамках этой концепции задача дистанционного зондирования Земли решается не одиночным НС или системой нескольких НС, а кластером НС, случайным образом распределенным по межвитковому интервалу трассы. Этот кластер должен рассматриваться как единая большая сеть с распределением ролей между НС кластера. Учитывая, что простейшие НС из-за малой массы не могут иметь собственной двигательной установки и автономной системы управления движением центра масс и организованное размещение отдельных НС в кластере в процессе полета НС не может быть поддержано, задачу определения необходимого количества случайным образом распределенных в пространстве спутников в таких кластерах предлагается решить путем статистического моделирования случайного процесса образования кластеров объектов на квадратной прямоугольной решетке. Оценка необходимого количества НС в кластере - первая задача, которую нужно решить в рамках этой задачи. Двухфазная операция создания управляемого перколяционного пути зоны обслуживания осуществима оптимальным образом при значении концентрации стохастической основы - вероятности нахождения НС в ячейке обслуживания равном 0,25; что примерно в 2,5 раза меньше порога стохастической перколяции. При этом среднее число добавленных НС для образования кратчайшего пути управляемой перколяции через кластеры стохастической основы не превышает 4% от числа НС стохастической основы (уменьшается с ростом размеров матрицы). Полученные результаты могут быть использованы для анализа безопасности больших информационных, вычислительных и социальных сетей, а также для исчисления путей в неблагоприятной случайной среде. Например, может быть создана также в два этапа социальная сеть, которая может добиться желаемого эффекта в своей зоне обслуживания при относительно низкой концентрации сил стохастической основы (~25%) путем добавления внедряемых в направлении кратчайшего пути перколяции зоны обслуживания объектов в количестве всего нескольких процентов от общего числа объектов в сети. С ростом размера сети относительная доля внедряемых объектов падает Для вычислительной сети, функционирующей в небезопасной среде, оптимальной стратегией может оказаться создание распределенной безопасной основы - системы защищенных узлов в точках, где затраты ожидаются минимальными, которую можно рассматривать в этом случае как стохастическую. В дальнейшем через созданные «островки безопасности» можно провести кратчайший безопасный путь, используя известные средства и системы информационной безопасности. Здесь так же, как и в предыдущем примере, относительная доля внедряемых для создания пути управляемой перколяции объектов изменяется от долей процента до нескольких процентов от общего числа объектов стохастической основы в зависимости от размера сети. Количество средств для создания безопасной распределенной основы и количество дополнительных узлов безопасного пути может быть определено по рис. 46). Этот вывод справедлив также и для деструктивной обратной задачи: достаточно управляемым образом нарушить работоспособность нескольких процентов от общего числа узлов, как «оптимально построенная» сеть перестанет «проводить». Справедливо также, что при прокладке пути через болотистую или небезопасную местность можно использовать двухфазную операцию рассмотренного типа через «островки безопасности». При этом из рис. 2б) ясно, что в среднем длина безопасного пути увеличится не более чем в 1,6 раза относительно пути, не учитывающего упомянутые опасности. Правда, для этой задачи необходим точный учет размеров ячейки матрицы на местности, который может быть непостоянным для матрицы. Полученные результаты являются достаточно общими. Конкретные результаты в конкретных сетях могут быть получены при учете конкретной их топологии и придании понятиям «зоны обслуживания», «создание объектов требуемого качества» «ячейки матрицы» конкретного соответствующего задаче смысла. Статистическое моделирование больших сетей при модальных законах распределения вероятностей нахождения объекта в ячейке Предположение о возможности равномерного по матрице распределения вероятности нахождения объекта в ячейке требует подтверждения для конкретных применений. «Инфокоммуникационные технологии» Том 11, № 1, 2013 Мостовой Я.А. 61 Рассмотрим в качестве более общего случая і направленную градиентную перколяцию, для ко- і торой вероятность нахождения объекта в ячейке і переменна либо по ширине матрицы вдоль каж- і дой строки, либо переменна по высоте матрицы вдоль каждого столбца [3]. При этом закон рас- ( пределения этой вероятности имеет моду, т.е. вероятность возрастает к оси матрицы и уменьша- } ется к краям матрицы. j Будем выдерживать при этом среднее значение } концентрации - вероятности нахождения объекта } в ячейке по всей матрице и соответственно откла- > дывать его по оси ординат графиков получаемых j зависимостей. Такой подход позволяет выделять і влияние неравномерности распределения вероятностей из-за наличия моды в законе распределения. Величину увеличения вероятности нахождения объекта в ячейке на центральной оси матрицы и уменьшения ее к краям будем описывать параметром f характеризующим относительное ] увеличение вероятности нахождения объекта в ячейке по оси матрицы по сравнению со средним ее значением. Мода закона распределения объек- ( тов по матрице может совпадать с рассматриваемым направлением перколяции либо она может быть «поперек» рассматриваемого направления і перколяции. Проведенное статистическое моделирование показало, что оба рассмотренных статистических феномена: наличие порога перколяции и наличие точки максимальной кластеризации - имеют место как в случае вертикального, так и в случае горизонтального градиентов распределения вероятности наличия объекта в ячейке. В таблице 1 приведены результаты статисти- ( ческого моделирования для матрицы 50*50 при ( Таблица 1. Результаты статистического моделирования модальных законах распределения НС по матрице с значением параметра f = 0,5. При этом значение порога перколяции изменяется значительно, а значение средней по матрице концентрации в точке максимальной кластеризации, которую обозначим Кмк, практически не меняется, а нулевые строки при Кмк в матрицах отсутствуют в подавляющем числе экспериментов (было сгенерировано и рассмотрено по 1000 случайных матриц для каждого из рассмотренных распределений и для каждого значения вероятности нахождения в ячейке объекта). При значении средней концентрации по матрице 0,1 и модальных законах распределения объектов по матрице имеется вероятность появления нулевых строк. Выводы В статье обсуждаются статистические феномены образования случайных кластеров при статистическом моделировании больших сетей на матрицах. Показано, что наряду со значением вероятности нахождения объекта в ячейке, соответствующим порогу перколяции, на оси вероятности нахождения объекта в ячейке имеется другая замечательная точка - точка максимальной кластеризации, в которой среднее число кластеров по матрице имеет максимум. После этой точки при добавлении новых объектов они начинают более активно присоединяться к уже образованным кластерам, и происходит слияние кластеров со снижением их общего количества. Рассмотрено понятие управляемой перколяции, которое введено в отличие от классической стохастической перколяции. Опираясь на это понятие, рассмотрены двухфазные операции на больших сетях. В течение первой фазы создается стохастическая основа с концентрацией случайно распределенных объектов значительно меньшей порога стохасти- Закон распределения вероятностей нахождения объектов по матрице Значение порога стохастической перколяции Значение концентрации в точке максимальной кластеризации Среднее нормированное количество кластеров в точке Кмк Максимальная средняя нормированная длина кратчайшего пути управляемой перколяции Концентрация для максимума среднего кратчайшего пути управляемой перколяции Равномерный 0,55 - 0,65 -0,25 0,13 1,66 0,6 Модальный, мода вдоль направления перколяции 0,45 - 0,55 -0,25 0,123 1,64 0,4 Модальный, мода поперек направления перколяции 0,65 - 0,75 -0,25 0,123 1,67 0,55 «Инфокоммуникационные технологии» Том 11, № 1, 2013 62 Мостовой Я.А. ческой перколяции. На второй фазе через имеющиеся кластеры стохастической основы проводится кратчайший перколяционный путь путем добавления в межкластерные интервалы дополнительных «управляемых» объектов. Путем статистического моделирования получено значение среднего числа добавляемых объектов для различной концентрации объектов стохастической основы. Также оценены среднее, максимальное и минимальное значения пути управляемой перколяции. Получены выражения для оценки суммарной эффективности двухфазной операции на больших сетях и значение концентрации объектов, обеспечивающее минимум суммарных затрат. В рассмотренном примере создания кластеров объектов большой сети значение концентрации стохастической основы - вероятности нахождения НС в ячейке обслуживания равно ~ 0,25, что в 2,5 раза меньше порога стохастической перколяции. При этом число добавленных объектов для образования пути управляемой перколяции через имеющиеся кластеры стохастической основы не превышает 4% от числа объектов стохастической основы. Это отношение падает с ростом размеров сети. Полученные результаты могут быть использованы для анализа безопасности больших информационных, вычислительных и социальных сетей, а также для исчисления путей в неблагоприятной случайной среде. Работа выполнена при поддержке РФФИ. Автор выражает благодарность Веричеву А.В., Ляховс-кому К.П., Малышкиной А.О., Пяткину А.С. за помощь в проведении статистических расчетов.

About the authors

J. A Mostovoi

Email: vt@ist.psati.ru

References

Supplementary files