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

Question

Может быть большое количество алгоритмов, предложенных для генерации графиков, удовлетворяющих некоторые общие свойства (например, коэффициент кластеризации, средняя кратчайшая длина пути, распределение степени и т. Д.).

Мой вопрос касается конкретного случая: я хочу создать несколько Недоставленный регулярный Графики (то есть каждый узел в этих графиках имеет одинаковое количество соседей) с различными коэффициентами кластеризации и средней краткой длиной пути. В более общем плане, исправляя распределение степени, я хочу генерировать графики с различными коэффициентами кластеризации и средней краткой длиной пути.

Интересно, каковы известные алгоритмы для этого (или на самом деле есть?), И каково рекомендуемое программное обеспечение для той же цели?

Answer 1

Для вашей проблемы нет общих алгоритмов, но обычно это делает (для графиков небольших заказов)

1. Использовать назой Чтобы сгенерировать графики, удовлетворяющие некоторым грубым ограничениям (вы можете сделать только сгенерированные графики (BI), обычные графики, треугольные/четырехугольные графики, ..)

2. Используйте внешнюю программу, чтобы извлечь только те графики, которые вам нужны в отношении некоторых дополнительных свойств, которые вы хотите.

Вы можете сделать как 1, так и 2 в мудрец! Например, рассмотрим, что вы хотите генерировать все подключенные 5-регулярные графики порядка 20, которые имеют среднее расстояние 10 (индекс Wiener ??) и некоторый коэффициент кластеризации. Вы делаете следующее

for G in graphs.nauty_geng(" 20 -c -d5 -D5" ):
    if G.wiener_index() == 10 and G.clustering_coeff() == SOMETHING:
       print G.adjacency_matrix()

Дайте мне знать, если вам нужны более конкретные ответы, связанные с мудрецем.