Is star complexity a proxy for information based complexity of graphs?

Sintesi Tecnica: La complessità delle stelle come proxy per la complessità basata sull'informazione dei grafi

Enunciato del problema
Il saggio investiga se la "complessità delle stelle" (star complexity), una misura strutturale dei grafi, possa fungere da proxy pratico per la "Complessità Basata sull'Informazione" (IBC). L'IBC è una misura di complessità formale definita dalla proporzione di descrizioni in un linguaggio specifico che mappano un dato oggetto tramite un classificatore. Sebbene l'IBC teorica (basata su macchine di Turing universali) sia asintoticamente indipendente dal linguaggio di codifica, il saggio ipotizza che le misure di IBC pratiche derivate da diversi schemi di codifica saranno anch'esse asintoticamente equivalenti. Nello specifico, lo studio confronta una misura IBC standard per i grafi ($C$), che codifica i grafi tramite liste di archi e li classifica tramite automorfismo, con la complessità delle stelle, che definisce la complessità sulla base del numero minimo di operazioni di unione e intersezione di "stelle" elementari necessarie per costruire un grafo.

Metodologia
La ricerca impiega un approccio empirico comparativo utilizzando due misure di complessità distinte:

1. Complessità del grafo ($C$): Calcolata utilizzando la formula $C(x) = \ell - \log_2 \omega(x)$, dove $\ell$ è la lunghezza della codifica della lista di archi e $\omega$ è il numero di stringhe di quella lunghezza che mappano lo stesso grafo (determinato tramite algoriti di automorfismo di grafi utilizzando la libreria Nauty).
2. Complessità delle stelle ($Star(G)$): Definita come il numero minimo di operazioni di insieme (unione/intersezione) di stelle elementari (un vertice hub connesso a tutti gli altri) necessarie per generare un grafo.
3. IBC basata sulle stelle ($C^*$): Una misura IBC derivata specificamente dalla complessità delle stelle. Codifica il grafo memorizzando il numero di vertici, il numero di stelle e una "ricetta" in Notazione Polacca Inversa (RPN) delle operazioni. $C^*$ aggiusta la lunghezza in bit di questa ricetta sottraendo $\log_2 \omega$, dove $\omega$ rappresenta il numero di ricette equivalenti per un dato grafo.
4. Stima del limite superiore ($\overline{Star}(G)$): Poiché il calcolo del valore esatto di $Star(G)$ richiede una ricerca esaustiva di tutte le possibili sequenze di operazioni (il che è computazionalmente impraticabile per grafi di grandi dimensioni), gli autori introducono un limite superiore algoritmico. Questo algoritmo costruisce un grafo coprendo i vertici di grado massimo con le stelle e coprendo gli archi rimanenti tramite intersezioni a coppie, ottimizzando poi l'espressione tramite associatività dell'insieme.

Esecuzione Sperimentale
Lo studio ha utilizzato il pacchetto EcoLab, ottimizzato per l'esecuzione su GPU (Intel Xe graphics) per ottenere un'accelerazione di 23 volte rispetto all'elaborazione su CPU single-threaded. Gli esperimenti hanno previsto:

• Ricerca esaustiva su piccola scala: Generazione di tutti i grafi con 10 e 22 vertici aventi una complessità delle stelle pari o inferiore a 8. Ciò ha permesso il calcolo esatto di $C$, $Star(G)$e$C^*$, inclusa l'enumerazione delle ricette equivalenti ($\omega$).
• Campionamento su larga scala: Generazione di 1.000 grafi casuali di Erdős-Rényi con 1.000 vertici per testare la relazione tra il facilmente computabile limite superiore $\overline{Star}(G)$ e la complessità standard $C$.

Risultati Chiave

• Piccoli grafi (10 e 22 vertici): La correlazione tra la complessità standard $C$ e la complessità delle stelle grezza $Star(G)$ è risultata trascurabile (coefficienti di correlazione $\rho \approx 0,08$ e $-0,04$, rispettivamente). Allo stesso modo, la correlazione tra $C$ e l'IBC derivata dalle stelle $C^*$ è stata debole ($\rho \approx 0,14$ e vicina allo zero).
• Correlazione delle misure: Tuttavia, $Star(G)$e$C^*$ hanno mostrato una moderata correlazione positiva ($\rho \approx 0,6$), e il limite superiore stimato $\overline{Star}(G)$ era fortemente correlato con l'esatto $Star(G)$($\rho \approx 0,85$).
• Grandi grafi (1.000 vertici): Il risultato più significativo è emerso dal campionamento su larga scala. È stata osservata una relazione forte, sebbene non lineare, tra il limite superiore computabile $\overline{Star}(G)$ e la complessità basata sull'informazione $C$.

Significatività e Rivendicazioni
Il saggio conclude che, sebbene la complessità delle stelle grezza non correli linearmente con la complessità basata sull'informazione su dataset esaustivi di piccole dimensioni, le due misure misurano probabilmente la stessa proprietà sottostante per grafi più grandi. La forte relazione empirica tra il facilmente computabile limite superiore della complessità delle stelle $\overline{Star}(G)$ e la misura IBC standard ($C$) suggerisce che la complessità delle stelle agisce come un valido proxy per la complessità basata sull'informazione in scenari pratici. Gli autori postulano che ciò supporti l'ipotesi più ampia secondo cui diversi schemi di codifica dell'IBC pratica sono asintoticamente equivalenti. Di conseguenza, la complessità delle stelle, essendo più computazionalmente trattabile rispetto ai calcoli completi dell'IBC per grafi di grandi dimensioni, può servire come stimatore affidabile della complessità del grafo.