Skip to content
Voltar aos resultados

Modelo de Bloco Estocástico — Detecção Probabilística de Comunidades em Redes

Ano
1983
Tipo
Probabilistic generative graph model

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?

O Modelo de Bloco Estocástico (SBM), introduzido por Holland, Laskey e Leinhardt (1983), é um modelo generativo probabilístico para grafos que atribui nós a blocos latentes e estima parametricamente as probabilidades de conexão entre os blocos.

É a abordagem fundamental para detecção de comunidades, identificação de núcleo-periferia e descoberta de estrutura hierárquica na análise de redes.

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

Imagine uma rede social onde as pessoas se agrupam — colegas, família, times esportivos — e as conexões dentro de um grupo são mais prováveis do que as conexões entre grupos. O Modelo de Bloco Estocástico formaliza essa intuição: ele assume que existe um rótulo de grupo oculto para cada nó, e que a probabilidade de uma aresta entre quaisquer dois nós depende apenas a quais grupos esses dois nós pertencem. Ajustar o modelo significa encontrar os rótulos ocultos que melhor explicam o padrão de arestas observado. O resultado é uma partição fundamentada e estatisticamente sólida da rede em blocos, sem a necessidade de que os grupos sejam cliques densas — o modelo acomoda estruturas de núcleo-periferia e até mesmo padrões disassortativos onde as conexões intergrupos excedem as intragrupos.

História

O Modelo de Bloco Estocástico foi introduzido por Holland, Laskey e Leinhardt em seu artigo de 1983 na Social Networks como uma generalização probabilística de trabalhos anteriores de modelagem de blocos na análise de redes sociais. Por duas décadas, permaneceu principalmente uma ferramenta teórica; ganhou força prática com o desenvolvimento de algoritmos de inferência escaláveis — EM variacional e MCMC — nos anos 2010. O SBM Corrigido por Grau foi introduzido por Karrer e Newman (2011) para abordar o problema da heterogeneidade de grau. A revisão de Lee e Wilkinson de 2019 na Applied Network Science consolidou a família de extensões, cobrindo modelos de partição plantada, SBM de associação mista e variantes hierárquicas. Hoje, o SBM e seus descendentes são o arcabouço probabilístico de referência para detecção de comunidades e agrupamento de grafos.

Quando usar

Use o Modelo de Bloco Estocástico quando você tem uma rede com pelo menos 50 nós e deseja descobrir uma estrutura de grupo latente sem assumir que os grupos devem ser cliques densas. É apropriado para grafos direcionados ou não direcionados, ponderados ou não ponderados, e adequado para tarefas exploratórias, bem como de classificação. A variante DCSBM é preferida quando os graus dos nós variam substancialmente. Se o grafo tiver menos de 20 nós, a estrutura da comunidade não pode ser estimada de forma confiável e métricas descritivas mais simples devem ser usadas. Premissas: as associações de bloco são latentes e não observadas; a matriz de conexão de bloco é assumida homogênea dentro de cada par de blocos; e K deve ser selecionado por BIC ou fator Bayes, em vez de fixado arbitrariamente.

Limitações e considerações

  • Requer pelo menos cerca de 50 nós para uma estimativa de bloco confiável; grafos muito pequenos produzem soluções instáveis.
  • A inferência é computacionalmente cara para grafos grandes: EM variacional ou MCMC é necessário, e a convergência não é garantida.
  • A suposição de homogeneidade do SBM básico dentro dos pares de blocos falha quando as taxas de conexão dentro do bloco variam — o DCSBM atenua, mas não elimina isso.
  • A seleção de blocos via BIC ou fator Bayes ainda pode sub- ou super-segmentar se o grafo tiver comunidades fracamente separadas.

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

  • Estrutura probabilística fundamentada que permite a seleção de modelos via BIC ou fator Bayes, evitando escolhas arbitrárias de parâmetros.
  • Acomoda uma ampla gama de padrões estruturais — comunidades, núcleo-periferia, bipartidos e hierárquicos — além da suposição de clique densa de métodos algorítmicos.
  • A variante Corrigida por Grau lida com grafos com distribuições de grau heterogêneas e hubs sem distorcer as atribuições de bloco.
  • Fornece probabilidades de associação posteriores, permitindo atribuições de nós "suaves" ou incertas, em vez de partições "rígidas".

Aplicações

  • Detecção de comunidades de pesquisa em redes de citação e colaboração nas ciências sociais e naturais.
  • Identificação de módulos funcionais em redes biológicas, como interação proteína-proteína e grafos de coexpressão gênica.
  • Descoberta de segmentos de clientes ou anéis de fraude em redes transacionais e financeiras.
  • Caracterização da estrutura núcleo-periferia em redes de comércio interorganizacionais ou entre países.
  • Benchmarking e avaliação de outros algoritmos de detecção de comunidades usando grafos sintéticos gerados por SBM como "verdade fundamental".

