# Algoritmos do Knowledge Graph — Mud Sentinel

**Documento:** `grafo/04-algoritmos.md`  
**Versão:** 1.0.0  
**Nota:** Descrições **conceituais** — sem implementação/código.

---

## 0. Orçamentos transversais (todos os algoritmos)

| Parâmetro | Default sugerido MVP | Motivo |
|-----------|----------------------|--------|
| `max_depth` | 3 (P0 UI) / 5 (jobs) | Custo e legibilidade |
| `max_nodes_expanded` | 500–2000 por request | Anti-DoS analítico |
| `max_fanout_per_node` | 50 (depois “+N mais”) | Evitar supernós |
| `edge_type_allowlist` | por perfil de análise | Foco semântico |
| `layer_filter` | L1+L2; L3 opt-in | Evitar ruído |
| `as_of` | timestamp | Temporal |
| `timeout_ms` | curto sync; async se estourar | UX |
| `quota` | por Tenant | Fairness |

Toda execução registra `algorithm_run_id`, parâmetros e contagens para Explainable Graph.

---

## 1. Expansão de grafos (Neighborhood Expansion)

### 1.1 Objetivo

A partir de um nó semente, materializar o **ego-network** para exploração visual e dossiê.

### 1.2 Algoritmo — BFS limitado com políticas

**Nome:** `ExpandEgoNetwork`

1. Entrada: `seed`, `depth`, allowlists, `as_of`, layer filter.
2. Em cada profundidade, expandir arestas cuja vigência intersecta `as_of`.
3. Aplicar **fan-out cap** por nó; priorizar arestas por `weight * confidence`.
4. Suprimir nós denylisted (telefones genéricos, etc.).
5. Retornar subgrafo + estatísticas de truncamento.

**Variantes:**

| Variante | Uso |
|----------|-----|
| `ExpandTyped` | Só societário / só contratos |
| `ExpandRadial` | Um hop de cada tipo (“vistão”) |
| `ExpandAroundPath` | Expandir nós de um path encontrado |

### 1.3 Justificativa

DFS profundo sem teto explode; BFS com prioridade por peso favorece o que é analiticamente mais forte.

---

## 2. Shortest Path / descoberta de caminhos

### 2.1 Objetivo

Responder: existe caminho entre A e B sob restrições? (UC-006)

### 2.2 Algoritmos

| Algoritmo | Quando | Notas |
|-----------|--------|-------|
| **BFS não ponderado** | hops mínimos | Rápido; ignora pesos |
| **Dijkstra / Bidirectional Dijkstra** | minimizar custo `1/(weight·confidence)` | Preferencial MVP ponderado |
| **A\*** | com heurística (embedding distance) | Opcional P2 |
| **Yen’s K-Shortest** | alternativas para dossiê | Limitar K≤5 |
| **Constrained walk** | só certos `edge_types` + janela temporal | Path semântico |

### 2.3 Política de resultado

- Retornar **até K paths** diversificados (penalizar overlap de nós).
- Rotular: `structural_path` — **nunca** “prova”.
- Se não houver path ≤ depth: `not_found` com explicação de limites.

### 2.4 Justificativa

Bidirectional reduz explosão em grafos sociais/empresariais densos.

---

## 3. Centralidade

### 3.1 Objetivo

Identificar atores “ponte”, hubs de risco, focos de concentração.

### 3.2 Medidas

| Medida | Interpretação no Mud Sentinel | Cuidado |
|--------|-------------------------------|--------|
| **Degree centrality** | Muitos vínculos diretos | Supernós (órgãos, big4) |
| **Weighted degree** | Fortaleza de vínculos | — |
| **Betweenness** | Ponte entre comunidades | Caro; amostrar |
| **Closeness / Harmonic** | Proximidade global | Sensível a componente |
| **PageRank / Eigenvector** | Influência recursiva | Bias a grandes órgãos — filtrar tipos |
| **Ego betweenness** | Ponte local no caso | Bom para dossiês |

### 3.3 Algoritmo operacional — `ComputeCentralitySlice`

1. Selecionar subgrafo (jurisdição, CNAE, watchlist, caso).
2. Filtrar labels (ex.: excluir `GEO_PLACE` de PageRank de empresas).
3. Calcular medidas pedidas.
4. Normalizar por tipo de nó.
5. Persistir scores como propriedades efêmeras ou sinais Integrity.

### 3.4 Justificativa

Centralidade global no grafo nacional inteiro é cara e pouco interpretável; **slices** > grafo total.

---

## 4. Descoberta de comunidades

### 4.1 Objetivo

Encontrar núcleos (grupos econômicos de fato, clusters de co-bidding, redes locais).

### 4.2 Algoritmos

| Algoritmo | Adequação | Notas |
|-----------|-----------|-------|
| **Louvain / Leiden** | Comunidades em redes societárias+contratos | Leiden mais estável |
| **Label Propagation** | Escala grande, aprox. | Não determinístico |
| **Connected components** (por tipo de aresta) | Grupos econômicos por ownership | Simples e explicável |
| **Bipartite community** (empresa–licitação) | Padrões de certame | Projetar grafo 1-mode |

