Visualizzazione della rete

Bisogno

Il principale bisogno dell’utente al quale si intende rispondere è quello di riuscire a visualizzare con immediatezza, le relazioni tra le entità citate nei documenti. L’utilizzo di una rete come strumento di visualizzazione consente di osservare queste relazioni con facilità.

Nel nostro caso, per la rappresentazione delle relazioni si è scelto di mante- nere il metodo già proposto, ovvero considerare come legate due entità se citate nello stesso documento. In qualche maniera, infatti, due persone o aziende citate nello stesso provvedimento possono suggerire di far parte dello stesso

procedimento amministrativo, e quindi è lecito supporre che anche nella realtà queste entità possano in qualche maniera "avere a che fare" l’una con l’altra.

Dato l’elevato numero di entità da rappresentare (nodi e archi), la scelta di utilizzare una rete per modellare i nostri dati può causare alcuni problemi, dovuti principalmente alla gestione e visualizzazione di grafi molto estesi: grafi che, senza i dovuti accorgimenti, possono divenire caotici e illeggibili.

Proposta

Una visualizzazione in rete che superi le criticità derivanti da un grafo troppo esteso, dovrà anzitutto essere interattiva. del grafo creato dovrà essere possibile spostare i nodi per fissarli sullo schermo e, con la stessa semplicità dovrà essere possibile sbloccarli: per questo, così come nella sezione nella sua versione attuale, si è scelto D3.js, una libreria Javascript che, attraverso funzioni "Force Layout". Gli elementi rappresentati, inoltre, dovranno muoversi sempre all’interno della cornice di visualizzazione, che varierà la propria area in base al device utilizzato dall’utente. Le entità che compongono la rete dovranno poi essere riconoscibili all’interno del grafo: per questo si è deciso di attribuire a ciascuna tipologia di entità un’icona diversa dalle altre, anche per il colore. Un’entità sarà così riconoscibile non solo per il proprio nome. Adottare icone siano di colore diverso consente di non fare confusione nel caso in cui i nodi siano molto vicini e, dall’altro lato, nel caso di utenti daltonici, la forma diviene un fattore discriminante per una chiara lettura del grafo.

L’utente dovrà quindi essere in grado di scegliere quali coppie di entità visualizzare selezionando gli elementi posti in due menù a tendina. Questi compariranno sullo schermo come soggetti di una frase di senso compiuto in grado di guidare le azioni dell’utente, ovvero: "Metti in relazione elemento1 con elemento2 e mostra la rete". Una legenda, inoltre sarà a disposizione dell’utente in qualsiasi momento. L’utente dovrà essere in grado di ridurre le dimensioni del grafo. Ciò sarà possibile, come già accade, stabilendo il numero massimo di nodi e il numero minimo di relazioni che dovranno intercorrere tra due elementi perché compaiano. A differenza di come avviene attualmente, però la scelta non avverrà attraverso una slide bar, ma sarà l’utente a digitare

il valore di questi attributi. L’intervallo di valori infatti, va da un minimo di 1 (10 per quanto riguarda le relazioni11_{) a un massimo di 100: soglia}

scelta poiché un numero di nodi maggiore potrebbe ostacolare una corretta visualizzazione della rete. Un’ulteriore soluzione adottata per far fronte ai problemi di visualizzazione, è l’applicazione dell’algoritmo di backbone, e, in particolare, una variante che consente anche di tenere conto di eventuale rumore in fase di computazione, denominata Noise Corrected (NC). Il risultato di questo calcolo sarà un sottografo in cui saranno mantenuti solo i nodi e gli archi statisticamente significativi, che garantiscano cioè il mantenimento della struttura della rete.

Il grafo

Dai dati alla rete Il processo di manipolazione dei dati che dal json fornito dalla query conta di restituire un file json compatibile con la libreria Javascript D3.js, è realizzato tramite uno script in Python, in cui il file json viene importato come un array associativo. I file corrispondenti a ciascuna categoria sono stati suddivisi in diverse cartelle. Si è scelto di esplorare i file di ciascuna di queste cartelle con un ciclo for, che permette di esplorare automaticamente ciascun file (si veda Algorithm 1) .

