Проверка случайности графа с использованием модели Эрдеша – Реньи?

Question

Учитывая некоторый график, я хотел бы определить, насколько вероятно, что он был сгенерирован случайным образом. Мне сказали, что сравнение с моделью Эрдеша – Реньи было хорошим способом получить эту информацию, но я не могу понять, как это сделать.

Любой совет?

Answer 1

Простейшим способом, вероятно, будет сравнение ожидаемого количества ссылок с тем, что вы наблюдали на данном графике. Немного разумнее было бы изучить распределение степеней. Графы Эрдеша – Реньи будут иметь биномиальное распределение, в то время как сети реального мира обычно имеют степенной закон.

Также было бы проще проверить, если у вас есть представление о том, какие другие типы моделей используются для генерации графа.

Answer 2

Вы можете ознакомиться с пакетом ERGM для R (www.r-project.org) на сайте www.statnet.org. Хотя вы не сможете со 100% уверенностью сказать, что ваша наблюдаемая сеть была создана случайным образом, вы сможете оценить вероятность того, что она была получена в результате случайного или неслучайного процесса выбора партнера. ERGM имеет функцию под названием gof, которая обозначает пригодность и сравнивает вашу наблюдаемую сеть с моделируемыми случайными сетями и анализирует сетевую статистику, такую ​​как: распределение геодезических расстояний, распределение партнеров по краям, распределение степеней и распределение по переписи триады. Это позволит вам принять обоснованное решение, считаете ли вы свою сеть случайной или нет.

Answer 3

Вы не сможете сказать, генерируется ли один график случайным образом. Если алгоритм генерации является случайным, то вы должны проверить случайность распределения ребер. Но вам понадобится много экземпляров, сгенерированных этим алгоритмом. Лучше проверить с понятием случайности в математике, криптографии и теории информации. [или, может быть, вы хотите начать с rfc 1750 ]

Модель Эрдеша – Реньи в основном утверждает, что вы берете число n узлов, и каждое возможное ребро имеет вероятность p существования [G (n, p) -модель]. Таким образом, с помощью p вы можете сгенерировать ожидаемое количество ребер и отклонение от этого ожидания. Если значительное соотношение графиков находится в пределах стандартного отклонения от этого ожидания, вы, возможно, не заявите, что ваш алгоритм вообще случайный, но у вас есть хотя бы одна раскрытая функция, ожидаемое количество ребер.

Но опять же, без большого количества состояний (графы, промежуточные этапы генерации графа и т. П.) Вы там потерялись. Скажем, я даю вам число: 4. Произведено ли оно случайно или нет?