Проблемы генерации структурно разнообразных графов
Проблемы генерации структурно разнообразных графов
Аннотация
Для многих задач, связанных с графами, принципиально важно располагать набором структурно разнообразных графов. Например, такие графы могут использоваться для тестирования графовых алгоритмов или их нейросетевых аппроксимаций. Однако, насколько нам известно, задача генерации структурно разнообразных графов ранее не рассматривалась в литературе. В настоящей работе мы восполняем этот пробел. Сначала мы обсуждаем, как определить разнообразие набора графов, почему эта задача нетривиальна и как выбрать подходящую меру разнообразия. Затем для заданной меры разнообразия мы предлагаем и сравниваем несколько оптимизирующих её алгоритмов: рассматриваются подходы на основе стандартных моделей случайных графов, локальной оптимизации графов, генетических алгоритмов и нейронных генеративных моделей. Мы показываем, что разнообразие сгенерированных графов можно существенно повысить по сравнению с базовыми генераторами случайных графов. Кроме того, анализ сгенерированных графов позволяет лучше понять свойства функций расстояний между графами: в зависимости от того, какая функция расстояния используется для оптимизации, получаемые графы могут обладать весьма различными структурными свойствами, что даёт более глубокое понимание расстояния между графами, лежащего в основе меры разнообразия.
Ключевые слова
Издание
Труды Института системного программирования РАН, том 38, вып. 5, 2026, стр. 217-234.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2026-38(5)-13
Для цитирования
Полный текст статьи в формате pdf
Вернуться к содержанию тома