Visto che una delle chiavi di accesso all’array degli elementi varia in base alle entità estratte, si sono inserite le chiavi in una lista, per poi selezionare il valore corrispondente attraverso un indice costituito da un numero intero. Due cicli for annidati controllano se il primo e il secondo elemento sono già stati registrati e aggiungendo eventualmente in due liste sia il nome dell’entità che il suo attributo, di cui si parlerà al prossimo punto.

Altri due cicli for annidati, come per i nodi, esplorano invece i nodi-source e i nodi-target, che vengono registrati, insieme al peso della relazione tra i due, solo dopo aver controllato che l’arco non sia in realtà un self-loop.

11_{Le query sono state eseguite con questo parametro minimo, per evitare di aumentare il} rumore della rete: entità che compaiono meno di dieci volte sono spesso refusi commessi da chi ha redatto l’atto o errori di estrazione dell’entità nel corso delle analisi linguistiche.

Algorithm 1 Data Manipulation

1: _{procedure Node Extraction} 2: for json file do

3: for element1 do

4: if element1 /∈ NodeList then

5: Add element1 to NodeList

6: Add attribute to AttrList

7: end if

8: for each element2 do

9: if element2 /∈ NodeList then

10: Add element2 to NodeList

11: Add attribute to AttrList

12: end if

13: end for

14: end for

15: end for

16: end procedure

I dati relativi agli archi sono stati poi utilizzati per ottenere un grafo, grazie alla libreria Networkx. Per far sì che venissero registrati anche i nodi isolati un ulteriore ciclo for crea i nodi che non sono stati ricavati dalla lista degli archi. Dal grafo risultante è stato creato un file json, che in fase di esportazione ha resituito un errore di serializzazione: non è possibile, infatti, processare gli oggetti numerici, identificati come un oggetto "numpy". Per ovviare a questo problema si è fatto ricorso a una classe12 _{che convertisse questi oggetti in}

semplici interi o float. Il parametro di encoding= "utf-8" è stato infine inserito per codificare anche i caratteri accentati contenuti nell’attributo dei nodi.

I file csv, input per gli algoritmi di backboning e di estrazione dei graphlet, sono esportati a partire dai dataframe creati con Pandas.

La visualizzazione La funzione D3.js in grado di ricreare gli il grafo, ne- cessita dapprima di creare un oggetto "svg" all’interno del quale sarà costruita la rete. Gli attirbuti assegnati hanno lo scopo di modellare la grandezza di questo contenitore in base alle dimensini della pagina e quindi anche al device utilizzato, garantendo un’esperienza utente unica e omogenea anche attraverso i diversi dispositivi.

Figura 5.2: Un particolare della rete prodotta attraverso la libreria Javacript

D3.js.

Dal file json sono estratte le informazioni sui nodi e sui link, associati agli attributi relativi e applicata la funzione di "Force Layout", che permette di regolare attributi come "charge", che consiste nella repulsione tra i nodi, "linkDistance", ovvero la lunghezza di ciascun arco, "linkStrenght" la flessibilità

di questa lunghezza e come già anticipato, la gravità ("gravity"). La funzione "tick" consente invece la scrittura vera e propria di archi e nodi.

I nodi e link con i relativi attributi saranno invece creati di volta in volta e saranno filtrati secondo le diverse impostazioni stabilite dall’utente, come quelle riguardanti le dimensioni e la tipologia (figura 5.2).

Tipologia degli elementi La tipologia degli elementi corrisponde, nel file json, risultato della query su Solr, al campo "field". I valori che questo campo può assumere, in base alle query effettuate, sono tre: "ne_norm_person", "ne_norm_group" e "ne_norm_aziende". Basterà quindi, in fase di manipola- zione dei dati, effettuare un controllo su questa voce in relazione a una certa entità: accanto al nome del nodo sarà aggiunto un attributo che corrisponderà a "Persona", "Azienda" o "Organizzazione".

