Gráfico aleatorio

Parte de una serie sobre
Ciencia de redes
Teoría
Gráfico Red compleja Contagio Mundo pequeño Sin escala Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de red
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neurona artificial Interdependiente Semántico Espacial Dependencia Fluir en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Bucle Vecindario Camino Vértice Lista  / matriz de adyacencia Listado  / matriz de incidencias Tipos Bipartito Completo Dirigido Hiper Etiquetado Multi Aleatorio Ponderado
Métrica Algoritmos
Centralidad Grado Motivo Agrupamiento Distribución de grados Asortatividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős–Rényi Barabási–Albert Bianconi–Barabási Modelo de fitness Watts-Strogatz Aleatorio exponencial (ERGM) Geometría aleatoria (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Modelado de bloques Entropía máxima Configuración suave Punto de referencia LFR Dinámica Red booleana basado en agente Epidemia / SIR
Liza Categorías
Temas Software Científicos de redes Categoría:Teoría de redes Categoría:Teoría de grafos
en a mi

En matemáticas , grafo aleatorio es el término general para referirse a distribuciones de probabilidad sobre grafos . Los grafos aleatorios pueden describirse simplemente por una distribución de probabilidad o por un proceso aleatorio que los genera. ^{[1] [2]} La teoría de grafos aleatorios se encuentra en la intersección entre la teoría de grafos y la teoría de probabilidad . Desde una perspectiva matemática, los grafos aleatorios se utilizan para responder preguntas sobre las propiedades de los grafos típicos . Sus aplicaciones prácticas se encuentran en todas las áreas en las que se necesitan modelar redes complejas ; por lo tanto, se conocen muchos modelos de grafos aleatorios, que reflejan los diversos tipos de redes complejas que se encuentran en diferentes áreas. En un contexto matemático, grafo aleatorio se refiere casi exclusivamente al modelo de grafo aleatorio de Erdős–Rényi . En otros contextos, cualquier modelo de grafo puede denominarse grafo aleatorio .

Un grafo aleatorio se obtiene partiendo de un conjunto de n vértices aislados y añadiendo aristas sucesivas entre ellos al azar. El objetivo del estudio en este campo es determinar en qué etapa es probable que surja una propiedad particular del grafo. ^[3] Diferentes modelos de grafos aleatorios producen diferentes distribuciones de probabilidad en los grafos. El más estudiado es el propuesto por Edgar Gilbert pero a menudo llamado modelo de Erdős–Rényi , denotado G ( n , p ). En él, cada arista posible ocurre independientemente con probabilidad 0 < p < 1. La probabilidad de obtener cualquier grafo aleatorio particular con m aristas es con la notación . ^[4]${\displaystyle p^{m}(1-p)^{N-m}}$${\displaystyle N={\tbinom {n}{2}}}$

Un modelo estrechamente relacionado, también llamado modelo Erdős–Rényi y denotado G ( n , M ), asigna la misma probabilidad a todos los grafos con exactamente M aristas. Con 0 ≤ M ≤ N , G ( n , M ) tiene elementos y cada elemento ocurre con probabilidad . ^[3] El modelo G ( n , M ) puede verse como una instantánea en un momento particular ( M ) del proceso de grafo aleatorio , un proceso estocástico que comienza con n vértices y sin aristas, y en cada paso agrega una nueva arista elegida uniformemente del conjunto de aristas faltantes.${\displaystyle {\tbinom {N}{M}}}$${\displaystyle 1/{\tbinom {N}{M}}}$ ${\displaystyle {\tilde {G}}_{n}}$

Si, en cambio, empezamos con un conjunto infinito de vértices y, de nuevo, dejamos que cada posible arista ocurra independientemente con una probabilidad de 0 < p < 1, obtenemos un objeto G llamado grafo aleatorio infinito . Excepto en los casos triviales en los que p es 0 o 1, es casi seguro que un grafo de este tipo tenga la siguiente propiedad:

Dados n + m elementos cualesquiera , hay un vértice c en V que es adyacente a cada uno de y no es adyacente a ninguno de .${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle b_{1},\ldots ,b_{m}}$

Resulta que si el conjunto de vértices es numerable, entonces existe, salvo isomorfismo , un único grafo con esta propiedad, a saber, el grafo de Rado . Por lo tanto, cualquier grafo aleatorio infinito numerable es casi con toda seguridad el grafo de Rado, que por esta razón a veces se denomina simplemente grafo aleatorio . Sin embargo, el resultado análogo no es cierto para grafos incontables, de los cuales hay muchos grafos (no isomorfos) que satisfacen la propiedad anterior.

Otro modelo, que generaliza el modelo de grafo aleatorio de Gilbert, es el modelo de producto escalar aleatorio . Un grafo de producto escalar aleatorio asocia con cada vértice un vector real . La probabilidad de una arista uv entre cualesquiera vértices u y v es alguna función del producto escalar u • v de sus respectivos vectores.

La matriz de probabilidad de red modela gráficos aleatorios a través de probabilidades de aristas, que representan la probabilidad de que exista una arista dada durante un período de tiempo específico. Este modelo es extensible a estructuras de gráficos dirigidos y no dirigidos, ponderados y no ponderados, estáticos o dinámicos.${\displaystyle p_{i,j}}$${\displaystyle e_{i,j}}$

Para M ≃ pN , donde N es el número máximo de aristas posibles, los dos modelos más utilizados, G ( n , M ) y G ( n , p ), son casi intercambiables. ^[5]

Los gráficos regulares aleatorios forman un caso especial, con propiedades que pueden diferir de los gráficos aleatorios en general.

Una vez que tenemos un modelo de gráficos aleatorios, cada función en los gráficos se convierte en una variable aleatoria . El estudio de este modelo consiste en determinar si una propiedad puede ocurrir o al menos estimar la probabilidad de que ocurra. ^[4]

El término "casi todos" en el contexto de gráficos aleatorios se refiere a una secuencia de espacios y probabilidades, tales que las probabilidades de error tienden a cero. ^[4]

La teoría de grafos aleatorios estudia las propiedades típicas de los grafos aleatorios, aquellas que se cumplen con alta probabilidad para los grafos extraídos de una distribución particular. Por ejemplo, podríamos preguntar por un valor dado de y cuál es la probabilidad de que esté conexo . Al estudiar tales cuestiones, los investigadores a menudo se concentran en el comportamiento asintótico de los grafos aleatorios, los valores a los que convergen varias probabilidades a medida que se hace muy grande. La teoría de la percolación caracteriza la conexidad de los grafos aleatorios, especialmente los infinitamente grandes.${\displaystyle n}$${\displaystyle p}$${\displaystyle G(n,p)}$${\displaystyle n}$

La percolación está relacionada con la robustez del grafo (también llamado red). Dado un grafo aleatorio de nodos y un grado promedio . A continuación, eliminamos aleatoriamente una fracción de nodos y dejamos solo una fracción . Existe un umbral crítico de percolación por debajo del cual la red se fragmenta mientras que por encima existe un componente conectado gigante. ^{[1] [5] [6] [7] [8]}${\displaystyle n}$${\displaystyle \langle k\rangle }$${\displaystyle 1-p}$${\displaystyle p}$${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$${\displaystyle p_{c}}$

La percolación localizada se refiere a la eliminación de un nodo, sus vecinos, los vecinos más próximos, etc., hasta que se elimina una fracción de nodos de la red. Se demostró que para un gráfico aleatorio con distribución de Poisson de grados, esto es exactamente igual que para la eliminación aleatoria.${\displaystyle 1-p}$${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$

Los grafos aleatorios se utilizan ampliamente en el método probabilístico , donde se intenta demostrar la existencia de grafos con ciertas propiedades. La existencia de una propiedad en un grafo aleatorio a menudo puede implicar, a través del lema de regularidad de Szemerédi , la existencia de esa propiedad en casi todos los grafos.

En grafos regulares aleatorios , son el conjunto de grafos -regulares con tales que y son los números naturales, , y es par. ^[3]${\displaystyle G(n,r-reg)}$${\displaystyle r}$${\displaystyle r=r(n)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle 3\leq r<n}$${\displaystyle rn=2m}$

La secuencia de grados de un gráfico depende únicamente del número de aristas en los conjuntos ^[3]${\displaystyle G}$${\displaystyle G^{n}}$

${\displaystyle V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}$

Si las aristas de un grafo aleatorio son lo suficientemente grandes como para garantizar que casi todas tengan un grado mínimo de al menos 1, entonces casi todas son conexas y, si son pares, casi todas tienen una correspondencia perfecta. En particular, en el momento en que el último vértice aislado desaparece en casi todos los grafos aleatorios, el grafo se vuelve conexo. ^[3]${\displaystyle M}$${\displaystyle G_{M}}$${\displaystyle G_{M}}$${\displaystyle G_{M}}$${\displaystyle n}$${\displaystyle G_{M}}$

Casi todos los procesos gráficos en un número par de vértices con el borde que eleva el grado mínimo a 1 o un gráfico aleatorio con un poco más de bordes y con una probabilidad cercana a 1 garantizan que el gráfico tenga una coincidencia completa, con excepción de como máximo un vértice.${\displaystyle {\tfrac {n}{4}}\log(n)}$

Para alguna constante , casi todo grafo etiquetado con vértices y al menos aristas es hamiltoniano . Con una probabilidad que tiende a 1, la arista particular que aumenta el grado mínimo a 2 hace que el grafo sea hamiltoniano.${\displaystyle c}$${\displaystyle n}$${\displaystyle cn\log(n)}$

Las propiedades de un grafo aleatorio pueden cambiar o permanecer invariables bajo transformaciones de grafos. Mashaghi A. et al., por ejemplo, demostraron que una transformación que convierte grafos aleatorios en sus grafos de aristas duales (o grafos lineales) produce un conjunto de grafos con una distribución de grados casi igual, pero con correlaciones de grados y un coeficiente de agrupamiento significativamente más alto. ^[9]

Dado un grafo aleatorio G de orden n con el vértice V ( G ) = {1, ..., n }, por el algoritmo voraz sobre el número de colores, los vértices pueden ser coloreados con los colores 1, 2, ... (el vértice 1 se colorea 1, el vértice 2 se colorea 1 si no es adyacente al vértice 1, de lo contrario se colorea 2, etc.). ^[3] El número de coloraciones propias de grafos aleatorios dado un número de q colores, llamado su polinomio cromático , sigue siendo desconocido hasta ahora. El escalado de ceros del polinomio cromático de grafos aleatorios con parámetros n y el número de aristas m o la probabilidad de conexión p se ha estudiado empíricamente utilizando un algoritmo basado en la coincidencia de patrones simbólicos. ^[10]

Un árbol aleatorio es un árbol o arborescencia que se forma mediante un proceso estocástico . En un amplio rango de grafos aleatorios de orden n y tamaño M ( n ), la distribución del número de componentes del árbol de orden k es asintóticamente Poisson . Los tipos de árboles aleatorios incluyen árbol de expansión uniforme , árbol de expansión mínima aleatoria , árbol binario aleatorio , treap , árbol aleatorio de exploración rápida , árbol browniano y bosque aleatorio .

Consideremos un modelo de gráfico aleatorio dado definido en el espacio de probabilidad y sea una función de valor real que asigna a cada gráfico en un vector de m propiedades. Para un fijo , los gráficos aleatorios condicionales son modelos en los que la medida de probabilidad asigna probabilidad cero a todos los gráficos tales que ' .${\displaystyle (\Omega ,{\mathcal {F}},P)}$${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$${\displaystyle \Omega }$${\displaystyle \mathbf {p} \in R^{m}}$${\displaystyle P}$${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$

Los casos especiales son los grafos aleatorios condicionalmente uniformes , donde asigna la misma probabilidad a todos los grafos que tienen propiedades específicas. Pueden verse como una generalización del modelo de Erdős–Rényi G ( n , M ), cuando la información de condicionamiento no es necesariamente el número de aristas M , sino cualquier otra propiedad arbitraria del grafo . En este caso, hay muy pocos resultados analíticos disponibles y se requiere simulación para obtener distribuciones empíricas de propiedades promedio.${\displaystyle P}$ ${\displaystyle {\mathcal {P}}(G)}$

El primer uso de un modelo de gráfico aleatorio fue realizado por Helen Hall Jennings y Jacob Moreno en 1938, donde se consideró un "sociograma aleatorio" (un modelo dirigido de Erdős-Rényi) al estudiar la comparación de la fracción de enlaces recíprocos en sus datos de red con el modelo aleatorio. ^[11] Otro uso, bajo el nombre de "red aleatoria", fue realizado por Ray Solomonoff y Anatol Rapoport en 1951, utilizando un modelo de gráficos dirigidos con grado de salida fijo y conexiones elegidas aleatoriamente a otros vértices. ^[12]

El modelo Erdős-Rényi de gráficos aleatorios fue definido por primera vez por Paul Erdős y Alfréd Rényi en su artículo de 1959 "On Random Graphs" ^[8] e independientemente por Gilbert en su artículo "Random Graphs". ^[6]

• Condensación de Bose-Einstein: un enfoque basado en la teoría de redes
• Método de cavidad
• Redes complejas
• Evolución de dos fases
• Modelo de Erdős-Rényi
• Modelo de gráfico aleatorio exponencial
• Teoría de grafos
• Redes interdependientes
• Ciencia de redes
• Filtración
• Teoría de la percolación
• Teoría de grafos aleatorios de la gelificación
• Gráfico regular
• Red libre de escala
• Respuesta semilineal
• Modelo de bloques estocásticos
• Punto de referencia Lancichinetti-Fortunato-Radicchi