Проверка, является ли график случайным использованием модели Erdős–Rényi?
Чтобы просто напечатать 1 или 0 на основе логического значения, которое я только что использовал:
printf("%d\n", !!(42));
Особенно полезно с флагами:
#define MY_FLAG (1 << 4)
int flags = MY_FLAG;
printf("%d\n", !!(flags & MY_FLAG));
3 ответа
Самым простым способом, вероятно, было бы сравнить ожидаемое количество ссылок с тем, что вы наблюдали на данном графике. Немного более разумным методом было бы изучение распределения степеней. Графы Эрдеша – Реньи будут иметь биномиальное распределение, в то время как сети реального мира, как правило, имеют степенной закон.
Также может быть легче проверить, если у вас есть представление о том, какие другие типы моделей использовались для создания графа.
Вы не сможете сказать, генерируется ли один график случайным образом. Если алгоритм генерации случайный, необходимо проверить случайность распределения ребер. Но вам понадобится много экземпляров, сгенерированных этим алгоритмом. Лучше ознакомьтесь с понятием случайности в математике, криптографии и теории информации. [или, может быть, вы захотите начать с rfc 1750 ]
Модель Эрдеша – Реньи в основном утверждает, что вы берете число n узлов, и каждое возможное ребро имеет вероятность существования p [G (n, p )-модель]. Таким образом, с помощью p вы можете сгенерировать ожидаемое количество ребер и отклонение от этого ожидания. Если значительное соотношение графиков находится в пределах стандартного отклонения этого ожидания, ну, вы можете не утверждать, что ваш алгоритм вообще случайный, но у вас есть по крайней мере одна обнаруженная функция, ожидаемое количество ребер.
Но опять же, не имея большого количества состояний (графов, промежуточных шагов генерации графов и т.п.), вы потеряетесь там. Скажите, я даю вам номер: 4. Он генерируется случайно или нет?
Вы можете ознакомиться с пакетом ERGM для R (www.r-project.org) на сайте www.statnet.org. Хотя вы, возможно, не сможете со 100% уверенностью сказать, что ваша наблюдаемая сеть создана случайным процессом, вы сможете оценить вероятность того, что она была создана в результате случайных или неслучайных процессов выбора партнеров. В ERGM есть функция под названием gof, которая означает степень соответствия и сравнивает наблюдаемую сеть с смоделированными случайными сетями и рассматривает сетевую статистику, такую как: распределение геодезических расстояний, распределение общих партнеров по краям, распределение степеней и распределение переписи по триадам. Это позволит вам принять осознанное решение, считаете ли вы свою сеть случайной или нет.