All’interno del documento Html, la scelta della tipologia dei due elementi è resa possibile da due menù a tendina. L’utente dovrà poi confermare la sua scelta cliccando sul pulsante "Mostra" (figura 5.3). A questo bottone è legato l’avvio di una funzione callback jQuery, che a sua volta, attraverso una chiamata asincrona jQuery Ajax, consente di catturare il valore assegnato ai due menù a tendina. I dati relativi ai nodi del grafo, contenuti in un file json,

Figura 5.3: Il menù a tendina consente di scegliere quali entità mettere in

relazione.

Figura 5.4: La scelta dei parametri relativi alle dimensioni del grafo. Il tasto

"Mostra tutti", invece mostra tutte le entità estratte dai documenti restituiti in seguito alla query dell’utente.

saranno importati e filtrati, in base all’attributo del singolo nodo.

A ciascuna tipologia di elemento è stata associata una diversa icona nel grafo. Perché ciò fosse possibile si è creato un array associativo in cui a ciascun valore dell’attributo corrispondesse il percorso fino all’immagine scelta. Nell’ambito della funzione D3.js che crea i nodi, sarà associato a ciascuno di essi un oggetto immagine, e dopo averne stabilito la grandezza e la posizione, una diversa immagine è attribuita grazie a una funzione callback che indaga il valore dell’attributo (chiave) e ricerca il valore corrispondente dell’array associativo precedentemente creato.

Gestire le reti più grandi La visualizzazione di grafi di grandi dimensioni è agevolata attraverso l’utilizzo di tre strumenti: filtri sulla grandezza del grafo, la backbone e lo spostamento manuale dei nodi.

Ridimenziona Sotto il grafo, sulla pagina, sono stati inseriti due diversi

number-form (figura 5.4): uno relativo al numero massimo dei nodi scelti tra

quelli con più alto degree e un altro relativo al peso minimo dell’arco che collega due elementi.

Analogamente alla scelta del tipo di entità, anche qui la funzione jQuery Ajax che consente di elaborare i dati inseriti è associata ad una funzione callback legata al click sul tasto "Ridimensiona".

I nodi e gli archi che rispettano queste caratteristiche sono selezionati attraverso una funzione di "filtraggio". Anzitutto vengono registrati i valori inseriti dall’utente. Poi si filtrano i nodi in relazione al degree (che D3.js associa direttamente all’attributo "weigth") ordinandoli e prendendo di questi solo i primi n, dove n corrisponde al parametro inserito dall’utente. Infine si scelgono i link, mantenendo solo quelli in cui sia l’origine che il target sono nodi il cui indice è tra quello dei nodi precedentemente filtrati.

Backbone L’algoritmo di estrazione della backbone Noise Corrected (NC) è scritto in linguaggio Python e prevede, oltre all’utilizzo dei pacchetti Numpy, Pandas e Networkx, anche l’importazione di tre librerie di cui non è stata fatta precedente menzione:

• Sys13_{, Warnings}14_{: il primo pacchetto prevede alcune funzioni che tentano}

di interagire direttamente con l’interprete, il secondo permette di gestire gli errori;

• Collection, Defaultdict: mette a disposizione datatype alternativi ai dizionari, insiemi e tuple15_;

• Scipy.stats16_{, Binom: un modulo che fornisce funzioni statistiche; servirà}

per il calcolo della distribuzione binomiale del peso degli archi;

Il file in input di NC deve essere un file csv separato da tabulatori, composto da tre diverse colonne: L’id del nodo-source, l’id del nodo-target e il peso dell’arco che li collega.

L’algoritmo di NC si compone di tre funzioni principali (si veda Algorithm

2). Per quanto riguarda la funzione "Read" occorre indicare se quello in input

è un grafo orientato. La funzione NC restituisce un grafo i cui attributi sono

