Contatti:
email istituzionale: g.recupito@studenti.unisa.it
email privata: gilbertrecupito@gmail.com
Github: https://github.com/gilbertrec
Introduzione:
Sono uno studente iscritto al Corso di Laurea Triennale in Informatica dell'Università degli Studi di Salerno. Da Aprile 2019 sono entrato a far parte dell'ISISLab come tirocinante. L'obiettivo di tirocinio è lo studio di ipergrafi per la realizzazione di una repository che analizza i diversi dataset del web tramite ipergrafi, messa a disposizione per la comunità scientifica, scritta in Linguaggio Julia.
Progressi di Tirocinio:
Il lavoro di tirocinio è iniziato con lo studio del linguaggio di programmazione Julia e delle definizioni, proprietà e contesti di applicazione reali degli Ipergrafi.
Il passo successivo è stato progettare e implementare un tool che permette operazioni di analisi su ipergrafi, per poi essere distribuiti e pubblicati sul repository.
E' stata quindi implementata la componente parser che trasforma i dataset relativi ai grafi in ipergrafi aggiungendo ad essa i metadata rilevanti, e la componente analyzer che prendendo in input il risultato della componente precedente, calcola e mostra le metriche che permettono di effettuare un'analisi accurata. E' stata poi aggiunta alla progettazione e implementata una nuova componente (PostsBuilder) per la generazione (semi) automatica di file utili per la pubblicazione sul repository Web.
Software e Librerie:
- Julia version 1.0.4 (https://julialang.org/)
- Atom release 1.37.0 x64 (https://atom.io/)
- SimpleHypergraphs.jl (https://github.com/pszufe/SimpleHypergraphs.jl)
- LightGraphs.jl ( https://github.com/JuliaGraphs/LightGraphs.jl)
Seminari:
Primo Seminario:
- Titolo seminario: Studio e Analisi di Ipergrafi in Julia
- Contenuto: Gli ipergrafi permettono di modellare relazioni più complesse rispetto ai grafi, dei quali ne costituiscono una generalizzazione. Infatti, mentre un grafo è in grado di modellare relazioni binarie, un ipergrafo è capace di modellare relazioni tra un numero arbitrario di oggetti.
Data la crescente importanza di tali strutture per modellare sistemi complessi reali, nasce la necessità per la comunità scientifica di avere un dataset comune, per avere un benchmark accurato e corretto tra i risultati di vari studi o di algoritmi.
In tale contesto si inserisce questo lavoro di tesi: Il primo obiettivo è stata l’implementazione di una libreria che permette la trasformazione dei grafi che sono rappresentati sulla base di dati e metadati in ipergrafi, scritta in linguaggio Julia. Secondo obiettivo è il design ed implementazione di un repository di benchmark e analisi di network tramite ipergrafi.
Questo seminario presenterà gli ipergrafi, le applicazioni di essi in vari contesti reali e infine verterà sul mio contributo al progetto, mostrando le componenti principali della nostra libreria. - Presentazione: la presentazione di questo seminario è disponibile al seguente link:
Abstract:
Questo lavoro di tesi si focalizza sullo studio e sull’analisi di ipergrafi, strutture matematiche impiegate nella modellazione di sistemi reali in cui le relazioni da rappresentare riguardano insiemi di oggetti. Gli ipergrafi permettono, infatti, di modellare relazioni più complesse rispetto ai grafi, dei quali ne costituiscono una generalizzazione; mentre un grafo è in grado di modellare relazioni tra coppie di oggetti, un ipergrafo è capace di modellare relazioni tra un insieme generico di oggetti.
Per avere un’intuizione della potenza espressiva di tali strutture matematiche, si pensi alla seguente situazione: si consideri un insieme di utenti ed un insieme di mail scambiate tra questi. La modellazione tramite grafo rappresenterebbe i diversi utenti come vertici e assocerebbe un arco per ogni coppia di vertici ad indicare uno scambio di mail tra questi.
Il problema di questa rappresentazione è che non si è in grado di risalire a quali mail i diversi utenti abbiano scritto o letto. In tali contesti, i grafi comportano quindi, una perdita di informazione.\
Per loro natura, gli ipergrafi permettono invece di modellare con facilità tali situazioni.
Gli ipergrafi trovano posizione e interesse in molti contesti reali come in una rete sociale, in una rete di telecomunicazione o in una rete molecolare. Una rete sociale può essere esaminata, ad esempio, come un sistema composto da utenti raggruppati per comunità. Una rete di telecomunicazione può essere rappresentata come un sistema di dispositivi assegnati a delle sottoreti. Una rete molecolare definisce una struttura composta da atomi uniti da legami chimici per la formazione di molecole. Questi sono tutti esempi concreti di sistemi di relazioni tra elementi e sottoinsiemi di elementi. Questi sistemi sono modellabili tramite un ipergrafo trattando gli elementi come vertici e i sottoinsiemi di elementi come iperarchi. Ad esempio, gli utenti di una rete sociale possono essere modellati tramite i vertici dell’ipergrafo e collegati tramite iperarchi per rappresentare le comunità.
Data la crescente importanza di tali strutture per modellare sistemi complessi reali, si sta riconsiderando l’utilità degli ipergrafi per la risoluzione di problemi in diversi ambiti scientifici. Tuttavia, non è ancora disponibile per la comunità accademica ed industriale un dataset comune per lo studio, lo sviluppo, l’analisi ed il benchmark di algoritmi ed applicazioni basati su ipergrafi, così come accade per i grafi.
Se tra diversi esperimenti vengono utilizzati dataset di diversa natura, non è semplice poter effettuare un confronto tra i risultati. Se invece gli esperimenti si attenessero allo stesso dataset, avendo quindi un comune punto di partenza, i risultati possono essere facilmente confrontabili. Nasce, quindi, la necessità per la comunità scientifica di avere, in maniera condivisa, un insieme di dataset in un formato standard e coerente, che permetta di avere un benchmark accurato e corretto dei risultati di vari studi o di algoritmi.
In tale contesto si inserisce questo lavoro di tesi.
Il primo obiettivo è l’implementazione di un tool che permetta la modellazione e l’analisi di insiemi di dati tramite ipergrafi, scritto in linguaggio Julia. L’architettura è stata progettata seguendo i principi di modularità e di raffinamento delle componenti. Il tool, infatti, è strutturato in due componenti principali: il Parser e l’ Analyzer. La prima componente si occupa di trasformare un insieme di dati in un ipergrafo, trovando gli elementi e le loro relazioni per rappresentare rispettivamente vertici e iperarchi. La seconda analizza la struttura generata dalla componente precedente attraverso il calcolo di specifiche metriche per mostrare le caratteristiche e la struttura dell’ipergrafo. La seconda componente fornisce, inoltre, una modellazione a grafo per poter evidenziare e confrontare le differenze strutturali tra la modellazione tramite un grafo e tramite un ipergrafo.
Il secondo obiettivo è la generazione di un repository di ipergrafi, disponibile sul Web, per collezionare, pubblicare, e visualizzare i dati delle diverse reti, accessibili da tutta la comunità scientifica.
Per consentire una generazione automatica delle pagine web contenenti informazioni sull’ipergrafo da visualizzare e analizzare è stata, quindi, aggiunta all’architettura una terza componente: il PostBuilder.
Questa componente riceve le metriche sulla struttura e le proprietà dell’ ipergrafo prodotte dal tool. Ad esse, aggiunge informazioni di varia natura sulla rete in questione, come titolo o descrizione. Tali informazioni sono pubblicate sul repository, dove è possibile scaricare il dataset e, attraverso grafici e tabelle, visualizzare e analizzare le metriche sulla rete.
Bibliografia:
- Documentazione di Julia
- Introduction to Distributed Computing with Julia -Przemysaw Szufel Warsaw School of Economics (WSE – SGH), Poland
- Documentazione di LightGraphs
- Hypergraph Theory - Alain Bretto, 2013