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

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

• Мельников Б.Ф.
• Сайфуллина Е.Ф.

• Прикладные науки. Медицина. Технология

• Физико-математические науки
• Естественные науки