Введение к работе
Актуальность темы исследования
Термин «сеть» широко распространён в современной научной и экономической литературе. На слуху такие выражения, как «розничная сеть», «железнодорожная сеть», «торговая сеть», «компьютерная сеть», «сеть магазинов», «сетевой маркетинг», «потоки в сетях», «филиальная сеть», «сеть трубопроводов», «социальная сеть», «информационная сеть», «телефонная сеть», «сеть Интернет» и т.д. Нередко смысл этого слова инвариантен при обозначении совершенно различных понятий.
Математиками «сеть» понимается как разновидность графа. Это множество элементов (вершин) системы (обязательно непустое), совокупность или множество отношений или связей (рёбер, дуг, петель, задаваемых кортежами длины два) между элементами или вершинами системы, трёхместный предикат или инцидентор, указывающий, какое ребро соединяет какую пару вершин, причём каждое ребро и/или каждая вершина могут быть отягощены некоторыми навешиваемыми скалярными характеристиками. Такими могут быть совокупности разных по интенсивности путей доставки товаров или услуг до конечного покупателя, длина пути, время движения по маршруту, пропускная способность газовой трубы, канала связи или электрического проводника, стоимость движения по участку платной автострады и т.д.
Системой в общем виде принято считать совокупность абстрактных и/или материальных объектов (элементов системы) с их известными внутренними свойствами (характеристиками) и заданными межобъектными отношениями (связями), образующими в известном смысле единой целое. Говорят, что это множество элементов, взаимосвязанных структурно и функционально, оно определено общей функцией, целью, назначением, входом и выходом. Системы, в основе функционирования которых лежат сетевые структуры, будем называть «сетевыми системами».
На протяжении длительного времени технические и экономические науки считали аксиомой стационарность структуры всякой сетевой системы. Структурой системы принято называть совокупность устойчивых связей между частями объекта или системы, обеспечивающих его (её) целостность и тождественность самому (самой) себе, сохранение основных характеристических свойств при внешних и внутренних воздействиях и изменениях. На этом понимании выросли научные школы в области теории графов, дискретной математики, комбинаторной оптимизации и теории систем. Не без основания все результаты деятельности научных школ имеют совершенно чётко очерченные области применения в практической деятельности.
Однако глобализация и либерализация общественной жизни и мировой экономики, усложнение производственных отношений и связей, развитие инфотелекоммуникационных технологий, ускорение процессов, обогащение их новыми составляющими приводит к экзогенному и эндогенному возмущению структуры изучаемого сигнала, делая его вариативным, стохастичным, циклическим, нестационар- ным. Сети разрастаются пространственно, а сетевые взаимодействия усложняются.
Это приводит к необходимости изучать мировые сетевые конъюнктуры новыми подходами, научными, более сложными, интеллектуально-ёмкими, математическими и инструментальными. В основании же сложности и противоречивости всех мировых процессов лежит существенная недетерминированность, присущая самой природе, сетевая структура с её перманентной изменчивостью. В такой ситуации в регулярных изменениях сетевых структур начинают прослеживаться закономерности. Сетевые структуры не только теряют свою стационарность (фиксированность), но и приобретают признаки динамических систем. Процессы развития и изменения сетевых структур можно объединить общим понятием «структурная динамика».
Исследования в области структурной динамики ведутся в научных школах профессора В.В. Кульбы, члена-корреспондента РАН Д.А. Новикова, профессора А.М. Кочкарова, в таких академических научно-исследовательских институтах и вузах России, как Институт проблем управления имени В.А. Трапезникова РАН, Институт прикладной математики имени М.В. Келдыша РАН, Вычислительный центр имени А.А. Дородницына РАН, Северо-Кавказская государственная гуманитарно-технологическая академия. Работы сотрудников научных школ профессора В.В. Кульбы и члена-корреспондента РАН Д.А. Новикова посвящены в большей степени задачам взаимодействия между элементами сложных иерархических систем, нежели задачам изменчивости и динамики сетевых структур. В работах школы профессора А.М. Кочкарова первичное внимание уделено решению динамических задач, задач развития сетевых структур. В качестве моделей структурной динамики сетевых систем в работах этой школы предлагаются различные классы масштабно-инвариант- ных графов, называемых предфрактальными.
Очевидно, что при исследовании, анализе и синтезе сетевых систем необходимо решать не только задачу распознавания структуры уже существующей сети, но и значительно более сложную динамическую задачу распознавания процесса изменения структуры сетевой системы. Задачу, объединяющую две указанные, назовём задачей «структурного распознавания». В настоящей работе предлагаются алгоритмы структурного распознавания динамики сетевых систем. Эти алгоритмы устанавливают, что, во-первых, процесс развития сетевых структур должен соответствовать тем или иным правилам порождения предфрактальных графов, а, во-вторых, они определяют, какие типы затравок были использованы при порождении графов.
Соответствие темы диссертации требованиям паспорта специальности
Диссертация выполнена в соответствие с пунктами: 1 «Разработка новых математических методов моделирования объектов и явлений»; 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; 6 «Разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента»; 8 «Разработка систем компьютерного и имитационного моделирования» «Паспорта специальности 05.13. 18 – математическое моделирование, численные методы и комплексы программ (физико-математические науки)» ВАК Министерства образования и науки РФ.
Объектом исследования являются
структуры сложных сетевых динамических систем (социальные сети, компьютерные сети, трубопроводные сети, сети управления и пр.).
Предмет исследования составляют
предфрактальные графы как математические модели сетевых структур, порождаемые множеством затравок разного типа с процессами их произвольного чередования, методология распознавания таких графов, вариативная архитектура программного комплекса, использующего предложенные модели, методы и алгоритмы.
Цель и задачи диссертационного исследования
Целью диссертационного исследования является применение математического моделирования, численных методов (алгоритмов) и комплексов программ при построении структурных моделей сетевых систем с выявлением описательного соответствия процесса развития структур этих систем процессу порождения и развития предфрактальных графов с произвольным чередованием затравок.
Сформулированная цель диссертационного исследования потребовала решения следующих задач:
разработка новых математических методов, использующих адаптацию предфрактальных графов к задачам моделирования сетевых структур с корректировкой основного правила порождения предфрактальных графов, приводящего к лучшей идемпотентности графа и моделируемой реальности;
нахождение численными методами в математических моделях сетей изменяющихся значений характеристик и новых качественных их свойств, приспособленных для работы с сетевыми структурами предфрактального класса;
проектирование взаимно интегрированных вычислительных алгоритмов распознавания, адаптированных к моделированию сетевых структур предфрактальных графов, получение новых закономерностей, характеризующих изучаемые объекты;
разработка вариативно перестраиваемой архитектуры, алгоритмов функционирования программного комплекса и самих программ, использующих предложенные алгоритмы и методики.
Методы исследования
В диссертационной работе использованы основные синергетические концепции динамического хаоса, фракталов и теории систем, применены современные методы и подходы теории графов, теории чисел, оптимизации и комбинаторики.
Достоверность и обоснованность
всех результатов диссертационного исследования подтверждается алгоритмами проверки адекватности построенных рядов математических моделей и объектов строгими и обоснованными логически последовательными умозаключениями в виде лемм и теорем с доказательствами.
Научная новизна диссертационного исследования
состоит в следующем:
-
Разработан новый математический метод моделирования сетей, проведена адаптация (с изменением правил) процесса порождения предфрактальных графов с целью моделирования развивающихся сетевых структур, отличающаяся динамикой фрактальных построений. Результатом адаптации стал новый класс предфрактальных графов, порождаемый множеством разных затравок с чередованием.
-
Вычислительными методами подсчитаны изменившиеся количественные характеристики и исследованы качественные свойства нового класса предфрактальных графов. Среди подсчитанных числовых характеристик находятся такие ключевые характеристики графов, как число вершин и число рёбер предфрактальных графов с чередованием, радиус, диаметр графов, хроматическое число. Для ряда исследованных графовых параметров (радиуса, диаметра, степеней вершин) адаптированных предфрактальных графов предложены достижимые количественные оценки.
-
Спроектированы взаимно интегрированные алгоритмы распознавания предфрактальных графов, порождённых множеством затравок с чередованием. Алгоритмы объединены в два блока. Первый блок состоит из алгоритмов распознавания предфрактальных деревьев, порождённых различными типами затравок-деревьев с чередованием и с вариациями условий сохранения смежности «старых» рёбер. Второй блок состоит из алгоритмов распознавания предфрактальных графов, порождённых различными типами регулярных затравок с чередованием, но с вариациями условия сохранения смежности «старых» рёбер. Все описанные алгоритмы обоснованы, подсчитана их вычислительная трудоёмкость, оказавшаяся полиномиальной.
-
Разработана архитектура и алгоритмы функционирования программной системы, не имеющей аналогов, изменяющей свою функциональную структуру при вариациях затравок, при вариации предложенных моделей и при вариации методов.
Теоретическая значимость и практическая ценность результатов исследования заключается в следующем:
Результаты диссертационного исследования, связанные с разработкой новых математических методов моделирования сетевых структур, подсчётом в динамике числовых характеристик и выявлением новых свойств предфрактальных графов с чередованием, имеют теоретическую значимость. Они могут вызвать интерес у специалистов по теории графов и структурной динамики для дальнейшего использования в научных обобщениях. Предложенный подход в динамическом моделировании саморазвивающихся сетевых систем в виде предфрактальных графов, порождаемых множеством разных затравок с чередованием, реализованный в комплексе программ с вариативной структурой, позволяет отслеживать и прогнозировать возможные структурные изменения в таких сетевых системах, как электроэнергетической, системах водо- и теплоснабжения, в системах трубопроводного транспорта, информационной, социальной, в системах управления торговыми сетями и т.п. системах. Методика позволяет учитывать и проектировать изменение структур сетевых систем в случае объективных изменений среды, внешней для системы.
Личный вклад соискателя
Все результаты диссертационного исследования получены автором самостоятельно.
На защиту выносятся следующие основные положения:
-
В рамках разработки новых методов математического моделирования сетевых структур определено понятие новой саморазвивающейся структуры - фрактального (предфрактального) графа, порождаемого множеством затравок с чередованием.
-
Алгоритмически с численной реализацией получены аналитические формы и произведён подсчёт числовых характеристик (числа вершин и рёбер графа, степени вершин, радиус, диаметр графа), даны оценки качественным показателям предфрактальных графов нового класса, порождаемых процессом чередования затравок.
-
Предложены, сконструированы и обоснованы эффективные полиномиальные алгоритмы распознавания предфрактальных графов с чередованием различных классов и типов затравок.
-
Применённый программный комплекс позволил менять свою структуру при работе с разными задачами порождения и распознавания предфрактальных графов как графов нового типа, с разными типами затравок при их чередовании и пр.
Апробация результатов исследования
Основные научные и практические результаты работы докладывались автором и получили одобрение:
на XII-ом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (Москва, 2009);
на Международной научной конференции «Проблемы регионального и муниципального управления» (Москва, 2009, 2010);
на IV-ой Международной конференции «Управление развитием крупномасштабных систем» (Москва, 2010);
на VII-ой Международной научной молодёжной школе «Высокопроизводительные вычислительные системы» (Таганрог, 2010);
на Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)» (Таганрог, 2010);
на XIV-ом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (Москва, 2011);
на VI-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и III-ей Молодёжной школе-семинаре «Управление и обработка информации в технических системах» - «Управление 2011» (Таганрог, 2011);
на Международной научно-практической конференции «Передовые информационные технологии, средства и системы автоматизации и их внедрение на российских предприятиях AITA-2011» (Москва, 2011);
на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской государственной технологической академии (Черкесск, 2002-2010);
на научных семинарах Ставропольского государственного университета (Ставрополь, 2010);
на научных семинарах филиала Южного федерального университета в г. Черкесске (Черкесск, 2008-2010).
Публикации
Основные результаты диссертационного исследования изложены в 14 опубликованных научных работах автора, в том числе 4 - в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК. Общий объём публикаций составляет 6.3 п.л., в том числе автора - 5.5 п.л.
Структура и объём диссертации
Диссертация состоит из введения, трёх разделов, заключения, библиографического списка использованных материалов, приложения. Текст диссертации изложен на 121 странице, включает 11 рисунков, в том числе описание программного комплекса в приложении насчитывает 17 страниц. Список использованной литературы содержит 144 источника.
