Componente gigante

Gran componente conectado de un gráfico aleatorio

Un gráfico aleatorio de Erdős-Rényi-Gilbert con 1000 vértices en la probabilidad del borde crítico , que muestra un componente grande y muchos pequeños. Con esta probabilidad de arista, el componente grande aún no es un componente gigante: contiene sólo 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 los vértices completos del gráfico .

Más precisamente, en gráficos extraídos aleatoriamente de una distribución de probabilidad sobre gráficos arbitrariamente grandes, un componente gigante es un componente conectado cuya fracción del número total de vértices está acotada desde cero. En gráficos suficientemente densos distribuidos según el modelo Erdős-Rényi , existe una alta probabilidad de que exista un componente gigante.

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 gráficos 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 es para cualquier constante , entonces con alta probabilidad (en el límite que llega al infinito) todos los componentes conectados del gráfico tienen tamaño O (log n ) , y no hay ningún componente gigante. Sin embargo, existe una alta probabilidad de que exista un solo componente gigante, y todos los demás componentes tienen un tamaño O (log n ) . Para , intermedio entre estas dos posibilidades, el número de vértices en el componente más grande del gráfico 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 . Arriba existe un componente gigante (el grupo más grande) de tamaño, . cumple, . Porque 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 los tamaños de los grupos 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 bordes seleccionados aleatoriamente uno a la vez, comenzando con un gráfico vacío , entonces no es hasta que se hayan agregado aproximadamente bordes que el gráfico contiene un componente grande, y poco después el componente se vuelve gigante. Más precisamente, cuando se han agregado t aristas, para valores de t cercanos pero mayores que , el tamaño del componente gigante es aproximadamente . ^[1] Sin embargo, según 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áficos con distribuciones de grados arbitrarios.

Un umbral similar y agudo 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 con distribuciones de grados no uniformes . La distribución de grados 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 grados, las gráficas se tratan como completamente aleatorias, se conocen muchos resultados sobre tamaños de componentes finitos/infinitos. En este modelo, la existencia del componente gigante depende sólo de los dos primeros momentos (mixtos) de la distribución de grados. Supongamos que un vértice elegido al azar tiene grado , entonces el componente gigante existe ^[3] si y solo si ${\displaystyle k}$

$${\displaystyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0.}$$

${\displaystyle \mathbb {E} [k]}$grafos dirigidosdistribución de grados^[4]gráficos dirigidos ${\displaystyle {\langle k\rangle }}$

1. el componente externo es un conjunto de vértices que se pueden alcanzar siguiendo recursivamente todos los bordes externos hacia adelante;
2. dentro del componente es un conjunto de vértices que se pueden alcanzar siguiendo recursivamente todos los bordes internos hacia atrás;
3. El componente débil es un conjunto de vértices que se pueden alcanzar siguiendo recursivamente todos los bordes independientemente de su dirección.

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

Dejemos que un vértice elegido al azar tenga aristas interiores y exteriores. Por definición, el número promedio de bordes de entrada y 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 gráficos 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}}$

Ver también

• Modelo Erdős-Rényi
• Fractales
• Teoría de grafos
• Redes interdependientes
• Teoría de la percolación
• Filtración
• Redes complejas
• Ciencia de redes
• Escalar redes libres

Referencias

1. Bollobás, Béla (2001), "6. La evolución de los gráficos aleatorios: el componente gigante", Gráficos aleatorios , Estudios de Cambridge en matemáticas avanzadas, 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; Caña, Bruce (1995). "Un punto crítico para gráficos aleatorios con una secuencia de grados determinada". Algoritmos y estructuras aleatorias . 6 (2–3): 161–180. doi :10.1002/rsa.3240060204. ISSN  1042-9832.
4. Newman, MEJ; Strogatz, SH; Watts, DJ (24 de julio de 2001). "Gráficos aleatorios con distribuciones de grados arbitrarios y sus aplicaciones". Revisión física E. 64 (2): 026118. arXiv : cond-mat/0007235 . Código bibliográfico : 2001PhRvE..64b6118N. doi : 10.1103/physreve.64.026118 . ISSN  1063-651X. PMID  11497662.
5. Kryven, Ivan (27 de julio de 2016). "Aparición del componente débil gigante en gráficos aleatorios dirigidos con distribuciones de grados arbitrarios". Revisión física E. 94 (1): 012315. arXiv : 1607.03793 . Código bibliográfico : 2016PhRvE..94a2315K. doi :10.1103/physreve.94.012315. ISSN  2470-0045. PMID  27575156. S2CID  206251373.