Medidas de aleatoriedad de los grafos

Question

Hay muchas medidas prácticas de aleatoriedad para secuencias binarias o numéricas. Algunas pruebas de aleatoriedad arrojan un único número (como Complejidad de Kolmogorov ), otros vienen como baterías de pruebas (como el pruebas de resistencia ). Se supone que estas pruebas de aleatoriedad no pueden aplicarse a los grafos (dados como matrices de adyacencia binarias), al menos no de forma directa. Esto se debe a que cada matriz de adyacencia permutada (que produce una secuencia binaria diferente) debe tener el mismo grado de aleatoriedad.

Estoy buscando una visión concisa sobre las medidas "directas" de aleatoriedad de los grafos.

Answer 1

Como probablemente sepa, la pregunta que se hace es crucial en muchos métodos de generación de grafos aleatorios.

De hecho, muchos de ellos comienzan con un gráfico dado (sesgado) en una clase de interés y realizan pequeños reordenamientos aleatorios de aristas que mezcla el gráfico y se sabe que en última instancia conducen a un gráfico aleatorio uniformemente distribuido la clase dada.

Un ejemplo típico es el intercambio de bordes (sustituir $u-v$ y $u'-v'$ por $u-v'$ y $u'-v$ ) bajo restricciones (no crear bucles ni multi-surcos) con el fin de generar simple gráficos. Para más información, consulte el siguiente documento: Generación de grafos aleatorios restringidos utilizando múltiples conmutadores de aristas por Lionel Tabourier, Camille Roth, Jean-Philippe Cointet.

Desgraciadamente, en la mayoría de los casos, el número de reordenamientos locales necesarios para alcanzar una distribución uniforme es enorme, y, lo que es peor, se trata de un número de reordenamientos locales, desconocido . Por lo tanto, se recurre entonces a hacer muchos reajustes y espero que esto sea suficiente . Aquí es donde su pregunta es crucial: ¿cómo sabemos que hemos hecho suficiente ¿reordenamientos?

Pues bien, la gente suele hacer todas las que puede, y trazar las estadísticas básicas de las gráficas obtenidas, en función del número de reordenamientos (hay varios ejemplos en el documento anterior). Si la estadística converge a un valor constante, entonces se asume que el gráfico es al azar con respecto a esta estadística . También se puede utilizar una estimación del valor esperado de la estadística (cuando se dispone de ella), y comprobar que la mezcla alcanzó un valor cercano a este valor esperado... pero esto sigue siendo muy empírico.

Me temo que esto no responde a su pregunta, pero esto demuestra que ciertamente no hay manera (conocida) de tener una prueba de aleatoriedad formalmente fundamentada pero práctica para los gráficos, en general .

¿Quizás esto sea posible en algunas clases restringidas?

Te sugiero que preguntes en MathOverflow.