Применение мультиэвристического подхода для случайной генерации графа с заданным вектором степеней

Актуальность и цели. Графы с заданным вектором степеней часто рассматриваются в качестве моделей для многих сложных реальных задач. Это обусловливает актуальность исследования алгоритмов генерации графов с заданным вектором степеней. Целью исследования является рассмотрение существующих методов и разработка собственного алгоритма, позволяющего сгенерировать граф на основе заданного вектора степеней. Приводится определение графической последовательности; формулируются известные критерии проверки, является ли данная последовательность графической. Результаты. Приводится разработанный авторами алгоритм, представляющий собой реализацию одного из критериев проверки на основе мультиэвристического подхода (незавершенного метода ветвей и границ). Вводится понятие вектора степеней второго порядка и приводится модификация разработанного алгоритма на случай генерации графов с заданным вектором степеней второго порядка. Эта модификация также выполнена на основе незавершенного метода ветвей и границ. Таким образом, предлагается новый подход к случайной генерации графов как к задаче дискретной оптимизации. В ходе вычислительных экспериментов на основе некоторых функций распределения были сгенерированы последовательности заданного размера (предполагаемое число вершин графа). В случае если сгенерированная последовательность является графической, на ее основе может быть сгенерирован граф. Затем на основе вектора степеней второго порядка полученного графа был сгенерирован еще один граф. Приводятся результаты измерения среднего времени выполнения программы (в миллисекундах) в случае разных функций распределения и разных размерностей графа. Выводы. Приведенные разные варианты генерации случайных графов могут быть полезны во многих приложениях, прежде всего в сетевых моделях; среди последних наиболее важными являются математические модели Интернета и социальных сетей, а также модели функционирования искусственных нейронных сетей. Еще одним из возможных направлений продолжения работ, описанных в данной статье, является «настройка» конкретных алгоритмов решения задач дискретной оптимизации (в частности, задачи проверки изоморфизма на конкретные предметные области применения графов).