3 - Grafos e Machine Learning: Centralidades e Autovetores

Existe uma pergunta que parece ingênua, mas esconde toda a matemática por trás do Google: quem são minhas conexões?

Não "quantas conexões eu tenho", isso é fácil de responder, e é exatamente o que a centralidade de grau mede. A pergunta mais rica, e mais difícil, está escondida numa armadilha lógica: para saber o quão importante você é, preciso saber o quão importantes são suas conexões. Mas para saber o quão importantes são suas conexões, preciso saber o quão importantes são as conexões delas. E assim por diante, infinitamente.

Centralidade de Grau e Intermediação

Como vimos no artigo 1 desta série, a forma mais simples de medir importância de um nó é contar conexões, a centralidade de grau:

C_D(x) = grau(x) / (N − 1)

onde:

• C_D(x): centralidade de grau do nó x

• grau(x): número de links conectados ao nó x

• N: número total de nós

A centralidade de grau mede a importância ou influência de um nó com base no número de links diretos que ele possui com outros nós na rede. Em redes sociais, ela representa popularidade, o número de seguidores diretos ou contatos.

Uma celebridade pode ter uma centralidade de grau extremamente alta: milhões de conexões diretas que permitem que a informação se espalhe instantaneamente. No entanto, isso não significa que ela é a posição mais estrategicamente importante, apenas que é altamente conectada. O posicionamento estratégico em uma rede não diz respeito apenas ao número de conexões.

Outras medidas, como a centralidade de intermediação (betweenness centrality), capturam quão bem um nó conecta diferentes grupos ou a rapidez com que pode alcançar todos os outros.

Na figura, uma pessoa com menos conexões (B), mas posicionada como uma ponte entre comunidades, pode ser mais influente na formação dos fluxos de informação.

Centralidade de autovetor (eigenvector)

A centralidade de intermediação trata todos os links igualmente, mesmo que se conectem a nós irrelevantes. A centralidade de autovetor resolve isso ponderando as conexões: um nó conectado a nós influentes ganha pontuação mais alta, recursivamente, sua importância depende da importância de seus vizinhos.

Na parte 1 desta série vimos que uma matriz de adjacência é uma forma de representar uma rede inteira como uma tabela de números: se a rede tem N nós, a matriz A tem tamanho N × N, e cada posição A_ij indica se existe uma conexão entre o nó i e o nó j, tipicamente 1 se existe um link, 0 caso contrário.

Para a rede de três nós abaixo (nó 1 conectado a 2 e 3; nós 2 e 3 sem conexão entre si), a matriz de adjacência é:

Lendo a primeira linha: o nó 1 (A_11 = 0, não conecta consigo mesmo) se conecta ao nó 2 (A_12 = 1) e ao nó 3 (A_13 = 1). A segunda linha mostra que o nó 2 só se conecta ao nó 1 (A_21 = 1), e assim por diante.

Repare que essa matriz é simétrica (A_ij = A_ji) porque a rede não é direcionada, cada link vale nos dois sentidos. Em redes direcionadas (como veremos no PageRank), essa simetria desaparece: um link de A para B não implica um link de B para A, e a matriz reflete isso diretamente.

Aqui entramos no que é o coração de toda uma área da álgebra linear chamada autovalores e autovetores (eigenvectors e eigenvalues), com aplicações que vão muito além de redes (aparece em física, em sistemas dinâmicos, em reconhecimento de padrões). Desenvolvi a intuição completa por trás disso, com a dedução matemática passo a passo, num artigo à parte: "O Que Significa Multiplicar um Vetor e Ele Não Mudar de Direção?", vale a leitura complementar se quiser entender o mecanismo por completo.

Para essa rede de três nós, resolver a equação de autovalor Av = λv dá o autovetor (já normalizado):

Um exemplo mais revelador: quando "ser a ponte" e "ter alta centralidade de autovetor" discordam

O exemplo anterior, com apenas três nós, tinha uma coincidência estrutural que confundia a interpretação: o nó de maior grau também era, por acaso, o único caminho entre os outros dois. Isso fazia parecer que "ser conector" e "ter alta centralidade de autovetor" fossem a mesma coisa. Não são. Vale um exemplo onde essas duas propriedades se separam claramente, e onde nem os próprios conectores são iguais entre si.

