7 - Grafos e Machine Learning: O Laplaciano do grafo: a peça que conecta redes dinâmicas

O que é o Laplaciano?

Imagine uma rede de pessoas, cada uma com uma opinião (um número, digamos de 0 a 10). O Laplaciano responde, para cada pessoa, uma pergunta simples: "você pensa muito diferente dos seus amigos, ou parecido com eles?"

Se você pensa igual a todo mundo ao seu redor, o Laplaciano te dá zero, você está "em paz" com a vizinhança. Se você pensa bem diferente dos seus amigos (mais radical, ou mais moderado), o Laplaciano (Lf) te dá um número maior, positivo ou negativo, mostrando o quanto você destoa.

No cenário da esquerda, "Você" tem opinião $5, igual aos três amigos ao redor, então (Lf) = (5-5)+(5-5)+(5-5) = 0 , em paz com a vizinhança. No cenário da direita, "Você" tem opinião $9, bem acima dos três amigos (todos em 4 ), então (Lf)=3×(9−4)=15, um valor alto, mostrando o quanto você destoa.

Pense numa panela de água, com algumas partes mais quentes e outras mais frias. O Laplaciano, naquele ponto específico da água, mede o quanto a temperatura ali é diferente da temperatura da vizinhança imediata. Um ponto muito mais quente que ao redor tem Laplaciano alto, é dali que o calor vai "escorrer" para os vizinhos mais frios. Um ponto já na mesma temperatura dos vizinhos tem Laplaciano zero, não vai esquentar nem esfriar mais, já está em equilíbrio.

Numa rede de pessoas, é a mesma ideia, só que em vez de temperatura, é opinião, ou dinheiro, ou qualquer coisa que possa "se espalhar" de pessoa para pessoa. É por isso que essa matriz se chama Laplaciano, é o mesmo nome usado em física para o operador que descreve como o calor se espalha.

Duas coisas que o Laplaciano calcula, em níveis diferentes

No nível de cada pessoa (nível local), o Laplaciano diz "você destoa da sua vizinhança, e para qual lado". No nível da rede inteira (nível global), o Laplaciano tem um número especial, chamado conectividade algébrica, que diz "quão fácil é para uma opinião se espalhar pela rede inteira, sem esbarrar num gargalo". Uma rede bem entrelaçada, sem pontos fracos, tem esse número alto. Uma rede com um "gargalo" (um único ponto por onde tudo precisa passar, como a "ponte" dos nossos diagramas) tem esse número baixo, e isso significa que, mesmo dando tempo suficiente, vai demorar muito para uma opinião de um lado da rede chegar até o outro lado.

O gargalo é uma propriedade da estrutura, não do estado de opinião. Mas o gargalo não causa desacordo, ele decide quanto tempo um desacordo, se existir, vai demorar para se resolver.

Pense assim: se surgir uma opinião divergente de um lado da rede, numa rede sem gargalo, ela se espalha rápido, e o Lf de cada pessoa volta a zero rapidamente, à medida que todo mundo converge. Numa rede com gargalo, mesmo o mesmo tipo de desacordo inicial, o Lf positivo de um lado (e negativo do outro) demora muito mais para desaparecer, porque a "correção" precisa atravessar o único ponto de passagem.

Em suma, o Laplaciano é uma régua que mede desacordo, pessoa por pessoa, e ao mesmo tempo revela, olhando a rede toda, onde estão os gargalos que atrasam qualquer coisa que precise se espalhar por ela, seja opinião, dinheiro, ou uma doença.

Matematicamente falando

Em uma dimensão, para uma função f(x), a primeira derivada indica a taxa de variação da função. A segunda derivada indica como essa taxa de variação está mudando, fornecendo uma medida da curvatura.

Para representar o mesmo operador matemático, o Laplaciano contínuo usamos:

Em uma dimensão, portanto, o Laplaciano coincide simplesmente com a segunda derivada.

Por exemplo, tomando um conceito da Física, temos

Conceito Matemático	Conceito Físico	O que mede
Função s(t)	Posição do carro	Onde ele está
Primeira derivada s'(t)	Velocidade v(t)	Taxa de variação da posição
Segunda derivada s''(t)	Aceleração a(t)	Curvatura da trajetória; como a velocidade varia
Laplaciano em 1D	Aceleração	Soma das segundas derivadas na única direção existente

• Se você olhar para o gráfico da posição  e ele for uma reta, a curvatura é zero (aceleração zero, Laplaciano zero).