13_{https://docs.python.org/2/library/sys.html} 14_{https://docs.python.org/2/library/warnings.html} 15_{https://docs.python.org/2/library/collections.html} 16_{https://docs.scipy.org/doc/scipy/reference/stats.html}

Algorithm 2 Noise Corrected Backbone Extraction

1: _{function Read(Filename, Undirected)} 2: return table, |V |, |E|

3: end function

4: _{function NC(table)}

5: return G(V, E, σ, score)

6: end function

7: _{function Thresholding(G, δ)} 8: return backbone(V ,E)

9: end function

10: _{function Main}

11: _{table, |V |, |E| = Read(Filename, Undirected)} 12: _{G(V, E, σ, score) = NC(table)}

13: _{backbone(V ,E) = Thresholding(G, δ)} 14: end function

δ p-value Nodi Archi

1.28 0.1 104 316

1.64 0.05 104 313

2.32 0.01 104 302

Tabella 5.2: Backbone threshold per la rete in esempio.

score17_{e σ. Quest’ultima corrisponde alla deviazione standard della probabilità}

attesa che un arco abbia un certo peso, rispetto a quella di un modello nullo. L’unico parametro di NC è invece δ, argomento della funzione di "Thresholding". Si tratta di un valore soglia che ha il suo corrispettivo nel p-value. Indica l’intervallo di significatività statistica entro il quale sarà rigettata l’ipotesi nulla, secondo la quale il peso di un certo arco è casuale. Ad esempio, il grafo costruito per i servizi finanziti è composto da 104 nodi e 361 archi, e i risultati ottenuti per i diversi valori (tabella 5.2) mostrano che il numero degli nodi rimane lo stesso, mentre varia il numero degli archi, che diminuisce. Si è scelto un valore di soglia corrispondente a un p-value di 0.01, che mantiene un numero di archi pari a 302.

Per far sì che la rete ridotta venga mostrata sul grafo, è stato creato un nuovo attributo booleano "Backbone" per vertici e per gli archi del grafo originale. Poi questi sono stati messi a confronto con i nodi e i link della backbone: gli elementi che compaiono in entrambi i grafi sono stati contrassegnati da un

17_{Il lift centrato sul valore 0. Misura quanto è inaspettatamente alto il valore del peso di un} certo arco. Il lift è una misura centrata su 1. Centrandola su 0, valori negativi indicheranno un’alta probabilità e valori positivi vicini a 1 una bassa probabilità.

Figura 5.5: Il tasto "Riduzione" consente di visualizzare la backbone del grafo,

nascondendo i nodi e gli archi scartati e colorando di verde i link mantenuti.

Figura 5.6: A sinistra il grafo originario, a destra la sua backbone estratta con

l’algoritmo di NC.

valore di "Backbone" pari a true, false per gli altri.

Ogni volta che l’utente premerà sul bottone "Riduzione" (figura: 5.5), rimarranno visibili solo gli archi e i nodi con il valore true per questo attributo, mentre gli altri saranno nascosti (figura 5.6). Per questo, in fase di creazione del grafo, si è modificato lo "stile" dei componenti, inserendo una condizione di visibilità proprio sull’attributo "Backbone".

Nel nostro caso saranno solamente gli archi ad essere cancellati: i rimasti saranno inoltre evidenziati in verde. Una funzione di callback farà sì che gli archi nascosti tornino visibili e del colore di partenza ogniqualvolta vengano scelte dall’utente altre opzioni.

Figura 5.7: Il tasto "Sblocca elementi" consente appunto di sbloccare i nodi di

cui l’utente ha fissato la posizione attraverso il drag&drop.

Drag&Drop Un altro metodo per facilitare la visualizzazione del grafo è quello di consentire all’utente di spostare i nodi a proprio piacimento attraverso il drag&drop e di fissarli sullo schermo. Ci sono delle specifiche funzioni D3.js a questo scopo: "behavior" e "drag". Si può quindi cliccare sul nodo, e continuando a premere il tasto destro del mouse è possibile trascinare l’elemento, che fisserà la propria posizione nel punto in cui l’utente rilascerà il tasto destro.

Per evitare che l’utente sposti in maniera definitiva il nodo all’esterno del perimetro del contenitore "svg", all’interno del quale il nodo è visibile, si è scelto di non utilizzare il menù-nodo, ma di creare un bottone che consentisse di sbloccare i nodi in qualsiasi momento (figura 5.7).