Matriz de Adjacência e Laplaciano de Rede

1. Definição e Importância

A matriz de adjacência é a representação matemática compacta de um grafo como uma matriz binária (ou ponderada). Enquanto a representação visual de uma topologia é intuitiva mas qualitativa, a matriz permite cálculos algorítmicos, análise espectral e simulações computacionais — essenciais para projeto e validação de topologias de rede em escala.

Para um grafo G = (V, E) com n vértices, a matriz de adjacência A é uma matriz n × n onde:

• A[i][j] = 1 se existe aresta (v_i, v_j), 0 caso contrário (não-dirigido).
• A[i][j] = w(i,j) se for ponderada.
• Em digrafos, A[i][j] ≠ A[j][i] em geral.

Esta representação é a base da teoria espectral de grafos, que usa autovalores e autovetores de matrizes associadas para analisar propriedades estruturais como conectividade, expansão, sincronização e resiliência.

2. Construção da Matriz de Adjacência

2.1 Exemplo Simples

Seja o grafo:

A ──── B
│      │
C ──── D ──── E

Vértices: {A, B, C, D, E}. Arestas: {(A,B), (A,C), (B,D), (C,D), (D,E)}.

Matriz de adjacência (5×5):

     A  B  C  D  E
  A [ 0  1  1  0  0 ]
  B [ 1  0  0  1  0 ]
  C [ 1  0  0  1  0 ]
  D [ 0  1  1  0  1 ]
  E [ 0  0  0  1  0 ]

Propriedades imediatas:

• É simétrica (A = Aᵀ) porque o grafo é não-dirigido.
• A diagonal principal é zero (sem laços).
• A soma da linha i = grau do vértice i.

2.2 Versão Ponderada

Se cada aresta tem peso (custo OSPF, latência, etc.), a entrada correspondente armazena esse peso:

     A    B    C    D    E
  A [ 0   10   5    ∞    ∞ ]
  B [10    0   ∞   20    ∞ ]
  ...

Em geral, ausência de aresta é representada por 0, ∞, ou NaN — convenção dependente da aplicação.

3. Propriedades da Matriz de Adjacência

3.1 Potências e Caminhos

A matriz A^k (k-ésima potência) tem interpretação combinatória: A^k[i][j] = número de caminhos de comprimento exatamente k entre v_i e v_j.

Isso permite calcular, por multiplicação matricial, todos os caminhos de comprimento k simultaneamente. Útil em:

• Análise de reachability em k hops.
• Detecção de ciclos ímpares (traço de A^k).
• Distribuição de mensagens em flooding.

3.2 Traço e Ciclos

• tr(A) = 0 (sem laços).
• tr(A²) / 2 = número de arestas (em multigrafos, conta arestas paralelas).
• tr(A³) / 6 = número de triângulos (ciclos de comprimento 3).

3.3 Espectro da Matriz

Os autovalores de A (espectro) revelam propriedades estruturais profundas:

• Número de componentes conexos = multiplicidade do autovalor 0 (em L, não em A — ver seção 6).
• Grafo bipartido ⇔ espectro simétrico em torno de 0.
• Maior autovalor (λ_max) ≥ grau médio; λ_max ≤ grau máximo.

4. Matriz de Incidência

Diferente da adjacência, a incidência B é uma matriz n × m (nós × arestas):

• B[i][e] = 1 se o nó i é incidente na aresta e, 0 caso contrário.
• Em digrafos: +1 para origem, -1 para destino.

Aplicação: fluxos em redes (max-flow), análise de circuitos elétricos (Kirchhoff).

5. Matriz Laplaciana (Laplaciano)

O Laplaciano de um grafo é definido como:

Onde D é a matriz diagonal de graus (D[i][i] = grau(i), 0 fora da diagonal).

Para o exemplo da seção 2.1:

D = diag(2, 2, 2, 3, 1)

L = D - A =
     A   B   C   D   E
  A [ 2  -1  -1   0   0 ]
  B [-1   2   0  -1   0 ]
  C [-1   0   2  -1   0 ]
  D [ 0  -1  -1   3  -1 ]
  E [ 0   0   0  -1   1 ]

5.1 Propriedades do Laplaciano

