А.
Ю. НикитинСовременные теоретико-графовые модели недостаточны для описания больших случайных графов (больших сетей). Эти графы представляют собой сложноструктурированную динамическую систему, меняющуюся с течением времени. Поэтому задача предложения удобного математического аппарата для изучения больших сетей является достаточно актуальной. Более того, основными моделями защиты информации являются графы и частичные порядки.
Цель данной работы заключаются в ознакомлении с существующими методами исследования больших сетей и предельных комбинаторик вообще. Ещё одной целью работы является обоснование теоретико-модельного подхода к изучению упомянутых моделей с точки зрения алгебраической геометрии и постановки вопросов и задач для продлжения разработки вышеуказанного метода для изучения больших сетей.
Теоретико-модельный подход к определению понятий предельной комбинаторики, и сетей в частности, уже был предложен В.Н. Ремесленниковым на конференции SIBECRYPT'16. Тезисы доклада с указанной конференции и будут являться базой для проведения теоретического анализа. Источниками уже существующих подходов к изучению случайных графов будут работы А.А. Разборова и Л.Ловаша.
Обозначенное направление изучения сетевых моделей является новым и исследования по нему начаты в Омском филиале Института математики им.С.Л.Соболева.
Поскольку графы будут сходиться к некоторому предельному графу, то очевидно, что нам достаточно будет решений системы уравнений на измеримом множестве графов, чтобы это решение являлось решением той же системы на предельной структуре (графоне).
Стоит так же отметить следующий факт о генерической теории для простых графов. Как известно, элементарная теория класса простых графов неразрешима. Но генерическая теория класса простых графов относительно меры, задающейся моделью Эрдёша-Реньи, полна и -категорична. Единственная счетная модель этой генерической теории является графом Радо (который вкладывает в себя все простые графы).
Преимуществом описанного метода является привлечение алгебро-геометрических методов для разрешения сложных систем уравнений и неравенств в больших сетях. Алгебро-геометрический аппарат можно использовать для эффективного поиска в сетях, категоризации подсетей и других вопросах, имеющих прикладной характер. Минусом подхода является его вероятностный характер, то есть решение какого-либо вопроса о системе уравнений будет нести асимптотический (приближенный) характер. С другой стороны, даже существующие методы не могут давать точного ответа на многие вопросы и, более того, сама природа болших сетей подразумевает сучайность. Поэтому, можно задать резонный вопрос: на сколько будет велик универсальный класс случайных графов, для которых алгебро-геометрические вопросы о системах уравнений и неравенств будут иметь точные ответы? Стоит привести несколько стандартных вопросов, которые возникают в алгебраической геометрии над любыми структурами: для фиксированной системы равенств и неравенств S разрешима ли десятая проблема Гильберта? Каков координатный граф системы S? Что является Dis-пределом для алгебраической структуры фиксированной сигнатуры?
