Critério de Molloy-Reed

O critério de Molloy-Reed busca demonstrar a existência, ou ausência, de um componente gigante em uma rede aleatória. Também é utilizado para explicar a robustez de uma rede, estudada usando a teoria de percolação.

Seguindo o principio que para um componente gigante existir em uma rede, a maioria dos nós precisam estar conectados a outros dois nós, pelo menos. Logo, o grau médio de um nó que faz parte do componente gigante deve ser de ao menos dois.

O critério de Molloy-Reed utiliza a razão entre $\langle k^{2}\rangle$ e $\langle k\rangle$ para definir a existência de um componente gigante, válido para distribuições de grau arbitrárias $p_{k}$.

$\kappa ={\frac {\langle k^{2}\rangle }{\langle k\rangle }}>2$

Uma rede com $\kappa >2$ representa a existência de um componente gigante.

Componente gigante

Um componente gigante pode ser definido como um componente de um grafo aleatório que possui uma fração finita de todos os vertices do grafo.

Componentes gigantes são uma característica proeminente do Modelo Erdős–Rényi.

Prova do Critério de Molloy-Reed

A prova do critério de Molloy-Reed parte do principio que um nó existente de um componente gigante está conectado a ao menos dois outros nós, em média.

A probabilidade condicional de um nó i, com grau $k_{i}$, estar conectado a um nó j, que pertence a um componente gigante se da por $P(k_{i}|i\leftrightarrow j)$.

Esta probabilidade condicional permite determinar o grau esperado do nó i como

$\left\langle {k_{i}|i\leftrightarrow j}\right\rangle =\sum \limits _{k_{i}}{k_{i}P\left({k_{i}|i\leftrightarrow j}\right)}=2$

A probabilidade que aparece no somatório pode ser escrita também como a equação a seguir, utilizando o Teorema de Bayes no ultimo termo.

$P\left({k_{i}|i\leftrightarrow j}\right)={\frac {P\left({k_{i}|i\leftrightarrow j}\right)}{P\left({i\leftrightarrow j}\right)}}={\frac {P\left({i\leftrightarrow j|k_{i}}\right)p(k_{i})}{P\left({i\leftrightarrow j}\right)}}$

Na ausência de correlação de graus, em um rede com distribuição de graus $p_{k}$, a probabilidade do nó i estar conectado ao nó j pode ser escrita como

$P\left({i\leftrightarrow j}\right)={\frac {2L}{N(N-1)}}={\frac {\left\langle k\right\rangle }{N-1}}$

E a probabilidade condicional

$P\left({i\leftrightarrow j|k_{i}}\right)={\frac {k_{i}}{N-1}}$

Expressamos o fato que podem ser escolhidos $N-1$ nós, com probabilidade $1/(N-1)$ para cada nó, e que pode ser feitas $k_{i}$ tentativas, obtendo

$\sum \limits _{k_{i}}{k_{i}}P\left({k_{i}|i\leftrightarrow j}\right)=\sum \limits _{k_{i}}{k_{i}}{\frac {P\left({i\leftrightarrow j|k_{i}}\right)p(k_{i})}{P\left({i\leftrightarrow j}\right)}}=\sum \limits _{k_{i}}{k_{i}}{\frac {k_{i}p(k_{i})}{\left\langle k\right\rangle }}={\frac {\sum \limits _{k_{i}}{k_{i}}^{2}p(k_{i})}{\left\langle k\right\rangle }}$

Dado a definição do grau médio no segundo momento

$\langle k^{2}\rangle =\sum \limits _{k}k^{2}P(k)$

Obtemos a equação do critério de Molloy-Reed

$\kappa ={\frac {\langle k^{2}\rangle }{\langle k\rangle }}>2$

O critério de Molloy-Reed também pode ser provado por um conjunto de proposições.

Robustez da rede

O critério de Molloy-Reed pode ser derivado para se encontrar um limite critico $f_{c}$, utilizado na a teoria de percolação. Este limite representa o percentual de nós necessários que precisam ser removidos, para uma rede complexa perder um componente gigante e se dividir em diversos componentes menores e isolados.

${\begin{aligned}f_{c}=1-{\frac {1}{{\frac {<k^{2}>}{<k>}}-1}}\end{aligned}}$