• Se ele for uma curva voltada para cima (como uma tigela), a curvatura é positiva (aceleração positiva, carro acelerando).

• Se ele for uma curva voltada para baixo (como um morro), a curvatura é negativa (aceleração negativa, carro freando).

É  essa "medida de curvatura total" que o Laplaciano captura. Na Física, chamamos de aceleração; na Matemática, chamamos de Laplaciano. A essência é a mesma.

Agora, considere uma função de duas variáveis, f(x,y). Existem duas direções independentes: x e y. Calculamos a segunda derivada em cada uma delas e somamos os resultados.

Δf = ∂²f/∂x² + ∂²f/∂y²

Em três dimensões, acrescentamos a segunda derivada na direção z.

Δf = ∂²f/∂x² + ∂²f/∂y² + ∂²f/∂z²

Então o Laplaciano permite comparar o comportamento da função ao redor de um determinado ponto.

·       Se Δf > 0, há uma tendência de o ponto estar numa região semelhante a uma depressão.

·       Se Δf < 0, há uma tendência de o ponto estar numa região semelhante a um pico.

·       Se Δf = 0, as curvaturas nas diferentes direções se compensam.

Considere a função f(x,y) = x² + y².

f(x,y) = x² + y²

As segundas derivadas são:

∂²f/∂x² = 2

∂²f/∂y² = 2

Logo, o Laplaciano é:

Δf = 2 + 2 = 4

O resultado positivo está relacionado ao fato de a superfície ter a forma de uma tigela, curvando-se para cima.

Essa é uma das razões pelas quais o Laplaciano é tão importante na Matemática aplicada e na Física.

O Laplaciano do grafo

Nos artigos anteriores desta série, vimos que os autovalores da matriz de adjacência A revelam quem é importante numa rede. Existe uma segunda matriz, derivada de A, que responde uma pergunta diferente: quão bem conectada é a rede como um todo, e o que acontece quando algo se propaga por ela.

Essa matriz é o Laplaciano do grafo.

Voltamos aqui ao tipo de rede não-direcionada dos primeiros artigos desta série (matrizes e centralidade), diferente das redes direcionadas que usamos nos artigos sobre PageRank. O Laplaciano, na forma que vamos usar, é definido especificamente para esse caso.

Para entender o Laplaciano de um grafo, vale olhar sob três perspectivas simultâneas: o que ele é (um objeto matemático), o que ele calcula quando aplicado a um estado da rede, e para que ele serve, na prática.

A definição

L = D - A

D é a matriz de grau, diagonal, onde a posição (i,i) é o grau do nó i. Fora da diagonal, L herda o padrão de −A: −1 onde existe link, 0 onde não existe.

O L que usamos nos nossos exemplos (a matriz D−A) é a versão discreta desse mesmo operador Δ (ou ∇²), adaptada para redes em vez de espaços contínuos.

Toda linha de L soma 0, o grau na diagonal sempre cancela exatamente os −1s dos vizinhos.

O Laplaciano, do jeito que definimos, L = D − A, só tem as propriedades bonitas que usamos o artigo inteiro (autovalores sempre reais, sempre maiores ou iguais a zero, λ₁ sempre igual a zero) porque estamos trabalhando com uma rede bidirecionada não-direcionada), onde a matriz A é simétrica (Aᵢⱼ = Aⱼᵢ). É essa simetria que sustenta a interpretação de conectividade algébrica.

Considere a mesma rede em caminho do primeiro artigo desta série, "Carla" ligada a "Ana", "Ana" ligada a "Bruno", "Bruno" ligado a "Diego". A matriz de grau tem 1, 2, 2, 1 na diagonal (os graus que já calculamos naquele artigo).

Para a rede em caminho "Carla"-"Ana"-"Bruno"-"Diego" (nessa ordem de linhas e colunas), a matriz de grau é:

E a matriz de adjacência, já vista no primeiro artigo desta série, é:

Subtraindo a matriz de adjacência:

Repare que cada linha de L soma exatamente 0. Isso não é coincidência, é uma propriedade que vale para qualquer Laplaciano, o grau de um nó (na diagonal) sempre cancela exatamente a soma dos -1 s dos seus vizinhos (fora da diagonal).

Os autovalores do Laplaciano

Resolvendo a equação característica dessa matriz (a demonstração completa, passo a passo, fica no artigo aqui ou, mais detalhado, no Volume I, para quem quiser conferir), chegamos aos quatro autovalores:

