Come i Big Data hanno portato la teoria dei grafi in nuove dimensioni

La teoria dei grafi non lo è abbastanza.

Il linguaggio matematico per parlare di connessioni, che di solito dipende dalle reti – vertici (punti) e bordi (linee che li collegano) – è stato un modo inestimabile per modellare i fenomeni del mondo reale almeno dal XVIII secolo. Ma alcuni decenni fa, l’emergere di set di dati giganteschi ha costretto i ricercatori ad espandere le loro cassette degli attrezzi e, allo stesso tempo, ha dato loro delle sabbiere tentacolari in cui applicare nuove intuizioni matematiche. Da allora, ha detto Josh Grochow, uno scienziato informatico dell’Università del Colorado, Boulder, c’è stato un entusiasmante periodo di rapida crescita poiché i ricercatori hanno sviluppato nuovi tipi di modelli di rete in grado di trovare strutture e segnali complessi nel rumore dei big data.

Grochow fa parte di un crescente coro di ricercatori che sottolineano che quando si tratta di trovare connessioni nei big data, la teoria dei grafi ha i suoi limiti. Un grafico rappresenta ogni relazione come una diade o interazione a coppie. Tuttavia, molti sistemi complessi non possono essere rappresentati da sole connessioni binarie. I recenti progressi nel campo mostrano come andare avanti.

Considera di provare a creare un modello di genitorialità in rete. Chiaramente, ogni genitore ha una connessione con un figlio, ma la relazione genitoriale non è solo la somma dei due collegamenti, come potrebbe modellarla la teoria dei grafi. Lo stesso vale per il tentativo di modellare un fenomeno come la pressione dei pari.

“Ci sono molti modelli intuitivi. L’effetto della pressione dei pari sulle dinamiche sociali viene catturato solo se hai già gruppi nei tuoi dati “, ha affermato Leonie Neuhauser della RWTH Aachen University in Germania. Ma le reti binarie non catturano le influenze del gruppo.

Matematici e informatici usano il termine “interazioni di ordine superiore” per descrivere questi modi complessi in cui le dinamiche di gruppo, piuttosto che i collegamenti binari, possono influenzare i comportamenti individuali. Questi fenomeni matematici compaiono in tutto, dalle interazioni di entanglement nella meccanica quantistica alla traiettoria di una malattia che si diffonde attraverso una popolazione. Se un farmacologo volesse fare il modello interazioni farmacologiche, ad esempio, la teoria dei grafi potrebbe mostrare come due farmaci rispondono l’uno all’altro, ma che dire di tre? O quattro?

Sebbene gli strumenti per esplorare queste interazioni non siano nuovi, è solo negli ultimi anni che i set di dati ad alta dimensionalità sono diventati un motore per la scoperta, offrendo a matematici e teorici delle reti nuove idee. Questi sforzi hanno prodotto risultati interessanti sui limiti dei grafici e sulle possibilità di scalabilità.

“Ora sappiamo che la rete è solo l’ombra della cosa”, ha detto Grochow. Se un set di dati ha una struttura sottostante complessa, modellarlo come un grafico può rivelare solo una proiezione limitata dell’intera storia.

Emilie Purvine del Pacific Northwest National Laboratory è entusiasta della potenza di strumenti come gli ipergrafi per mappare le connessioni più sottili tra i punti dati.

Fotografia: Andrea Starr/Laboratorio nazionale nordoccidentale del Pacifico

“Ci siamo resi conto che le strutture di dati che abbiamo usato per studiare le cose, da una prospettiva matematica, non si adattano perfettamente a ciò che vediamo nei dati”, ha detto il matematico Emilie Purvine del Pacific Northwest National Laboratory.

Ecco perché matematici, informatici e altri ricercatori si stanno sempre più concentrando sui modi per generalizzare la teoria dei grafi, nelle sue molte forme, per esplorare fenomeni di ordine superiore. Gli ultimi anni hanno portato un torrente di modi proposti per caratterizzare queste interazioni e per verificarle matematicamente in set di dati ad alta dimensione.

Per Purvine, l’esplorazione matematica delle interazioni di ordine superiore è come la mappatura di nuove dimensioni. “Pensa a un grafico come base su un appezzamento di terreno bidimensionale”, ha detto. Gli edifici tridimensionali che possono andare in cima potrebbero variare notevolmente. “Quando sei a livello del suolo, hanno lo stesso aspetto, ma ciò che costruisci sopra è diverso.”

Entra nell’Ipergrafo

La ricerca di quelle strutture a più dimensioni è il punto in cui la matematica diventa particolarmente torbida e interessante. L’analogo di ordine superiore di un grafico, ad esempio, è chiamato ipergrafo e, invece di bordi, ha “iperagenti”. Questi possono connettere più nodi, il che significa che possono rappresentare relazioni multidirezionali (o multilineari). Invece di una linea, un hyperedge potrebbe essere visto come una superficie, come un telo fissato in tre o più punti.

Il che va bene, ma ci sono ancora molte cose che non sappiamo su come queste strutture si relazionano alle loro controparti convenzionali. I matematici stanno attualmente imparando quali regole della teoria dei grafi si applicano anche alle interazioni di ordine superiore, suggerendo nuove aree di esplorazione.

Per illustrare i tipi di relazione che un ipergrafo può ricavare da un grande insieme di dati, e un normale grafico non può, Purvine indica un semplice esempio vicino a casa, il mondo della pubblicazione scientifica. Immagina due set di dati, ciascuno contenente articoli scritti da un massimo di tre matematici; per semplicità, chiamiamoli A, B e C. Un set di dati contiene sei documenti, con due documenti per ciascuna delle tre coppie distinte (AB, AC e BC). L’altro contiene solo due articoli in totale, ciascuno scritto da tutti e tre i matematici (ABC).

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *