Skip to content
Voltar aos resultados

Detecção de Comunidades — Agrupamento de Grafos em Redes

Proposto por
Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
Ano
2002–2019 (algorithm family)
Tipo
Graph-partitioning / clustering algorithm family

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A detecção de comunidades é uma família de algoritmos de particionamento de grafos que descobrem subgrupos densamente conectados — comunidades — dentro de uma rede.

Formalizado pela primeira vez através da medida de modularidade por Girvan e Newman (2002), o campo avançou rapidamente com o método Louvain (Blondel et al., 2008), o refinamento Leiden (Traag et al., 2019) e a abordagem informacional Infomap. Todas as variantes respondem à mesma pergunta: quais nós se agrupam mais intimamente entre si do que com o resto da rede?

A intuição por trás do método

Imagine uma grande rede social onde algumas pessoas falam principalmente com seu círculo imediato, enquanto ocasionalmente se comunicam com o exterior. A detecção de comunidades encontra esses círculos automaticamente, sem que você precise rotulá-los antecipadamente. O algoritmo reorganiza os nós em grupos de modo que as conexões internas sejam densas e as conexões entre grupos sejam esparsas — maximizando uma pontuação de qualidade chamada modularidade (ou, no Infomap, minimizando o comprimento de descrição de uma caminhada aleatória pela rede). O resultado é um particionamento: cada nó pertence a exatamente uma comunidade, e você pode visualizar a rede como um conjunto de clusters coesos.

História

O estudo da estrutura de comunidades em redes foi colocado em uma base quantitativa por Girvan e Newman (2002), que introduziram o conceito de centralidade de intermediação como uma ferramenta para divisão hierárquica de redes. Newman e Girvan (2004) então formalizaram a medida de modularidade Q, que se tornou o critério de qualidade padrão. Blondel et al. (2008) publicaram o método Louvain — uma otimização gulosa em duas fases que tornou a detecção de comunidades de alta qualidade prática em redes com milhões de nós. Traag, Waltman e van Eck (2019) identificaram uma falha estrutural no Louvain — que ele pode produzir comunidades internamente desconectadas — e desenvolveram o algoritmo Leiden para corrigi-lo, garantindo particionamentos bem conectados. Em paralelo, Rosvall e Bergstrom (2008) desenvolveram Infomap, que reformula a detecção de comunidades como um problema de compressão: encontre o particionamento que minimiza o comprimento de descrição de uma caminhada aleatória na rede.

Quando usar

A detecção de comunidades é apropriada quando você tem uma rede (no mínimo ~20 nós) e deseja descobrir estrutura de grupo latente sem pré-especificar os grupos. Adapta-se a objetivos exploratórios, descritivos e de classificação em dados de arestas binárias ou contínuas, incluindo dados de rede transversais e longitudinais. Não requer atributos de nó ou distribuições normais. O método é particularmente adequado quando o número de comunidades é desconhecido. Se a rede for muito pequena (menos de 20 nós), estatísticas descritivas de rede são preferíveis. Os resultados são sensíveis às definições de peso das arestas e à densidade da rede, portanto, essas escolhas merecem reflexão cuidadosa.

Limitações e considerações

  • A maximização da modularidade é suscetível a ótimos locais; os resultados podem variar entre execuções e devem ser relatados como o melhor de múltiplas execuções.
  • O limite de resolução significa que comunidades muito pequenas em redes grandes podem ser mescladas, mascarando a estrutura de grão fino.
  • Os resultados são sensíveis a como os pesos das arestas são definidos; diferentes esquemas de ponderação podem produzir particionamentos significativamente diferentes.
  • Girvan-Newman tem complexidade O(m²n) e é impraticável em redes grandes; Louvain ou Leiden devem ser preferidos para escala.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Não requer que o número de comunidades seja especificado antecipadamente — o tamanho do particionamento é determinado pelos dados.
  • Escala para redes grandes: Louvain e Leiden executam em tempo quase linear, tornando-as práticas para redes com milhões de nós.
  • Leiden garante comunidades internamente coesas e bem conectadas, corrigindo a falha de comunidades desconectadas do Louvain.
  • Aplicável a redes não ponderadas e ponderadas sem suposições de distribuição sobre os dados.

Aplicações

  • Identificar clusters de pesquisa em redes de citação e coautoria para mapear campos científicos.
  • Detectar módulos funcionais em redes de interação proteína-proteína em biologia.
  • Encontrar comunidades de usuários em redes sociais e de comunicação para análise comportamental.
  • Segmentar redes de clientes em negócios e marketing para revelar grupos coesos de clientes.
  • Descobrir blocos estruturais em redes de infraestrutura, transporte ou cadeia de suprimentos.

Como funciona

Como funciona

1

