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

Figura 3.1: Da sinistra a destra, l’icona usata per le persone, quella usata per

organizzazioni e aziende e l’icona che rappresenta i comuni.

},

Un’altra chiave dovrà invece essere "links", il cui valore è un altro array associativo, stavolta composto dagli archi che collegano i nodi: essenziali saranno le indicazioni di "source" e "target" indicati attraverso i valori indice dei nodi.