Componente gigante

En la teoría de redes , un componente gigante es un componente conectado de un grafo aleatorio dado que contiene una fracción significativa de los vértices de todo el grafo .

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 lejos de cero. En grafos suficientemente densos distribuidos según el modelo de Erdős-Rényi , un componente gigante existe con alta probabilidad.

Los componentes gigantes son una característica prominente del modelo de 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${\displaystyle p\leq {\frac {1-\epsilon }{n}}}$para cualquier constante${\displaystyle \epsilon >0}$, entonces con alta probabilidad (en el límite como${\displaystyle n}$(tiende a infinito) todos los componentes conectados del grafo tienen un tamaño O(log n ) y no hay ningún componente gigante. Sin embargo, para${\displaystyle p\geq {\frac {1+\epsilon }{n}}}$Existe con alta probabilidad un único componente gigante, y todos los demás componentes tienen un tamaño O(log n ) . Para${\displaystyle p=p_{c}={\frac {1}{n}}}$, intermedio entre estas dos posibilidades, el número de vértices en el componente más grande del grafo,${\displaystyle P_{\inf }}$es con alta probabilidad proporcional a${\displaystyle n^{2/3}}$. ^{[ 1 ]}

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

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

Alternativamente, si se agregan aristas seleccionadas aleatoriamente una por una, comenzando con un grafo vacío , entonces no es hasta aproximadamente${\displaystyle n/2}$Se han añadido aristas de tal forma que el grafo contiene un componente grande, y poco después ese componente se vuelve gigante. Más precisamente, cuando se han añadido t aristas, para valores de t cercanos pero mayores que${\displaystyle n/2}$El tamaño del componente gigante es aproximadamente${\displaystyle 4t-2n}$. ^{[ 1 ]} Sin embargo, según el problema del coleccionista de cupones ,${\displaystyle \Theta (n\log n)}$Se necesitan aristas para tener una alta probabilidad de que todo el grafo aleatorio esté conectado.

Un umbral similar y bien definido entre los parámetros que dan lugar a gráficos con todos los componentes pequeños y los parámetros que dan lugar a un componente gigante también se produce en gráficos aleatorios con estructura de árbol y distribuciones de grado no uniformes.${\displaystyle P(k)}$La distribución de grados no define un grafo de forma única. Sin embargo, bajo el supuesto de que en todos los aspectos, excepto en su distribución de grados, los grafos 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 grados. Sea un vértice elegido al azar con grado${\displaystyle k}$, entonces el componente gigante existe ^{[ 3 ]} si y solo si$${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0.}$$Esto se conoce como la condición de Molloy y Reed. ^{[ 4 ]} El primer momento de${\displaystyle P(k)}$es el grado medio de la red. En general, el${\displaystyle n}$El momento -ésimo se define como${\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 puede determinarse mediante los momentos primero y segundo y es${\displaystyle 1+{\frac {\langle k\rangle ^{2}}{2\langle k\rangle +\langle k^{2}\rangle }}.}$Sin embargo, cuando hay un componente gigante, el tamaño de dicho componente es más difícil de evaluar. ^{[ 2 ]}

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 conexas en grafos dirigidos . Para un vértice elegido al azar:

1. El componente de salida es un conjunto de vértices a los que se puede llegar siguiendo recursivamente todas las aristas de salida hacia adelante;
2. El componente interno es un conjunto de vértices al que se puede llegar siguiendo recursivamente todas las aristas internas hacia atrás;
3. El componente débil es un conjunto de vértices a los que se puede llegar siguiendo recursivamente todas las aristas, independientemente de su dirección.

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

• Red compleja : red con características topológicas no triviales. 
• Modelo Erdős-Rényi : dos modelos estrechamente relacionados para generar gráficos aleatorios 
• Fractales : estructura matemática infinitamente detallada. Páginas que muestran breves descripciones de destinos de redireccionamiento. 
• Teoría de grafos – Área de las matemáticas discretas 
• Redes interdependientes – Subcampo de la ciencia de redes 
• Ciencia de redes – Campo académico 
• Teoría de la percolación : teoría matemática sobre el comportamiento de grupos conectados en un grafo aleatorio. 
• Percolación – Filtración de fluidos a través de materiales porosos 
• Red libre de escala : red cuya distribución de grados sigue una ley de potencias.