Entropia della gerarchia di rete per quantificare la dissimilarità dei grafi

Perché piccole differenze nelle reti contano

Dalle amicizie sui social media alle rotte aeree e alle strutture proteiche, molti sistemi intorno a noi possono essere rappresentati come reti di nodi e collegamenti. Ma stabilire quando due di queste reti sono significativamente diverse è sorprendentemente difficile, specialmente quando a prima vista sembrano simili. Questo articolo introduce un nuovo modo per misurare quanto due reti siano effettivamente diverse, prestando attenzione non solo ai singoli punti (nodi) ma anche ai collegamenti (archi) e a come funzionano insieme. Il metodo, chiamato entropia della gerarchia di rete, è in grado di rilevare cambiamenti strutturali sottili che altri strumenti non colgono e aiuta persino a distinguere proteine enzimatica da non enzimatica.

Osservare le reti strato dopo strato

Per comprendere una rete, gli autori considerano prima quanto è distante ogni nodo da ogni altro in termini di passi lungo i collegamenti. Intorno a un nodo scelto, gli altri nodi possono essere raggruppati in strati: vicini immediati, vicini dei vicini e così via. Questa “gerarchia” attorno a un nodo descrive come l’influenza o un’infezione potrebbe propagarsi verso l’esterno attraverso la rete. La particolarità è che due reti molto diverse possono condividere la stessa stratificazione a livello di nodi, quindi questa visione da sola può non bastare per distinguerle. L’articolo mostra che esempi classici, come i grafi di Desargues e il dodecaedro, condividono gerarchie dei nodi identiche nonostante il loro cablaggio interno sia diverso.

Lasciare parlare gli archi: contrazione di coppie di nodi

Per catturare ciò che la vista a livello di nodi perde, gli autori si concentrano sugli archi — i collegamenti tra nodi — e su come questi rimodellano le distanze nella rete. Introducono un’idea semplice ma efficace: la “contrazione” di coppie di nodi. Qui, due nodi connessi vengono temporaneamente fusi in un unico nuovo nodo, mantenendo però i loro vicini combinati. Questo rivela quanto ogni altro nodo sia vicino alla coppia rispetto a ciascuno degli estremi da solo. In termini di diffusione, imita l’effetto di infettare contemporaneamente entrambe le estremità di un collegamento invece di partire da un solo nodo. Da questi schemi di distanza per strati, definiscono la “centralità gerarchica” per nodi e archi, che risulta fortemente correlata con l’efficacia di nodi o archi come diffusori in epidemie simulate su reti reali.

Misurare la perdita di informazione con l’entropia

Partendo da queste centralità, gli autori definiscono due tipi di entropia della gerarchia. L’entropia della gerarchia degli archi si chiede: quanta informazione perdiamo se proviamo ad approssimare l’importanza di un arco semplicemente mediando l’importanza dei due nodi che collega? L’entropia della gerarchia dei nodi pone la domanda inversa per i nodi e i loro archi circostanti. Entrambe le quantità sono normalizzate in modo da non dipendere dalla dimensione complessiva della rete. Insieme formano un’impronta a due numeri per qualsiasi rete. La distanza tra due reti è quindi semplicemente la distanza geometrica tra le loro impronte. Questa nuova metrica obbedisce alle regole standard che ci si aspetta da una distanza e corrisponde a intuizioni pratiche, per esempio infliggendo penalità maggiori quando un cambiamento frammenta la rete.

Rilevare strutture più fini e i cambiamenti nel tempo

Gli autori testano la loro misura sia su reti artificiali sia reali. In benchmark sintetici che simulano sistemi sociali o tecnologici, la nuova metrica può seguire l’evoluzione delle reti al variare dei parametri del modello e distingue chiaramente reti con comunità forti da quelle con comunità più deboli, anche quando metodi concorrenti faticano. In esperimenti controllati in cui le reti sono rimescolate con cura per preservare molte statistiche comuni — come le sequenze di grado e persino le distribuzioni delle distanze — la distanza basata sull’entropia della gerarchia rileva comunque differenze che altre misure popolari considerano trascurabili. Eccelle anche nel raggruppare versioni randomizzate della stessa rete nelle categorie corrette, indicando una sensibilità acuta alla struttura di ordine superiore che va oltre il semplice conteggio di collegamenti e percorsi.

Applicazioni nel mondo reale: mobilità e proteine

Per mostrare il valore pratico, gli autori applicano la loro misura di distanza alle reti di mobilità quotidiana tra centinaia di città cinesi nei primi mesi della COVID-19. Usando i primi giorni di gennaio come riferimento, l’entropia della gerarchia rivela come i pattern di viaggio cambiano durante il picco delle partenze per il Capodanno lunare, l’introduzione di severe quarantene e il periodo di ripresa graduale, in accordo con le modifiche delle politiche note e con i modelli di comunità nella mobilità. In un’altra applicazione, trattano le strutture proteiche come reti di amminoacidi connessi quando sono vicini nello spazio. Senza alcun apprendimento o caratteristiche costruite a mano, il clustering delle proteine usando la nuova distanza raggiunge circa il 75% di accuratezza nella separazione di enzimi da non enzimi — competitivo con approcci moderni supervisionati basati su reti neurali.

Cosa significa, in termini semplici

In sostanza, questo lavoro mostra che prestare attenzione a come nodi e archi modellano congiuntamente le distanze in una rete fornisce un’impronta molto più netta rispetto all’osservazione dei soli nodi. Quantificando quanto si perde quando si tenta di sostituire gli archi con i loro estremi — o i nodi con gli archi circostanti — la distanza basata sull’entropia della gerarchia mette in luce differenze strutturali sottili che influenzano fortemente la diffusione, la mobilità e la funzione biologica. Per scienziati e analisti che lavorano con qualsiasi tipo di dati di rete, questo offre uno strumento pratico e di uso generale per confrontare sistemi complessi in modo sia matematicamente solido sia strettamente legato a come i processi effettivamente si svolgono su tali reti.

Citazione: 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

Parole chiave: similarità delle reti, reti complesse, misure di entropia, diffusione epidemica, reti di struttura proteica