Distribuições, Limiares e o Momento em que a Rede Aleatória “Ganha Vida"

Depois de mergulhar no exemplo da festa do vinho — e na diferença entre fofoca em redes sociais reais e o modelo de Erdős–Rényi — avancei para outra parte fundamental: a matemática por trás da conectividade em redes aleatórias.

Do número de links ao grau médio

Em um grafo com NN nós, o número máximo de pares possíveis é:

M=N(N−1)2
M = \frac{N(N-1)}{2}.

O número de links LL segue uma distribuição binomial:

P(L)=(ML)pL(1−p)M−L
P(L) = \binom{M}{L} p^L (1-p)^{M-L}.

O valor esperado é:

⟨L⟩=Mp
\langle L \rangle = M \cdot p.

Como cada link conecta dois nós, o grau médio é:

⟨k⟩=2⟨L⟩N=p(N−1)
\langle k \rangle = \frac{2\langle L \rangle}{N} = p (N-1).

Minha intuição: cada nó tem N−1N-1 chances de se conectar, cada uma com probabilidade pp.


O limiar crítico: ⟨k⟩=1\langle k \rangle = 1

Esse foi o ponto mais marcante do meu aprendizado:

  • Se ⟨k⟩<1\langle k \rangle < 1: a rede é formada por pequenos fragmentos → a informação não se espalha.

  • Se ⟨k⟩=1\langle k \rangle = 1: surge a primeira componente gigante — um subgrafo que conecta uma fração significativa dos nós.

  • Se ⟨k⟩>1\langle k \rangle > 1: a componente gigante domina a rede e permite que a informação atravesse rapidamente.

Esse é o “big bang” da conectividade: a rede deixa de ser apenas pares dispersos e passa a funcionar como um organismo coletivo.


Distribuição de graus: Binomial vs. Poisson

Outro aprendizado importante foi perceber que:

  • Para NN finito, o grau kk segue uma binomial:

P(k)=(N−1k)pk(1−p)N−1−k
P(k) = \binom{N-1}{k} p^k (1-p)^{N-1-k}.

  • Para N→∞N \to \infty (com ⟨k⟩\langle k \rangle fixo), essa binomial se aproxima de uma Poisson:

P(k)≈e−⟨k⟩⟨k⟩kk!
P(k) \approx \frac{e^{-\langle k \rangle} \langle k \rangle^k}{k!}.

Isso significa que em redes grandes não precisamos mais controlar NN e pp separadamente — basta conhecer o valor de ⟨k⟩\langle k \rangle.

O pico da distribuição está em k≈⟨k⟩k \approx \langle k \rangle.

Resultado: em redes aleatórias, todos os nós têm graus parecidos.


E por que isso importa?

  • Em redes aleatórias (Poisson), não existem hubs: ninguém é muito mais conectado do que os outros.

  • Já em redes sociais reais, os hubs fazem toda a diferença — são eles que aceleram a fofoca, o vírus ou a novidade.

Esse contraste mostra tanto a força quanto a limitação do modelo de Erdős–Rényi.


Meu aprendizado até aqui

  • A fofoca do vinho foi o gancho para entender como a componente gigante surge.

  • O grau médio ⟨k⟩\langle k \rangle é a chave para identificar o momento crítico da conectividade.

  • A transição da binomial para a Poisson mostra por que, em redes aleatórias, todo mundo tem quase o mesmo número de vizinhos.

  • Comparar isso com redes sociais reais (que são small-world, clusterizadas e com hubs) deixa claro por que a vida vai muito além do modelo.

Para mim, estudar redes aleatórias é como aprender a gramática antes de escrever poesia. É o alicerce matemático que explica quando e como a rede “ganha vida” — mesmo que, no mundo real, as redes humanas sejam muito mais ricas e complexas.

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Assortatividade em redes: o algoritmo da afinidade

Entendendo a Correlação de Grau em Redes: quem se conecta com quem? Você já parou para pensar se os “nós populares” de uma rede tendem a se conectar entre si — ou se preferem fazer amizade com nós menores, menos conectados? Essa simples pergunta leva a um dos conceitos mais elegantes da Ciência de Redes : a correlação de grau  e o coeficiente de assortatividade . O que é o grau de um nó? O grau  de um nó é o número de conexões que ele possui. Em redes não direcionadas , é apenas o número de vizinhos. Já em redes direcionadas , distinguimos: grau de entrada (in-degree) : quantas conexões chegam; grau de saída (out-degree) : quantas conexões saem. Esse número simples — o grau — é a base de muitas propriedades emergentes das redes complexas. Correlação de grau: quando a afinidade cria estrutura A correlação de grau  mede o quanto o grau de um nó influencia o grau dos nós com que ele se conecta. Em termos simples: quem se conecta com quem: Quando nós de alto grau se conectam ...
Leia mais

Questão 4 - When Identical Degree Distributions Hide Distinct Correlation Patterns

When Identical Degree Distributions Hide Distinct Correlation Patterns “Two networks may share the same degree distribution and yet encode profoundly different organizational principles.”   Context Consider two undirected networks, A and B , each with the same degree distribution $P(k)$ and identical average degree $\langle k \rangle = 6.2$. Despite this structural similarity, empirical analysis shows that the average neighbor degree function $k_{nn}(k)$ behaves differently for each network: For Network A , $k_{nn}(k)$ increases approximately as a power law $k_{nn}(k) \sim a,k^{\mu}$ with $\mu > 0$. For Network B , $k_{nn}(k)$ decreases with $k$, following $k_{nn}(k) \sim a,k^{\mu}$ with $\mu < 0$. Definition The Pearson correlation coefficient of degree correlation r r r is defined as: r = ∑ j , k j k   ( e j k − q j q k ) σ 2 r = \frac{\sum_{j,k} j k \,\big(e_{jk} - q_j q_k\big)}{\sigma^2} r = σ 2 ∑ j , k ​ jk ( e jk ​ − q j ​ q k ​ ) ​ where: ejk e_{jk} e ...
Leia mais
Questão 5 — When 1.5 Beats 2: The Strength of Christofides under the Triangle Inequality Consider a symmetric, weighted, complete graph \( G = (V, E) \) with \( |V| = 6 \) vertices that satisfies the triangle inequality. The minimum spanning tree (MST) of \( G \) has total cost \( c(T) = 60 \). Two algorithms are applied to this graph: Rosenkrantz–Stearns–Lewis (RSL) Finds \( T=\mathrm{mst}(G) \); doubles each edge of \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices. Performance guarantee: \( c(C_{\mathrm{RSL}}) \le 2\,c(TSP^*) \). Christofides Finds \( T=\mathrm{mst}(G) \); lets \( S \) be the set of odd-degree vertices of \(T\); finds a minimum perfect matching \( M \) on \(S\); adds \(M\) to \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices. Performance guarantee: \( c(C_{\mathrm{Chr}}) \le 1.5\,c(TSP^*) \). Answer in one go: (i) the maximum tot...
Leia mais