Entropia da hierarquia de redes para quantificar a dissimilaridade de grafos

Por que pequenas diferenças em redes importam

De amizades em redes sociais a rotas aéreas e estruturas proteicas, muitos sistemas ao nosso redor podem ser representados como redes de nós e ligações. Mas dizer quando duas dessas redes são significativamente diferentes é surpreendentemente difícil, especialmente quando à primeira vista parecem semelhantes. Este artigo introduz uma nova maneira de medir quão diferentes duas redes realmente são, prestando atenção não apenas aos pontos individuais (nós), mas também às conexões (arestas) e a como elas atuam em conjunto. O método, chamado entropia da hierarquia de redes, consegue detectar mudanças estruturais sutis que outras ferramentas perdem e até ajuda a distinguir proteínas enzimas de não-enzimas.

Analisando redes camada por camada

Para entender uma rede, os autores primeiro consideram quão distante cada nó está de todos os outros em termos de passos ao longo das conexões. Em torno de qualquer nó escolhido, outros nós podem ser agrupados em camadas: vizinhos imediatos, vizinhos de vizinhos e assim por diante. Essa “hierarquia” em torno de um nó descreve como influência ou uma infecção pode se espalhar pela rede. A reviravolta é que duas redes muito diferentes podem compartilhar a mesma camadação ao nível dos nós, então essa visão isolada pode falhar ao distingui-las. O artigo mostra que exemplos clássicos, como os grafos de Desargues e Dodecaedro, apresentam hierarquias de nós idênticas apesar de suas ligações internas serem diferentes.

Dando voz às arestas: encolhimento de pares de nós

Para capturar o que a visão ao nível dos nós não percebe, os autores focam nas arestas — as ligações entre nós — e em como elas remodelam as distâncias pela rede. Eles apresentam uma ideia simples, porém poderosa: “encolhimento de pares de nós”. Aqui, dois nós conectados são temporariamente fundidos em um único novo nó, mantendo-se, porém, seus vizinhos combinados. Isso revela quão próximo cada outro nó está do par em comparação com cada extremidade isolada. Em termos de propagação, imita o efeito de infectar ambas as extremidades de uma aresta ao mesmo tempo, em vez de começar por apenas um nó. A partir desses padrões de distâncias em camadas, definem a “centralidade hierárquica” tanto para nós quanto para arestas, que se mostra fortemente correlacionada com a eficiência de nós ou arestas como espalhadores em simulações epidêmicas em redes do mundo real.

Medindo perda de informação com entropia

Com base nessas centralidades, os autores definem dois tipos de entropia hierárquica. A entropia hierárquica de arestas pergunta: quanta informação perdemos se tentarmos aproximar a importância de uma aresta simplesmente pela média da importância dos dois nós que ela conecta? A entropia hierárquica de nós faz a pergunta inversa, para nós e suas arestas circundantes. Ambas as quantidades são normalizadas para não dependerem do tamanho total da rede. Juntas, formam uma impressão digital de dois números para qualquer rede. A distância entre duas redes é então simplesmente a distância geométrica entre essas impressões digitais. Essa nova métrica obedece às regras padrão esperadas para uma distância e corresponde a intuições, como atribuir penalidades maiores quando uma mudança fragmenta a rede.

Vendo estrutura mais fina e mudança ao longo do tempo

Os autores testam sua medida tanto em redes artificiais quanto reais. Em benchmarks sintéticos que imitam sistemas sociais ou tecnológicos, a nova métrica consegue acompanhar como redes evoluem conforme parâmetros do modelo variam, e separa claramente redes com comunidades fortes daquelas com comunidades mais fracas, mesmo quando métodos concorrentes têm dificuldades. Em experimentos controlados em que redes são cuidadosamente embaralhadas para preservar muitas estatísticas comuns — como sequências de grau e até distribuições de distâncias — a distância por entropia hierárquica ainda detecta diferenças que outras medidas populares tratam como insignificantes. Ela também se destaca ao agrupar versões randomizadas de uma mesma rede nas categorias corretas, indicando sensibilidade aguda a estruturas de ordem superior que vão além de contagens simples de arestas e caminhos.

Usos no mundo real: mobilidade e proteínas

Para demonstrar valor prático, os autores aplicam sua medida de distância a redes diárias de mobilidade entre centenas de cidades chinesas durante os primeiros meses da COVID-19. Usando o início de janeiro como linha de base, a entropia hierárquica revela como os padrões de viagem mudam ao longo do período de pico de deslocamentos do Ano Novo Lunar, do início das quarentenas rígidas e da recuperação gradual, alinhando-se bem com mudanças conhecidas de políticas e padrões comunitários de mobilidade. Em outra aplicação, tratam estruturas proteicas como redes de aminoácidos conectados quando estão próximos no espaço. Sem qualquer aprendizado ou características feitas à mão, agrupar proteínas pela nova distância alcança cerca de 75% de acurácia na separação de enzimas e não-enzimas — competitiva com abordagens modernas supervisionadas baseadas em redes neurais.

O que isso significa em termos simples

Essencialmente, este trabalho mostra que prestar atenção a como nós e arestas moldam conjuntamente as distâncias em uma rede fornece uma “impressão digital” muito mais nítida do que olhar apenas para nós. Ao quantificar quanto se perde quando tentamos substituir arestas por seus extremos — ou nós por suas arestas circundantes — a distância por entropia hierárquica proposta destaca diferenças estruturais sutis que afetam fortemente a propagação, a mobilidade e a função biológica. Para cientistas e analistas que trabalham com qualquer tipo de dados de rede, isso oferece uma ferramenta prática e de uso geral para comparar sistemas complexos de maneira matematicamente sólida e intimamente ligada a como processos realmente se desenrolam nessas redes.

Citação: Mou, J., Wang, L., Zhang, C. et al. Network hierarchy entropy for quantifying graph dissimilarity. Commun Phys 9, 83 (2026). https://doi.org/10.1038/s42005-026-02523-9

Palavras-chave: similaridade de redes, redes complexas, medidas de entropia, propagação epidêmica, redes de estrutura de proteínas