Componente gigante

Componente grande conectado de un gráfico aleatorio

Un grafo aleatorio de Erdős–Rényi–Gilbert con 1000 vértices en la probabilidad crítica de borde , que muestra un componente grande y muchos pequeños. En esta probabilidad de borde, el componente grande aún no es un componente gigante: contiene solo un número sublineal de vértices. ${\displaystyle p=1/(n-1)}$

En teoría de redes , un componente gigante es un componente conectado de un gráfico aleatorio dado que contiene una fracción significativa de todos los vértices del gráfico .

Más precisamente, en grafos extraídos aleatoriamente de una distribución de probabilidad sobre grafos arbitrariamente grandes, un componente gigante es un componente conexo cuya fracción del número total de vértices está acotada a partir de cero. En grafos suficientemente densos distribuidos según el modelo de Erdős–Rényi , existe un componente gigante con alta probabilidad.

Componente gigante en el modelo Erdős-Rényi

Los componentes gigantes son una característica destacada del modelo Erdős–Rényi (ER) de grafos aleatorios, en el que cada posible arista que conecta pares de un conjunto dado de n vértices está presente, independientemente de las otras aristas, con probabilidad p . En este modelo, si para cualquier constante , entonces con alta probabilidad (en el límite como tiende a infinito) todos los componentes conectados del grafo tienen tamaño O(log n ) , y no hay ningún componente gigante. Sin embargo, para hay con alta probabilidad un único componente gigante, con todos los demás componentes teniendo tamaño O(log n ) . Para , intermedio entre estas dos posibilidades, el número de vértices en el componente más grande del grafo, es con alta probabilidad proporcional a . ^[1] ${\displaystyle p\leq {\frac {1-\epsilon }{n}}}$ ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle p\geq {\frac {1+\epsilon }{n}}}$ ${\displaystyle p=p_{c}={\frac {1}{n}}}$ ${\displaystyle P_{\inf }}$ ${\displaystyle n^{2/3}}$

El componente gigante también es importante en la teoría de la percolación. ^{[1] [2]} Cuando una fracción de nodos, , se elimina aleatoriamente de una red ER de grado , existe un umbral crítico, . Por encima existe un componente gigante (el grupo más grande) de tamaño, . cumple, . Para la solución de esta ecuación es , es decir, no hay ningún componente gigante. ${\displaystyle q=1-p}$ ${\displaystyle \langle k\rangle }$ ${\displaystyle p_{c}={\frac {1}{\langle k\rangle }}}$ ${\displaystyle p_{c}}$ ${\displaystyle P_{\inf }}$ ${\displaystyle P_{\inf }}$ ${\displaystyle P_{\inf }=p(1-\exp(-\langle k\rangle P_{\inf }))}$ ${\displaystyle p<p_{c}}$ ${\displaystyle P_{\inf }=0}$

En , la distribución de tamaños de clúster se comporta como una ley de potencia, ~ que es una característica de la transición de fase . ${\displaystyle p_{c}}$ ${\displaystyle n(s)}$ ${\displaystyle s^{-5/2}}$

Alternativamente, si uno agrega aristas seleccionadas aleatoriamente una a la vez, comenzando con un gráfico vacío , entonces no es hasta que se hayan agregado aproximadamente aristas que el gráfico contiene un componente grande, y poco después de eso el componente se vuelve gigante. Más precisamente, cuando se han agregado t aristas, para valores de t cercanos a pero mayores que , el tamaño del componente gigante es aproximadamente . ^[1] Sin embargo, de acuerdo con el problema del recolector de cupones , se necesitan aristas para tener una alta probabilidad de que todo el gráfico aleatorio esté conectado. ${\displaystyle n/2}$ ${\displaystyle n/2}$ ${\displaystyle 4t-2n}$ ${\displaystyle \Theta (n\log n)}$

Gráficas con distribuciones de grado arbitrario

Un umbral agudo similar entre los parámetros que conducen a gráficos con todos los componentes pequeños y los parámetros que conducen a un componente gigante también ocurre en gráficos aleatorios tipo árbol con distribuciones de grado no uniformes . La distribución de grado no define un gráfico de forma única. Sin embargo, bajo el supuesto de que en todos los aspectos distintos de su distribución de grado, los gráficos se tratan como completamente aleatorios, se conocen muchos resultados sobre tamaños de componentes finitos/infinitos. En este modelo, la existencia del componente gigante depende solo de los dos primeros momentos (mixtos) de la distribución de grado. Sea un vértice elegido aleatoriamente de grado , entonces el componente gigante existe ^[3] si y solo si Esto se conoce como la condición de Molloy y Reed. ^[4] El primer momento de es el grado medio de la red. En general, el -ésimo momento se define como . ${\displaystyle P(k)}$ ${\displaystyle k}$ $${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0.}$$ ${\displaystyle P(k)}$ ${\displaystyle n}$ ${\displaystyle \langle k^{n}\rangle =\mathbb {E} [k^{n}]=\sum k^{n}P(k)}$