Considere dois grupos de quatro nós cada, ligados por um único nó ponte. O grupo da esquerda é totalmente conectado, todo mundo conhece todo mundo dentro dele. O grupo da direita tem exatamente a mesma quantidade de nós, mas falta uma conexão interna, é um pouco menos denso.

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

A Ponte, de novo, tem a maior centralidade de intermediação da rede inteira, o único caminho entre os dois grupos. Mas sua centralidade de autovetor (0,215) fica no meio da tabela, nem a maior nem a menor, porque depende só de dois vizinhos, e um deles (o nó 5) não é particularmente bem cercado.

Um detalhe que vale destacar na tabela: o grupo 1 (nós 1, 2, 3) tem intermediação uniformemente 0,000 para todos, mas o grupo 2 (nós 6, 7, 8) tem um intervalo, de 0,000 a 0,018. Essa diferença não é ruído, ela revela algo estrutural sobre os dois grupos.

O grupo 1 é um grafo completo, todo nó tem link direto com todos os outros. Isso significa que o caminho mais curto entre qualquer par de nós do grupo tem comprimento 1, a aresta direta, sem nunca precisar passar por um terceiro nó. Como ninguém nunca é o único caminho entre dois vizinhos, ninguém intermedeia nada, e a intermediação de todos fica em 0.

O grupo 2 é quase idêntico, mas falta um único link, entre os nós 7 e 8. Essa ausência muda tudo. O caminho mais curto entre 7 e 8 deixa de ser direto, e passa a precisar de um nó intermediário. Dois candidatos servem igualmente bem: 7→6→8 e 7→5→8, ambos de comprimento 2. Como os dois caminhos são igualmente curtos, o crédito de intermediação para o par (7, 8) se divide meio a meio entre quem está em cada rota, o nó 6 e o conector, nó 5. Essa fração pequena, normalizada pelo total de pares possíveis na rede inteira, é o que produz o valor 0,018 do nó 6.

Já os nós 7 e 8, mesmo sendo as pontas da conexão que falta, continuam com intermediação exatamente 0. Eles nunca aparecem como o nó "do meio" de nenhum caminho, para chegar a 7 ou a 8 a partir de qualquer outro ponto da rede sempre existe uma rota que não depende de passar por um deles primeiro.

A intermediação 0,0 não é a condição natural de "ter poucas conexões", é a condição de "sempre existir uma rota alternativa igualmente curta que não depende de mim". Um único link faltando, em qualquer lugar da rede, já é suficiente para quebrar essa garantia em algum nó, mesmo dentro de um grupo que parecia tão denso e simétrico quanto o primeiro.

O ponto mais revelador está nos nós 4 e 5. Os dois têm exatamente o mesmo grau, 4 conexões cada, e centralidade de intermediação parecida (0,536 e 0,554). Se a pergunta fosse só "quantas conexões diretas", esses dois nós seriam, para efeitos práticos, equivalentes. Mas o autovetor de 4 é mais de três vezes maior que o de 5, 0,514 contra 0,156. A diferença não está no nó em si, está na vizinhança dele. O grupo à esquerda é um grafo completo, cada vizinho de 4 também está bem conectado aos outros vizinhos, o que amplifica a pontuação de todos ao mesmo tempo, num ciclo de reforço mútuo. O grupo à direita, com um único link a menos, já perde parte desse reforço, e isso se propaga para o valor de 5.

É esse o ponto central da centralidade de autovetor: não basta ter conexões, e não basta nem ter o mesmo número de conexões que outro nó. É preciso que essas conexões, por sua vez, estejam bem conectadas entre si. Intermediação mede posição estratégica no fluxo entre partes da rede, mesmo com poucas conexões. Autovetor mede o quanto você está cercado de vizinhos importantes, e "importante", aqui, é uma propriedade que se propaga de vizinho em vizinho, não que se conta isoladamente.

Continue essa jornada matemática

Na Parte 4 desta série, vamos ver como o Google adaptou essa mesma centralidade de autovetor para lidar com redes direcionadas, dando origem ao PageRank.

No Volume III, Redes, da coleção Matemática para o Século XXI, desenvolvo essas medidas de centralidade com mais profundidade.