Dado algún gráfico, me gustaría determinar qué tan probable es que se haya generado al azar. Me dijeron que una comparación con el modelo Erdős-Rényi era una buena forma de obtener esta información, pero no puedo entender cómo hacerlo.Verificando si un gráfico es aleatorio usando el modelo Erdős-Rényi?
¿Algún consejo?
La manera más simple probablemente sea comparar el número esperado de enlaces con lo que observa en el gráfico dado. Un método un poco más inteligente sería examinar las distribuciones de grados. Los gráficos de Erdős-Rényi tendrán una distribución binomial, mientras que las redes del mundo real son típicamente leyes de poder.
También podría ser más fácil probar si tenía una idea de qué otros tipos de modelos se usaban para generar el gráfico.
No podrá decir si un solo gráfico se genera aleatoriamente. Si el algoritmo de generación es aleatorio, entonces debe verificar la aleatoriedad de la distribución de los bordes. Pero necesitará muchas instancias generadas por ese algoritmo. Mejor verificar con la noción de aleatoriedad en matemáticas, criptografía y teoría de la información. [o tal vez desea comenzar con rfc 1750]
El modelo de Erdős-Rényi básicamente establece que toma un número n de nodos y cada posible borde tiene probabilidad p de existencia [G (n, p) -model]. Así, por p puede generar el número esperado de bordes y la desviación de esta expectativa. Si una proporción significativa de gráficos está dentro de la desviación estándar de esta expectativa, bueno, puede que no indique que su algoritmo es aleatorio en absoluto, pero tiene al menos una característica descubierta, el número esperado de bordes.
Pero de nuevo, sin tener muchos estados (gráficos, pasos de generación de gráficos intermedios o similares) se perderá allí. Diga, le doy un número: 4. ¿Se genera al azar o no?
Puede consultar el paquete ERGM para R (www.r-project.org) en www.statnet.org. Aunque es posible que no pueda decir con 100% de certeza que su red observada se produce mediante un proceso aleatorio, podrá evaluar la probabilidad de que haya sido producida por procesos de selección de socios aleatorios o no aleatorios. ERGM tiene una función llamada gof que significa bondad de ajuste y comparará su red observada con redes aleatorias simuladas y observará las estadísticas de la red tales como: distribución de distancia geodésica, distribución de socios compartidos edgewise, distribución de grados y distribución de censos tríada. Esto le permitirá tomar una decisión informada si considera que su red es aleatoria o no.