Cuando no hay un componente gigante, el tamaño esperado del componente pequeño también se puede determinar mediante el primer y segundo momento y es Sin embargo, cuando hay un componente gigante, el tamaño del componente gigante es más complicado de evaluar. ^[2] ${\displaystyle 1+{\frac {\langle k\rangle ^{2}}{2\langle k\rangle +\langle k^{2}\rangle }}.}$

Criterios para la existencia de componentes gigantes en gráficos de configuración dirigidos y no dirigidos

Expresiones similares también son válidas para grafos dirigidos , en cuyo caso la distribución de grados es bidimensional. ^[5] Hay tres tipos de componentes conexos en grafos dirigidos . Para un vértice elegido aleatoriamente:

1. out-component es un conjunto de vértices a los que se puede llegar siguiendo recursivamente todos los bordes de salida hacia adelante;
2. in-component es un conjunto de vértices a los que se puede llegar siguiendo recursivamente todos los bordes de entrada hacia atrás;
3. El componente débil es un conjunto de vértices a los que se puede llegar siguiendo recursivamente todos los bordes independientemente de su dirección.

Sea un vértice elegido al azar con aristas de entrada y de salida. Por definición, el número medio de aristas de entrada y de salida coincide de modo que . Si es la función generadora de la distribución de grados para una red no dirigida, entonces se puede definir como . Para redes dirigidas, la función generadora asignada a la distribución de probabilidad conjunta se puede escribir con dos valores y como: , entonces se puede definir y . Los criterios para la existencia de componentes gigantes en grafos aleatorios dirigidos y no dirigidos se dan en la siguiente tabla: ${\displaystyle k_{\text{in}}}$ ${\displaystyle k_{\text{out}}}$ ${\displaystyle c=\mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$ ${\displaystyle G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}}$ ${\displaystyle P(k)}$ ${\displaystyle G_{1}(x)}$ ${\displaystyle G_{1}(x)=\textstyle \sum _{k}\displaystyle {\frac {k}{\langle k\rangle }}P(k)x^{k-1}}$ ${\displaystyle P(k_{in},k_{out})}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle {\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}}$ ${\displaystyle g(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}}$ ${\displaystyle f(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}}$

Véase también

• Modelo Erdős-Rényi  : dos modelos estrechamente relacionados para generar gráficos aleatorios
• Fractales  : Estructura matemática infinitamente detalladaPages displaying short descriptions of redirect targets
• Teoría de grafos  – Área de las matemáticas discretas
• Redes interdependientes  : subcampo de la ciencia de redes
• Teoría de la percolación  : teoría matemática sobre el comportamiento de grupos conectados en un gráfico aleatorio
• Percolación  – Filtración de fluidos a través de materiales porosos
• Red compleja  : red con características topológicas no triviales
• Ciencia de redes  – Campo académico
• Red libre de escala  : red cuya distribución de grados sigue una ley de potencia

Referencias

1. Bollobás, Béla (2001), "6. La evolución de los grafos aleatorios: el componente gigante", Random Graphs , Cambridge studies in advanced mathematics, vol. 73 (2.ª ed.), Cambridge University Press, págs. 130-159, ISBN 978-0-521-79722-1.
2. Newman, MEJ (2010). Redes: una introducción . Nueva York: Oxford University Press. OCLC  456837194.
3. Molloy, Michael; Reed, Bruce (1995). "Un punto crítico para gráficos aleatorios con una secuencia de grados dada". Estructuras y algoritmos aleatorios . 6 (2–3): 161–180. doi :10.1002/rsa.3240060204. ISSN  1042-9832.
4. Molloy, Michael; Reed, Bruce (marzo de 1995). "Un punto crítico para gráficos aleatorios con una secuencia de grados dada". Estructuras y algoritmos aleatorios . 6 (2–3): 161–180. doi :10.1002/rsa.3240060204. ISSN  1042-9832.
5. Newman, MEJ; Strogatz, SH; Watts, DJ (24 de julio de 2001). "Gráficos aleatorios con distribuciones de grado arbitrario y sus aplicaciones". Physical Review E . 64 (2): 026118. arXiv : cond-mat/0007235 . Bibcode :2001PhRvE..64b6118N. doi : 10.1103/physreve.64.026118 . ISSN  1063-651X. PMID  11497662.
6. Kryven, Ivan (27 de julio de 2016). "Aparición del componente débil gigante en grafos aleatorios dirigidos con distribuciones de grado arbitrario". Physical Review E . 94 (1): 012315. arXiv : 1607.03793 . Bibcode :2016PhRvE..94a2315K. doi :10.1103/physreve.94.012315. ISSN  2470-0045. PMID  27575156. S2CID  206251373.