### 4.3 Pipeline `DetectCommunities`

1. Escolher edge set (ex.: `OWNS`+`ADMIN_OF`+`SHARES_ADDRESS`).
2. Rodar Leiden com resolução configurável.
3. Naming: maior Company ou regra de label.
4. Materializar `ECONOMIC_GROUP` candidatos (L2/L3).
5. Expor stability score (Jaccard entre runs).

### 4.4 Justificativa

Leiden reduz comunidades desconectadas; components em ownership são mais **explicáveis** para compliance.

---

## 5. Clusterização

### 5.1 Objetivo

Agrupar nós por similaridade de atributos e/ou embedding estrutural — além de comunidades topológicas.

### 5.2 Métodos

| Método | Features | Uso |
|--------|----------|-----|
| **Hierarchical clustering** | vetores de atributos (CNAE, geo, capital) | Peer groups |
| **k-means / k-medoids** em embeddings | node2vec/GraphSAGE vectors | Exploratório |
| **DBSCAN** | densidade | Detectar núcleos sem K fixo |
| **Blocking + clustering** | entity resolution | SAME_AS candidates |

### 5.3 Separação conceitual

- **Comunidade** = topologia de arestas.
- **Cluster** = proximidade em espaço de features (pode coincidir).

Relatórios devem nomear qual dos dois foi usado.

---

## 6. Similaridade

### 6.1 Objetivo

“Quem se parece com esta Company/Person?” para peers e match.

### 6.2 Funções

| Similaridade | Entrada | Saída |
|--------------|---------|-------|
| **Jaccard vizinhos** | sets de neighbor ids | 0–1 |
| **Adamic-Adar / Preferential** | vizinhos comuns pesados | score |
| **Cosine de embeddings** | vetores de nó | 0–1 |
| **Atributo-híbrido** | nome+geo+CNAE+identifier weak | score calibrado |
| **Path similarity** | overlap de paths até órgãos | score |

### 6.3 Algoritmo `TopKSimilar`

1. Blocking (mesmo município / CNAE / n-gram nome).
2. Scoring híbrido.
3. Diversificar resultados.
4. Devolver razões (explain features).

---

## 7. Detecção de padrões

### 7.1 Objetivo

Sinalizar **motifs** relevantes a integridade — sempre como padrão/indício.

### 7.2 Catálogo de padrões (exemplos)

| Código | Padrão | Descrição | Arestas típicas |
|--------|--------|-----------|-----------------|
| `P_COI_MANDATE_CONTRACT` | COI clássico | Titular de mandato ligado a Company que contrata o mesmo órgão | `HOLDS_MANDATE`, `OWNS`, `AWARDED_TO`, `CONTRACTED_BY` |
| `P_SHARED_CONTACT_BID` | Contato compartilhado + co-bid | SHARES_PHONE/ADDRESS entre co-licitantes | `SHARES_*`, `PARTICIPATED_IN` |
| `P_ROTATING_WINNERS` | Rodízio | Empresas do mesmo cluster vencem alternadamente | `AWARDED_TO`, comunidade |
| `P_AMENDMENT_SPIKE` | Aditivos agressivos | Σ deltas > limiar % | `AMENDED_BY` |
| `P_SANCTION_NEIGHBOR` | Vizinho sancionado | Path curto até SANCTION_ENTRY | `APPLIES_TO`, `OWNS` |
| `P_PEP_SUPPLIER` | PEP × fornecedor | PEP_FLAG + cadeia societária até contrato | PEP, `OWNS`, `AWARDED_TO` |
| `P_SINGLE_BID` | Licitação 1 proposta | BIDDING com 1 participante | `PARTICIPATED_IN` |

### 7.3 Algoritmo `MatchPatterns`

1. Compilar padrão como **graph query template** (subgraph isomorphism / path constraints) — conceitualmente.
2. Escopo: watchlist, município, janela temporal.
3. Emitir `INTEGRITY_SIGNAL` com pointer aos nós/arestas matchados.
4. Deduplicar por assinatura canônica do match.
5. Exigir evidence_refs ≥ 1 fato L1.

### 7.4 Justificativa

Templates nomeados > “IA achou algo estranho” — auditável e treinável para analistas.

---

## 8. Orquestração recomendada (jobs vs online)

| Algoritmo | Online (sync) | Offline (batch/async) |
|-----------|---------------|------------------------|
| Expand depth≤2 | Sim | — |
| Shortest path depth≤4 | Sim se quick; senão async | Sim |
| Centralidade slice | Opcional async | Sim |
| Comunidades | Não | Sim |
| Cluster/embeddings | Não | Sim |
| Pattern match watchlist | Nearline | Sim full scan |

---

## 9. Avaliação dos algoritmos

- **Ground truth** parcial de merges e COIs revisados por humanos.
- **Stability:** comunidades vs seed shuffle.
- **Custo:** p95 runtime e nós tocados.
- **Explicabilidade:** % resultados com explanation payload completo.