UNIVERSITÀ DI PISA
Dipartimento di Filologia, Letteratura e Linguistica Corso di Laurea Magistrale In Informatica Umanistica
TESI DI LAUREA
Open Data nelle pubbliche amministrazioni: esplorare gli atti attraverso tecniche di network analysis e data visualization
RELATORI
Prof. Roberto Trasarti Dr. Giulio Rossetti
CANDIDATO Martina Miliani
Indice
1 SemplicePA, la piattaforma 3
1.1 Gli OpenData in Italia . . . 3
1.1.1 Open Data, una definizione . . . 3
1.1.2 Open Europe . . . 4
1.1.3 L’Italia che insegue . . . 4
1.2 Il valore della Rete . . . 6
1.2.1 Reti aperte ed Open Data . . . 7
1.3 L’Albo Pretorio, questo sconosciuto . . . 9
1.4 Cos’è un motore di ricerca semantico . . . 10
1.5 SemplicePA, una piattaforma . . . 13
1.5.1 Il motore semantico . . . 13
1.5.2 Scenari . . . 15
1.5.3 Informazioni in Rete . . . 16
2 Network Analysis: proprietà e misure 18 2.1 Nodi e Archi . . . 18
2.1.1 Direzione . . . 18
2.1.2 Componenti . . . 19
2.1.3 Densità . . . 19
2.1.4 Ego-Network . . . 20
2.2 Le misure dei nodi . . . 20
2.2.1 Degree Centrality . . . 20
2.2.2 Closeness Centrality . . . 22
2.2.3 Betweenness Centrality . . . 22
2.3.1 Bridge e Legami deboli . . . 23
2.4 Backboning . . . 24
2.4.1 Stato dell’Arte . . . 25
2.4.2 Noise Corrected . . . 27
2.5 Graphlet, pattern e anomalie . . . 28
2.5.1 Motif . . . 28
2.5.2 Graphlet . . . 30
3 Inferenza, lo strumento e i dati 32 3.1 Dati . . . 32
3.2 Funzionalità . . . 36
4 Progettare la User Experience 39 4.1 Architettura dell’Informazione . . . 39
4.1.1 Progettazione . . . 43
4.2 Usabilità . . . 46
4.2.1 Realizzare un dialogo semplice e naturale . . . 47
4.2.2 Semplificare la struttura dei compiti . . . 48
4.2.3 Favorire il riconoscimento piuttosto che il ricordo . . . . 48
4.2.4 Rendere visibile lo stato del sistema attraverso un feedback 49 4.2.5 Prevenire e limitare gli errori di interazione e facilitarne il recupero . . . 50
4.2.6 Essere coerenti . . . 50
4.2.7 Facilitare la flessibilità d’utilizzo e l’efficienza dell’utente 51 4.2.8 Fornire help e manuali . . . 51
4.3 Accessibilità . . . 54
4.3.1 Aspetto . . . 54
4.3.2 Struttura . . . 55
4.3.3 Comportamento . . . 56
5 Progettazione del Servizio 59 5.1 Dati e strumenti . . . 59
5.1.1 Trasformazione dei dati . . . 59
5.1.3 Gli strumenti . . . 61
5.2 Componenti . . . 64
5.2.1 Visualizzazione della rete . . . 64
5.2.2 Misure di centralità . . . 73
5.2.3 Download dei dati . . . 76
5.2.4 Statistiche del grafo . . . 77
5.2.5 Statistiche dei nodi . . . 78
5.2.6 Rete dei vicini . . . 79
5.2.7 Graphlet . . . 80
6 Test di usabilità 85 6.1 Metodologia . . . 85
6.1.1 Test fai da te . . . 86
6.1.2 eGLU: usabilità per le PA . . . 88
6.2 Il test . . . 89
6.2.1 Partecipanti . . . 89
6.2.2 Esecuzione . . . 89
6.2.3 Risultati . . . 95
Introduzione
Questo elaborato intende descrivere il processo di progettazione e creazione di un’interfaccia web che consenta la visualizzazione dei dati estratti dai do-cumenti degli atti amministrativi. I dati testuali sono definiti non strutturati, proprio perché, al contrario di strutture dati come le tabelle o database, non sono machine readable. Lo strumento utilizzato per l’estrazione delle informa-zioni dai documenti è SemplicePA e si basa su Natural Language Processing, Machine Learning e altre tecniche che rientrano nell’ambito della linguistica computazionale. Nato da un progetto che vede la collaborazione dell’Univer-sità di Pisa, SemplicePA è una piattaforma in grado di navigare i documenti attraverso un motore di ricerca semantico, che, tra le altre, comprende una sezione di visualizzazione degli atti che intende esplorare le relazioni tra le entità citate. Questa sezione mostra infatti una rete i cui elementi sono dati dalle persone, le aziende e le organizzazioni estratte, legate tra loro se citate nello steso documento. L’uscita delle nuove linee guida dell’Agenzia per l’Italia Digitale e le possibilità offerte dalle teniche di network analysis esistenti hanno posto la questione di un possibile restyling della sezione. In questa tesi si propone quindi un nuovo prototipo, che non solo rispetti i criteri di usabilità e accessibilità dettati da AgID per le pubbliche amministrazioni, ma che inquadri, all’interno di un processo di analisi progettuale, in termini di architettura dell’informazione, vecchie e nuove funzionalità, queste ultime ispirate a tecniche di network analysis.
Nel primo capitolo sarà quindi introdotto lo stato degli open data in Italia, con particolare riferimento all’albo pretorio, l’archivio degli atti di ciascun comune amministrativo. Dopo uno stato dell’arte sulle soluzioni e le piattaforme adottate in Europa e in Italia per la gestione dei documenti attraverso motori
di ricerca semantici, saranno introdotte le funzionalità di SemplicePA.
Il capitolo successivo, invece, mostra un excursus delle basilari nozioni di network analysis, con particolare riferimento a due tecniche che saranno poi implementate anche nell’interfaccia: il calcolo della backbone e l’individuazione dei graphlet, con relativo stato dell’arte.
Nel terzo capitolo sarà descritta nel dettaglio la sezione di SemplicePA esistente relativa alla visualizzazione delle reti, sia dal lato server che da quello client, comprendendo anche un’analisi delle funzionalità e degli strumenti di web-design scelti.
Il quarto capitolo propone una visione progettuale della nuova interfaccia e si suddivide in tre parti: la prima relativa all’architettura dell’informazione, in cui si individuano i bisogni dell’utente e relative funzionalità della piattaforma, e le restanti in cui si riportano le regole di usabilità e accessibilità di AgID, si compie un’analisi delle criticità della sezione esistente e si illustrano le soluzioni adottate per superarle.
Il quinto capitolo è strettamente legato alla fase di implementazione. Sono illustrati, oltre ai linguaggi, i framework le librerie utilizzate, anche il flusso e l’elaborazione dei dati. Viene poi ripresa l’architettura progettata nelle pagine precedenti, e analizzato punto per punto il processo di sviluppo della piattaforma.
L’ultimo capitolo di questa tesi descrive una prima sessione di test di usabilità condotta sul prototipo. Dopo aver motivato la scelta della metodologia utilizzata, che si attine al protocollo eGLU per i siti delle PA, si procede all’esposizione dell’esecuzione e all’analisi dei risultati. Alcune proproste sono infine avanzate con lo scopo di superare le criticità riscontrate.
Capitolo 1
SemplicePA, la piattaforma
Not using knowledge is an offense to it. If it cannot fly free beyond the
confines of content, knowledge cannot reach its full value through collaboration, correction, inspiration, and use. (Jarvis, 2013)
La trasformazione digitale italiana sta procedendo ancora a rilento rispetto a quella Europea, con un digital divide che penalizza soprattutto i comuni più piccoli e gli open data che faticano ad essere pienamente valorizzati, con il risultato che il Foia è ancora ben lungi dall’essere applicato come dovrebbe. Eppure non mancano le iniziative civiche, alcune stimolate dalle stesse am-ministrazioni. Così come non mancano le tecnologie di eccellenza, sviluppate all’interno di start-up che collaborano con università statali e centri di ricerca. SemplicePa nasce in questo contesto con lo scopo di fornire uno strumento utile alla cittadinanza e alle amministrazioni a partire dalla trasformazione digitale di un archivio spesso sconosciuto, l’albo pretorio.
1.1
Gli OpenData in Italia
1.1.1
Open Data, una definizione
"Open data is data that anyone can access, use or share”. Sono le parole dell’Open Data Institute (2017), co-fondato dall’inventore del web Tim Berners-Lee. Lo stesso che 20 anni dopo ha lanciato un appello: “Raw data now!” (Berners-Lee, 2009). La rete non è la stessa che Berners-Lee si immaginava
riportare il web alle sue origini, quelle di uno spazio libero e aperto (Berners-Lee, 2017).
Gli open data sono dati non personali rilasciati da aziende, pubbliche amministrazioni e governi. L’importanza di questi dati deriva dal fatto che se condivisi “permettono a piccole imprese, cittadini ma anche ricercatori e medici di sviluppare risorse che consentono cruciali miglioramenti nella vita delle loro comunità” (ODI, 2017).
1.1.2
Open Europe
Otto paesi su dieci, in Europa, hanno attivato una regolamentazione sugli open data. “Open Data Maturity in Europe 2016: Insights into the European state of play” mostra come l’Italia si trovi solo tra i “follower” delle buone pratiche: un anno fa eravamo ancora sotto la media europea. Il report segnala anche il divario Nord-Sud, con un “Mezzogiorno nettamente indietro” (Tre-molada, 2017). Eppure secondo l’Open Data Census, che raccoglie dati da tutto il mondo, in Italia le cinque amministrazioni che meglio hanno saputo condividere i propri dati sono al momento Lecce, Bologna, Matera, Ferrara e Albano Laziale: ben due città meridionali tra le prime posizioni. Anche secondo l’Open Data Census però il totale di “apertura” dei database italiani resta basso, toccando solo il 38%1.
1.1.3
L’Italia che insegue
La Penisola sta comunque migliorando il suo rapporto col digitale. Dal 2012 al 2015 secondo un report Istat è cresciuto più del doppio il numero di enti che acquista in modalità e-procurement2., che adottano l’e-learning e servizi
di cloud computing: tutte tecnologie volte a ridurre i costi amministrativi. Già due anni fa gli utenti potevano avviare e concludere online l’iter di un servizio per il 33, 8% degli enti, contro il 19, 1% di due anni prima Istat (2015). Ad alimentare le speranze di una pubblica amministrazione più attenta alla condivisione dei propri dati anche l’approvazione del Freedom of Information
1Italia Open Data Census, Overview goo.gl/KAHQPF
2Acquisti online compiuti attraverso il Mepa, il mercato elettronico per le pubbliche amministrazioni.
Act, il 23 dicembre 2016. L’Italia si dota così di uno strumento giuridico che mette avanti i bisogni informativi del cittadino: ogni diniego alla cessione di dati va infatti esplicitato e motivato dall’ente pubblico. Quindi non è più il cittadino a dover motivare la sua richiesta ma l’ente pubblico che deve fornire spiegazioni riguardo l’eventuale incapacità di fornire informazioni.
Allora perché l’Italia sta ancora inseguendo gli standard europei? Due sono i motivi che tra gli altri è possibile individuare. Il primo è il grande divario tra le piccole e le grandi amministrazioni. In base all’osservatorio dell’Istat citato prima, le province autonome e l’85, 5% dei comuni sopra i 60.000 abitanti possiede un ufficio dedicato all’ICT3. Se guardiamo all’intera penisola parliamo
di 90 comuni sui 7978 in totale: poco più dell’1%. Secondo il 60, 7% delle PA l’ostacolo all’utilizzo delle tecnologie informatiche risiede nella mancanza di staff qualificato in materia. Ecco perché “quasi tutte le Amministrazioni locali si avvalgono anche di fornitori privati (94, 1%)”. Ma se il 67, 5% dei comuni lamenta scarse risorse finanziarie da investire in materia, quante volte una pubblica amministrazione potrà avvalersi di questi fornitori? I data scientist che potrebbero occuparsi di open data trovano spazio nelle “grandi testate giornalistiche, le uniche ad assoldarli (anche in organico) insieme alle grandi aziende multinazionali che lavorano con i big data“ spiega Francesco Piero Paolicelli, che ha lavorato da collaboratore esterno come webmaster dei portali open data di Lecce e Matera, due tra le amministrazioni più “aperte” d’Italia. Queste figure sono in genere “chiamate esternamente a consulenza: poche PA -continua - riconoscono la competenza e prima ancora la necessità di un figura professionale che possa aiutarle”. Un altro dei motivi di questo rallentamento va di pari passo con la velocità con cui il Foia viene compreso dagli enti pubblici. I risultati del primo monitoraggio sull’applicazione della legge sono tutt’altro che positivi: 136 risposte soddisfacenti su 800 richieste inviate, il 73% degli utenti non ha ricevuto risposta e un diniego su tre era invece illegittimo. Questi dati sono stati raccolti dal 23 dicembre 2016 al 28 febbraio 2017 dall’associazione Diritto di Sapere che ha deciso di chiamare il report “Ignoranza di Stato”. A motivare questo titolo anche un piccolo aneddoto: “abbiamo toccato con mano la scarsa conoscenza del nuovo istituto - scrive Dds - quando ci è stato
chiesto se il Foia fosse un’azienda” (di Sapere, 2017). Non per niente l’Italia si è auto-commissariata: adesso, accanto all’AgID (Agenzia per l’Italia Digitale), che ha visto succedersi alla guida tre direttori in tre anni (Wikipedia, 2017b), sta lavorando il Team per la Trasformazione Digitale. Un gruppo di esperti, tra data scientist e sviluppatori, riuniti da un ex big di Apple e Amazon, Diego Piacentini, nominato a febbraio 2016 “Commissario per l’attuazione dell’Agenda Digitale”. Il Team di Piacentini ha l’obiettivo di costruire quello che lui stesso ha definito il “sistema operativo del Paese”. Una delle funzioni di questo sistema operativo sarà quella di portare a una diversa concezione delle informazioni possedute dalla pubblica amministrazione, che lascia ben sperare sulla futura applicazione del Foia: “I dati sono nostri e li gestiamo insieme” (Lillo, 2017).
Matteo Fortini, che ha collaborato a progetti come AlboPop4 e
Terremoto-CentroItalia5, adesso assessore per i servizi informativi nel suo comune, sostiene
però che questa “gelosia” delle PA non esista davvero. Secondo Fortini (2017) in realtà le amministrazioni “non sono padrone dei loro dati”: questi sono “chiusi in archivi creati e gestiti dai software dei loro fornitori del momento,
nei confronti dei quali hanno ridottissimi margini contrattuali”. “Aprire i dati -continua - non richiede solo buona volontà: richiede tempo, persone dedicate, e anche denaro. Tutto moltiplicato per gli adempimenti burocratici”. In questo contesto “dei regolamenti che impongano di creare un ufficio per il digitale” non servono a molto: “digitale, open data, formati aperti, sono parole vuote, quasi una lingua straniera, percepita come una complicazione e un dispendio di tempo e denaro, anziché una risorsa”.
1.2
Il valore della Rete
Ma perché considerare gli open data una risorsa su cui spendere nuove energie? Le agenzie di statistica esistono da diverso tempo prima dell’esistenza della rete, anche nella “parentesi Gutenberg” (Garber, 2010) che abbiamo appena superato. Nella fase appena conclusa la comunicazione a livello
indu-4http://albopop.it/
striale è stata possibile adottando un modello standard, quello lineare in cui il limite spazio-temporale stabiliva la direzione da seguire all’interno di una qualsiasi narrazione (da quella dettata dalla scaletta di un tg a quella data dalla successione dei capitoli di un romanzo). Il modello della nuova fase è ovviamente quello della rete che si basa su una “disponibilità illimitata di spazio e su una forma di tempo sospeso che assume le sembianze di un eterno presente” (Badaloni, 2016). Ma l’assioma fondamentale di questa struttura, secondo
Giuseppe Attardi (2011) dell’Università di Pisa, è che “la condivisione di risorse è ciò che gli attribuisce valore: una rete cui non si connette nessuno non ha alcun valore, ed il valore cresce in base al quadrato del numero di nodi connessi [. . .]. Pertanto e nell’interesse di ciascuno, che coincide con l’interesse di tutti, di massimizzare l’interconnettività della propria rete”. E, come precisato da Federico Badaloni, “ciò che vale per la rete nella sua interezza vale anche per le sue porzioni”, quindi perché no, anche per i siti, i dati e le app di servizi che girano intorno a un’amministrazione locale.
1.2.1
Reti aperte ed Open Data
Le nuove tecnologie, infatti, hanno trasformato il modello industriale della comunicazione, e con esso anche le relazioni degli utenti con le istituzioni cardine del governo, dell’istruzione e del commercio (Jenkins, 2006). Gli open data sono una di queste nuove tecnologie. L’elaborazione e la trasformazione dati aperti, quando possibile, viene compiuta anzitutto dalle stesse amministrazioni. Per tutelare la salute dei propri cittadini, ad esempio, il Comune di Lecce ha deciso di mappare le postazioni dei defibrillatori in città6. Ma almeno per il
momento sono le iniziative dei singoli a fare la differenza, sono i cittadini ad aggiungere “archi e nodi” a partire dalle informazioni messe a disposizione dalle amministrazioni. A volte con la collaborazione degli enti pubblici stessi, che indicono contest per premiare il migliore utilizzo degli open data: senza spostarsi da Lecce, l’hackaton sulla disabilità indetto dal Comune ha premiato il censimento delle barriere architettoniche in città7; in Toscana è stato pubblicato
6#opendatalecce, Progetto “Comune Cardio-protetto”, 2 Ottobre 2015 (goo.gl/3xU9ES). 7Lecce, Luoghi accessibili per disabilità varie e di interesse, Umap, 30 Aprile 2016 (goo.gl/NJq6g7).
un bando di concorso per premiare le app create attraverso gli open data della Regione8. Ma sono tantissime anche le iniziative civiche, come il già
citato TerremotoCentroItalia legato al progetto di crowdfunding Ricostruzione Trasparente9, il cui obiettivo è quello di tenere traccia di tutti gli atti pubblici
che consentano di esercitare un controllo diffuso sugli attori della ricostruzione. Si tratta di dati rilasciati dalle pubbliche amministrazioni, che sono stati poi rielaborati e resi fruibili in modi totalmente nuovi dai cittadini, come i dati sulla vulnerabilità sismica degli edifici di Palermo elaborati in 3D dai promotori dell’iniziativa civica #opendatasicilia10. Utilizzando ancora le parole
di Badaloni, ciò può accadere perché “una rete aperta consente a tutti di collaborare per creare nuovi nodi o nuovi archi: così la rete aumenta il proprio valore, aumentando il numero (e in certi casi anche la qualità) dei suoi significati”. Un altro esempio che può spiegare questa affermazione viene d’Oltreoceano e vede una amministrazione americana rendere pubbliche le posizioni degli idranti in città e qualcuno decidere di creare una app mappandoli. Nella app si chiedeva di adottare un idrante e dargli un nome, togliendo la neve che lo ricopre nei mesi invernali e rendendolo quindi utilizzabile: le risposte dei concittadini sono state numerose e immediate (Pahlka, 2012). La messa a disposizione di dati su costi e procedimenti portati avanti dagli enti pubblici, inoltre, facilita il fact-checking e consente di individuare più facilmente le fake news che girano intorno alla governance locale e non (Belisario, 2017). Ai giornali resta forse ancora molto poco da vivere, mentre i giornalisti si sono moltiplicati: in un momento in cui chiunque può agire da reporter, con una risonanza che mai un privato cittadino avrebbe immaginato di avere qualche decennio fa, è fondamentale mantenere e continuare ad applicare alcune regole cardine del giornalismo. Una su tutte, la verifica delle fonti (Kovach and Rosenstiel, 2011).
Non solo la salute, la sicurezza, l’anticorruzione e una corretta informazione, che sono i diretti obiettivi di alcuni dei progetti citati: gli open data portano spesso a un coinvolgimento della popolazione, che attivamente si fa fruitrice
8Open Toscana, StrartApp Contest Toscana (http://open.toscana.it/web/startup/ startapp-contest).
9Ricostruzione Trasparente (http://partecipa.ricostruzionetrasparente.it/).
10Vitrano, “Vulnerabilità Sismica”, OpenData Sicilia (http://gbvitrano.it/qgis/vuln_ sismica-pa-3d/).
degli open data, ne comprende la ricchezza e ne condivide i risultati attraverso quello che sembra un modo tutto nuovo (che è anche molto vecchio) di costruire una comunità (Biase and Pievani, 2016). D’altra parte agire collettivamente, collaborare è possibile solo a partire da una narrazione condivisa. Una nar-razione che probabilmente dovrà fondarsi anche su una conoscenza condivisa della realtà circostante. Una volta riconosciuta l’importanza dei dati aperti sarà più facile che i dati vengano richiesti alle amministrazioni, forzandole a concederli, o come si è visto, più probabilmente, portarle a riorganizzare il rapporto dell’ente pubblico con le risorse digitali.
Perché digitalizzare le risorse non corrisponde a un semplice passaggio di medium, non modifica solo le modalità di acquisizione delle informazioni, ma ne amplifica anche le possibilità di utilizzo e porta a ripensare i processi in cui vengono impiegate. Le nuove tecnologie consentono anche l’elaborazione di dati non strutturati, come immagini, suoni, testi. E se anche i dati testuali delle pubbliche amministrazioni venissero aperti? Abbiamo solo accennato ad AlboPop, nato proprio con questo scopo: ciascun utente decide di occuparsi di un comune della penisola e sviluppare uno scraper capace di “grattare via” gli atti pubblicati sul web da quel comune e pubblicarli in una news feed consultabile da chiunque. E sarà proprio l’albo pretorio al centro dei prossimi capitoli. Quanti altri modi di dare valore a questo patrimonio informativo esistono? Quante altre modalità di gestione alle quali non avevamo pensato?
1.3
L’Albo Pretorio, questo sconosciuto
La prima legge che sancisce la trasformazione dell’Albo Pretorio risale al gennaio 2009, l’archivio nel quale sono pubblicati tutti quegli atti emanati dalle amministrazioni e che devono essere resi pubblici doveva diventare una risorsa online. Il passaggio dalla pubblicazione cartacea a quella digitale giungeva a pieno regime nel 2013, quando anche i bandi di gara avevano assunto una valenza legale solo se pubblicati sul web. L’albo pretorio è il diario di bordo dell’amministrazione e del consiglio comunale: qui vengono pubblicate determine dirigenziali, delibere di consiglio, gli atti prodotti della giunta e le ordinanze sindacali (QualitàPA, 2015a). Nonostante la trasformazione sia
avvenuta, la consultazione di questo registro è ancora lontana dall’essere “user friendly”. Intanto perché gli atti sono ricercabili solo in un arco di tempo ristretto, in genere 15 giorni. E poi perché nei siti di molti comuni per recuperare un certo provvedimento è necessario conoscerne la data, l’organo che lo ha emanato, l’oggetto o il suo numero identificativo. In altre parole: cercare un atto all’interno dell’albo pretorio è possibile solo se conosciamo piuttosto accuratamente il documento che ci interessa. Una versione vintage del web che ricorda il tempo in cui per accedere a un sito era necessario conoscere esattamente l’indirizzo che portava a destinazione: una navigazione senza motori di ricerca, insomma. Ecco perché l’albo pretorio sembra più uno strumento utilizzato dagli addetti ai lavori e dai diretti interessati di un provvedimento, piuttosto che dai comuni cittadini. Non si può dire quindi che le potenzialità di una simile quantità di conoscenza siano sfruttate come dovrebbero. A mancare sono soprattutto le relazioni tra i singoli documenti, non solo tra quelli di uno stesso comune, ma anche e soprattutto tra comuni differenti. Quelle relazioni che arricchiscono la conoscenza posseduta e ne creano di nuova.
1.4
Cos’è un motore di ricerca semantico
Quasi vent’anni dopo Berners-Lee continua a guardare allo sviluppo della sua invenzione. In un paper del 2001 racconta lo scenario di una ricerca compiuta “non attraverso il World Wide Web di oggi, ma piuttosto nel Semantic Web di domani”. Una rete in grado di dare struttura al significato contenuto nei documenti grazie all’annotazione del testo (tag su parole o frasi) e un’ontologia: “un documento che descrive le relazioni tra i termini”. Una tassonomia che raggruppa i termini attorno a delle classi, dei concetti, collegati tra loro con un certo peso e delle regole di inferenza: se due elementi sono collegati in un certo modo, allora sarà possibile dedurre qualcos’altro. Un sistema pensante, dunque (Berners-Lee et al., 2001). I motori di ricerca semantici non sono ovviamente in grado di pensare, ma riescono, nella migliore delle ipotesi, a rispondere a domande poste in “linguaggio naturale”. Il primo scopo di questa tecnologia è quello di districarsi tra le ambiguità del lessico. La collocazione dei termini all’interno di un’ontologia permette di distinguere, ad esempio nei casi
di omonimia, a quale entità l’utente si stia riferendo. E nel caso dell’utilizzo del linguaggio naturale11, è il contesto nel quale un termine è inserito ad aiutare il
motore di ricerca ad associare il termine alla corretta categoria.
Google Knowledge Graph Nel 2012 Google iniziava ad analizzare le ricer-che degli utenti attraverso il suo “Knowledge Graph”: un’ontologia, una mappa della conoscenza costruita dal colosso di Mountain View per rispondere alle que-ry direttamente dalla SERP, la pagina dei risultati della ricerca (LaRepubblica, 2012). Certo non sempre il Knowledge Graph riesce a interpretare e risolvere le complessità del reale (Graham, 2015), ma può rispondere a domande del tipo “chi vinse la battaglia di Waterloo?” con una breve sintesi sulla sconfitta di Napoleone, e rispondere correttamente alla domanda “in quanti film ha recitato Marilyn?” senza specificare di quale Marilyn stiamo parlando.
Facility Live In Italia un motore semantico alternativo a Google è “Facility Live”. “Non che Page e Brin si sveglino ogni mattina pensando a cosa succede a Pavia” dicono dalla start-up: la loro tecnologia, infatti, sarebbe migliore di quella di Google non sul web aperto, dove l’azienda americana sembra non avere rivali, ma su domini più ristretti. In altre parole l’ontologia dietro a motori di ricerca come questo è molto più “specializzata” e per questo anche molto più precisa e puntuale nel recupero delle informazioni richieste dall’utente(Piana, 2015).
Cogito Nato tra l’ambito di analisi del testo e quello dell’intelligenza artificiale, la “semantic intelligence” ha consentito ad Expert System di contare sedi in Italia, Spagna, Francia, Inghilterra e Stati Uniti e Microsoft tra i propri clienti. Uno dei progetti di punta dell’azienda è Cogito12, che si basa sull’analisi semantica dei testi. Il punto di forza di Cogito è l’ampissima banca di dati “concettuali” di cui dispone, che vede raggruppate più ontologie differenti,
costruite anche in diverse lingue, che l’azienda chiama il “Sensigrafo”. Da quanto riportato sul sito dell’azienda, questo software non sembra andare
11Si parla di linguaggio naturale, nell’ambito delle computer science, per riferirsi ad espressioni alternative al linguaggio macchina e paragonabili al linguaggio umano utilizzate dai calcolatori.
molto lontano rispetto al sistema pensante di Tim Berners-Lee: Cogito infatti rende utilizzabile la conoscenza ricavata dai testi, “simula alcuni processi di comprensione umana, consentendo di individuare rapidamente modelli, segnali e connessioni tra i dati”.
Légilocal Allargando lo sguardo all’Europa troviamo motori di ricerca semantici il cui dominio di riferimento è quello della pubblica amministra-zione. Il francese Légilocal è un motore di ricerca semantico che si occupa della gestione degli atti delle amministrazioni locali nello stesso modo con cui Légifrance gestisce gli atti a livello statale ed europeo. Qui il recupero dei provvedimenti è modellato anche in funzione di supporto alla stesura dei nuovi documenti. Légilocal dedica infatti un framework apposito alla scrittura di atti in modo che siano facilmente leggibili ed elaborabili dal motore di ricerca, che allo stesso tempo suggerisce documenti simili, per tipo o per argomento trattato, al funzionario che sta redigendo l’atto. Il quale può servirsi anche del supporto di colleghi avendo la possibilità di chattare tra gli utenti connessi. I futuri sviluppi dell’applicazione prevedono la possibilità di giudicare la validità giuridica degli atti e cercheranno di fornire le risposte migliori anche alle query formulate dai comuni cittadini, con un linguaggio non caratterizzato dal punto di amministrativo (Amardeilh, 2013).
Sophia Semantic Engine Ma alla gestione di atti delle pubbliche ammini-strazioni si dedica anche un’impresa con sede centrale a Torino, la Celi13. Questa
azienda ha messo a punto un motore di ricerca semantico il cui dominio è quello delle pubbliche amministrazioni italiane e collabora già dal 2012 con quella piemontese. Sophia Semantic Search riconosce le entità elencate all’interno dei documenti (luoghi, persone, aziende, ecc) e li classifica per similarità. Il modello di Sophia è dislocato su tre livelli di analisi: una tecnologia statistica per la classificazione, una linguistica superficiale per l’indicizzazione delle parole e una tecnologia semantica per individuare le entità e le relazioni morfo-sintattiche basilari (soggetto, verbo, complemento oggetto)14. Gli ambiti di pubblicazione
13https://www.celi.it/
vanno “dalla Cultura alla Promozione della Salute, dalla Protezione Civile alle Immagini Sanitarie, dagli open data ai Sistemi di Performance”15.
1.5
SemplicePA, una piattaforma
Potremmo dire che quello offerto da Sophia Semantic Search è un servizio, una soluzione a un unico problema: la ricerca “intelligente” degli atti pubblici. Potremmo dire anche che Légilocal è qualcosa di più: una piattaforma, un ambiente, che favorisce la collaborazione tra i comuni (e tra i funzionari di questi comuni) nella produzione degli atti amministrativi; allo stesso tempo migliora la gestione di questi atti per una maggiore efficienza e trasparenza verso i cittadini, i quali possono trovare ciò che cercano attraverso un linguaggio via via sempre più “naturale”. Cosa potremmo dire allora di SemplicePA? Nato nel 2012, SemplicePA16 è un progetto di ETI317, una start-up con sede a Città di
Castello, una cittadina umbra al confine con la Toscana. L’obiettivo principale dell’iniziativa è quello di valorizzare i contenuti degli atti registrati negli albi pretori dei comuni di tutta Italia, di rendere navigabili queste informazioni e le relazioni che tra esse intercorrono. In altre parole il suo scopo è creare un albo pretorio nazionale che sia possibile esplorare attraverso un motore di ricerca semantico, in grado di estrarre elementi testuali significativi, quali nomi di aziende e organizzazioni, e mostrare come sono collegati attraverso strumenti di visual analytics. Prima di individuare gli intenti di questo elaborato, è il momento di analizzare le tecnologie di cui SemplicePA dispone e almeno uno degli scenari in cui è possibile applicarle.
1.5.1
Il motore semantico
Estrazione delle Entità All’interno di ogni documento sono individuate le diverse entità: persone, dei luoghi, delle aziende, delle organizzazioni, im-porti, date e indirizzi email ma anche elementi più specifici dei provvedimenti amministrativi come riferimenti legislativi e ad altri atti di enti locali, partite
15“Motori di ricerca semantici per la PA del Piemonte”, Forum PA, 30 Aprile 2012 (goo.gl/cch4IH).
16http://www.semplicepa.it/ 17http://www.eti3.it/
iva, codici identificativi di gara e codici fiscali. L’estrazione avviene attraverso un modello che integra due approcci diversi, uno basato su delle regole e un altro su calcoli statistici. L’approccio ruled-based è ordinato da algoritmi che contengono regole precise sull’estrazione. Ad esempio, la regola che estrae nomi e cognomi prevederà di estrarre due parole una di seguito all’altra che inizino per lettera maiuscola, e così via. L’altro approccio vede la collaborazione del CoLing Lab18 dell’Università e del Centro di Linguistica Computazionale del
CNR di Pisa: un modulo di T2K19 (CNR, 2017), detto NLP Analyzer20, ed
Extra21 (Lenci and Passaro, 2015) estraggono in maniera automatica e non
supervisionata le entità in base a calcoli statistici. La probabilità che i termini estratti siano delle entità è dedotta dalla distribuzione del lessico all’interno del testo, appresa inizialmente da un corpus, un insieme di atti, annotato manualmente. Una stessa entità, però, è riportata in diversi modi non solo negli atti amministrativi di diversi comuni, ma in quelli dello stesso comune o addirittura all’interno dello stesso provvedimento. Per questo è in fase di elaborazione un modulo di “normalizzazione” che sostituisca con una forma univoca e standard le diverse declinazioni in cui una stessa entità è presente nei documenti.
L’ontologia L’ontologia su cui si basa è costruita con un modello top-down e bottom-up, ovvero sia attraverso l’individuazione di termini e della loro classificazione da parte di esperti di dominio, sia estraendo i termini più rap-presentativi di una classe in seguito all’analisi automatica degli atti. Anche di quest’ultima classificazione automatica, detta di topic modeling, si è occupata l’Università di Pisa. Si tratta di un metodo unsupervised, che non necessita cioè di una precedente annotazione degli atti. Il tool open source utilizzato
18Il laboratorio di Linguistica Computazionale del Dipartimento di Filologia, Letteratura e Linguistica dell’Università di Pisa.
19«Il sistema T2K (Text to Knowledge) progettato e sviluppato dall’Istituto di Linguistica Computazionale di Pisa in collaborazione con il Dipartimento di Linguistica dell’Università di Pisa, si propone di offrire una batteria integrata di strumenti avanzati di analisi linguistica del testo, analisi statistica e apprendimento automatico del linguaggio, destinati a offrire una rappresentazione accurata del contenuto di una base documentale non strutturata, per scopi di indicizzazione avanzata e navigazione intelligente.»
20Ovvero Natural Language Processing Analyzer.
21Uno strumento creato per estrarre e calcolare il grado di termhood (quanto una unità lessicale stabile sia legata a un concetto relativo a uno specifico dominio) di espressioni multiparola.
per questo compito è chiamato Mallet (Blei, 2012) e si avvale dell’algoritmo di Latent Dirichlet Allocation 22. Le classi corrispondenti ai topic quindi, da una
parte vengono individuate in base alla presenza dei termini dell’ontologia, e dall’altra da termini automaticamente estratti dagli stessi testi: il risultato è un approccio integrato dei due metodi. Attraverso il LDA è inoltre possibile estrarre da uno stesso documento più di una categoria, per cogliere le diverse sfumature semantiche dell’atto amministrativo. Alcuni degli argomenti sono ad esempio “Urbanistica”, “Servizi Finanziari”, “Ambiente”, le cui sottocatego-rie comprendono rispettivamente anche “Gestione della Viabilità”, “Bandi e Contratti” e “Verde Comunale”.
1.5.2
Scenari
Scenari Un imprenditore viene colto in flagranza di reato, mentre intasca una mazzetta per aver subappaltato una commissione ad un’azienda amica. Sappiamo che l’azienda a cui l’imprenditore era a capo ha svolto diversi lavori per varie amministrazioni nel territorio nazionale, ma non sappiamo né dove né quando. Immaginiamo di dover ricostruire la storia di questa azienda a partire dai comuni e le strutture in cui ha operato, il suo principale settore di intervento e le aziende e le persone ad essa collegate. Prendiamo il caso delle cooperative che si occupavano di accoglienza profughi e che si sono ritrovate al centro delle indagini di “Mafia Capitale”. Una di queste si chiama “29 Giugno” (Autieri et al., 2015). Un normale motore di ricerca includerebbe tra i risultati anche quei documenti che contengono “29 Giugno” come data piuttosto che come nome di una cooperativa. Specificando il tipo di entità del nostro oggetto di analisi sulla barra di ricerca di SemplicePA, il motore semantico assocerà subito questo oggetto ad un’azienda. Automaticamente comparirà anche una mappa, con evidenziati i comuni dai quali sono stati pubblicati i documenti che parlano di quest’azienda. Luoghi e comuni che sono esplicitati nelle liste. Tracciare i luoghi in cui operano le aziende a livello nazionale è “una delle difficoltà maggiori che riscontriamo” dice Valentina Usai, Capitano della Guardia di Finanza della Compagnia di Pisa. “Spesso - continua - non possiamo venire a
22Un algoritmo del campo della modellazione probabilistica conosciuto come generative probabilistic modeling.
sapere se l’azienda che vince un appalto in un comune ha trascorsi in un’altra amministrazione dove magari un altro appalto le è stato revocato per via di illeciti che non conosciamo”. Le liste mostrano anche gli argomenti trattati dai documenti recuperati. E qui passiamo ai fatti riguardanti la costruzione in seguito al terremoto del centro Italia. L’appalto della costruzione delle cosiddette “casette” sarebbe stato affidato a un’azienda che poco ha a che vedere con la ricostruzione (Gazzarini, 2017). In cima alla lista degli argomenti, infatti, compare la classe “ambiente” invece di quella relativa all’edilizia e le costruzioni. L’accesso alla sezione Trend ci permette di capire a quando risale l’ultima attività dell’impresa, che potrebbe aver avuto il tempo di specializzarsi in altri settori se l’ultimo documento che la nomina risale a diversi anni fa. A ricostruire il singolo procedimento in cui l’impresa è coinvolta anche la sezione iter, che mostra il riferimento di atti che si citano tra di loro. Passiamo adesso alle relazioni. L’accesso alla sezione “Inferenza” consente di individuare le altre aziende con cui compare citata nei documenti l’impresa sulla quale stiamo compiendo la ricerca: potremmo così avere un primo indizio su quali aziende potrebbero aver goduto di un subappalto. Poi ci sono le persone: i titolari di queste aziende, i funzionari e i tecnici che hanno supervisionato o autorizzato i lavori.
1.5.3
Informazioni in Rete
Una volta che ciascuna entità è stata estratta è possibile metterla in rete in diversi modi. Sia in base alla compresenza di due entità all’interno dello stesso documento, sia in base a tutta una serie di relazioni che possono essere apprese da algoritmi di semantica distribuzionale23e che costituiranno il prossimo passo
della piattaforma, che riuscirà a fornire informazioni sul territorio sul quale una certa azienda opera, ma anche dove e con chi lavora una certa persona. Come anticipato, al momento le relazioni tra le entità presenti nei documenti sono calcolate dalla piattaforma sulla base della compresenza all’interno degli atti. Nella rete in cui vengono rappresentati, i nodi sono le entità estratte, le relazioni sono gli archi che le collegano mentre il peso degli archi è dato
23Si tratta di algoritmi statistici che deducono il significato di un termine dalla posizione delle parole della frase in cui è contenuto.
dal numero di documenti in cui le entità collegate sono entrambe nominate. L’interfaccia di navigazione “in rete” analizza gli elementi a partire da un gruppo di documenti selezionati: permette di regolare il peso degli archi e il numero dei nodi da visualizzare, e di scegliere quale entità va collegata all’altra (le persone con le aziende o le aziende con le organizzazioni). Ma prima di passare a un’analisi approfondita di questa sezione, occorre passare in rassegna alcuni concetti chiave dell’analisi delle reti, utili per la progettazione di nuove funzionalità.
Capitolo 2
Network Analysis: proprietà e
misure
L’obiettivo di questo progetto è quello di apportare alcuni miglioramenti proprio alla sezione "Inferenza" di SemplicePA, sfruttando le proprietà delle reti studiate in matematica e informatica. In questo capitolo oltre alle misure dell’intera rete, saranno presentate anche le misure relative ai singoli nodi e le caratteristiche degli archi. Infine saranno esaminate e approfondite due proprietà dei grafi che saranno applicate alle reti di entità, la backbone e i
graphlet.
2.1
Nodi e Archi
Le reti sono composte da elementi connessi tra di loro. Nella rappresen-tazione matematica delle reti, che sono detti grafi, gli elementi connessi sono chiamati nodi o vertici (V ) e le connessioni sono i link o archi (edge E ). Si dice pertanto che un grafo G(V,E) è formato da un gruppo di vertici V(G) e un gruppo di link E(G).
2.1.1
Direzione
Gli archi possono avere una direzione. Connettendo i due nodi u e v, un arco può avere la sua origine in u e puntare in v (e(u, v)), o viceversa (e(v, u)). Si parla in questo caso di archi orientati, e guardando all’intera rete,
di grafi orientati (directed graph). Un esempio di questo genere sono le reti costituite dalle telefonate effettuate e da un gruppo di utenti, in cui abbiamo sempre un utente che telefona e uno che riceve la telefonata. Allo stesso modo esistono grafi che non sono orientati, grafi in cui le relazioni tra i nodi sono ambivalenti e gli archi non hanno una specifica direzione. Ad esempio, hanno queste caratteristiche le reti degli attori, che possono risultare connessi se hanno recitato in uno stesso film (Barabási, 2012). Sarà questo il tipo di rete sulla quale si svilupperà il presente progetto.
2.1.2
Componenti
Un grafo può dirsi disconnesso nel caso in cui sia formato da più componeneti, più grafi "sconnessi" tra di loro. Il gruppo con il maggior numero di nodi viene detto giant component, mentre i nodi isolati e gli altri sottogruppi sono detti
isolates1.
2.1.3
Densità
A variare nei grafi, è anche la densità dei collegamenti, ovvero quanto i nodi sono connessi tra loro. Un grafo con il massimo valore di densità è detto
completo, mentre se possiede un basso valore di densità si dice sparso.
Grafo completo Si ha un grafo completo quando una rete ha il numero massimo di link, che in un grafo non orientato si esprime con:
Emax = N (N − 1)
2 (2.1)
dove N è il numero totale dei nodi della rete
Sparse graph Ma la maggior parte delle reti che si osservano nei sistemi reali sono sparse. In queste reti i nodi sono scarsamente connessi tra di loro.
Density La densità di un grafo è costituita quindi dal rapporto tra il numero dei link esistenti e i nodi. In particolare, sempre per i grafi non
1Nel progetto proposto le due nozioni saranno distinte: da una parte vi saranno i nodi isolati e dall’altra il numero dei gruppi di cui è composto il grafo.
orientati:
D = 2E
N (N − 1) (2.2)
2.1.4
Ego-Network
Una ego-network è una rete che vede al centro un nodo e soltanto i nodi collegati ad esso per diversi gradi di distanza. Nell’analisi delle reti sociali, può essere definita come la cerchia delle conoscenze di una singola persona. È possibile ricavare la ego-network di un nodo n che appartiene ad una rete G, come il sottografo che include tutti i nodi a una certa distanza da n. In altre parole la ego-network non è altro la rete dei nodi vicini, collegati al nodo stesso, posti alla distanza di un certo numero di archi.
2.2
Le misure dei nodi
Anche gli stessi nodi, in base al numero di relazioni e alla loro posizione all’interno del grafo, assumono diverse caratteristiche. In questa sezione si parlerà in particolare di tre misure di centralità: degree, closeness e betweenneess.
2.2.1
Degree Centrality
Il degree centrality, più comunemente conosciuto come degree di un nodo
u, consiste nel numero degli archi in cui u è posto ad uno dei due estremi.
Nei grafi orientati si distingue tra in-degree, ovvero il numero degli archi che puntano a un nodo, e out-degree, ovvero il numero degli archi che partono da un nodo. Per quanto riguarda i grafi non orientati, come quello che prenderemo in considerazione, si parla semplicemente di degree, visto che la relazione tra due nodi è simmetrica e gli archi non possiedono una direzione. Il valore per ciascun nodo è dato da:
ki = n
X
j=1
Aij (2.3)
dove Aij è una terminologia che deriva dalla possibilità di rappresentare i grafi
attraverso una matrice di adiacenza. Si tratta di una matrice in cui righe e colonne sono costituite da nodi. La presenza di un arco tra il nodo i e il nodo
Figura 2.1: In alto a destra il plot con le distribuzioni dei degree di una rete
random, in verde, e di una rete reale in viola. A sinistra in scala logaritmica. In basso una rappresentazione grafica; le dimensioni dei nodi dipendono dai loro degree. Fonte immagine:Barabási (2012).
j, fa sì che, all’interno della matrice, alla cella che corrisponde all’incrocio di
questi due nodi (riquadro 2.4), ovvero Aij, corrisponderà il valore 12, 0 se tra
i due nodi non esiste relazione. La sommatoria di tutti i legami del nodo i corrisponderà al suo degree.
a11 a12 a13 . . . a1n a21 a22 a23 . . . a2n .. . ... ... . .. ... ai1 ai2 ai3 . . . ain .. . ... ... . .. ... an1 an2 an3 . . . ann (2.4)
Scale-Free & Random Network La distribuzione dei degree all’interno di una rete fornisce delle informazioni rilevanti riguardo la natura della rete stessa. Se i nodi hanno all’incirca tutti lo stesso degree è probabile che ci si
trovi davanti a una rete costruita randomicamente. La curva di distribuzione del degree di una rete simile è molto vicina a una normale, approssimabile per la precisione alla curva di Poisson. Se la distribuzione di una rete segue invece una curva long-tail, che segue la power-law, o anche principio di Pareto (1964) allora si tratterà di una rete reale (figura 2.1). È propria delle reti reali,
infatti, la presenza di pochi nodi, con tantissime connessioni, gli hub, mentre la maggior parte di questi hanno un numero di connessioni relativamente molto basso e per questo sono dette scale-free (Barabási, 2009). Uno scenario che non riesce difficile immaginare se guardiamo alle social network. Pochissime persone possono vantare di conoscere un numero di individui pari a quello con cui entrano in contatto i capi di stato ad esempio.
2.2.2
Closeness Centrality
La closeness centrality indica invece la distanza media di un nodo rispetto agli altri nodi della stessa rete. Più precisamente, la closeness di un nodo u è il reciproco della somma delle distanze degli shortest path da u verso tutti gli altri nodi. Dal momento in cui la somma delle distanze dipende dal numero dei nodi all’interno del grafo, la closeness è normalizzata dalla somma delle possibili distanze n − 1.
C(u) = Pn−1n − 1
v=1d(v, u)
(2.5)
dove d(u, v) è la distanza dello shortest-path tra v e u, e n è il numero dei nodi nel grafo. Lo shortest-path a cui si fa riferimento non è altro che il numero degli archi lungo il percorso più breve possibile tra due nodi. Se i due nodi sono disconnessi, questa distanza corrisponde a infinito.
2.2.3
Betweenness Centrality
Anche la betweenness centrality è misurata attraverso gli shortest-path, i quali però stavolta riguardano gli altri nodi. La centralità di un nodo, in questo caso è data dalla sua presenza o meno all’interno degli shortest-path che congiungono tutti gli altri nodi del grafo. La betweennes di un nodo v è
data dalla sommatoria del numero di shortest path di tutte le coppie di nodi fratto gli shortest-path che passano per v:
B(v) = X
s,tv
σ(s, t|v)
σ(s, t) (2.6)
dove σ(s, t) è il numero degli shortest (s, t)-paths, e σ(s, t|v) è il numero di quei percorsi che passano attraverso un dato nodo v diverso da s e t.
2.3
Le proprietà degli archi
Non sono solo i nodi a possedere specifiche proprietà. Anche agli archi hanno alcune caratteristiche, come ad esempio il peso, che dipende, in genere, dal numero di volte in cui due nodi si trovano in relazione. Tornando al presente progetto, se due entità sono citate in 10 documenti, l’arco che le collega avrà peso 10. Ma ci sono anche proprietà che, come nel caso dei vertici, dipendono dalla struttura della rete. Per rappresentare una rete pesata, si può dire che
G = (V, E, W ), dove V è l’insieme dei vertici, E l’insieme dei link e W è
l’insieme dei pesi, tale che E sia un insieme di triple (i, j, w), ciascuna che identifica un arco, attraverso un nodo di origine i, uno di destinazione j, e il suo peso w.
2.3.1
Bridge e Legami deboli
Un arco può considerarsi un bridge se alla sua rimozione corrispondesse una disconnessione del grafo. In altre parole un bridge è quel link grazie al quale due componenti di un grafo rimangono uniti, e che senza di esso sarebbero quindi due entità separate. Ma esiste anche una nozione "locale" di bridge. Un arco e(u, v) è un local bridge se u e v non hanno nodi in comune. Si dice span di un local brige la distanza tra u e v nel caso in cui l’arco venisse eliminato.
Un’altra nozione da tenere in considerazione per quanto riguarda gli archi è quella relativa alla triadic closure. Se due persone hanno un amico in comune, c’è una crescente probabilità che diventino amiche tra di loro. Per questo, è possibile distinguere tra legami deboli e legami forti. Una caratteristica di quest’ultimi è che se il nodo A ha un legame forte sia con B che con C, allora
Figura 2.2: La backbone della rete degli aeroporti statunitensi estratta attraverso
l’applicazione del disparity filter. Fonte immagine: Serrano et al. (2009).
necessariamente vi sarà i link (B, C). In altre parole, se il nodo A soddisfa la triadic closure ed è coinvolto in almeno due legami forti, allora qualsiasi altro local bridge adiacente deve essere un legame debole, altrimenti non sarebbe più un local bridge ma un altro legame forte che completa una nuova struttura triadica.
2.4
Backboning
Uno dei problemi legati alla network visualization, è quello relativo alla eccessiva complessità delle reti. Un numero elevato di nodi e di link rende infatti molto difficile la comprensione e la lettura dei dati, che la visualizzazione in rete dovrebbe invece facilitare. Due sono i metodi principalmente utilizzati: • Coarse-Graining: Si approssima per livelli di granularità. I nodi che condivisono un attributo comune possono essere radunati insieme in una stessa classe (gruppo, comunità, ecc.) e poi sostituiti da una nuova singola unità che rappresenta l’intera classe;
• Filtering/Pruning: con questa tecnica si cerca di mantenere solo gli archi e i nodi che trasportano informazioni rilevanti riguardanti la struttura della rete, mentre i restanti vengono scartati;
Questa sezione si concentrerà sul secondo approccio, il cui scopo è quello di mantenere, in reti ridotte, solo quei componenti che garantiscano il mante-nimento delle informazioni riguardanti la struttura della rete originaria. La nuova rete ridotta costituirà quella che viene definita la backbone della rete,
la spina dorsale, le sue fondamenta. Gli obiettivi dietro all’individuazione di una backbone dipendono senz’altro dal tipo di rete che ci troviamo davanti. Nel caso della rete degli scali degli aeroporti americani (Figura 2.2) ad esem-pio, individuare la relativa backbone potrebbe significare ottenere la lista di quegli aeroporti senza i quali il trasporto aereo statunitense si bloccherebbe. Un’informazione necessaria almeno per due possibili provvedimenti: aumentare l’efficienza di questi aeroporti o diversificare maggiormente il traffico per non rischiare l’isolamento di intere aree (figure 2.2).
2.4.1
Stato dell’Arte
Un minore livello di dettaglio può sicuramente portare a una perdita delle informazioni consistente, che però può avvenire con facilità anche utilizzando un metodo di filtraggio non adeguato. Di seguito alcune delle tecniche adottate con questo appoccio, di cui saranno analizzati anche i punti deboli.
Naive
Un approccio considerato naive è quello che vede come parametro scelto per il filtraggio delle reti un peso soglia minimoi degli archi. Per cogliere le criticità di questo metodo basta pensare alle reti reali, in cui come accennato, la distribuzione dei degree attraversa diversi ordini di magnitudo. Applicando un approccio simile a una rete reale porterebbe quindi allo scarto di un gran numero di archi, compromettendo in questo modo la struttura della rete.
Maximum Spanning Tree
Il Maximum Spanning Tree (MST), consiste nello spanning tree di un grafo non orientato, per cui il peso totale dei suoi archi è massimo. Si dice spanning
tree, quell’albero che connette tutti i vertici di un grafo. Per estrarre il MST
si utilizza generalmente l’algoritmo di Kruskal (1956), che riesce a rispondere al problema di preservare tutti i nodi. Eppure vi sono almeno due criticità in questo approccio: il grafo potrebbe avere più di uno spanning tree, e non si tiene conto di fenomeni fondamentali delle reti reali, come le transitività e le community.
High Salience Skeleton
Hight Salience Skeleton (HSS) (Grady et al., 2012) è un algoritmo che fa
derivare la backbone dallo Shortest Path Tree (SPT) di ciascun nodo, ovvero l’albero in grado di connettere quel nodo a tutti gli altri nodi della rete. Questo approccio non considera il rumore nella stima del peso di ciascun arco. Ovvero: un utente può accidentalmente aver detto di aver letto un libro quando in realtà non lo ha fatto, magari perché i titoli erano molto simili. La possibilità che sussista una certa percentuale di errore va tenuta in considerazione sia nel caso in cui l’arco esista, sia nel caso di una sua inesistenza.
Disparity Filter
Si tratta di un metodo sviluppato da Serrano et al. (2009) che si basa sulle eterogeineità del peso degli archi statisticamente rilevanti a livello locale, preservando le proprietà strutturali e gerarchiche della rete a ogni grado di magnitudo.
Ciò avviene principalmente in due passaggi:
• L’individuazione delle fluttuazioni locali del peso;
• Il confronto con un modello nullo che dimostri la validità statistica di queste fluttuazioni;
Fluttuazioni locali In molte reti reali i nodi sono circondati da archi i cui pesi associati sono distribuiti in maniera eterogenea, ma tra i quali intercorre un certo livello di correlazione. Esiste cioè una certa dipendenza tra pesi e topologia: più un nodo è connesso al resto della rete e maggiore sarà il peso dei suoi archi. Quindi anzitutto si normalizza il peso degli archi connessi ad un certo nodo rispetto alla sua forza, e poi si applica una funzione di
disparità che consente di individuare quali archi trasportano una frazione di
peso sproporzionata rispetto a quella degli altri archi.
Modello nullo Le eterogeneità locali potrebbero tuttavia essere casuali. Per questo la rete viene confrontata con un modello nullo, in cui la misura di disparità viene applicata agli archi della rete in maniera randomica, ma
Figura 2.3: La diversa applicazione degli algoritmi di disparity filter e NC.
Fonte immagine: Coscia and Neffke (2017).
sempre in relazione al degree del nodo posto a uno degli estremi. Se il peso assegnato casualmente all’arco corrisponde in qualche modo al peso dell’arco nella rete originaria, allora può essere rimosso, perché non statisticamente rilevante. Il confronto tra le due reti è infatti compiuto attraverso l’utilizzo di uno strumento della statistica inferenziale, il p-value, per cui l’ipotesi nulla considerata sarà quindi che i pesi normalizzati delle connessioni di un certo nodo di degree k sono vicini a quelli prodotti da un’assegnazione random a partire da una distribuzione uniforme, e quindi non rilevanti. I link che non rientrano nell’ipotesi nulla per almeno uno dei due nodi ai propri estremi vengono invece mantenuti. La soglia di significatività sarà quindi imposta da un certo valore α, per cui tutti i link con αij < α rifiutano l’ipotesi nulla e la propria eterogeneità
può considerarsi dovuta ai principi di organizzazione della rete.
2.4.2
Noise Corrected
Come l’HSS neanche il filtro di disparità non tiene conto del "rumore" sui dati che costituiscono una rete. Per ovviare a questa mancanza, Coscia and Neffke (2017) ha proposto un nuovo approccio, denominato Noise Corrected (NC).
In cosa si differenziano principalmente i due approcci? Come mostrato in figura 2.3 le connessioni dei nodi 2 e 3 sono eliminate dal disparity filter (DF), che invece mantiene tutte le connessioni del nodo 1, comprese quelle che hanno come target 2 e 3. Con NC, invece, l’arco rosso viene mantenuto, mentre gli archi blu vengono tagliati. Il nodo 1 ha infatti solo connessioni forti e i suoi archi blu sono particolarmente deboli se paragonati agli altri. Dall’altro
lato il nodo 3 ha solo connessioni deboli, per questo l’arco rosso è molto più importante per lui rispetto a quello blu.
NC paragona il peso degli archi a un modello nullo, il quale è creato a livello di coppie e non del singolo nodo. Non viene quindi considerata solo la propensione del nodo in origine di inviare connessioni, ma anche quella del nodo destinatario a riceverle. Il modello nullo sarà quindi costruito su una distribuzione delle probabilità dei pesi binomiale e non uniforme. La probabilità di osservare il peso Nij sarà calcolata attraverso il principio di Bayes, ovvero
come un’estrazione “senza sostituzione”. Si intende così rispondere a domande come: quanto è grande o piccola la probabilità che dato il peso degli altri archi, questo arco abbia un peso simile?
La probabilità, stimata attraverso un framework bayesiano, consente di generare valori di varianza per tutti gli archi. In altre parole, si trasforma il peso degli archi così che siano espressi in forma di deviazione rispetto al modello nullo. Saranno esclusi quegli archi il cui peso è minore di δ standard deviation in più di quanto aspettato, dove δ è l’unico parametro dell’algoritmo di NC.
2.5
Graphlet, pattern e anomalie
Un altro modo per superare la complessità di una rete è quello di analizzare i sottografi che con una certa regolarità compaiono al suo interno, andando cioè a scomporre la rete in componenti dalla struttura ricorrente. Il profilo creato in seguito al calcolo della frequenza di questi pattern, consente quindi di caratterizzare una rete a un livello locale, diversamente dalle proprietà topografiche dei grafi nella loro struttura complessiva (Ahmed et al., 2017). I sottografi individuati possono essere definiti in due modi: come motif o come
graphlet.
2.5.1
Motif
I primi a parlare di motif furono Milo et al. (2002), che in un articolo su Science descrissero un metodo per individuare pattern di interconnessione ricorrenti e significativi all’interno delle reti.
L’approccio consisteva principalmente in due step. Come prima cosa veniva-no individuati tutti i sottografi di n-veniva-nodi, registrando il numero delle occorenze di ciascun sottogafo, distinguendoli in base alla diversa struttura assunta. I sottografi vengono infatti considerati separatamente non solo in base al numero dei nodi, ma anche in relazione alla forma: si ottiene cioè la frequenza di diversi gruppi di sottografi che sono isomorfi tra loro. Due sottografi G1 = (V 1, E1) e
G2 = (V 2, E2) si dicono isomorfi se c’è una corrispondenza uno a uno tra i
propri vertici e se, in presenza di un arco orientato tra un vertice e un altro in un grafo, un arco con la stessa direzione si trova anche tra i nodi corrispondenti del secondo sottografo.
Il secondo step mira a individuare quei sottografi che possono assumere un certo significato. La rete reale infatti viene paragonata a una rete randomizzata con lo scopo di selezionare solo quei pattern che compaiono nella rete reale un numero di volte che sia sufficientemente superiore rispetto alla rete random. Perché il confronto sia significativo, la rete randomizzata dovrà avere i nodi con le stesse caratteristiche di quelli della rete reale (archi incoming e outgoing) e lo stesso numero di occorrenze dei sottografi di n − 1-nodi. Corrispondenza che risulta necessaria al fine di evitare che un pattern venga considerato significativo solo perché sono significativi i suoi subpattern.
I network motifs, quindi, sono quei pattern per cui la probabilità p di apparire in una rete randomizzata, in un numero uguale o superiore rispetto alla rete reale, sia più bassa di un certo valore soglia (nel paper citato p = 0.01).
La sfida di questo genere di approcci, corrisponde all’esecuzione del calcolo ricorsivo di questi sottografi, generalmente molto dispendiosa in termini di spazio e tempo di calcolo. Questi sono quattro dei tentativi che sono stati compiuti allo scopo di migliorare le prestazioni di quest’analisi:
Mfinder Propone due tipi di algoritmi di ricerca: uno detto di full
enu-meration, per il conteggio delle occorrenze di tutti i sottografi presenti, e un
metodo di campionamento. Quest’ultimo è molto veloce: assegna valori di probabilità ai motif individuati e deduce la frequenza delle occorrenze da questi valori (Kashtan et al., 2004).
Pajek La sua efficienza è dovuta alla specificità dei motif che è in grado di recuperare, ovvero triadi e particolari motif di tre nodi (Batagelj and Mrvar, 2003).
FANMOD Il migliore in termini di tempo computazionale. L’unico limite di questo algoritmo è che non può gestire sottografi con più di otto nodi. L’utilizzo dello spazio di memoria cresce notevolmente sia al crescere dei sottografi che delle dimensioni dell’intera rete (Wernicke and Rasche, 2006).
Kavosh È l’approccio che riesce a dare i migliori risultati sia per quanto riguarda il tempo che lo spazio impiegato nel calcolo di motif di misura k. A migliorare i tempi di esecuzione è il particolare algoritmo utilizato nel conteggio dei motif (Kashani et al., 2009).
2.5.2
Graphlet
Anche i graphlet, introdotti per la prima volta due anni dopo l’articolo di Milo (Pržulj et al., 2004), sono sottografi ricorrenti, considerati tali solo se appaiono con una certa significatività statistica, e anche per loro questa validazione è data dal confronto con un modello nullo. A distinguere i graphlet dai motif è però il fatto che si tratta di sottografi indotti, mentre i motif sono sottografi parziali. Per intenderci, se il sottografo Gk di un grafo G è un grafo
di dimensione k in cui V (Gk) ⊆ V (G) e E(Gk) ⊆ E(G), questo sottografo si
dice indotto se (u, v)E(Gk) ↔ (u, v)E(G) (Ribeiro et al., 2009).
In altre parole, se un motif è il sottografo di una rete più grande in cui non necessariamente tutti gli archi tra i nodi sono preservati, il graphlet sarà un sottografo indotto in cui tutti gli archi tra i nodi sono preservati. Per fare un esempio, se 4 nodi di una rete sono scelti per comporre un motifs, questo può non comprendere tutti gli archi che li collegano nella rete originaria, mentre nel caso dei graphlet, sì.
Il fatto che non vengano calcolate tutte le possibili combinazioni di assenza o presenza dei link appartenenti a un sottografo della rete originaria, per definizione fa sì che i costi a livello di computazione vengano ridotti.
L’utilità derivata dall’estrazione dei graphlet è molteplice. A un livello più generale, i graphlet sono utili per individuare reti simili, o all’opposto reti molto diverse. In particolare, come anticipato, i graphlet possono caratterizzare le reti e il loro comportamento a un livello locale. Come in alcuni esempi forniti da Ahmed et al. (2017) la ricerca dei graphlet simili nelle diverse reti può trovare applicazione nella sicurezza, nella cosiddetta role discovery3, link prediction,
ecc.
I graphlet, infine possono essere utilizzati per classificare nodi e archi e trovare pattern unici e anomalie. Analizzando un grafo i cui nodi possedevano ciascuno un’etichetta non univoca, Noble and Cook (2003) hanno proposto tecniche di identificazione delle anomalie, intese come occorrenze di pattern inaspettate o inusuali. Un compito che non si esaurisce nell’individuazione delle strutture che semplicemente occorrono meno di frequente: se consideriamo l’intero grafo come un pattern, questo non occorre più di una volta, ma non si tratta certo di un’anomalia. Individuare invece i pattern meno frequenti tra i graphlet, la cui significatività è statisticamente rilevante, potrebbe costituire possibile soluzione, le cui applicazioni ci saranno utili nel prossimo capitolo.
Capitolo 3
Inferenza, lo strumento e i dati
In questo capitolo saranno esposti i componenti della sezione "Inferenza" di SemplicePA, come questa si inserisce all’interno della piattaforma e quali sono i dati che elabora per giungere alla rappresentazione del grafo delle entità. Queste informazioni saranno il punto di partenza per progettare un miglioramento della sezione che sarà oggetto del capitolo successivo.
3.1
Dati
La sezione "Inferenza" diviene accessibile da homepage solo dopo aver effettuato una ricerca. Lo scopo della sezione, infatti, è proprio quello di mostrare in una rete le entità estratte dai documenti restituiti. Le entità estratte che è possibile esplorare attraverso questa sezione sono 4: i comuni, le persone, le aziende e le organizzazioni (ad esempio: associazioni, ministeri, province, comuni, ecc.). Come anticipato, due entità sono collegate se sono citate all’interno dello stesso documento. In seguito alla query formulata dall’utente in homepage, vengono restituiti i documenti corrispondenti, registrati i un database SolR Apache. A questo punto l’icona della sezione "Inferenza" si attiva ed è possibile accedervi. Alla query eseguita dall’utente, intanto, è stata associata una Url unica, che viene conservata in vista delle azioni successive.
All’interno della sezione l’utente dovrà scegliere, attraverso due menù a tendina, I due elementi da collegare tra le quattro entità estratte a disposizione. Sono presentati come "elemento1" e "elemento2". Poi attraverso due slide-bar
potrà modificare:
• Il peso minimo della relazione (o link), ovvero il numero minimo di documenti in cui devono comparire insieme due elementi perché appaiano; • Il numero massimo di elementi che dovrà comporre il grafo.
Dopo aver impostato questi parametri l’utente può visualizzare la rete cliccando sul pulsante "Mostra". Dal momento in cui l’utente clicca su questo bottone, all’apparizione della rete, si verificano i seguenti passaggi:
• La query precedentemente eseguita viene arricchita di nuovi parametri e nuovamente eseguita su SolR con una chiamata in Java;
• Il risultato della query sarà un file XML poi elaborato in json in modo che sia accessibile alla libreria Javascript D3.js, in particolare alla funzione "Force Layout" per la visualizzazione;
La query si presenta in forma di Url e assume questi parametri:
solr/semplice/select?version=2.2&start=0&rows=-1&indent= on&sort=score%20desc&facet=true&facet.limit=20&facet.pivot. mincount=10&facet.pivot=ne_norm_aziende,ne_norm_person&fq= provider:054056&q=*
dove:
• facet.limit indica il numero limite di nodi che fanno parte della categoria del primo elemento;
• sort=score indica che saranno selezionati i primi n nodi che hanno il numero di relazioni più alto;
• facet.pivot.mincount indica il numero di relazioni che devono avere due nodi perché il secondo elemento possa apparire;
• facet.pivot=ne_norm_aziende,ne_norm_person indica le entità estratte: in questo caso il primo elemento sono le aziende, e per ogni azienda, saranno estratte le entità relative al secondo elemento selezionato ad essa collegate.
I dati restituiti, in formato json si presentano così: { "responseHeader":{ "status":0, "QTime":266, "params":{ "facet":"true", "sort":"score desc", "indent":"on", "start":"0", "q":"classcategory_all:\"servizi informativi\"", "facet.limit":"100000", "facet.pivot.mincount":"10", "wt":"json", "facet.pivot":"ne_norm_aziende, ne_norm_aziende", "rows":"-1", "version":"2.2"}}, "response":{"numFound":1489,"start":0,"docs":[] }, "facet_counts":{ "facet_queries":{}, "facet_fields":{}, "facet_dates":{}, "facet_ranges":{}, "facet_pivot":{ "ne_norm_aziende,ne_norm_aziende":[{ "field":"ne_norm_aziende", "value":"Actalis S.p.a.", "count":18, "pivot":[{ "field":"ne_norm_aziende", "value":"Actalis S.p.a.", "count":18}, { "field":"ne_norm_aziende", "value":"Aruba S.p.a.", "count":18},
Alla chiave che corrisponde alla tipologia di elementi scelti (per questa query: "ne_norm_aziende,ne_norm_aziende") è associato come valore la lista delle entità "elemento1", in questo caso le aziende. Per ciascuna azienda è riportata come valore alla chiave "pivot" la lista delle aziende ad essa collegate, e per ciascuna sono riportate, come array associativo, i relativi attributi.
Per poter divenire un input compatibile con la libreria javascript D3.js, questi dati dovranno assumere la forma di un json-graph che avrà invece queste caratteristiche: { "directed": false, "multigraph": false, "graph": {}, "nodes": [ {
"name": "Actalis S.p.a." },
{
"name": "Aruba S.p.a." },
Un array associativo in cui una delle chiavi dovrà corrispondere a "nodes", il cui valore sarà una lista di array associativi, in cui ciascuno degli elementi corrisponde a un nodo.
{
"name": "Orietta Occhiolini" } ], "links": [ { "weight": 18, "source": 0, "target": 1 }, { "weight": 18, "source": 0, "target": 2
