Ricerca ProgettiProgetti nazionaliNextGRAAL

NextGRAAL - Next-generation algorithms for constrained GRAph visuALization

Descrizione

I modelli basati su grafi sono pervasivi in molti campi della scienza e della tecnologia, e la loro visualizzazione svolge un ruolo cruciale nell'analisi e nell'esplorazione di dataset complessi. In questo scenario, il disegno dei grafi è un'area di ricerca chiave il cui obiettivo finale è costruire visualizzazioni utili di grafi e reti. Nonostante i grandi sforzi degli ultimi trent'anni, il problema di calcolare visualizzazioni efficaci rimane ampiamente sfuggente e urgente. L'obiettivo del progetto NextGRAAL è sviluppare nuovi risultati algoritmici e nuovi paradigmi di visualizzazione che forniranno le basi scientifiche per la prossima generazione di software e strumenti, capaci di calcolare efficientemente visualizzazioni di grafi di alta qualità con vincoli applicativi di vario tipo. Oltre ai contributi metodologici, il progetto validerà sperimentalmente le soluzioni algoritmiche su due rilevanti domini applicativi e sarà conseguentemente organizzato in due principali parti di lavoro.

WP1: Metodologie algoritmiche con garanzie teoriche per la visualizzazione e l'esplorazione di grafi vincolati. Pianifichiamo di sfruttare algoritmi parametrizzati ed esatti, possibilmente abbinati a limiti inferiori di complessità, per calcolare in modo efficiente soluzioni provabilmente buone per problemi difficili riguardanti i layout di grafi vincolati. Progetteremo inoltre algoritmi di enumerazione per esplorare soluzioni derivanti da problemi di layout con vincoli rilassati.

WP2: Validazione delle soluzioni algoritmiche per la visualizzazione e l'esplorazione di grafi vincolati. Sebbene i nostri algoritmi possano essere utili per molteplici applicazioni, li valideremo su due scenari rilevanti, cioè le reti socio-semantiche e di trasporto. Esplorare il primo riunisce lo studio di due processi di generazione dei dati intrecciati: una comunità sociale e un processo di creazione di contenuti. Visualizzare il secondo è cruciale per rendere complesse infrastrutture facilmente accessibili a un ampio insieme di utenti.

Impatto. Data l'ubiquità dei grafi nella scienza e nella tecnologia, nonché il ruolo chiave della visualizzazione nelle pipeline di elaborazione dei grafi, NextGRAAL ha un grande potenziale per avere un forte impatto sulla ricerca, sull'industria e sulla società.

Personale DiSIA coinvolto

Andrea Marino, responsabile unità operativa
Ana Shirley Ferreira Da Silva

Partenariato

Coordinatore
Università degli Studi di Perugia
Partner
Università degli Studi di Firenze - UNIFI
Luiss Libera Università internazionale degli studi sociali Guido Carli - LUISS
Università degli Studi di Roma Tre - UNIROMA3

 

Progetto finanziato all’Università degli Studi di Firenze nell’ambito del PNRR-M4C2 - linea di investimento 1.1. Progetti di Ricerca di Rilevante Interesse Nazionale (PRIN) – Avviso 104 del 2 FEBBRAIO 2022 - BANDO PRIN 2022. CUP B53D23013130006.