15.6: Generación de gráficas aleatorias

Última actualización
Guardar como PDF

Page ID: 115875

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Hasta el momento, hemos estado creando redes usando métodos deterministas, por ejemplo, agregando manualmente nodos y bordes, importando archivos de datos, etc. Mientras tanto, hay algunas ocasiones en las que se quiere tener una red generada aleatoriamente. Aquí hay algunos ejemplos de las funciones integradas de NetworkX que pueden generar muestras de gráficas aleatorias:

$Código 15.21.png$

$Código 15.21 pt2.png$

La salida se muestra en la Fig. 15.10. El primer ejemplo, gnm_random_graph (n, m), simplemente genera una gráfica aleatoria compuesta por n nodos y m bordes. El segundo ejemplo, gnp_random_graph (n, p), genera una gráfica aleatoria hecha de n nodos, donde cada par de nodos está conectado entre sí con probabilidad p. Estos dos tipos de gráficos aleatorios se llaman gráficos aleatorios Erd"os-R'enyi después de dos matemáticos húngaros Paul Erd"os y Alfr'ed R'enyi que estudiaron gráficas aleatorias en la década de 1950 [63]. El tercer ejemplo, random_regular_graph (k, n), genera una gráfica regular aleatoria compuesta por n nodos que todos tienen el mismo grado k. El cuarto ejemplo, random_degree_sequence_graph (list), genera una gráfica aleatoria cuyos nodos tienen grados especificados en lista. En este ejemplo particular, cuatro nodos tienen grado 3, cuatro nodos tienen grado 4 y dos nodos tienen grado 5. Tenga en cuenta que esta función puede no ser capaz de generar una gráfica dentro de un número dado de pruebas (que se establece en 10 por defecto). Puede aumentar el número de pruebas especificando la opción de intentos en la función, por ejemplo, intenta = 100.

$Higo 15.10.png$

Fig 15.10 2.png — Figura$\PageIndex{1}$: Salida visual del Código 15.21.

Las gráficas aleatorias también se pueden generar aleatorizando topologías de gráficas existentes. Dicha aleatorización de redes es particularmente útil cuando se desea comparar una determinada propiedad de una red observada con la de un modelo aleatorio “nulo”. Por ejemplo, imagina que encontraste que la difusión de información era muy lenta en la red que estabas estudiando. Entonces podrías probar si la topología específica de la red causó o no esta lentitud simulando la difusión de información tanto en tu red como en sus contrapartes aleatorias, y luego comparando la velocidad de difusión de información entre ellas. Hay varias formas diferentes de aleatorizar topologías de red. Se diferencian en cuanto a qué propiedades de red deben conservarse durante la aleatorización. A continuación se muestran algunos ejemplos (aquí asumimos que g es la red original a aleatorizar):

• gnm_random_graph (g.number_of_nodes (), g.number_of_edges ()) conserva los números de nodos y bordes, nada más.
• random_degree_sequence_graph (g.degree () .values ()) conserva la secuencia de grados de nodo, además de los números de nodos y aristas. Como se señaló anteriormente, esta función puede no generar una gráfica dentro de un número dado de ensayos.
• expected_degree_graph (g.degree () .values ()) conserva el número de nodos y la secuencia de grados de nodo “esperados”. Esta función siempre puede generar una gráfica muy rápidamente utilizando el eficiente algoritmo Miller-Hagberg [64]. Si bien la secuencia de grados de la red generada no coincide exactamente con la de la entrada (especialmente si la red es densa), este método suele ser un enfoque práctico y razonable para la aleatorización de grandes redes del mundo real.
• double_edge_swap (g) conserva los números de nodos y aristas y la secuencia de grados de nodo. A diferencia de las tres funciones anteriores, esta no es una función generadora de gráficos, sino que modifica directamente la topología de la gráfica g. Realiza lo que se llama un intercambio de doble borde, es decir, seleccionar aleatoriamente dos bordes a − b y c − d, eliminar esos bordes y luego crear nuevos bordes a−c y b−d (si alguno de los pares ya está conectado, se intentará otro intercambio). Esta operación realiza una ligera aleatorización de la topología de g, y repitiéndola muchas veces, se puede aleatorizar gradualmente la topología desde la g original hasta una red completamente aleatoria. double_edge_swap (g, k) realiza k swaps de doble borde. También hay connected_double_edge_swap disponible, lo que garantiza que el gráfico resultante permanezca conectado.

Ejercicio$\PageIndex{1}$

Randomizethetopologyofzachary'skarateclubgraphbyUsando cada una de las siguientes funciones y visualizar los resultados:

• gnm_random_graph

• grado_aleatorio_secuencia_gráfica

• gráfico_grado_esperado

• double_edge_swap (5 veces)

• double_edge_swap (50 veces)