A entrada é um grafo cujos nós representam entidades (pessoas, páginas da web, proteínas, citações) e cujas arestas representam relacionamentos entre elas. As arestas podem ser direcionadas ou não direcionadas e podem ter pesos. A estrutura de adjacência — quais nós estão conectados e com que intensidade — é a única entrada que os algoritmos necessitam. Nenhum rótulo de nó, classe ou atributo externo é necessário, embora possam ser usados para validar os resultados posteriormente.

2

Cada algoritmo começa com uma atribuição inicial de nós a comunidades. Em Louvain e Leiden, cada nó começa como sua própria comunidade singleton. Girvan-Newman começa com a rede completa e remove iterativamente a aresta com a maior centralidade de intermediação, revelando progressivamente a estrutura da comunidade. Infomap começa a partir de uma descrição de caminhada aleatória da rede e a codifica usando um mapa de dois níveis para minimizar o comprimento do código.

3

A fase central busca um particionamento que maximize a modularidade Q (Louvain, Leiden) ou minimize o comprimento do código da equação do mapa (Infomap). Louvain move gananciosamente nós únicos entre comunidades para melhorar Q, então agrega comunidades em super-nós e repete — um processo de duas fases que escala bem, mas pode produzir comunidades desconectadas. Leiden refina Louvain garantindo que cada comunidade seja internamente conectada, usando um passo local de movimento e refinamento antes da agregação. Girvan-Newman remove arestas iterativamente e registra o dendrograma de divisões; o particionamento que maximiza Q em qualquer corte do dendrograma é selecionado. O número de comunidades emerge do próprio algoritmo; não precisa ser especificado antecipadamente.

4

A qualidade do particionamento final é resumida pela pontuação de modularidade Q, que varia de −0.5 a 1. Valores acima de ~0.3–0.5 são geralmente considerados indicativos de uma estrutura de comunidade significativa. Como a otimização da modularidade pode ficar presa em ótimos locais, executar o algoritmo várias vezes e pegar o melhor resultado é uma prática padrão. O particionamento também é inspecionado visualmente e validado cruzadamente contra quaisquer atributos de nó disponíveis ou rótulos de verdade fundamental para confirmar que é substancialmente significativo.

Erros comuns

  • Executar o algoritmo uma vez e tratar o único resultado como verdade fundamental — sempre execute várias vezes e relate a melhor modularidade ou use métodos de ensemble.
  • Ignorar o limite de resolução: em redes esparsas grandes, comunidades pequenas, mas reais, podem ser absorvidas em outras maiores sem aviso.
  • Aplicar algoritmos baseados em modularidade a redes com menos de 20 nós — a estrutura da comunidade não pode ser identificada de forma confiável nessa escala.
  • Confundir uma alta pontuação de modularidade com estrutura de comunidade confirmada no mundo real; a modularidade é uma medida de qualidade do particionamento, não um teste inferencial se as comunidades são estatisticamente significativas.

Perguntas frequentes

Qual algoritmo devo escolher — Louvain, Leiden, Girvan-Newman ou Infomap?

Louvain é uma linha de base rápida e amplamente utilizada para redes grandes. Leiden é a escolha preferida quando a correção é importante, pois garante comunidades internamente conectadas e geralmente atinge maior modularidade. Girvan-Newman produz um dendrograma útil para exploração hierárquica, mas é muito lento para redes grandes. Infomap é adequado para redes direcionadas ou baseadas em fluxo onde o caminho que um caminhante aleatório percorre é significativo.

Preciso especificar o número de comunidades antecipadamente?

Não. Louvain, Leiden e Infomap determinam o número de comunidades automaticamente a partir da estrutura da rede. Girvan-Newman produz um dendrograma completo a partir do qual qualquer número de comunidades pode ser lido; o particionamento que maximiza Q é geralmente selecionado.

Como sei se as comunidades encontradas são significativas?

A pontuação de modularidade Q fornece uma medida de qualidade interna dos dados; valores acima de aproximadamente 0.3–0.5 sugerem uma estrutura de comunidade não trivial. Além disso, as comunidades devem ser validadas contra conhecimento de domínio, atributos de nó ou rótulos externos. Um Q alto por si só não prova significância sociológica ou biológica.

O que acontece se os resultados diferirem entre as execuções?

A otimização da modularidade é uma heurística e execuções diferentes podem produzir particionamentos ligeiramente diferentes, especialmente em Louvain. Execute o algoritmo várias vezes (pelo menos 10–100 execuções em redes grandes) e relate o particionamento com o maior Q. Leiden é mais estável que Louvain porque seu passo de refinamento é mais completo, mas execuções repetidas continuam sendo uma boa prática.

Métodos relacionados

Fontes

  1. Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.

    Abrir referência DOI
    Copiado.
  2. Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.

    Abrir referência da publicação
    Copiado.