• Simétrico e semidefinido positivo: todos os autovalores são ≥ 0.
• Soma das linhas = 0: o vetor all-ones é autovetor com autovalor 0.
• Multiplicidade do autovalor 0 = número de componentes conexos.
• Segundo menor autovalor λ₂ (algebraic connectivity): mede quão "conectado" é o grafo. Maior λ₂ → mais robusto.

5.2 Conectividade Algébrica (λ₂)

O autovalor λ₂ (Fiedler value) é uma medida de coesão:

• λ₂ = 0 → grafo desconexo.
• λ₂ pequeno → conectado por poucos "gargalos".
• λ₂ grande → bem conectado, resiliente a remoções.

Em redes, topologias com λ₂ alto são preferíveis: spine-leaf tem λ₂ máximo para n fixo.

6. Análise Espectral e Centralidade

Centralidade de autovetor: x_i = Σ (A[i][j] × x_j) / λ_max. Um nó é central se seus vizinhos são centrais. É o princípio do PageRank (com damping factor). Clustering espectral: usa autovetores de L para particionar o grafo em comunidades, mais robusto que heurísticas clássicas em muitos casos.

7. Aplicações em Redes Reais

• Caminhos mínimos: dada a matriz A ponderada, aplica-se Floyd-Warshall para obter todas as distâncias em O(n³) (paralelizável em GPU).
• Análise de bissecção: largura de bissecção pode ser aproximada via λ₂ de L (Cheeger inequality): λ₂/2 ≤ φ(G) ≤ √(2 d_max × λ₂). Em datacenters, alta bissecção = boa performance East-West (spine-leaf).
• Detecção de componentes conexos: pela multiplicidade do autovalor 0 do Laplaciano, ou algoritmo Union-Find em O(E × α(V)).
• Resiliência a falhas: k-conectividade calculável via max-flow (polinomial) ou λ(G).
• Análise de LSDB OSPF: matriz exportável offline para identificar SPOFs, calcular diâmetro, validar designs.

8. Ferramentas Computacionais

import networkx as nx
import numpy as np

G = nx.Graph()
G.add_edges_from([('A','B'), ('A','C'), ('B','D'), ('C','D'), ('D','E')])
A = nx.adjacency_matrix(G).toarray()  # Matriz de adjacência
L = nx.laplacian_matrix(G).toarray()  # Laplaciano
eigvals = np.linalg.eigvalsh(L)         # Autovalores
print("λ₂ =", eigvals[1])              # Conectividade algébrica

Para grafos grandes, use matrizes esparsas via SciPy (scipy.sparse.csgraph.laplacian + scipy.sparse.linalg.eigsh).

9. Limitações Práticas

A matriz A ocupa O(n²) espaço, mesmo para grafos esparsos. Em redes com milhões de nós (Internet), inviável — solução: listas de adjacência ou matrizes esparsas (CSR/CSC). Adicionar/remover aresta em A é O(1), mas recalcular autovalores é O(n³). Em redes dinâmicas (SDN), isso limita análise em tempo real — solução: algoritmos incrementais (restart Arnoldi, randomized SVD).

10. Caso de Estudo: Spine-Leaf

Datacenter com 4 spines e 8 leaves, full mesh entre spines e leaves: spines não se conectam entre si; leaves não se conectam entre si; cada spine conecta-se a cada leaf. É grafo bipartido (spines | leaves). Autovalores de L: 0 (mult 1), 4 (mult 7), 8 (mult 3), 12 (mult 1). λ₂ = 4 → excelente conectividade algébrica. Diâmetro = 2 (qualquer leaf a leaf via spine). Bissecção máxima → ideal para East-West. Esta análise numérica fundamenta por que spine-leaf substituiu 3-tier em datacenters modernos.

11. Conclusão

A matriz de adjacência e o laplaciano traduzem topologias de rede em objetos algébricos manipuláveis. Com eles, engenheiros podem calcular métricas de resiliência, identificar gargalos, otimizar caminhos e validar designs antes de implementar. A teoria espectral de grafos é particularmente poderosa: autovalores revelam propriedades globais (conectividade, expansão) que seriam invisíveis na inspeção visual. Para quem projeta redes de datacenter, backbones ou até overlays SDN, dominar este ferramental é tão importante quanto dominar os próprios protocolos de rede.