Генератор случайных списков смежности
В настоящее время я работаю над разработкой приложения, чтобы найти максимальный клик на графике для моего проекта за последний год. У меня большая часть проекта завершена, и я только начинаю тестировать приложение.
В настоящее время приложение использует список смежности в качестве входных данных, и мне было интересно, если кто-нибудь знал о генераторе случайных списков смежности, так что я могу проверить свое приложение?
Большое спасибо
2 ответа
Эту проблему гораздо проще решить, если вы думаете о графах в терминах матриц смежности, а не списков смежности. График с m вершины могут быть представлены m от m матрица, в которой каждое ребро равно 0, если оно отсутствует, или 1, если оно присутствует.
Для ориентированного графа требуются все элементы, но для неориентированного графа вам понадобится верхняя треугольная матрица.
Получив матрицу смежности, вы можете легко преобразовать ее в списки смежности.
Это зависит от вашей модели случайного графа. Простейшей моделью является модель Эрдеша – Реньи, где вы указываете количество узлов и вероятность связи между любой данной парой. Это легко сгенерировать, но полученные графики не будут очень интересными, потому что они совсем не похожи на большинство сетей, наблюдаемых в реальном мире. Реальные сети обычно имеют степени степенного закона и более высокие коэффициенты кластеризации. Есть несколько других стандартных моделей, которые могут вас заинтересовать ( Уоттс- Строгатц или Барабази-Альберт). Я также использовал модель LFR, описанную в этой статье, с исходным кодом, доступным здесь.