Cómo aleatorio generar un gráfico con nodos de grado de Pareto lognormal?

Question

He leído que el grado de los nodos en un gráfico de "conocimiento" de la gente sigue aproximadamente una distribución de ley de potencia, y más exactamente se puede aproximar con una distribución de Pareto-lognormal.

¿Dónde puedo encontrar un tipo de algoritmo que producirá un gráfico aleatoria con esta distribución?

Ver por ejemplo el papel Nueva revisión del Grado de distribución Modelos para el Análisis Social Graph (página 4, la ecuación 1) para una descripción matemática (función de distribución) del tipo de distribución que estoy interesado.

Answer 1

Para generar un gráfico de una secuencia de grado prescrito (independientemente de la secuencia de grado), se puede utilizar un algoritmo por Blitzstein y Diaconis:

• "Un algoritmo de muestreo de importancia secuencial para la generación de grafos aleatorios con grados prescritos" por J. Blitzstein y P. Diaconis

Desafortunadamente su algoritmo es potencialmente $ O (n ^ 2 \ bar {d}) $, por $ n vértices $ con grado medio de $ \ bar {d} $, por lo que esto podría no ser lo suficientemente rápido en función del tamaño de la gráfica y la aplicación en cuestión.

Molloy y Reed introdujo el "modelo de configuración Erased", que pares de vértices basado en una secuencia de grado elegido proporcional a las ranuras libres restantes.

• "un punto crítico para los gráficos al azar con una secuencia de grado dado" por M. Molloy y B. Reed

Un artículo de Britton, Deijfen y Martin-Lof muestran que el modelo de configuración Erased aproxima asintóticamente a la distribución grado prescrito elegido. Aunque no garantiza la entrada de secuencia grado exacto, recomendaría el modelo de configuración borrado por su sencillez y velocidad.

• "Generación aleatorio simple gráficos con distribución de grado prescrito" por T. Britton, M. Deijfen y A. Martin-Lof

En pocas palabras, el algoritmo de generación de gráficos modelo de configuración borrado crea "ganchos" para cada vértice, donde el número de ganchos para cada vértice está inicialmente dada por la secuencia de grado. Saliendo desde el vértice con la mayoría de los ganchos primeros, otro gancho se elige de manera uniforme al azar de la piscina todavía sin unir. Se realiza una conexión de este emparejamiento. Una vez que el conjunto de ganchos se agota, bucles auto se retiran y múltiples bordes se colapsan en una sola.

Desde bucles autónomos están permitidos y multi-bordes colapsaron, la secuencia de grado resultante podría potencialmente ser diferente de la secuencia de entrada, por lo que este método no es exacto. Si se prefiere la exactitud, el algoritmo por Blitzstein y Diácono se puede utilizar a un coste computacional más alto. Tenga en cuenta que el algoritmo de Blitzstein y diaconus comprueba si una secuencia grado prescrito es factible (o "gráfica" en su lenguaje), por lo que puede ser que necesite ser regenerado secuencias grado en caso de que no sea realizable.

secuencias de grado puede ser elegido en virtud de cualquier distribución que desee. En su caso, usted quiere elegir ellos sobre la base de una distribución de Pareto-lognormal.

También me gustaría brevemente Las gráficas de generación de secuencias con grado prescrito que siguen una distribución particular, digamos la distribución de Pareto-lognormal, no pueden generar el tipo de gráficos de "conocimiento" que desee. El grado de distribución es sólo un perfil de un gráfico y no dice nada acerca de otras características que pudieran estar presentes en el gráfico original de conjunto que estaría tratando de modelo. Como Raphael señala en los comentarios, la página de Wikipedia sobre redes libres de escala es un buen punto de partida punto por alguna revisión.