Como funciona

Como funciona

1

O analista especifica um intervalo candidato para o número de blocos K e escolhe uma variante: o SBM básico assume distribuição de grau homogênea dentro do bloco, enquanto o SBM Corrigido por Grau (DCSBM) adiciona parâmetros de grau em nível de nó para lidar com hubs e sequências de grau heterogêneas. A escolha da variante é informada pela distribuição de grau do grafo observado.

2

Dada a matriz de adjacência, o modelo estima as associações de bloco e uma matriz K×K de probabilidades de conexão usando um algoritmo de inferência. Para grafos pequenos a médios, a maximização exata é viável; para grafos grandes, a Expectation-Maximisation variacional (EM variacional) ou a amostragem por Monte Carlo via Cadeias de Markov (MCMC) são usadas para tornar a inferência tratável.

3

O número de blocos K não é conhecido antecipadamente e deve ser escolhido a partir dos dados. Os critérios de seleção preferidos são o Critério de Informação Bayesiano (BIC) e o fator Bayes, ambos penalizam a complexidade do modelo e selecionam o K que melhor equilibra o ajuste com a parcimônia. O princípio do comprimento mínimo de descrição (MDL) fundamenta a implementação em graph-tool.

4

Uma vez que o K ótimo e as atribuições de bloco são determinados, a matriz de conexão de blocos é inspecionada para caracterizar a estrutura: blocos assortativos correspondem a comunidades, blocos disassortativos a padrões bipartidos, e perfis mistos a arranjos de núcleo-periferia. As associações de nós são relatadas com probabilidades posteriores onde o algoritmo de inferência as fornece.

Erros comuns

  • Fixar K arbitrariamente, em vez de selecioná-lo por BIC ou fator Bayes, produz partições não confiáveis — sempre use um critério de seleção de modelo fundamentado.
  • Aplicar o SBM básico a um grafo com uma sequência de graus heterogênea (hubs, distribuição de grau de lei de potência) infla as estimativas de contagem de blocos; use DCSBM em vez disso.
  • Tratar a associação de bloco como certa quando a posterior é difusa superestima a confiança — relate a incerteza quando disponível.
  • Confundir a saída do SBM com comunidades de "verdade fundamental": o modelo encontra uma estrutura latente estatisticamente plausível, não necessariamente grupos sociologicamente significativos. Valide com o conhecimento do domínio.
  • Executar o SBM em menos de 20 nós produz soluções degeneradas — recorra a métricas descritivas de rede ou detecção de comunidade simples para grafos pequenos.

Perguntas frequentes

Como o Modelo de Bloco Estocástico difere da detecção de comunidades baseada em modularidade?

A maximização da modularidade (por exemplo, Louvain, Leiden) otimiza um objetivo heurístico que implicitamente assume comunidades assortativas, de tamanhos aproximadamente iguais, e tem um limite de resolução conhecido que impede a detecção de comunidades pequenas. O SBM é um modelo probabilístico generativo com suposições explícitas; a contagem de blocos é escolhida por seleção de modelo (BIC ou fator Bayes) em vez de otimização heurística, e pode detectar estruturas disassortativas e de núcleo-periferia que os métodos baseados em modularidade perdem.

Quando devo usar o DCSBM em vez do SBM básico?

Use o DCSBM quando a distribuição de grau dos nós for heterogênea — por exemplo, quando um pequeno número de hubs responde por uma grande fração das arestas, ou quando a sequência de graus segue uma lei de potência aproximada. O SBM básico trata todos os nós dentro de um bloco como intercambiáveis, o que faz com que os hubs sejam puxados para seus próprios blocos espúrios. O DCSBM adiciona um termo de correção de grau que separa a posição estrutural do grau, produzindo atribuições de bloco mais interpretáveis em tais grafos.

Como escolho o número de blocos K?

Ajuste modelos para uma gama de valores de K e selecione aquele que minimiza o BIC ou maximiza o fator Bayes (ou, equivalentemente, minimiza o comprimento da descrição). Não escolha K com base na inspeção visual do grafo ou em expectativas prévias. A maioria das implementações (graph-tool, blockmodels em R) automatiza essa busca. A análise de sensibilidade — verificando se a estrutura qualitativa do bloco muda quando K é variado em um — também é recomendada.

Qual é o tamanho mínimo da rede para que o SBM seja confiável?

O registro especifica um mínimo de 50 nós para inferência confiável. Com menos de 20 nós, o modelo não consegue identificar uma estrutura de comunidade significativa e ajustará o ruído — use estatísticas descritivas de rede ou detecção de comunidade simples. Entre 20 e 50 nós, os resultados devem ser tratados como exploratórios e interpretados com cautela.

Métodos relacionados

Fontes

  1. Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.

    Abrir referência DOI
    Copiado.
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

    Abrir referência DOI
    Copiado.