Resumo — O que torna um nó “importante” em um grafo? A resposta não é única. Depende do que você quer medir. Um nó pode ser popular (alto Grau), ser uma “ponte” crítica (alta Betweenness) ou ter “influência” recursiva (alto PageRank). Escolher a métrica errada de centralidade pode levar a decisões de negócio desastrosas. Este post é um guia fundamental sobre as principais medidas de centralidade e, o mais importante, quando usar cada uma.
1. “Importância” é Relativa
Em análise de redes, “centralidade” é a palavra técnica para “importância”. Mas assim como no mundo real, a importância pode significar coisas diferentes:
- O influencer com mais seguidores é importante? (Sim, Grau).
- A pessoa quieta que conecta dois departamentos que não se falam é importante? (Sim, Betweenness).
- A pessoa que é amiga de outras pessoas importantes é importante? (Sim, PageRank).
Vamos quebrar as quatro medidas de centralidade mais essenciais.
2. As Quatro Medidas de Centralidade Essenciais
A. Grau (Degree Centrality)
A Intuição: A medida mais simples de “popularidade”. É, literalmente, a contagem de conexões (arestas) que um nó possui.
O Conceito Técnico: É uma medida puramente local. O nó não sabe nada sobre o resto do grafo, apenas sobre seus vizinhos imediatos. Em grafos dirigidos (como o Twitter), ela se divide em:
- In-Degree (Grau de Entrada): Quantas arestas apontam para o nó. (ex: Quantos seguidores você tem).
- Out-Degree (Grau de Saída): Quantas arestas saem do nó. (ex: Quantas pessoas você segue).
Quando usar: Para encontrar “hubs” locais e identificar popularidade imediata. É rápido, barato e ótimo como um primeiro filtro.
B. Betweenness (Centralidade de Intermediação)
A Intuição: Esta medida não se importa com quantas conexões você tem. Ela mede o quanto você atua como uma “ponte” entre outros nós. Se você é a única conexão entre dois grandes grupos de amigos, você tem alta betweenness. Remover você “quebraria” o grafo.
O Conceito Técnico: A Betweenness Centrality de um nó é a contagem de quantas vezes ele aparece nos caminhos mais curtos (shortest paths) entre todos os outros pares de nós na rede. É uma medida de “gargalo” ou “fluxo de informação”.
Quando usar: Para encontrar pontos únicos de falha, gargalos de comunicação, ou mediadores críticos em uma rede (ex: em detecção de fraude, o “laranja” que conecta vários esquemas).
C. Closeness (Centralidade de Proximidade)
A Intuição: Mede quão “rápido” um nó consegue alcançar todos os outros nós na rede. Um nó com alta closeness é um bom “centro de transmissão”, pois a informação que sai dele se espalha rapidamente para todo mundo.
O Conceito Técnico: É o inverso da soma da distância de um nó para todos os outros nós.
Armadilha: A closeness tradicional quebra em grafos desconexos (pois a distância para um componente separado é infinita). Por isso, na prática, quase sempre usamos a Closeness Harmônica, que lida bem com grafos desconexos.
Quando usar: Para identificar os melhores “difusores” de informação em uma rede conectada (ex: escolher o “paciente zero” ideal para uma campanha de marketing viral).
D. PageRank (Centralidade de Importância Recursiva)
A Intuição: A ideia genial de que “não é sobre quantos amigos você tem, é sobre quem são seus amigos”. Ter uma conexão de uma pessoa muito importante (um nó de alto score) vale mais do que 10 conexões de nós irrelevantes. É uma medida de “influência” ou “autoridade”.
O Conceito Técnico: O PageRank (como vimos em detalhes no nosso post sobre o Google) é uma variante da Centralidade de Eigenvector. Ele calcula a importância de forma recursiva. A grande sacada do PageRank é adicionar o “fator de teleporte” (controlado por
Quando usar: Para encontrar a “autoridade” ou “influência” global em um grafo dirigido (ex: rankear páginas na web, artigos científicos por citação, ou contas mais influentes no Twitter).
3. Tabela Resumo: Quando Usar Cada Métrica
| Métrica | Pergunta que Responde | Exemplo de Caso de Uso |
| Grau (Degree) | Quem é o mais popular localmente? | Identificar o “influenciador” mais visível (com mais seguidores). |
| Betweenness | Quem é a ponte ou gargalo mais crítico? | Encontrar o intermediário (“laranja”) em uma rede de lavagem de dinheiro. |
| Closeness | Quem consegue espalhar informação mais rápido? | Escolher o ponto de partida ideal para uma campanha de marketing viral. |
| PageRank | Quem é a autoridade ou influenciador global? | Rankear páginas na web (Google) ou artigos científicos (citações). |
4. Armadilhas de Engenharia: Custo e Aproximações
Não podemos simplesmente rodar todas as métricas em qualquer grafo. Elas têm custos computacionais drasticamente diferentes:
- Grau: É extremamente barata de calcular (complexidade
ou`, dependendo da representação).
- PageRank: É rápida. Usa o método de power iteration, que converge em poucas passadas e escala muito bem.
- Closeness (Harmônica): É cara. Ela requer o cálculo dos caminhos mais curtos de cada nó para todos os outros (ex: rodando um BFS a partir de cada nó), o que em grafos não ponderados tem complexidade de
- Betweenness: É extremamente cara. O cálculo exato tem complexidade de
Regra de bolso: Nunca rode Betweenness ou Closeness exata em um grafo com mais de algumas dezenas de milhares de nós. Em grafos grandes (milhões/bilhões de nós), usamos aproximações, que estimam os scores “amostrando” um subconjunto de nós ou caminhos, em vez de calcular todos eles.
Conclusão
“Importância” não é um conceito único. Escolher a métrica de centralidade errada pode levar a conclusões erradas. Antes de calcular, pergunte-se: estou procurando a popularidade local (Grau), o gargalo (Betweenness), o difusor rápido (Closeness) ou a autoridade recursiva (PageRank)? A resposta a essa pergunta definirá o sucesso da sua análise de rede.
Referências
- Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry.
- Bonacich, P. (1987). Power and centrality: A family of measures. American Journal of Sociology.
- Brin, S., & Page, L. (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. WWW.
- Newman, M. E. J. (2018). Networks. Oxford University Press. (Um livro-texto fundamental sobre o assunto).
Sobre o autor
Rener Menezes
Cofundador & CTO — FitBank
Rener Menezes é cofundador e CTO do FitBank, fintech brasileira de Banking-as-a-Service. Com mais de 25 anos de experiência projetando sistemas financeiros em larga escala, é bacharel em Sistemas de Informação e mestrando na Unifor, onde pesquisa Redes Neurais de Grafos e aprendizado por reforço para detecção de fraude. Interesses: sistemas distribuídos, infraestrutura de pagamentos e graph ML.
Links: LinkedIn · ORCID · contato@grafolab.ia.br
Deixe uma resposta