Para a rede que estamos usando no artigo, "Carla"-"Ana"-"Bruno"-"Diego" (o caminho de 4 nós), a conectividade algébrica é

Esse é o segundo menor autovalor do Laplaciano dessa rede, calculado tanto pelo polinômio característico quanto pelo atalho da fórmula fechada para caminhos, que já vimos.

Lembre que λ (lambda) é o símbolo genérico para "autovalor". Qualquer Laplaciano de rede tem vários autovalores, λ₁​, λ_2​, λ₃​, …, ordenados do menor para o maior.

Conectividade algébrica é o nome específico dado a um desses autovalores, o segundo menor da lista, λ₂​ (porque o ménor é sempre 0).

Os três termos, "λ₂​", "conectividade algébrica" e "valor de Fiedler", são sinônimos, usados de forma intercambiável na literatura, o mesmo número, três nomes diferentes.

O estado da rede num momento específico

Vamos separar dois objetos que aparecem juntos, mas que são coisas diferentes: a rede (a estrutura, quem se conecta com quem, representada pela matriz L e o estado da rede num momento específico (o que cada pessoa carrega, representado pelo vetor f).

f é um vetor, um número para cada nó

f não é uma fórmula, nem uma propriedade da rede em si. É simplesmente uma lista ordenada de números, um número por pessoa, na mesma ordem em que você numerou os nós da rede. Aqui:

f₁​=3 é a opinião da Carla, f₂​=4 é a opinião da Ana, f₃​=9 é a opinião do Bruno, f₄​=6 é a opinião do Diego.

A posição no vetor precisa coincidir com a posição usada para montar a matriz L, se Carla é a linha 1 de L, ela também precisa ser a primeira entrada de f, senão a conta Lf mistura pessoas erradas.

Notq que a matriz L é fixa, ela só depende de quem está ligado a quem (a estrutura da rede não muda de um dia para o outro). f, em contraste, é o que você escolhe medir sobre a rede, naquele momento específico. Poderia ser opinião sobre um assunto (o exemplo que estamos usando), mas poderia ser temperatura corporal, saldo bancário, tempo de tela no celular, qualquer grandeza que faça sentido atribuir um número a cada pessoa. A mesma rede, com a mesma matriz L, pode receber vetores f diferentes, dependendo do que você está analisando, e o resultado de Lf muda de acordo, mesmo que a rede continue sendo fisicamente a mesma.

Em suma, L responde "como essas pessoas estão conectadas". f responde "o que cada uma delas pensa, agora".

Lf combina as duas coisas, usando a estrutura de L para medir o quanto o estado f de cada pessoa diverge do estado f dos vizinhos dela, especificamente.

Lendo os resultados como detecção de influenciador

Suponha que cada pessoa tenha uma polaridade de opinião sobre um assunto, numa escala de 0 a 10:

Carla = 3 , Ana = 4, Bruno = 9 , Diego = 6.

Calculando Lf, pessoa por pessoa

Usando a fórmula

a soma das diferenças entre cada pessoa e seus vizinhos diretos:

Carla (só fala com Ana): 3 - 4 = -1

Ana (fala com Carla e Bruno):

Bruno (fala com Ana e Diego):

Diego (só fala com Bruno): 6 - 9 = -3

Bruno: +8, o maior valor da rede, e de longe. Sua opinião (9) é muito mais extrema que a média dos dois vizinhos dele (Ana em 4 , Diego em 6, média 5 ). Numa rede social real, esse é exatamente o perfil que o Laplaciano identifica como formador de opinião, ou dissidente influente, alguém puxando a conversa com força na própria direção, destoando de quem está ao redor.

Ana: −4, a mais moderada. Ela está entre dois valores mais altos que o dela (Carla em 3, mas principalmente Bruno em 9 ), então sua opinião é "puxada para cima" pela vizinhança, um alvo de influência, não uma fonte.

Carla e Diego: −1 e −3. Como têm um único vizinho cada, o valor deles reflete só essa relação direta, Carla é ligeiramente mais moderada que Ana (diferença pequena, −1), Diego é bem mais moderado que Bruno (diferença maior, −3), coerente com Bruno ser o polo mais extremo da rede inteira.

A soma dá exatamente zero. Isso não é coincidência deste exemplo, é uma propriedade geral, Lf sempre soma zero, porque cada "unidade de desacordo" que sai de um nó entra como "unidade de desacordo" em outro, o desacordo se redistribui pela rede, não se cria nem se destrói.

Se você trocasse "opinião" por "polaridade de tweets" numa rede real do Twitter, o mesmo cálculo, aplicado a milhares de contas, destacaria como "Bruno" as contas com o maior (Lf) positivo, exatamente as que empurram a conversa contra a maré da própria vizinhança de seguidores, o sinal matemático de um formador de opinião ativo, não passivo.

Abaixo temos quatro topologias clássicas, lado a lado, todas com o mesmo número de nós, para ver, de forma direta, como a estrutura muda a conectividade algébrica.

Como enfatizamos, λ₂​ é o primeiro autovalor que realmente varia de acordo com a estrutura da rede, e ele mede especificamente quão robusta, ou quão fácil de fragmentar, é a rede inteira, como já vimos na comparação entre topologias (caminho, ciclo, estrela, completo) e no exemplo da rede com gargalo.

Fica claro o caminho (λ₂​=0,268, o mais frágil) até o grafo completo (λ₂​=6,000, o mais robusto), passando por ciclo e estrela, empatados em 1,000.

Onde isso fica visível

Comparando com a rede de dois clusters densos ligados por um nó ponte, já usada no artigo sobre autovetor, vale trazer de volta a tabela daquele artigo, lado a lado com a informação nova, para deixar clara a diferença de natureza entre elas.

Nó	Grau	Intermediação	Autovetor (adjacência)	Autovetor de Fiedler
Nós internos do grupo 1 (1, 2, 3)	3	0,000	0,462	0,371
Conector do grupo 1 (nó 4)	4	0,536	0,514	0,294
Ponte	2	0,571 (o maior de todos)	0,215	≈0,000
Conector do grupo 2 (nó 5)	4	0,554	0,156	−0,294
Nós internos do grupo 2 (6, 7, 8)	2 a 3	0,000 a 0,018	0,083 a 0,104	−0,371

Conectividade algébrica da rede inteira: λ₂ ≈ 0,209

Diferente da intermediação e do autovetor de adjacência, calculados nó por nó, a conectividade algébrica é a primeira métrica desta série que descreve a rede inteira com um único número, não cada nó individualmente. Repare na última coluna: todo o grupo 1 recebe valores positivos, todo o grupo 2 recebe valores negativos, e a ponte fica quase exatamente em zero, no meio dos dois lados (figura abaixo). É o autovetor de Fiedler fazendo, sozinho, o trabalho de separar a rede em dois grupos coesos, só olhando o sinal de cada entrada, o mecanismo que vamos formalizar no próximo artigo, sobre comunidades.

λ₂​≈0,209, bem menor que o 0,586 do caminho anterior. Remover o nó "ponte" desconecta a rede inteira, e o Laplaciano sinaliza essa fragilidade sem precisar remover nada, só pelo valor de λ₂​. Numa dinâmica de opinião, isso significa que, mesmo com tempo suficiente, os dois clusters demoram muito mais para entrar em consenso um com o outro, porque toda a informação precisa atravessar o único gargalo entre eles.

Onde isso se conecta com o mundo real (e com Machine Learning)?

1. Câmaras de Eco (Echo Chambers): Se todos os quatro tivessem a mesma opinião, o cálculo daria (Lf) = 0 para todo mundo. Isso significa que ninguém destoa. A rede está em equilíbrio (consenso). Esse é o sinal matemático de uma bolha ou câmara de eco: todo mundo repete o mesmo discurso, e não há fluxo de opinião contrária. O Laplaciano captura isso perfeitamente.

2. Detecção de Anomalia (Fraude): Troque "opinião" por "valor médio de transação em reais" em uma conta bancária. Se uma conta tem um fluxo de dinheiro muito maior que a média das contas que se conectam a ela (vizinhos), o Laplaciano vai gerar um pico positivo gigante. Esse pico é exatamente o que um sistema anti-fraude usa para sinalizar uma conta suspeita (um hub de lavagem de dinheiro) que não se comporta como a vizinhança dela.

Continue essa jornada matemática

No próximo artigo, "Comunidades em redes: a matemática de dividir sem perder informação", os autovetores do Laplaciano particionam uma rede em grupos coesos, um problema aparentemente combinatório resolvido em álgebra linear.

No Volume III, Teoria das Redes, desenvolvo esse assunto com mais profundidade, incluindo sua versão normalizada. No Volume V, Dinâmica e Fractais, a mesma matriz sustenta sistemas de difusão e sincronização.

[Link para o Volume III]