Lede. Os nós do artigo anterior estão soltos: ninguém se relaciona com ninguém. Neste artigo você escolhe o que é um nó e o que é uma aresta — e essa escolha decide todo o resto —, monta o grafo, e usa os dois detectores de comunidade que o
python-igraphoferece. Você sai com o número de comunidades, e também com a resposta para a pergunta que quase ninguém faz: se a sua comunidade é um assunto ou é a sua fonte de letra. Onde você está na linha. Este é o passo 7 de 13 — grafo de conhecimento e comunidades. Depende do artigo 06, de onde vêm os nós já casados; aqui eles ganham arestas. Depois dele: o artigo 08, que consulta o grafo. Se você só quer decidir se precisa de grafo, leia as seções 1 e 9 — a segunda é a que ninguém costuma ler.
1. O que é um nó, o que é uma aresta, e onde o grafo não ajuda
Um grafo de conhecimento tem duas coisas: nós (as entidades, já com o nó canônico do
artigo 06) e arestas (as relações entre elas, com um peso). Só isso. Toda a dificuldade
deste artigo está numa frase que parece dispensa e não é: a escolha da aresta decide o grafo inteiro.
Você pode dizer que duas entidades têm uma aresta porque aparecem na mesma frase, no mesmo
trecho, no mesmo documento, ou porque o modelo disse que existe uma relação entre elas.
Cada uma dessas definições produz um grafo diferente, com comunidades diferentes, e todas
respondem à pergunta "quem se relaciona com quem" — com respostas diferentes. Não existe
grafo neutro, e escolher sem querer é a forma mais comum de construir um grafo inútil.
O grafo existe para responder pergunta de caminho: "quem assinou o contrato que substituiu
este", "quais empresas aparecem com esta norma nos mesmos documentos". Para isso ele
precisa ser melhor que a busca por texto, e às vezes é.
E às vezes não é. Este é o parágrafo que economiza meses:
⚠️ O grafo não é um RAG melhor. É um RAG diferente, e mais caro
Um grafo de conhecimento custa uma passagem de LLM por documento para ser extraído (oartigo 05), mais a deduplicação de nós (o artigo 06), mais o custo da detecção de comunidade
a cada mudança do acervo. Em troca, ele só paga se a sua pergunta depender do caminho
entre entidades. Se a pergunta é "o que este documento diz", a busca vetorial do artigo 03
responde melhor, mais rápido e com menos peça para manter. Se a pergunta é "quais
documentos mencionam X e Y juntos", e você tem um grafo de coocorrência, o grafo ganha.
Se a base é uma coleção de documentos independentes, sem pergunta de relação, o grafo é
custo sem retorno — e isso não se descobre depois, se descobre.
Como a extração de grafo acontece antes de qualquer consulta, o custo é pago no carregamento
e o benefício só aparece na consulta. É por isso que a decisão "grafo ou não" é do artigo
12, e por isso que ela depende do tipo de pergunta, não do tamanho da base.
2. De onde sai a aresta: coocorrência, distância e contagem
A definição mais usada de aresta em grafo de texto é a mais barata: duas entidades coocorrem no mesmo trecho, e o peso da aresta é quantas vezes isso aconteceu. É a que
vou usar, e ela tem dois defeitos conhecidos que valem ser ditos antes do código, porque o
resultado da detecção de comunidade depende deles:
O trecho é grande demais. Se a aresta é "coocorrem no mesmo Chunk" e o Chunk tem
dois parágrafos, você liga uma entidade do primeiro parágrafo a uma do segundo sem que
nunca tenham aparecido na mesma frase. Todo par do trecho vira aresta, e o grafo enche de
aresta que não significa nada.
A contagem premia o estilo, não o assunto. Uma fórmula que se repete em todos os
documentos da família cria o mesmo par em todos eles, e esse par acumula um peso enorme —
maior que o peso de qualquer relação real do acervo. E a detecção de comunidade, que é um
algoritmo de achar estrutura, acha exatamente essa: a estrutura do seu documento.
Há três consertos, e nenhum é perfeito:
| Critério da aresta | O que ele mede | Custo | Quando usar |
|---|---|---|---|
coocorrência no Chunk | "aparecem juntos no mesmo trecho" | nenhum | linha de base, e só para grafo pequeno |
| coocorrência na mesma frase | "aparecem juntos na mesma proposição" | quebrar o trecho em frase | padrão, e o que o código usa |
| proximidade no trecho | "aparecem perto, mesmo sem estar na mesma frase" | um número de distância por par | grafo de prosa corrida, sem frase limpa |
E há o quarto ajuste, que é ortogonal: ponderar cada ocorrência pela raridade da frase.
Uma frase que aparece em três documentos de três pesa um terço de uma frase que aparece em
um. Isso derruba o peso da fórmula repetida sem precisar identificar o que é fórmula. O
preço é conhecido: se a repetição da frase for o assunto, o peso do assunto cai. O
método não sabe a diferença entre " boilerplate" e "conteúdo"; ele sabe que a frase se
repete, e a distinção é sua.
3. O que é comunidade, e o que é modularidade
Uma comunidade é um grupo de entidades que se relacionam muito entre si e pouco com o
resto do grafo. A analogia honesta é a mesa do restaurante: um grupo de pessoas que
sempre senta junto, e quase sempre com as mesmas pessoas. Você não sabe de antemão quem
senta com quem — o detector descobre.
Dizer "descobre" é ser generoso. O detector não descobre nada: ele maximiza uma função e a partição que sai é o ponto alto que ele encontrou. A função quase sempre é a
modularidade (modularity), que mede o quanto as arestas ficaram dentro dos grupos
em vez de entre eles, comparado com o que aconteceria se as arestas fossem espalhadas
ao acaso. A leitura é direta:
- modularidade perto de 0: os grupos não explicam nada além do acaso;
- modularidade alta: as arestas internas de cada grupo dominam as que saem dele.
Modularidade é uma medida relativa. Ela compara a sua partição com um grafo aleatório
com o mesmo número de nós e arestas. Uma partição com modularidade 0.4 num grafo de
contratos pode ser uma partição excelente, e a mesma partição num grafo de rede social é
ruído. Não existe "boa modularidade" acima de um número: existe modularidade deste grafo, comparada com o grafo anterior, com os parâmetros anteriores.
4. A armadilha do resolution limit
Antes de rodar qualquer detector, você precisa saber de uma limitação que vem da própria
função de qualidade, e não do algoritmo: existe um tamanho mínimo de grupo que a
modularidade consegue enxergar como comunidade.
O que acontece na prática: você tem um grupo de seis entidades, todas ligadas entre si e
quase nada para fora. Ele é uma comunidade que qualquer pessoa que lê o grafo reconhece. Só
que a modularidade compara com o acaso, e o acaso também coloca arestas dentro de um grupo
de seis. O resultado da conta é que fundir aquele grupo com o resto rende mais
modularidade do que mantê-lo separado. O detector, que está otimizando a modularidade,
faz exatamente o que pede: ele dissolve o grupo.
É o resolution limit (limite de resolução), e ele tem duas consequências practices:
-
Grupos pequenos não aparecem, e não há parâmetro que os faça aparecer. Abaixar o
resolutionnão conserta: você pede mais resolução ao detector e ele dissolve aindamais, porque é isso que a conta está rewarding.
-
O sintoma é uma comunidade. Você olha o resultado e vê communities enormes onde
existiamsubjects médios. Não é bug, é a função de qualidade escolhendo.
A defesa não é afinar o detector. É escolher uma função de qualidade que tenha o
tamanho embutido no parâmetro — que é exatamente o que a seção 7 faz com o CPM.
5. Louvain: o detector greedy que é estocástico
Louvain é o detector que virou padrão depois do
artigo de Blondel e colaboradores. A chamada, na
assinatura verificada do python-igraph, é
g.community_multilevel(weights=g.es["weight"], resolution=1.0) — a seção 8 mostra a
versão completa, dentro de uma função.
community_multilevel é o nome porque o algoritmo é multinível: ele faz uma passada
rápida juntando nós em grupos, encolhe cada grupo em um nó só, e repete. A segunda passada é
barata porque o grafo encolheu. Ele é greedy (cada junta usa o que está disponível
naquele momento) e é estocástico (a ordem de visita dos nós depende de um gerador
aleatório, então duas execuções sobre o mesmo grafo podem sair diferentes).
E aqui está o gancho deste artigo:
⚠️ Rodar dez seeds e escolher a de maior modularidade não é robustez
É a admissão de que o resultado é instável somada ao fato de que a modularidade não medeo que você quer. As duas informações são ruins, e a segunda é a que importa. Se dez
execuções dão partições diferentes, a partição não é uma propriedade do grafo — é uma
propriedade de uma sequência de sorteios. Guardar a "melhor" das dez é escolher um
resultado arbitrário com um critério que não tem relação com a pergunta do usuário.
Quando a modularidade varia muito entre execuções, o número que você precisa olhar é outro:
o grafo tem estrutura forte o suficiente para existir? E a resposta é não.
O resolution do Louvain é o botão de granularidade: alto produz mais comunidades
menores, baixo produz menos comunidades maiores. É o controle de caso, e ele não escapa
do resolution limit da seção 4 — só muda o ponto em que a dificuldade aparece. A
assinatura também tem return_resolution, que existe para o detector devolver a resolução
que ele acabou de usar; o que ela devolve exatamente depende da versão da biblioteca, e
isso está na
documentação de comunidade do igraph
— confira antes de usar em código que dependa do valor.
6. Leiden: o conserto do que o Louvain não faz bem
Leiden (Traag, Waltman e van Eck) refaz o Louvain
com três correções. A chamada, na assinatura verificada, é
g.community_leiden(objective_function="CPM", weights=g.es["weight"], resolution_parameter=1.0, beta=0.01, n_iterations=2).
As três fases, na ordem em que o algoritmo as executa:
-
Movimento local: cada nó visita seus vizinhos e tenta mudar de comunidade, um a um,
aceitando a mudança que mais melhora a qualidade. É a mesma ideia do passe rápido do
Louvain.
-
Refinamento: as comunidades interfaces são desdobradas em subcomunidades quase
desconectadas, e a parte conexa é repartida. É aqui que o Leiden conserta o defeito mais
concreto do Louvain: comunidades internamente desconectadas. No Louvain isso é
possível, e um nó pode ser "comunidade" junto com outro sem nenhum caminho entre os dois
— o que quebra qualquer travessia de caminho e qualquer resumo de comunidade.
-
Agregação: as comunidades refinadas são encolhidas em nós, e o grafo recomeça em um
nível acima. É o multinível do Louvain, agora com a garantia de que a partição é
conexa e "bem conectada".
Os outros dois parâmetros importam menos do que parecem. beta é o peso do termo de
estabilidade (randomização) dentro de cada passe, e valores baixos dão partições mais
determinísticas. n_iterations=2 é o número de passes por nível: mais passes, mais
tempo, e a qualidade para de melhorar em algum lugar. Leiden é mais rápido e de qualidade maior que o Louvain nos testes do artigo original, e o motivo relevante para
aqui não é a velocidade: é a garantia de comunidades conexas, que é o que o artigo 08
precisa para atravessar o grafo sem errar.
7. CPM × modularidade: escolher a função de qualidade
Este é o parágrafo que decide qual argumento você passa para o detector, e é onde a
autoridade.
-
Modularidade é a função clássica. Ela não tem parâmetro de tamanho: o detector não
tem como saber que você queria uma comunidade de seis, e por isso cai no resolution limit. Vantagem: a partição é comparável entre execuções e entre grafos parecidos.
-
CPM (Constant Potts Model) é a função alternativa. Ela tem um parâmetro com
unidade de tamanho: o
resolution_parameterdiz, na prática, qual o tamanho a partir doqual vale a pena separar uma comunidade. Uma comunidade menor que esse tamanho não
paga na conta. Efeito colateral útil: com CPM, um grupo de seis nós bem conectados é
encontrado mesmo com a configuração padrão, que é justamente o caso que a modularidade
dissolve.
Em Python, a escolha é um parâmetro: objective_function="CPM" ou
objective_function="modularity". E a qualidade do resultado se lê em lugares diferentes:
community.modularity para a partição de modularidade, community.quality para a de CPM.
Nenhuma das duas é "acerto": as duas medem a função que você pediu para maximizar.
E há um detalhe de unidade que só aparece quando se usa modularidade no Leiden: para
maximizar a modularidade, os graus dos vértices entram como pesos de vértice, e o
resolution_parameter tem que ser 1/(2m), sendo m a soma dos pesos das arestas. Sem
isso, o número que o Leiden maximiza não é a modularidade que você pensou. O nome do
parâmetro de peso de vértice mudou entre versões do python-igraph, então confira o da sua
na documentação antes de copiar a chamada.
8. O código: montagem em Python puro, detecção no igraph
Primeiro a montagem, que não depende de biblioteca nenhuma e é onde a maior parte das
decisões acontece. A detecção vem depois, dentro de funções que ninguém chama.
Sobre o import abaixo: o python-igraph não está instalado no ambiente onde este
artigo é verificado, e este artigo não instala nada. Por isso o import está dentro das
funções, e as funções não são chamadas. O bloco compila, executa e não depende da
biblioteca. Para rodar de verdade, instale pelo
python-igraph e chame as funções no seu lugar — o
referência das assinaturas.
# O grafo, montado com dicionário e comprehension. Sem igraph, sem rede. from __future__ import annotations import hashlib import math from collections import Counter, defaultdict from collections.abc import Sequence from enum import StrEnum from typing import Any, NamedTuple from pydantic import BaseModel, ConfigDict, Field class Contract(BaseModel): """Base de todas as fichas. `extra="forbid"` = campo que não existe é erro, não é ignorado. `frozen=True` = ninguém muda a ficha depois que ela foi criada. """ model_config = ConfigDict(extra="forbid", frozen=True) class Document(Contract): """A peça 1: o arquivo cru, antes de qualquer transformação. Guardar `uri` e `metadata` aqui é o que permite citar a fonte e filtrar por permissão mais adiante. """ doc_id: str uri: str # de onde veio title: str text: str metadata: dict[str, Any] = Field(default_factory=dict) @property def content_hash(self) -> str: """Impressão digital do texto. Serve para uma coisa só: saber se o documento mudou desde a última indexação. Sem isso, reindexar significa reindexar tudo. """ return hashlib.blake2b( self.text.encode("utf-8"), digest_size=16 ).hexdigest() class Chunk(Contract): """A peça 3: o trecho indexado. `parent_id` existe porque quase todo documento tem hierarquia (capítulo > seção > parágrafo). Guardar o pai desde o começo permite buscar no trecho pequeno e entregar o trecho grande, sem reindexar. """ chunk_id: str doc_id: str parent_id: str | None # None = é a raiz ordinal: int # posição dentro do pai text: str token_count: int # contagem de token, não de letra metadata: dict[str, Any] = Field(default_factory=dict) class EntityType(StrEnum): """A ontologia do artigo 05, reexibida porque o grafo classifica por tipo.""" ORGANIZACAO = "organizacao" PESSOA = "pessoa" DOCUMENTO = "documento" LOCAL = "local" TEMPORAL = "temporal" VALOR = "valor" PRODUTO = "produto" class NoLigado(NamedTuple): """O que o artigo 06 entrega aqui: a menção, já com o nó canônico. `estagio` e `similaridade` viajam junto porque a auditoria do artigo 06 depende deles. O grafo ignora os dois campos — e é por isso que eles podem ficar na tabela sem atrapalhar a consulta. """ node_id: str kind: EntityType doc_id: str chunk_id: str estagio: str similaridade: float class Ocorrencia(NamedTuple): """As entidades que aparecem na mesma frase, num documento. A frase entra inteira porque a ponderação da seção 2 precisa saber quantos documentos compartilham ela. """ doc_id: str frase: str node_ids: tuple[str, ...]
Agora a montagem, com as duas definições de aresta lado a lado:
# Continua o bloco anterior: as regras de aresta, uma por vez. def pares_da_ocorrencia(node_ids: Sequence[str]) -> list[tuple[str, str]]: """Todos os pares de uma lista de nós, sem ordem, sem repetição. Ordenar o par antes de guardá-lo é o que faz (A, B) e (B, A) serem a mesma aresta. Sem isso, o peso da aresta é a soma de duas metades e o grafo dobra sem motivo. """ return sorted( (a, b) if a <= b else (b, a) for i, a in enumerate(node_ids) for b in node_ids[i + 1:] if a != b ) def frase_normalizada(frase: str) -> str: """Chave de frase, para contar em quantos documentos ela aparece. Minúsculas e espaços normalizados servem: o objetivo aqui é detectar a frase que se repete, não canonizar a frase. (O pipeline de sete passos do artigo 06 é outro problema, com outro objetivo.) """ return " ".join(frase.lower().split()) def montar_arestas(ocorrencias: Sequence[Ocorrencia], *, granularidade: str = "frase", ponderar_frase: bool = True) -> dict[tuple[str, str], float]: """Monta o dicionário de arestas com peso. `granularidade="frase"` liga só o que está na mesma frase. `granularidade="documento"` liga tudo que está no mesmo documento, e é a versão ingênua da seção 2: ela multiplica as arestas e conecta entidades que nunca dividiram a mesma proposição. `ponderar_frase` divide o peso de cada ocorrência pelo número de documentos que têm aquela frase. É o conserto do boilerplate. """ if granularidade not in ("frase", "documento"): raise ValueError(f"granularidade desconhecida: {granularidade}") # 1. Em quantos documentos cada frase aparece. Precisa vir antes do # acúmulo de peso, porque é dele que sai o divisor. por_documento: dict[str, set[str]] = defaultdict(set) for ocorrencia in ocorrencias: chave = frase_normalizada(ocorrencia.frase) for node_id in ocorrencia.node_ids: por_documento[chave].add(ocorrencia.doc_id) n_documentos = len({o.doc_id for o in ocorrencias}) or 1 # 2. Arestas de documento, quando for esse o modo: junta as frases do # mesmo documento e liga tudo com tudo. if granularidade == "documento": por_doc: dict[str, set[str]] = defaultdict(set) frases_por_doc: dict[str, list[str]] = defaultdict(list) for ocorrencia in ocorrencias: por_doc[ocorrencia.doc_id].update(ocorrencia.node_ids) frases_por_doc[ocorrencia.doc_id].append(frase_normalizada(ocorrencia.frase)) alvos = [ Ocorrencia(doc_id=doc_id, frase=" ".join(sorted(frases_por_doc[doc_id])), node_ids=tuple(sorted(nos))) for doc_id, nos in por_doc.items() ] # No modo documento, a frase sintética não divide: a contagem real # de peso é o número de documentos em que o par aparece. return _acumular(alvos, por_documento, n_documentos, ponderar_frase, divisor="documentos") return _acumular(ocorrencias, por_documento, n_documentos, ponderar_frase, divisor="frases") def _acumular(ocorrencias, por_documento, n_documentos, ponderar, divisor) -> dict: """Acumula o peso de cada par. Separado para os dois modos compartilharem.""" arestas: dict[tuple[str, str], float] = defaultdict(float) for ocorrencia in ocorrencias: documentos_da_frase = len(por_documento.get(frase_normalizada(ocorrencia.frase), {1})) if ponderar: if divisor == "documentos": peso = 1.0 / max(1, documentos_da_frase) else: peso = 1.0 / documentos_da_frase else: peso = 1.0 for par in pares_da_ocorrencia(ocorrencia.node_ids): arestas[par] += peso return dict(arestas)
O grafo de três contratos, e o que o boilerplate faz com ele
Este é o acervo de teste, e ele tem uma fórmula que se repete nos três documentos. É o
acervo mais honesto que dá para montar com três linhas: a fórmula existe em qualquer base
de documentos de verdade.
# Continua o bloco anterior: o acervo de teste, com boilerplate de propósito. FORMULA = ("Fica eleito o foro da Comarca de Belo Horizonte e o regime de bens " "das partes contratantes.") ACERVO = [ Ocorrencia("doc-1", FORMULA, ("comarca-bh", "partes")), Ocorrencia("doc-1", "O lote Serra Azul é entregue na unidade de Campinas.", ("serra-azul", "unidade-campinas")), Ocorrencia("doc-2", FORMULA, ("comarca-bh", "partes")), Ocorrencia("doc-2", "O lote Vale do Sol é entregue na unidade de Recife.", ("vale-do-sol", "unidade-recife")), Ocorrencia("doc-3", FORMULA, ("comarca-bh", "partes")), Ocorrencia("doc-3", "O lote Monte Alto é entregue na unidade de Salvador.", ("monte-alto", "unidade-salvador")), ] for modo, pondera in (("documento", False), ("frase", False), ("frase", True)): arestas = montar_arestas(ACERVO, granularidade=modo, ponderar_frase=pondera) total = sum(arestas.values()) or 1.0 topo = sorted(arestas.items(), key=lambda item: -item[1])[:3] print(f"\n{modo} ponderar={pondera}: {len(arestas)} arestas, peso total {total:.1f}") for (a, b), peso in topo: print(f" {a:20} -- {b:20} peso {peso:.2f} ({round(100 * peso / total)}% do total)")
Três leituras dessa saída, e a terceira é a que o artigo inteiro prepara:
-
Modo documento, sem ponderar: 16 arestas em vez de 4. O par da fórmula é a ponte
entre os três documentos — é o único par que aparece em mais de um deles —, então o
grafo inteiro fica conectado por ele e a detecção de comunidade não tem o que separar.
Repare que o peso dele é só 17% do total: a diluição numérica esconde o problema, que
não é de peso, é de estrutura.
-
Modo frase, sem ponderar: a fórmula sobe para 50% do peso, e continua sendo a ponte.
Aqui o problema aparece no número, e o detector vai devolver uma comunidade com a fórmula
e as três entidades de cada documento puxadas para dentro.
-
Modo frase, ponderado: a ponte desce para 25%, o mesmo peso de qualquer par interno,
e o grafo fragmenta em quatro duplas. Nenhum par domina.
E aqui está a honestidade do terceiro ponto, que seria errado omitir: quatro duplas não são comunidades úteis. O ponderamento removeu o domínio da fórmula, e no mesmo gesto
removeu a única coisa que ligava os documentos. Com três documentos, o grafo ponderado não
tem estrutura de comunidade nenhuma — a auditoria da seção 10 mostra quatro componentes
conexas de dois nós cada. A lição não é "pondera e resolva"; é "pondera, e olhe o que sobra": se o que sobra é nada, você tem um acervo pequeno demais para detectar
comunidade, e nenhum detector vai consertar isso. O conserto é mais documento, não outro
parâmetro.
E a detecção, que é a parte que depende de biblioteca:
# Continua o bloco anterior: a detecção, que depende do python-igraph. # O `import` está DENTRO das funções de propósito. O python-igraph não está # instalado no ambiente onde este artigo é verificado, e este artigo não # instala nada: então estas funções são escritas, mas não são chamadas. O # bloco executa, compila e não depende da biblioteca. Para rodar de verdade, # instale o pacote e chame as funções no seu lugar. def para_igraph(nos: Sequence[str], arestas: dict[tuple[str, str], float]): """Converte o dicionário de arestas em grafo do igraph. `n=` explícito porque a lista de nós pode conter vértices isolados, que não aparecem em nenhuma aresta e sumiriam se o grafo fosse construído só pelas arestas. Comunidade de vértice isolado não é o problema grave, mas o grafo silenciosamente menor é. """ import igraph indice = {no: i for i, no in enumerate(nos)} arestas_igraph = [(indice[a], indice[b]) for a, b in arestas] g = igraph.Graph(n=len(nos), edges=arestas_igraph, directed=False) g.es["weight"] = [arestas[par] for par in arestas] return g def louvain(g, resolution: float = 1.0): """Louvain, greedy multinível. Estocástico: muda entre execuções.""" return g.community_multilevel(weights=g.es["weight"], resolution=resolution) def louvain_dez_seeds(g): """Dez execuções, dez partições — e é isso que o argumento precisa mostrar. O trecho que fixa a semente do gerador aleatório do igraph não está aqui: essa chamada mudou de nome entre versões, e o nome correto é o da sua versão, na documentação. O que importa para o raciocínio é o laço. """ particoes = [] for _ in range(10): # <- aqui entraria a chamada que fixa a semente do gerador do igraph particoes.append(g.community_multilevel(weights=g.es["weight"], resolution=1.0)) return particoes def leiden(g, objective_function: str = "CPM", resolution_parameter: float = 1.0, beta: float = 0.01): """Leiden: movimento local, refinamento e agregação, `n_iterations=2`. Com CPM, o `resolution_parameter` tem unidade de tamanho, e é ele que resolve o *resolution limit* da seção 4. """ return g.community_leiden(objective_function=objective_function, weights=g.es["weight"], resolution_parameter=resolution_parameter, beta=beta, n_iterations=2) def leiden_para_modularidade(g, m: float): """Modularidade no Leiden: graus como peso de vértice e resolução 1/(2m). O nome do parâmetro de peso de VÉRTICE mudou entre versões do python-igraph e não está na assinatura usada no resto do artigo; confira o da sua antes de copiar. O resto da conta é este, e `m` é a soma dos pesos das arestas. """ return g.community_leiden(objective_function="modularity", weights=g.es["weight"], resolution_parameter=1.0 / (2 * m), beta=0.01, n_iterations=2, # e os graus, no parâmetro de peso de vértice da # sua versão: vertex_weights=[v.degree() for v in g.vs] ) def qualidade(particao, objetivo: str) -> float: """A qualidade da partição, no lugar certo para cada objetivo. `modularity` para a partição de modularidade, `quality` para a de CPM. Nenhuma das duas é acerto: as duas medem a função que você pediu para maximizar. """ return (particao.modularity if objetivo == "modularity" else particao.quality)
💡 Trocar de biblioteca é um problema de versão, não de código
Toda a detecção deste artigo cabe em quatro linhas de chamada, e as quatroestão em funções isoladas. É por isso que vale a pena manter a montagem do grafo em Python
puro como está: se a biblioteca mudar de nome de método, o que você reescreve são quatro
linhas, e o grafo — que é onde mora o trabalho de verdade — não é tocado.
O conserto é uma linha de ponderação, e ele não sabe o que é fórmula. Ele sabe que a frase
se repete. Se a frase que se repete for o assunto — e em base de contrato, a cláusula de
foro é assunto — o conserto derruba o assunto junto, e o detector vai devolver uma
comunidade por documento em vez de uma comunidade por cláusula. A auditoria da seção 9 é o
que separa os dois casos.
9. Modularidade alta não é partição certa
Esta seção é a mais importante do artigo, e a que ninguém lê porque está no fim.
Modularidade alta não é partição certa. A modularidade mede o quanto a partição se
afasta do grafo aleatório com o mesmo número de arestas. Ela não sabe se a partição
combina com o assunto, e ela não tem como saber. Um grafo de texto com modularidade 0.45
pode ter comunidades que são exatamente as cláusulas, ou pode ter comunidades que são
exatamente a fonte, o tipo de documento e o rodapé. O número é o mesmo.
A forma mais comum de a comunidade refletir o estilo do documento em vez do assunto é
exatamente a da seção 8: a fórmula repetida. Ela cria um par de peso altíssimo entre duas
entidades que aparecem juntas em toda a família de documentos, e o par puxa para dentro
com ele tudo que tem qualquer relação com uma das duas. O resultado é uma comunidade gigante e várias comunidades miúdas — assinatura da detecção de comunidade em grafo de
coocorrência sobre texto, e a forma mais rápida de reconhecer o problema sem medir nada.
Quatro coisas que a modularidade alta não é, e que valem como checagem antes de acreditar
no resultado:
-
Não é validação. É otimização. O detector devolve o melhor ponto que ele achou, e
"melhor" é com relação à função, não com relação à sua pergunta.
-
Não é estabilidade. Se duas execuções com seeds diferentes dão partições
diferentes, a partição é um artefato do sorteio. Guardar a de maior modularidade é
guardar um sorteio com aprovação.
-
Não é um id estável. O identificador de comunidade (
membership) muda quando oacervo cresce, quando um par muda de peso e quando você mexe no
resolution. Nunca useo id de comunidade como chave de cache persistente, e nunca como identificador de
assunto: se o acervo mudar, o mesmo assunto recebe outro número, e o histórico dele
fica com você, não com o grafo.
-
Não sobrevive à mudança de parâmetro. A mesma base com
resolution0.8 e 1.2 dápartições diferentes, e as duas com modularidade parecida. O parâmetro é parte do
resultado.
E a consequência prática, que é o que você faz amanhã: a comunidade é hipótese, e a hipótese se testa lendo. Abra as duas maiores comunidades e leia os nós delas. Se
elas são "toda a empresa X" e "o rodapé", o grafo pegou estilo. Se são "fornecedores" e
"clientes", o grafo pegou assunto. Essa leitura de cinco minutos vale mais do que comparar
modularidade entre execuções, e é a única que responde à pergunta que o usuário fez.
⚠️ A comunidade que responde tudo não está respondendo nada
Uma comunidade com 80% dos nós é o detector dizendo que o grafo é um bloco só. Amodularidade dela pode ser alta — é a sua própria média que está sendo maximizada. Se
a sua resposta de
community reporté "a empresa fala de contratos", você não estáusando detecção de comunidade; você tem um grafo com aresta demais e detecção de
comunidade a menos.
10. A auditoria antes de acreditar, e a ordem para montar
A auditoria é um grafo de três perguntas, e todas as três rodam sem igraph:
# Continua do bloco anterior: a auditoria, com Python puro. arestas = montar_arestas(ACERVO, granularidade="frase", ponderar_frase=True) nos = sorted({no for par in arestas for no in par}) grafo: dict[str, set[str]] = {no: set() for no in nos} for (a, b) in arestas: grafo[a].add(b) grafo[b].add(a) def componentes_conectadas(grafo: dict[str, set[str]]) -> list[list[str]]: """Componentes conexas, por busca em largura. É a pergunta "o grafo é um bloco só?", e ela responde sozinha a maioria dos casos da detecção de comunidade em grafo de texto: quando dá uma só, não há o que agrupar. """ vistas: set[str] = set() componentes: list[list[str]] = [] for origem in grafo: if origem in vistas: continue fila, componente = [origem], [] vistas.add(origem) while fila: atual = fila.pop() componente.append(atual) for vizinho in grafo[atual] - vistas: vistas.add(vizinho) fila.append(vizinho) componentes.append(sorted(componente)) return sorted(componentes, key=len, reverse=True) componentes = componentes_conectadas(grafo) graus = Counter(no for no in nos for _ in grafo[no]) total_peso = sum(arestas.values()) or 1.0 print("nós:", len(nos), "| arestas:", len(arestas), "| peso total:", round(total_peso, 2)) print("componentes conexas:", len(componentes), "->", [len(c) for c in componentes]) print("nós isolados:", [no for no in nos if graus[no] == 0]) print("grau médio:", round(sum(graus.values()) / len(nos), 2)) print("três nós mais conectados:", graus.most_common(3)) # A pergunta que decide se o grafo é seu ou da sua fonte de letra: quanto # do peso está em pares que aparecem em mais da metade dos documentos. pares_por_documento: dict[tuple[str, str], set[str]] = defaultdict(set) for ocorrencia in ACERVO: for par in pares_da_ocorrencia(ocorrencia.node_ids): pares_por_documento[par].add(ocorrencia.doc_id) repetidos = {par for par, docs in pares_por_documento.items() if len(docs) > 1} peso_repetido = sum(arestas.get(par, 0.0) for par in repetidos) print(f"peso em pares que se repetem entre documentos: " f"{round(100 * peso_repetido / total_peso)}% do total")
Leitura dos três números que importam:
-
componentes conexas: se deu uma só, o grafo não tem estrutura de comunidade. O
conserto não é o detector, é a aresta.
-
peso em pares repetidos: muito alto significa que o grafo mede a sua fórmula. A
ponderação da seção 8 existe para baixar esse número, e ele é a métrica de sanidade do
grafo inteiro.
-
três nós mais conectados: leia esses três nomes. Se forem a entidade que o texto
repete em todo documento, e não o assunto, o grafo está medindo estilo.
A ordem para montar, cada passo verificável sem o seguinte:
-
Monte o grafo em Python puro e rode esta auditoria. A detecção de comunidade é a última
etapa, não a primeira: ela responde "como agrupar", e ninguém vai pergunta isso se o
grafo for um bloco só.
-
Decida a aresta — frase, documento ou proximidade — e escreva a regra no código,
com o motivo. Trocar de regra depois exige re-detectar tudo.
-
Rode o Louvain com o
resolutionpadrão, uma vez, para ter uma linha de base. -
Rode o Leiden com CPM, e compare com o Louvain pelo relatório, não pela
modularidade. A pergunta é "a partição do Leiden tem comunidades conexas e de tamanho
plausível para o meu acervo?".
-
Leia as duas maiores comunidades e decida se elas são assunto. Se forem estilo,
volte para o passo 2. Nenhum detector conserta uma aresta errada.
Se você parou aqui, o seu grafo tem nós e arestas com peso, a detecção de comunidade rodou em
Python puro e no igraph, e você tem três números de sanidade antes de confiar em qualquer
comunidade. O que falta é o uso: percorrer o grafo a partir de um nó, e resumir uma
comunidade para entrar no contexto do modelo. Isso é o artigo 08.
TL;DR
-
Nó e aresta são decisão sua, e a aresta decide o grafo inteiro. Coocorrência no
trecho liga o que nunca esteve na mesma frase.
-
A contagem de coocorrência premia o estilo, não o assunto. Uma fórmula que se repete
vira o par mais pesado do acervo, e a detecção de comunidade acha a estrutura do seu
documento em vez do assunto dele.
-
Ponderar cada frase pela raridade dela derruba o boilerplate sem precisar saber o
que ele é — ao custo de também derrubar conteúdo que se repete.
-
Modularidade é medida relativa (contra um grafo aleatório), é otimização e não
validação, e não sobrevive a mudança de
resolution. -
O resolution limit faz grupos pequenos sumirem na modularidade: o optimum funde o
grupo com o entorno. Não é bug, e mexer no
resolutionnão resolve. -
Louvain é multinível, greedy e estocástico. Dez seeds e a melhor modularidade é
escolher um sorteio com aprovação, não é robustez.
-
Leiden conserta o defeito concreto do Louvain: comunidades internamente desconectadas,
que quebram travessia de caminho e resumo de comunidade.
-
CPM resolve o resolution limit por construção, porque o parâmetro tem unidade de
tamanho. Com modularidade no Leiden, informe os graus como peso de vértice e
resolution_parameter = 1/(2m). -
A comunidade é hipótese. Abra as duas maiores e leia os membros: é o único teste que
diz se ela é assunto ou fonte de letra.
Referências
- Community detection — python-igraph (C manual) — as assinaturas verificadas de
community_multilevelecommunity_leiden, e o que cada parâmetro faz - From Louvain to Leiden: guaranteeing well-connected communities — as três fases, o defeito que o Leiden conserta e a relação com o resolution limit
- Fast unfolding of communities in large networks — o artigo do Louvain, para o que o "multinível" faz
- python-igraph — instalação e link da documentação por versão