Challenges-on-generating-structurally-diverse-graphs

В репозитории опубликован код для воспроизведения результатов работы по генерации структурно разнообразных графов. Авторы впервые формализуют и системно исследуют задачу построения наборов графов с максимальным структурным разнообразием — задача, критически важная для тестирования алгоритмов на графах, оценки нейросетевых приближений и построения бенчмарков. В работе подробно анализируется, как определить меру разнообразия для множества графов и почему задача не сводится к стандартным генераторам случайных графов. Введён показатель diversity на основе агрегирования попарных расстояний между графами (Energy), обладающий важными теоретическими свойствами, как монотонность и уникальность. Экспериментально исследованы и сравниваются различные алгоритмы генерации: жадный отбор из большого пула, генетические алгоритмы, локальная оптимизация и нейросетевые генеративные модели. Показано, что предлагаемые методы существенно превосходят классические случайные модели, например, Erdős–Rényi, GraphWorld, по мере diversity, позволяя получать выборки графов с сильно отличающимися характеристиками. Исследование также даёт новые инсайты о свойствах различных метрик расстояния между графами. Работа будет полезна исследователям в области графов, алгоритмистам, а также разработчикам бенчмарков и тестовых наборов для графовых задач.

статья | код