Università di Catania
Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Laurea di Primo Livello in Informatica
UN TOOL PER LA VISUALIZZAZIONE
E L’ANALISI DI RETI
BIOLOGICHE E SOCIALI
Progetto Finale
Relatore:
Prof.ssa Rosalba Giugno
Correlatore:
Dott. Giuseppe Pigola
Anno Accademico 2009 - 2010
Candidato:
Fabio Rinnone
A Mariolina
Indice
Introduzione
vii
1 Panoramica di Graphtool
1
1.1
Definizioni preliminari . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Interfaccia utente . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Creazione e caricamento di grafi . . . . . . . . . . . . . . . . .
4
1.4
Opzioni di visualizzazione . . . . . . . . . . . . . . . . . . . .
6
2 Formati per la rappresentazione dei grafi
8
2.1
Simple Interaction Format . . . . . . . . . . . . . . . . . . . .
2.2
Graph Modelling Language . . . . . . . . . . . . . . . . . . . . 10
2.3
eXtensible Graph Markup and Modeling Language . . . . . . 11
2.4
Resource Description Framework . . . . . . . . . . . . . . . . 12
2.5
8
2.4.1
Statements . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2
URIs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.3
Literals . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.4
Blank nodes . . . . . . . . . . . . . . . . . . . . . . . . 16
Sintassi per il formato RDF . . . . . . . . . . . . . . . . . . . 16
2.5.1
RDF/XML . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.2
N-Triples
. . . . . . . . . . . . . . . . . . . . . . . . . 17
1
Indice
i
2.5.3
Notation 3 . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.4
TriX . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.5
TriG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Algoritmi su grafi con applicazioni su reti biologiche e sociali 23
3.1
Dijkstra Shortest Path . . . . . . . . . . . . . . . . . . . . . . 24
3.2
Misure di Centralità . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1
Degree Centrality . . . . . . . . . . . . . . . . . . . . . 25
3.2.2
Node/Edge Betweenness . . . . . . . . . . . . . . . . . 26
3.2.3
Closeness . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.4
Barycenter . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.5
Page Rank . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.6
Authority & Hub . . . . . . . . . . . . . . . . . . . . . 29
4 Subgraph matching
31
4.1
Algoritmo di ricerca . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2
Opzioni di ricerca . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3
Network Motifs . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4
Motif Verification . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5
Un esempio completo . . . . . . . . . . . . . . . . . . . . . . . 38
5 Conclusioni
41
Appendice
42
Bibliografia
47
Indice analitico
48
Elenco delle figure
1.1
Grafo e matrice d’adiacenza . . . . . . . . . . . . . . . . . . .
3
1.2
Schermata principale di Graphtool . . . . . . . . . . . . . . .
4
1.3
Pannello laterale di Graphtool . . . . . . . . . . . . . . . . . .
5
1.4
Grafo con layout circolare . . . . . . . . . . . . . . . . . . . .
6
1.5
Hyperbolic View . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1
Grafo in formato SIF . . . . . . . . . . . . . . . . . . . . . . .
9
2.2
File NA con attributi dei nodi di un file SIF . . . . . . . . . .
9
2.3
File EA con attributi degli archi di un file SIF . . . . . . . . . 10
2.4
Grafo in formato GML . . . . . . . . . . . . . . . . . . . . . . 11
2.5
Parametri grafici di un file GML . . . . . . . . . . . . . . . . . 11
2.6
Grafo in formato XGMML . . . . . . . . . . . . . . . . . . . . 12
2.7
Parametri grafici di un grafo XGMML . . . . . . . . . . . . . 13
2.8
Modello dati RDF
2.9
Grafo RDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . . . . . . 14
2.10 Grafo RDF e sua serializzazione in RDF/XML . . . . . . . . . 18
2.11 Grafo RDF con language tags . . . . . . . . . . . . . . . . . . 19
2.12 Grafo in formato N-Triples . . . . . . . . . . . . . . . . . . . . 19
2.13 Semplice grafo in formato Notation 3 . . . . . . . . . . . . . . 20
2.14 Grafo in formato Notation 3 . . . . . . . . . . . . . . . . . . . 20
ii
Indice
iii
2.15 Grafo in formato TriX . . . . . . . . . . . . . . . . . . . . . . 21
2.16 Grafo in formato TriG . . . . . . . . . . . . . . . . . . . . . . 22
3.1
Esempio di Indegree Centrality . . . . . . . . . . . . . . . . . 26
3.2
Esempio di Closeness Centrality . . . . . . . . . . . . . . . . . 28
4.1
Subgraph Matching . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2
Passi dell’algoritmo VF2 . . . . . . . . . . . . . . . . . . . . . 34
4.3
Tipi di Query . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.4
Caratteristiche delle query . . . . . . . . . . . . . . . . . . . . 35
4.5
Esecuzione di una ricerca . . . . . . . . . . . . . . . . . . . . . 36
4.6
Feed-forward loop . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.7
Motifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.8
Query d’esempio . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.9
Target d’esempio . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.10 Selezione di un match . . . . . . . . . . . . . . . . . . . . . . . 39
4.11 Motif Verification . . . . . . . . . . . . . . . . . . . . . . . . . 40
Elenco degli algoritmi
1
Rilassamento di un arco . . . . . . . . . . . . . . . . . . . . . 24
2
Algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . . 25
3
Calcolo dell’Hub e dell’Authority . . . . . . . . . . . . . . . . 30
4
Algoritmo di matching VF2 . . . . . . . . . . . . . . . . . . . 33
iv
Introduzione
Una delle strutture dati più potenti e largamente utilizzate in informatica
è sicuramente il grafo (di seguito indicato anche come network o rete). Esso
permette di modellare diversi problemi che spaziano, ad esempio, dall’analisi
di network biologiche allo studio di interazioni sociali. Numerose sono le
problematiche che possono essere affrontate mediante tale struttura dati: tra
queste troviamo la ricerca di un cammino minimo, il calcolo delle misure
di centralità e la ricerca di occorrenze di sottostrutture all’interno di un
grande grafo. Esse sono tutte operazioni comuni su grafi che richiedono
algoritmi raffinati ed efficienti. Non di minore importanza è la possibilita di
visualizzare in modo efficiente un grafo ed eventualmente avere la possibilità
di rappresentare graficamente il risultato di un algoritmo applicato ad esso.
Lo scopo di questo progetto è stato la realizzazione di un tool, chiamato Graphtool, per la visualizzazione e l’analisi di reti biologiche e sociali.
Esso è portabile e, di conseguenza, eseguibile su tutte le principali piattaforme hardware e sistemi operativi (Microsoft Windows, GNU/Linux, Solaris,
etc.). Fornisce, inoltre, un’intuitiva interfaccia grafica che guida agevolemente l’utente nel caricamento, creazione e visualizzazione di grafi. Dà altresi la
possibilità di creare ed eventualmente salvare il proprio grafo in una serie di
diversi formati standard. Infine, Graphtool mette a disposizione dell’utente
una serie di algoritmi per li calcolo di misure di centralità e per la ricerca di
v
Introduzione
sottostrutture all’interno di un grafo (subgraph matching).
Dal momento in cui lo scopo principale di Graphtool è stato quello di sviluppare algoritmi per l’analisi di grafi di interazioni sociali, esso si pone nel
contesto dell’Analisi dei Social Network. Ciò non preclude la possibilità di
poter permettere all’utente di lavorare su network biologiche e d’interazione
molecolare e di porre anche l’attenzione al concetto di Web semantico, attualmente in fase di continua evoluzione grazie al progressivo diffondersi del
formato RDF (Resource Description Framework), quest’ultimo particolarmente adatto per la rappresentazione di risorse correlate fra loro e reperibili
nel World Wide Web e non solo.
Intuitivamente una rete sociale è una struttura sociale caratterizzata dalla
presenza di individui (o organizzazioni) rappresentabili mediante nodi ed una
serie di relazioni che intercorrono tra di essi, quest’ultimi rappresentabili sotto
forma di archi. I tipi di relazione possono essere i piu svariati: da relazioni di
amicizia, di parentela, interessi comuni o altro ancora. L’Analisi dei Social
Network deriva della Teoria dei Grafi e si occupa di analizzare le reti sociali
individuando ed analizzando i legami che intercorrono tra i vari individui o
nodi e permettendo di fornire delle specifiche misure (dette di centralità) che
danno una misura dell’importanza di ciascun nodo in base al posto che esso
occupa all’interno della rete. Graphtool fornisce una serie di algoritmi per il
calcolo di molte tra le più importanti misure di centralità.
Ovviamente il calcolo delle misure di centralità non è una prerogativa
esclusiva delle network sociali. Le misure di centralità possono anche essere
calcolate su reti biologiche: in tali reti un nodo rappresenta una componente
biologica (ad es. un gene, una proteina, etc.) ed un arco tra due nodi
rappresenta una interazione (conosciuta o prevista) tra due componenti.
Sia nelle reti biologiche che nelle reti sociali, Graphtool permette infi-
vi
Introduzione
ne di ricercare occorrenze di sottostrutture, anche approssimate, mediante l’applicazione di un efficiente algoritmo di matching [1] opportunamente
modificato.
Di seguito presenteremo, nel capitolo 1, una panoramica generale del
funzionamento e delle opzioni di Graphtool, nel capitolo 2 una descrizione
completa dei formati di rappresentazione dei grafi supportati da Graphtool,
nel capitolo 3 mostreremo gli algoritmi per il calcolo della centralità supportati ed infine, nell’ultimo capitolo, descriveremo la ricerca di sottostrutture
nei grafi.
vii
Capitolo 1
Panoramica di Graphtool
In questo capitolo presenteremo una panoramica generale di Graphtool,
mostrandone dettagli relativi all’interfaccia utente. La parte di codice relativa ad analisi e visualizzazione di Graphtool si basa sulla libreria Java
Universal Network/Graph Framework (JUNG2.0) [2]. Essa permette di modellare, analizzare e visualizzare grafi. Scritta in Java, JUNG2.0 si presta perfettamente per la realizzazione di Graphtool. Per maggiori dettagli
implementativi si rimanda il lettore all’appendice.
1.1
Definizioni preliminari
Graphtool è stato sviluppato per la visualizzazione ed analisi di grafi
con particolare riferimento a reti biologiche e sociali. Presenteremo, quindi,
alcune definizioni preliminari riguardanti i grafi.
Definizione 1.1. Un grafo è una coppia G = (V, E) dove V è l’insieme dei
vertici (o nodi) ed E è l’insieme degli archi (v, w) tali che v ∈ V e w ∈ V . Il
numero di vertici e di archi è dato rispettivamente da |V | e |E|.
1
1.1 Definizioni preliminari
2
Definizione 1.2. Un grafo si dice orientato quando E è un insieme di coppie
ordinate. Un arco (w, u) si dice incidente da w in u.
Definizione 1.3. Un grafo si dice non orientato quando E è un insieme di
coppie non ordinate.
Definizione 1.4. Una matrice d’adiacenza A(aij ) di un grafo è una matrice
| V | × | V | tale che

 1 se (i, j) ∈ E,
aij =
 0 altrimenti.
(1.1)
In Figura 1.1 è mostrato un semplice grafo e la sua matrice d’adiacenza.
Definizione 1.5. Il grado (degree) di un vertice u ∈ V di un grafo non
orientato è il numero di archi (u, w) ∈ E.
Definizione 1.6. Il grado entrante (indegree) di un vertice w ∈ V di un
grafo orientato è il numero di archi (u, w) ∈ E incidenti in esso.
Definizione 1.7. Il grado uscente (outdegree) di un vertice u ∈ V di un
grafo orientato è il numero di archi (u, w) ∈ E che da esso si dipartono.
Definizione 1.8. Dato un grafo è possibile definire una funzione peso (weight)
w : E → R tale che associ ad ogni arco un valore nell’insieme dei numeri
reali.
Definizione 1.9. Dato un grafo pesato, il peso di un cammino p da un
vertice v0 ad un vertice vk (tali che vi ∈ V con i = 0, 1, ..., k) è definito da
w(p) =
k
X
i=1
w(vi−1 , vi )
(1.2)
1.2 Interfaccia utente
1
3
2
3
5
4
(a)
1
2
3
4
5
1
0
1
0
0
0
2
1
0
0
0
1
3
0
1
1
1
0
4
0
1
0
0
1
5
1
0
0
0
0
(b)
Figura 1.1: Grafo e matrice d’adiacenza. (a) Grafo orientato G. (b)
Matrice d’adiacenza di G.
Graphtool fornisce un’intuitiva interfaccia utente utile per la rappresentazione dei grafi e l’applicazione di diversi algoritmi. Segue adesso una rapida
panoramica dell’interfaccia utente.
1.2
Interfaccia utente
All’avvio dell’applicazione viene mostrato un framework con un pannello laterale ed un pannello centrale principale. In Figura 1.4 è mostrata la
schermata principale di Graphtool con all’interno la rappresentazione di un
grafo.
Il pannello laterale mostra le opzioni principali mentre il pannello centrale permette di visualizzare contemporaneamente diversi grafi (gestiti tutti
in memoria principale). L’utente puo decidere se creare un nuovo grafo,
aprirne uno esistente, salvare, chiudere i grafi correntemente aperti o uscire
dall’applicazione. L’utente puo anche scegliere se visualizzare o nascondere
il pannello laterale delle opzioni in modo da ottenere piu spazio per l’editing
o la visualizzazione dei grafi aperti. Dal pannello laterale è possibile visualizzare la lista dei grafi correntemente caricati, le opzioni di visualizzazione
ed impostare le opzioni per l’esecuzione di vari algoritmi.
1.3 Creazione e caricamento di grafi
Figura 1.2: Schermata principale di Graphtool.
1.3
Creazione e caricamento di grafi
Alla creazione di un nuovo grafo viene aperta una nuova scheda in corrispondenza del pannello principale che permette di disegnare un nuovo grafo.
Utilizzando il mouse l’utente puo creare vertici ed archi e visualizzare proprietà del grafo corrente, editare etichette e attributi dei vertici e degli archi
o modificarne proprietà grafiche (quali spessore della linea di contorno o colore). È data anche la possibilita di decidere se visualizzare o meno i grafi
caricati. Quest’ultima opzione risulta particolarmente utile quando si ha a
che fare con grafi di grandi dimensioni per i quali la visualizzazione potrebbe non essere possibile a causa delle enormi richieste in termini di spazio di
memoria. Con tale opzione è possibile caricare comunque un grafo, anche
se non visualizzato, al fine di poter applicare comunque un algoritmo su di
esso. Per evitare un sovraccarico della memoria i grafi caricati da file con un
numero di vertici superiore a 1000 non sono visualizzati come impostazione
4
1.3 Creazione e caricamento di grafi
5
(a)
(b)
(c)
(d)
Figura 1.3: Pannello laterale di Graphtool. (a) Visualizzazione dei grafi
correntemente caricati con rispettivi numero di vertici e di archi. (b) Opzioni di visualizzazione. (c) Scelta e calcolo delle misure di centralità su
grafi. (d) Ricerca di sottostrutture in un grafo.
1.4 Opzioni di visualizzazione
Figura 1.4:
Grafo con layout circolare:
visualizzazione dei grafi.
6
layout predefinito di
di default.
1.4
Opzioni di visualizzazione
Dal pannello delle opzioni è possibile settare alcune impostazioni di visualizzazione dei grafi. In particolare l’utente puo scegliere la modalità di
interazione con i grafi correntemente aperti: Editing permette di aggiungere o rimuovere vertici ed archi, Transforming permette di ruotare o ridimensionare il grafo, Piking permette di spostare vertici ed archi. Possono
inoltre essere impostate le viste iperboliche ossia particolari metodi di visualizzazione pseudo tridimensionale (Figura 1.5) e selezionati diversi layout di
disposizione dei grafi sul piano. Il layout predefinito è quello circolare: in
1.4 Opzioni di visualizzazione
tal caso i vertici vengono disposti in eguale distanza dal centro del pannello
di visualizzazione e in eguale distanza gli uni dagli altri. Altre opzioni di
visualizzazione riguardano la tipologia di archi (ad esempio curvilinei od ortogonali), il tipo di colorazione degli archi, la posizione e la visualizzazione
delle etichette sia dei vertici che degli archi.
Figura 1.5: Hyperbolic View.
7
Capitolo 2
Formati per la rappresentazione
dei grafi
Graphtool supporta svariati formati di file per la rappresentazione di grafi ed in particolare di reti biologiche e sociali. Tali formati sono compatibili
con standard riconosciuti a livello internazionale. In questo capitolo verranno descritti in dettaglio i formati supportati con particolare attenzione allo
standard Resource Description Framework (RDF) e delle notazioni usate per
la rappresentazione dei dati.
2.1
Simple Interaction Format
Il formato Simple Interaction Format (SIF) è un formato di rappresentazione di reti biologiche correntemente adottato da diversi tool tra cui Cytoscape, quest’ultima un’applicazione ampiamente usata nell’ambito della
bioinformatica per la visualizzazione e l’analisi di reti biologiche [3].
Tale formato permette di rappresentare testualmente le interazione tra i
vari nodi. Ogni riga assume il formato source edge target1 ...
8
targetN.
2.1 Simple Interaction Format
node1 edge1 node2 node3
node2 edge2 node3
node3
node4 edge3 node4 node5
Figura 2.1: Grafo in formato SIF: il grafo rappresentato è costituito
da 5 nodi e 3 vertici. Il nodo node1 è connesso tramite l’arco edge1 ai
nodi node2 e node3. Il nodo node3 non ha archi in uscita, ma ha due
archi in ingresso provenienti rispettivamente da node1 e node2. Il nodo
node4, inoltre, ha un arco avente se stesso come destinazione. Archi con
indentica etichetta sono consentiti: saranno, tuttavia, caricati in memoria
con id numerici differenti.
In Figura 2.1 è mostrato un esempio di grafo in formato SIF. In Cytoscape
i tag per i nodi specificano l’id dell’arco (tipicamente una stringa di testo),
mentre i tag degli archi specificano il tipo di relazione tra due o più nodi.
In Graphtool i suddetti tag vengono interpreati come etichette (labels) dei
nodi e degli archi essendo essi identificati mediante id numerici univoci. Il
formato SIF consente, oltre che a definire le etichette dei nodi e degli archi,
di associare ad essi anche attributi. Gli attributi sono definiti in due file
separati aventi lo stesso nome del file SIF ma estensioni differenti: NA per il
file degli attributi dei nodi e EA per il file degli attributi degli archi. Nelle
figure Figura 2.2 e Figura 2.3 sono mostrati due esempi di file degli attributi
associabili al file in Figura 2.1. Da notare che non è obbligatorio che ad un
file in formato SIF siano associati i rispettivi file degli attributi.
node1
node2
node3
node4
node5
=
=
=
=
=
nattr1
nattr2
nattr3
nattr4
nattr5
Figura 2.2: File NA con attributi dei nodi di un file SIF: ad ogni nodo è
associato un solo attributo.
9
2.2 Graph Modelling Language
node1
node1
node2
node4
node4
(edge1)
(edge1)
(edge2)
(edge3)
(edge3)
node2
node3
node3
node4
node5
=
=
=
=
=
eattr1
eattr2
eattr3
eattr4
eattr5
Figura 2.3: File EA con attributi degli archi di un file SIF: per ogni
arco con specifica etichetta, avente nodo sorgente e destinazione definiti, è
associato un attributo.
2.2
Graph Modelling Language
Il formato Graph Modelling Language (GML) è un formato portabile per
la rappresentazione di grafi [4]. Le caratteristiche che lo contraddistinguono
sono semplicità d’interpretazione, estensibilità e particolare flessibilità. Un
file GML consiste in una serie di coppie chiave-valore organizzate gerarchicamente. L’implementazione è molto flessibile poiché non è necessario che
venga garantito un ordine specifico nella dichiarazione dei vari elementi che
caratterizzano il grafo. Un grafo in formato GML è un insieme di liste di
valori racchiuse tra parentesi quadre che identificano le caratteristiche principali della struttura. Ogni lista può contenere al suo interno ulteriori liste:
l’idea di base è che un grafo è costituito da un insieme di nodi e di archi ed
ogni nodo o arco può essere costituito da insiemi di proprietà (quali possono
essere aspetto grafico o posizione). In Figura 2.4 è mostrato un semplice
grafo in formato GML che rappresenta un grafo costituito da un ciclo con 3
nodi.
Possono, quindi, essere definiti per ciascun nodo od arco appositi parametri grafici in cui sono descritte caratteristiche relative al loro aspetto e
le coordinate che identificano la posizione di ogni singolo nodo. In figura
Figura 2.5 è riportato un esempio di grafo GML.
10
2.3 eXtensible Graph Markup and Modeling Language
graph [
node [ id 1 label "node1" ]
node [ id 2 label "node2" ]
node [ id 3 label "node3" ]
edge [ source 1 target 2 label "edge1" ]
edge [ source 2 target 3 label "edge2" ]
edge [ source 2 target 3 label "edge3" ]
]
Figura 2.4: Grafo in formato GML: dopo la definizione iniziale graph
sono definiti tre nodi (node) per ognuno dei quali è definito un id, un etichetta e successivamente gli archi. Per ogni arco (edge) sono definiti, oltre
che l’etichetta, i rispettivi id del nodo sorgente e del nodo destinazione.
graph [
node [ id 1 label "node1"
graphics [ x 1.0 y 1.0 w 2.0 h 2.0 color "green" ]
]
node [ id 2 label "node2"
graphics [ x 3.0 y 4.0 w 1.5 h 1.5 color "red" ]
]
edge [ source 1 target 2 label "edge1"
graphics [ color "blue" ]
]
Figura 2.5: Parametri grafici di un file GML: il parametro graphics
definisce proprietà grafiche per i nodi e per gli archi. In questo caso x e y
fissano le coordinate dei nodi mentre w e h larghezza ed altezza di nodi ed
archi. Il parametro color definisce la colorazione del nodo o dell’arco.
2.3
eXtensible Graph Markup and Modeling
Language
Il formato GML è particolarmente flessibile, ha una sintassi intuitiva ed
è molto potente in quanto permette la rappresentazione di qualsiasi struttura dati arbitraria che va oltre quella dei grafi. Tuttavia esiste un’estensione
del linguaggio di modellazione di grafi GML basata su XML, detta eXten-
11
2.4 Resource Description Framework
sible Graph Markup and Modeling Language (XGMML), che consente di
rappresentare le medesime strutture dati sfruttando le potenzialità semantiche del diffuso metalinguaggio di markup incrementandone notevolmente
l’espressività [5]. Un grafo espresso in formato GML può essere agevolmente
convertito in XGMML e viceversa. L’XML (eXtensible Markup Language)
è un linguaggio di markup particolarmente flessibile ed essendo estendibile
consente la definizione di tags personalizzati che possono essere utilizzati per
i più svariati scopi: proprio per questo motivo le coppie chiavi-valori descritte per il formato GML possono essere agevolmente espresse sotto forma di
coppie attributi-valori di appositi tag XGMML. In Figura 2.6 è mostrato il
grafo visto in Figura 2.4 espresso in notazione XGMML.
<graph directed="1 id="1" label="Graph">
<node id="1" label="node 1"> </node>
<node id="2" label="node 2"> </node>
<node id="3" label="node 3"> </node>
<edge source="1" target="2" label="edge 1"> </edge>
<edge source="2" target="3" label="edge 2"> </edge>
<edge source="3" target="1" label="edge 3"> </edge>
</graph>
Figura 2.6: Grafo in formato XGMML: il grafo è costituito da un ciclo
con 3 nodi. Sono indicati anche un id ed un’etichetta associati al grafo. Il
significato degli attributi dei tag relativi ai nodi ed agli archi è intuitivo.
Analogamente al formato GML è possibile definire anche in XGMML
una serie di tag che impostano le opzioni grafiche dei nodi e degli archi. Un
esempio è mostrato in Figura 2.7.
2.4
Resource Description Framework
Graphtool supporta pienamente il caricamento ed il salvataggio di grafi
in formato Resource Descripion Framework (RDF). RDF è uno standard
12
2.4 Resource Description Framework
<graph directed="1" id="1" label="Graph">
<node id="1" label="node 1">
<graphics x="1.0" y="1.0" w ="2.0" h="2.0" color="green">
</graphics>
</node>
<node id="2" label="node 2">
<graphics x="3.0" y="4.0" w ="1.5" h="1.5" color="red">
</graphics>
</node>
<edge source="1" target="2" label="edge 1">
<graphics color="blue"> </graphics>
</edge>
</graph>
Figura 2.7: Parametri grafici di un grafo XGMML: il grafo è analogo a
quello rappresentato in Figura 2.5 ed è costituito da due nodi interconnessi
da un arco.
proposto dal World Wide Web Consortium (W3C) [6] nel 1999 ed usato
come metodo generale per la descrizione concettuale e la modellazione di
informazioni implementate sotto forma di risorse disponibili sul Web [7, 8].
Nella maggior parte dei casi è utilizzato per la rappresentazione di metadati
sul Web, quali potrebbero essere titolo, autore o data di ultima modifica di
una pagina web, ma, generalizzando, può essere applicato per la definizione
di qualsiasi risorsa anche non disponibile nel web.
2.4.1
Statements
Lo standard RDF si basa sull’idea che le singole risorse possano essere identificate mediante Uniform Resource Identificator (URI). Un URI è
una stringa di caratteri adibita all’identificazione univoca di una risorsa disponibile sul Web, ma anche di un file, un’immagine, un indirizzo di posta
elettronica e quant’altro. Ogni concetto che può essere descritto con RDF è
costituito da un insieme di proprietà che possono assumere determinati valo-
13
2.4 Resource Description Framework
14
ri: la definizione di tali relazioni avviene mediante appositi statements, ossia
triple di elementi chiamati rispettivamente subject, predicate e object.
Si veda [9] per una descrizione dettagliata della sintassi URI.
predicate
subject
object
Figura 2.8: Modello dati RDF.
Da questa premessa appare evidente che RDF consista nella definizione
di una serie di triple di elementi che esprimono relazioni tra varie risorse.
Risulta evidente, altresì, che tale notazione può essere agevolmente espressa
sotto forma di grafo in cui ogni singola tripla rapresenta una coppia di nodi
connessa con un arco. Particolare attenzione occorre prestare al fatto che i
grafi RDF sono orientati: la direzione di ogni arco va sempre dal soggetto
verso l’oggetto.
Da quanto detto, durante lo sviluppo di Graphtool, si è voluto fare in
modo che fosse in grado di elaborare dati RDF e di fornirne una rappresentazione grafica intuitiva. L’utente sarà in grado di analizzare tali dati ed
eventualmente modificarli, garantendo comunque che in fase di salvataggio
lo standard sia rispettato. In Figura 2.9 è riportato un semplice grafo RDF
costituito da due triple.
Lo standard RDF impone vincoli ben precisi ai tipi di dati che i componenti di una singola tripla possono assumere [10]. In particolare è consentito
che il subject possa essere un URI o un blank node, il predicate esclusivamente un URI, mentre il object un URI, un blank node o un tipo literal.
Mostriamo un dettaglio di queste queste caratteristiche.
2.4 Resource Description Framework
15
http://www.example.org/index.html
http://purl.org/dc/elements/1.1/language
EN
http://purl.org/dc/elements/1.1/creator
http://www.example.org/id/459569
Figura 2.9: Grafo RDF: un semplice grafo RDF costuito da due triple
aventi medesimo subject. In questo caso il grafo è costituito da tre nodi e
due archi.
2.4.2
URIs
Un URI consente di identificare una risorsa univoca (generalmente nel
Web). Esso è una stringa di caratteri UNICODE non contenente alcun carattere di controllo ed identificata dalla presenza di un apposito separatore
(:) che distingue lo schema (identificante il protocollo di comunicazione utilizzato) e una stringa (la cui interpretazione dipende dal tipo di schema) [9].
La stringa può essere suddivisa in namespace e localname distinti mediante
un apposito carattere di separazione.
2.4.3
Literals
Un literal è una stringa di caratteri che può assumere due forme distinte:
plain literal a cui può essere associato un tag language opzionale oppure typed
literal a cui è associato un tag datatype obbligatorio. Un datatype associato
ad un typed literal consiste in un URI [11]. Una descrizione dettagliata dei
tag language si trova in [12].
2.5 Sintassi per il formato RDF
2.4.4
Blank nodes
I blank nodes sono appartenenti ad un insieme infinito di elementi tale
che esso, l’insieme infinito degli URI e l’insieme infinito dei literals siano a
due a due disgiunti. In Graphtool un blank node è rappresentato come un
nodo del grafo con etichetta uguale ad una stringa vuota di caratteri.
2.5
Sintassi per il formato RDF
Esistono svariate sintassi che permettono di esprimere grafi RDF: esse possono essere più o meno semplici notazioni testuali o serializzazioni
in XML. In questo paragrafo vedremo le principali notazioni supportate da
Graphtool sia in caricamento che in salvataggio.
2.5.1
RDF/XML
RDF/XML è la serializzazione più comune e più diffusa di grafi RDF. Il
suo utilizzo è altamente raccomandato dal World Wide Web Consortium in
quanto può essere utilizzato per codificare il modello di dati per lo scambio
d’informazioni tra applicazioni [10]. Tale serializzazione permette, altresì, la
possibilità di poter effettuare uno scambio di informazioni tra RDF e qualsiasi
altra applicazione XML. Un nodo RDF/XML può essere un URI, un literal
o un blank node. Un nodo subject può essere un URI o un blank node: nel
caso sia un URI, esso rappresenta tipicamente una proprietà dell’elemento. Il
predicate può essere esclusivamente un URI ed in questo caso rappresenta
una relazione che intercorre tra soggetto ed oggetto. Un nodo object, invece,
può anche essere un literal. Nel caso in cui il nodo è un blank node può essere
associato opzionalmente ad esso un apposito tag detto blank node identifier.
Tale identificatore viene usato per consentire di distinguere più agevolmente
16
2.5 Sintassi per il formato RDF
un blank node da un URI o da un literal. Graphtool permette di salvare
in formato RDF/XML, come impostazione di default, impostando un blank
node identifier per ciascun blank node del grafo. Un grafo RDF ed una sua
possibile serializzazione in RDF/XML sono mostrati in Figura 2.10.
I nodi plain literal possono avere un attributo language opzionale mentre
i nodi typed literal hanno un attributo datatype obbligatorio. Nel primo
caso nodi con la stessa etichetta, ma con attributi language, devono essere
rappresentati da Graphtool come vertici distinti. In Figura 2.11 è mostrato
un semplice grafo RDF in cui sono definiti alcuni tags language.
Le specifiche complete della sintassi RDF/XML sono riportate in [13].
Una successiva revisione del formato RDF/XML detta RDF Revised, che
risolve alcuni problemi sintattici intrinsechi ad RDF/XML, è descritta in
[14].
2.5.2
N-Triples
La notazione N-Triples, tipicamente usata a fini di testing, è una semplice
notazione testuale per esprimere in modalità chiara ed intuitiva le triple
di un documento RDF [15]. Un documento N-Triples è una sequenza di
dichiarazioni subject predicate object, i cui delimitatori differiscono nel
caso in cui siano URI, blank nodes o literals. In Figura 2.12 è mostrato il
grafo visto in Figura 2.10(b) espresso nella notazione N-Triples.
2.5.3
Notation 3
Notation 3 (N3) è un’ulteriore notazione usata per esprimere grafi in
formato RDF. Ha un formato compatto e leggibile che costituisce una valida alternativa alla serializzazione in XML conferendone, altresì, maggiore
espressività e simmetricità [16]. Tale notazione è particolarmente adatta
17
2.5 Sintassi per il formato RDF
18
http://www.example.org/example
http://www.example.org/editor
http://purl.org/elements/1.1/title
Example Page
http://www.example.org/homepage
http://purl.org/net/mariorossi
http://www.example.org/name
Mario Rossi
(a)
<rdf:RDF
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:ex="http://www.example.org/">
<rdf:Description rdf:about="http://www.example.org/example">
<ex:editor rdf:nodeID="A0"/>
<dc:title>Example Page</dc:title>
</rdf:Description>
<rdf:Description rdf:nodeID="A0">
<ex:homepage rdf:resource="http://purl.org/net/mariorossi"/>
<ex:name>Mario Rossi</ex:name>
</rdf:Description>
</rdf:RDF>
(b)
Figura 2.10: Grafo RDF e sua serializzazione in RDF/XML. (a) Il grafo
RDF. (b) Una possibile serializzazione in RDF/XML: È differente la notazione per identificare gli URI dai literals nei nodi subject ed object.
Gli archi sono URI per i quali è specificato un prefisso associato ad un
localname. Le corrispondenze tra prefisso e specifico namespace sono elencate all’inizio del file: ad esempio al prefisso ex è associato il namespace
http://www.example.org. Il blank node è identificato dall’id A0 ed è presente in due distinte triple: infatti gli archi uscenti da esso nel grafo sono
due.
2.5 Sintassi per il formato RDF
19
http://www.example.org/example
http://www.example.org/name
http://www.example.org/name
http://www.example.org/name
Example Page
Example Page @it
Example Page @en
(a)
<rdf:RDF
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:ex="http://www.example.org/">
<rdf:Description rdf:about="http://www.example.org/example">
<ex:name>Example Page</ex:name>
<ex:name xml:lang="it">Example Page</ex:name>
<ex:name xml:lang="en">Example Page</ex:name>
</rdf:Description>
</rdf:RDF>
(b)
Figura 2.11: Grafo RDF con language tags. (a) Il grafo RDF. (b)
Serializzazione in RDF/XML.
_:a <http://www.example.org/homepage> <http://purl.org/net/mariorossi/> .
_:a <http://www.example.org/name> "Mario Rossi" .
<http://www.example.org/example> <http://www.example.org/example> _:a .
<http://www.example.org/example> <http://purl.org/dc/elements/1.1/title>
"Example Page" .
Figura 2.12: Grafo in formato N-Triples.
per fornire un elenco chiaro e leggibile delle triple RDF. Analogamente alla
notazione N-Triples è possibile specificare le singole triple riga per riga apponendo appositi delimitatori a seconda che gli elementi siano URI, blank
nodes o literal. In Figura 2.13 è mostrato un semplice file N3 con una tripla
RDF.
A differenza della notazione N-Triples, tuttavia, è possibile semplificare
2.5 Sintassi per il formato RDF
<http://www.example.org/example> <http://www.example.org/name>
"Mario Rossi";
Figura 2.13: Semplice grafo in formato Notation 3: la notazione è molto
simile alla N-Triples.
la sintassi nel caso in cui più triple abbiano lo stesso subject. Come nella
sintassi RDF/XML, è possibile specificare appositi prefix da associare ai
namespaces dei riferimenti URI [17]. In Figura 2.14 è fornito un esempio
completo di rappresentazione di un grafo in Notation 3. Esiste anche una
notazione più semplice della Notation3, chiamata Turtle [18], che ne costituisce un sottoinsieme: anch’essa è pienamente supportata in lettura e scrittura
da Graphtool.
@prefix p:
@prefix m:
<http://www.example.org/personal_details#> .
<http://www.example.org/meeting_organization#> .
<http://www.example.org/people#fred>
p:GivenName "Fred";
p:hasEmail <mailto:[email protected]>;
m:attending <http://meetings.example.com/cal#m1> .
<http://meetings.example.com/cal#m1>
m:homePage <http://meetings.example.com/m1/hp> .
Figura 2.14: Grafo in formato Notation 3: in questo caso al namespace http://www.example.org/meeting_organization# è associato il
prefisso m e al namespace http://www.example.org/personal_details#
il prefisso p.
Il nodo http://www.example.org/people#fred ha
tre archi in uscita definiti nelle tre righe successive.
Il nodo
http://meetings.example.com/cal#m1 ha, invece, un solo arco in uscita.
La rappresentazione di questo grafo in notazione Turtle è, in questo caso,
identica.
20
2.5 Sintassi per il formato RDF
<TriX>
<graph>
<triple>
<id>x</id>
<uri>http://example.org/wife</uri>
<uri>http://example.org/Mary</uri>
</triple>
<triple>
<uri>http://example.org/Bob</uri>
<uri>http://example.org/name</uri>
<plainLiteral>Bob</plainLiteral>
</triple>
<triple>
<uri>http://example.org/Mary</uri>
<uri>http://example.org/age</uri>
<typedLiteral
datatype="http://www.w3.org/2001/XMLSchema#integer"
>32</typedLiteral>
</triple>
</graph>
</TriX>
Figura 2.15: Grafo in formato TriX: si distinguono chiaramente, per ogni
tripla, gli URI, i blank nodes, i plain literals ed i typed literals. Il tag id
identifica un blank node.
2.5.4
TriX
Il formato RDF/XML presenta diversi problemi che non ne possono consentire un uso completo, soprattutto per quanto riguarda problemi relativi
alla validazione e per quanto riguarda l’interoperabilità con altre applicazioni
XML. Per questo motivo si è tentato d’introdurre una nuova notazione, sintatticamente più semplice e pur sempre basata su XML: essa prende il nome
di TriX [19]. Un documento in formato TriX è un documento XML il cui
grafo è delimitato da tag graph ed ogni tripla è delimitata da appositi tag
triple. Sono esplicitamente distinti tag che identificano blank node, URI,
21
2.5 Sintassi per il formato RDF
plain literal e typed literal. Un esempio è mostrato in Figura 2.15. Graphtool, oltre ai formati RDF già descritti, supporta, anche in questo caso,
caricamento e salvataggio di questo formato.
2.5.5
TriG
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix ex: <http://www.example.org/vocabulary#> .
@prefix : <http://www.example.org/exampleDocument#> .
:G1 { :Mario ex:name Mario Rossi .
:Mario ex:homepage <http://www.mariorossi.it> .
:Mario ex:email <mailto:[email protected]> .
:Mario ex:hasSkill ex:Management }
:G2 { :Mario rdf:type ex:Person .
:Mario ex:hasSkill ex:Programming }
Figura 2.16: Grafo in formato TriG: in questo file sono descritti due
differenti grafi (G1 e G2) separati dai delimitatori { e }. La definizione
delle triple e dei namespaces è identica a Turtle.
Il formato TriG è una sintassi per descrivere grafi RDF che nasce come
valida alternativa a TriX ed ha una sintassi simile a Turtle, di cui ne costituisce un’estensione [20]. Tale sintassi aggiunge due nuovi delimitatori per
permettere di raggruppare più grafi in un unico file e permette di associare
ad ogni grafo un nome. In Figura 2.16 è mostrato un semplice esempio in
cui sono descritti due differenti grafi.
22
Capitolo 3
Algoritmi su grafi con applicazioni
su reti biologiche e sociali
Graphtool permette di eseguire una serie di algoritmi sui grafi fornendo
all’utente una chiara ed intuitiva interfaccia che lo guida nella selezione e
nell’esecuzione dell’algoritmo desiderato. I risultati sono mostrati in un apposito log e sono agevolmente consultabili. Inoltre, a seconda dell’algoritmo
scelto e del risultato ottenuto, la rete sui cui è eseguito assume connotazioni
visive tali da descrivere visivamente il risultato di tale algoritmo.
Graphtool consente, inoltre, di assegnare valori reali per i pesi degli archi
dei grafi. È possibile pertanto poter calcolare i cammini minimi (Algoritmo di
Dijkstra) a partire da un vertice sorgente ad un vertice destinazione prefissati.
Si può scegliere di calcolare tali cammini considerando il grafo come pesato o
non pesato (in questo ultimo caso il peso di un cammino è dato dal numero
di archi da cui è composto).
Segue, in questo capitolo, la descrizione dell’algoritmo di Dijkstra e delle
misure di Centralità supportate da Graphtool.
23
3.1 Dijkstra Shortest Path
3.1
Dijkstra Shortest Path
Si supponga di considerare un grafo G = (V, E) i cui pesi degli archi
siano tutti non negativi, ossia valga w(u, v) ≥ 0 per ogni arco (u, v) ∈ E.
Si supponga, dunque, di voler calcolare il camminino minimo a partire da
un vertice sorgente singolo prefissato, che indicheremo con s. Per un vertice
u indichiamo con d[u] la stima del costo del cammino minimo da s ad u
correntemente aggiornata. Indichiamo, inoltre, il predecessore di u con π[u].
L’algoritmo di Dijkstra costruisce un insieme, che indicheremo con S,
contenente tutti i vertici il cui peso di cammino minimo dalla sorgente è stato
determinato, ossia tutti i vertici v ∈ S per cui d[v] = δ(s, v). L’algoritmo
seleziona, ad ogni passo, il vertice u ∈ V − s avente la stima di cammino
minimo, inserisce u in S ed esegue l’operazione di rilassamento di tutti gli
archi uscenti u [21]. Tale operazione, per un generico arco (u, v) consiste nel
valutare se è possibile migliorare il cammino minimo per v trovato fino a quel
momento con un nuovo cammino passante per u. In un secondo momento
aggiorna la stima di cammino minimo ed imposta, eventualmente, il nuovo
predecessore di v. In Algoritmo 1 è mostrata la procedura di rilassamento
di un arco, mentre in Algoritmo 2 è mostrato l’algoritmo per la ricerca dei
cammini minimi.
RELAX(u,v,w)
1: if d[v] > d[u] + w(u, w) then
2:
d[v] ← d[u] + w(u, v)
3:
π[v] ← u
4: end if
Algoritmo 1: Rilassamento di un arco
24
3.2 Misure di Centralità
25
DIKJKSTRA(G,w,s)
1: Per ogni vertice v ∈ V imposta d[v] ← ∞ e π[v] ←NIL
2: d[s] ← 0
3: S ← ∅
4: Q ← V
5: while Q 6= ∅ do
6:
u ← elemento con valore minimo da Q
7:
S ← S ∪ {u}
8:
for ogni vertice v ∈ V do
9:
RELAX(u, v, w)
10:
end for
11: end while
Algoritmo 2: Algoritmo di Dijkstra
3.2
Misure di Centralità
Come già ampiamente anticipato, dato un grafo è possibile definire una
misura della centralità dei nodi (ma anche degli archi) che la costituiscono.
Una misura della centralità, intuitivamente, dà informazioni su quanto un
nodo della rete sia più centrale, ossia più importante, rispetto ad un altro
[22, 23, 24]. Esistono molteplici misure di centralità e Graphtool ne supporta
svariate: un nodo quindi, può risultare più o meno centrale a seconda della
misura di centralità adottata.
3.2.1
Degree Centrality
La Degree Centrality è una misura di centralità basata sul grado (entrante
o uscente) dei nodi di un grafo. Sia G = (V, E) un grafo con n vertici e sia
deg(v) il grado del vertice v. Allora la Degree Centrality CD (v) è definita
come
CD (v) =
deg(v)
n−1
(3.1)
A seconda che si considerino solo archi entranti od uscenti si potrà definire
3.2 Misure di Centralità
26
rispettivamente la InDegree e OutDegree Centrality. Si noti come questa
misura di centralità dia solo una misurazione locale in quanto, per ciascun
nodo è definita solo in funzione dei nodi immediatamente adiacenti.
La Degree Centrality può essere di grande utilità quando si analizza una
rete sociale in cui gli archi rappresentano relazioni sociali tra individui. Ad
esempio, si supponga di considerare una rete sociale i cui nodi rappresentano
studenti di un corso di laurea che vogliono eleggere il loro rappresentante e
gli archi rappresentano chi ha votato chi (Figura 3.1). Appare evidente in
questo contesto che uno studente è più importante, e quindi più centrale di
un altro, se avrà ricevuto un maggior numero di voti (determinati dal numero
di archi entranti per nodo). In questo caso la misura di centralità che mette
in evidenza questa importanza è proprio la Indegree Centrality.
A
A vota lo studente C
C
B
B vota lo studente C
Figura 3.1: Esempio di Indegree Centrality: gli studenti A e B di un corso
di laurea votano entrambi per lo studente C quale loro rappresentante. In
questo caso lo studente C è il più centrale.
3.2.2
Node/Edge Betweenness
Sia
δst (v) =
σst (v)
σst
dove σst è il numero di cammini minimi tra il nodo s e t mentre σst (v)
rappresenta il numero di cammini minimi tra il nodo s e t passanti per
3.2 Misure di Centralità
27
v. Possiamo asserire che δst rappresenti la probabilità che il nodo v sia
coinvolto in una comunicazione tra s e t. Allora la misura di centralità detta
Betweenness è definita come
CB (v) =
X X
δst (v)
(3.2)
s6=v∈V t6=v∈V
Analogamente alla Betweenees dei nodi di un grafo è possibile fornire
un’analoga misura di centralità in funzione degli archi.
La Betweenness Centrality può essere utile, nell’ambito delle reti sociali,
per la misurazione del potere di controllo del flusso della conoscenza. In tale
contesto, generalmente, i nodi con un’alta Betweenness Centrality sono definiti brokers. Un broker può essere un membro di una rete sociale tramite
il quale avviene la comunicazione tra gli altri nodi (in questo caso è detto
coordinator ), un membro che ottiene dall’esterno il flusso di conoscenza e
lo trasferisce ad un gruppo (gatekeeper ), un membro che trasferisce la conoscenza tra membri dello stesso gruppo a cui esso tuttavia, non appartiene
(itinerant) o, infine, un membro che trasferisce la conoscenza tra distinti
gruppi della rete sociale (liason). In tutti questi casi il broker ha una funzione importante all’interno della rete sociale. Tale importanza viene messa in
evidenza da valori di Betweenness Centrality più alti.
3.2.3
Sia
Closeness
P
v∈V
d(u, v) la somma delle distanze da un vertice u ∈ V ad ogni
altro. Allora la Closeness Centrality è definita come
1
v∈V d(u, v)
CD (u) = P
(3.3)
3.2 Misure di Centralità
28
Tale funzione cresce se la distanza totale di u decresce. In Figura 3.2 è mostrato un esempio. La Closeness Centrality può risultare molto utile quando
si vuole determinare il nodo che minimizza la distanza totale da tutti gli altri.
Un esempio pratico consiste nel ricercare la posizione ottimale di un centro
commerciale in una città (rappresentata adeguatamente da un grafo). Una
buona posizione potrebbe essere quella che minimizza la distanza del centro
commerciale da tutti i clienti in modo da ottimizzare lo spostamento della
maggior parte dei clienti.
Figura 3.2: Esempio di Closeness Centrality: in questo caso i valori
indicati rappresentano le distanze totali. In questo caso i nodi u e v sono
i più centrali.
3.2.4
Barycenter
Sia p ∈ V , un vertice di un grafo. Allora la Baricenter Centrality è
definita come
Ucenter (p) =
X
kpu − pv k2
(3.4)
(u,v)∈E
Con questa misura di centralità viene assegnata una importanza ad un vertice
in funzione della somma delle distanze del nodo da tutti gli altri [25].
3.2 Misure di Centralità
3.2.5
29
Page Rank
L’algoritmo Page Rank [26] è ampiamente utilizzato nel World Wide Web
nell’ambito della classificazione delle pagine web in relazione alla loro importanza: essa è tipicamente determinata dalla quantità di collegamenti ipertestuali presenti nella pagina e a quanto importanti sono le pagine web linkate.
In questo caso le pagine web rappresentano i nodi di un grafo mentre i link
tra le pagine rappresentano gli archi. Tale algoritmo è utilizzato su larga
scala da alcuni tra i principali motori di ricerca disponibili sul web. Si supponga di voler calcolare l’algoritmo di Page Rank su un nodo p (una pagina
web). Indichiamo con Pp l’insieme dei nodi raggiungibili a partire da p e sia d
un fattore di smorzamento (dumping factory). Allora la misura di centralità
indotta da Page Rank per un nodo p è definita come
CP R (p) = d
X CP R (q)
+ (1 − d)
d+ q
−
(3.5)
q∈Pp
La misura della centralità basata su Page Rank si inserisce nel generico di
concetto di Web Centralities, ossia di centralità orientate al Web. Anche le
misure di centralità presentate di seguito (Hub e Authority) appartengono a
tale categoria.
3.2.6
Authority & Hub
Nell’ambito del World Wide Web possiamo definire come Authority una
pagina web autorevole, ossia una pagina web che contiene informazioni rilevanti e precise sull’argomento desiderato e, quindi, linkata da parecchie altre
pagine web. Possiamo altresì definire come Hub, una pagina web contenente molti collegamenti verso pagine web autorevoli, ossia verso Authorities.
Come descritto da Kleinberg [27, 28] un buon hub è, dunque, una pagina
3.2 Misure di Centralità
web che punta a molte buone autorithies e, viceversa, una buona autorithy
è una pagina web che punta a molti buoni hub: appare dunque evidente che
i due concetti sono strettamente correlati l’uno con l’altro. L’algoritmo per
il calcolo dell’hub e dell’autority è stato proposto da Kleinberg e consta di
due fasi: la prima fase consiste nella ricerca delle pagine web, a partire da
una query definita dall’utente: questa fase, nel nostro caso, non interessa in
quanto vogliamo effettuare il calcolo su una network prestabilita e già caricata nello spazio di lavoro di Graphtool. La seconda fase consiste nel vero e
proprio calcolo dei valori hub e autorithy. Sia, dunque, G un grafo e siano
cHA−H = AcHA−A con cHA−A noto e cHA−A = AcHA−H con cHA−H noto,
rispettivamente i valori di hub ed autority, dove A è la matrice d’adiacenza
del grafo G: l’algoritmo per il calcolo di tali valori restituisce le approssimazioni di cHA−H e cHA−A . Si veda a tal proposito 3 per un’implementazione
dell’algoritmo per il calcolo delle approssimazioni dell’hub e dell’authority.
Output: : approssimazioni di cHA−A e cHA−H
1: c0HA−A ← 1n
2: for k = 1 . . . do
k−1
3:
ckHA−H ← AcHA−A
4:
ckHA−A ← AckHA−C
5:
ckHA−H ←
ckHA−A ←
7: end for
6:
ckHA−H
kckHA−H k
ckHA−A
kckHA−A k
Algoritmo 3: Calcolo dell’Hub e dell’Authority
30
Capitolo 4
Subgraph matching
In questo capitolo verrà presentata un’altra funzionalità di Graphtool
che permette di ricercare tutte le occorrenze di sottostrutture G1 (indicato
anche come grafo query) all’interno di un grafo G2 (indicato anche come grafo target) (Figura 4.1). Questo problema noto come subgraph matching è
un problema NP-Completo [29] per cui non esistono soluzioni polinomiali.
Nonostante ciò, esistono diversi algoritmi che risultano particolarmente efficienti anche su grandi grafi. Il metodo implementato su Graphtool si basa
sull’algoritmo VF2 [1].
1
2
4
5
3
(a)
6
7
(b)
Figura 4.1: Subgraph Matching. (a) Grafo query. (b) Grafo target.
31
4.1 Algoritmo di ricerca
4.1
32
Algoritmo di ricerca
L’algoritmo di ricerca implementato in Graphtool è descritto in [1] e fornisce una soluzione più efficiente rispetto ad altri algoritmi per la ricerca
delle sottostrutture in grafi [30]. L’algoritmo è applicabile ad ogni tipo di
grafo, è particolarmente adatto a grafi con etichette o attributi, utilizza una
rappresentazione nello spazio degli stati con una strategia di ricerca depthfirst (in profondità) ed ha cinque regole di fattibilità (feasibility rules) che
permettono di ridurre lo spazio degli stati.
Il matching tra due grafi G1 = (V1 , E1 ) e G2 = (V2 , E2 ) consiste nel determinare una mappatura M che associa nodi di G1 a nodi di G2 e viceversa,
tenendo conto di alcune costanti predefinite. Una mappatura M è un insieme
di coppie (n, m) con n ∈ G1 e m ∈ G2 . Definiamo, inoltre, l’insieme M(s),
come un sottoinsieme di M che identifica univocamente due sottografi di G1
e G2 , rispettivamente indicati come G1 (s) e G2 (s) tale da rappresentare il
matching parziale dello stato s ossia l’insieme corrente delle coppie di nodi
dei due grafi che sono corrispondenti.
Una transizione da uno stato s ad uno stato successore s′ consiste nell’aggiunta nello spazio degli stati di una coppia di nodi (n, m). Otteremo,
dunque, un nuovo insieme
M(s′ ) = M(s) ∪ (n, m) con n ∈ V1 e m ∈ V2
(4.1)
Per stabilire se una coppia (n, m) da aggiungere allo stato s produce
uno stato inconsistente o meno si utilizza un’apposita funzione di fattibilità
F (s, n, m) che ha lo scopo di filtrare più strade possibili per cercare di arrivare più velocemente alla soluzione. A tal scopo si costruisce un insieme
P (s) delle coppie candidate. La scelta delle coppie da inserire in P (s) sfrutta
4.2 Opzioni di ricerca
i cosidetti terminal sets, indicati rispettivamente con T1 e T2 , che contengono i nodi direttamente connessi a quelli già inseriti nel mapping parziale e
che provengono da V1 e V2 . Le coppie vengono scelte in modo da assicurare che l’eventuale inconsistenza venga riconosciuta quanto più velocemente
possibile.
L’algoritmo VF2 è descritto in Algoritmo 4, mentre in Figura 4.2 sono
schematizzati i suoi passi fondamentali.
MATCH(s)
Input: uno stato intermedio s. Lo stato iniziale è s0 ha M(s0 ) = ∅
Output: la mappatura tra due grafi
1: if M(s) copre tutti i nodi di G2 then
2:
mostra M(S)
3: else
4:
calcola l’insieme P (s) delle coppie candidate per l’inclusione in M(s)
5:
foreach p ∈ M(s) do
6:
if p è una fattibile coppia then
7:
calcola lo stato s′ ottenuto aggiungendo p a M(s)
8:
MATCH(s′ )
9:
end if
10:
end for
11:
aggiorna le strutture dati
12: end if
Algoritmo 4: Algoritmo di matching VF2
4.2
Opzioni di ricerca
L’agortimo VF2 è stato adattato in Graphtool in modo da supportare
ricerche esatte e approssimate. Nel primo caso è data all’utente la possibilità
di impostare le etichette dei vertici e degli archi della query (Figura 4.3(a)),
nel secondo caso (impostazione predefinita nel caso in cui l’utente disegna il
grafo query) è data la possibilità di impostare vertici ed archi non etichettati
33
4.2 Opzioni di ricerca
34
Y
TERMINA
M(s) copre tutti i nodi?
N
Calcola l’insieme P di tutte le coppie
da poter accoppiare
S’ = NEW STATE (M+p)
FOREACH p E P
N
Y
IF (M+p) è feasible set of mapping
Figura 4.2: Passi dell’algoritmo VF2.
(Figura 4.3(b)) che in questo caso possono essere accoppiati a qualunque nodo
del grafo target. Sono inoltre supportate le ricerche con nodi con self-loops
(Figura 4.4(a)) e con archi multipli (Figura 4.4(b)).
A
B
?
C
(a)
?
C
(b)
Figura 4.3: Tipi di Query. (a) Query esatta. (b) Query approssimata.
Una vota selezionati il grafo query ed il grafo target, l’utente può eseguire
l’algoritmo di matching. Al termine dell’esecuzione della ricerca saranno
4.3 Network Motifs
label
(a)
35
label1
label2
(b)
Figura 4.4: Caratteristiche delle query. (a) Self-loop. (b) Archi multipli
(multiple edges).
mostrati il numero di occorrenze trovate e l’elenco dei match rilevati (si veda
la Figura 4.5).
L’algoritmo di matching si occupa anche di mostrare il numero totale di
match trovati ed il numero di match distinti. Il motivo di questa distinzione
sta nel fatto che, data una query di partenza, possono essere restituiti in
output sottografi equivalenti (che rappresentano quindi, in buona sostanza,
la stessa struttura), ma che sono stati accoppiati in modo diverso. Affinché
due match risultino distinti, essi devono essere diversi in almeno un nodo.
4.3
Network Motifs
Graphtool permette anche di disegnare alcune query predefinite tipicamente importanti in alcuni contesti come quello delle network biologiche
[31]. È molto frequente, ad esempio, che le reti di trascrizione che regolano le
risposte delle cellule obbediscano ad alcuni principi che ricorrono più volte,
identici, all’interno della stessa rete. Uno tra i modelli più comuni e frequenti
è certamente il cosiddetto feed-forward loop: esso è un modello a tre geni
costituito da due fattori di trascrizione di input (uno dei quali regola l’altro)
ed un gene su cui effettuare la trascrizione. In Figura 4.6 è mostrata una
schematizzazione del feed-forward loop [32]. Altri motifs predefiniti sono resi
4.3 Network Motifs
36
(a)
(b)
Figura 4.5: Esecuzione di una ricerca. (a) Selezione della query e del rete
target su cui cercare tutte le occorrenze. L’utente può decidere se nella
ricerca si deve tenere conto anche delle etichette dei vertici e degli archi
(labeled) e se si deve tenere conto delle direzioni degli archi (directed).
(b) Log e tabella con i risultati: sono mostrati il numero di match totali e
distinti trovati e nella tabella è fornito l’elenco completo dei match distinti
con indicatore del numero di match, numero di occorrenze per singolo
match e nodi coinvolti.
disponibili in Graphtool come ad esempio i motifs Bi-Fan (Figura 4.7(a)) e
Bi-Parallel (Figura 4.7(b)), spesso ricorrenti nell’ambito delle reti neuronali
e i motifs Fully connected triad (Figura 4.7(c))e Uplinked mutual dyad (Figura 4.7(d)), quest’ultimi di fondamentale rilevanza nel contesto del World
Wide Web.
X
Y
Z
Figura 4.6: Feed-forward loop.
4.4 Motif Verification
37
X
X
Y
Z
Y
W
Z
W
(a)
(b)
X
X
Z
Y
(c)
Z
Y
(d)
Figura 4.7: Motifs. (a) Bi-fan. (b) Bi-parallel. (c) Fully connected triad.
(d) Uplinked mutual dyad.
4.4
Motif Verification
L’algoritmo di matching offre anche la possibilità di verificare se i match
trovati in una network siano statisticamente significativi (e non ottenuti per
caso) e fornisce in tal senso una serie di indici calcolati opportunamente. In
particolar modo, questa funzionalità permette di generare automaticamente
una serie di network randomizzate che hanno caratteristiche simili al grafo
target, sia in termini di numero di nodi e di archi, che in termini di grado dei
vertici. Di default la verifica viene effettuata su 100 network randomizzate
generate casualmente effettuando uno switch (scanbiando gli archi) sugli archi
della network. Per ciascuna delle network generate casualmente vengono
calcolate le occorrenze del grafo query calcolando E − value e Z − score:
E − value =
randomnewtorkhavingoccurrences ≥ nreal
numberof randomnetworks
(4.2)
4.5 Un esempio completo
Z − score =
4.5
occurrencesreal − occurrencesrandom
sdrand
38
(4.3)
Un esempio completo
Figura 4.8: Query d’esempio.
Mostriamo infine un esempio completo di esecuzione dell’algoritmo di
matching in Graphtool. Si supponga di voler trovare tutte le occorrenze
del grafo mostrato in Figura 4.8 nel grafo galFiltered.sif1 mostrato in
Figura 4.9.
La ricerca, in questo esempio, viene effettuata senza tenere conto delle
etichette dei nodi e degli archi.
La query restituisce 22 match esatti (l’output è mostrato in Figura 4.5(b)).
Al termine dell’esecuzione della ricerca l’utente potrà selezionare un match
in corrispondenza della tabella dei risultati e i nodi coinvolti saranno opportunamente evidenziati sul grafo target (Figura 4.10). L’utente può anche
1
Il grafo d’esempio rappresenta una rete d’interazione molecolare tra 331 geni.
4.5 Un esempio completo
Figura 4.9: Target d’esempio.
Figura 4.10: Selezione di un match.
decidere di visualizzare il singolo match come nuovo grafo ed eventualmente
salvarlo.
Se si vuole, infine, eseguire la Motif Verification è sufficiente selezionare i
valori switch/edges ed il numero di network randomizzate che si vuole venga-
39
4.5 Un esempio completo
Figura 4.11: Motif Verification.
no generate: il risultato dettagliato sarà mostrato nel log ed in un’apposita
finestra di dialogo (Figura 4.11).
40
Capitolo 5
Conclusioni
In questa tesi è stato affrontato il problema della realizzazione di un tool
efficiente per la visualizzazione e l’analisi di grafi anche di grandi dimensioni.
Lo scopo principale del tool realizzato è stato quello di avere a dispozione
una piattaforma software aperta in grado di visualizzare grafi anche di grandi
dimensioni e di implementare e testare nuovi algoritmi.
Graphtool implementa alcuni tra i più importanti standard per la rappresentazione di grafi come ad esempio i formati RDF, nelle varie notazioni
usate per la sua rappresentazione (RDF/XML, Notation 3, N-Triples, TriX,
Turtle e TriG), SIF, GML e XGMML. Esso permette inoltre di calcolare svariate misure di Centralità e applicare l’algoritmo VF2 per il matching di grafi
opportunamente modificato per trattare anche match approssimati.
Il tool realizzato è particolarmente adatto per l’analisi di reti biologiche e sociali che negli ultimi anni stanno diventanto sempre di maggiore
importanza nei rispettivi settori di ricerca.
41
Appendice
Note implementative
Per l’implementazione di Graphtool si è scelto di utilizzare un linguaggio
molto potente ed elegante come Java. La scelta è stata quasi ovvia in quanto
le potenzialità offerte dal paradigma della programmazione ad oggetti, rese
disponibili dal linguaggio Java, si sposavano egregiamente con le esigenze del
tool che si voleva sviluppare. Java mette a disposizione una serie di utilissime
API che rendono particolarmente agevole ed efficiente l’implementazione di
taluni algoritmi descritti in questa tesi. Sfruttando, altresì, le potenzialità di
ulteriori librerie Java open source, liberamente accessibili in rete, il risultato
è stato eccezionale. Le librerie utilizzate, oltre quelle standard di Java, sono
state le seguenti:
• JUNG (v.2.0.1): l’ultima versione delle popolari librerie Java Universal
Network/Graph Framework. Utilissime in quanto mettono a disposizione una serie di funzioni per la costruzione delle strutture di tipo grafo,
per la loro visualizzazione e per l’innumerevole quantità di algoritmi
che è possibile eseguire.
• Common-Collections (v.4.01): librerie che forniscono una serie di interfacce utili nell’uso di JUNG per la creazione delle strutture dati.
42
Appendice
• Colt (v.1.2.0): ottime librerie Java per operazioni numeriche. Sviluppate presso il CERN, sono state utili in alcuni casi, in particolar modo
per la scrittura del parser GML.
• Xerces Java Parser (v.1.4.4): eccellente parser XML per Java, utilissimo
per il parsing dei file XGMML.
• Sesame (v.2.3.1): note anche come openRDF, forniscono una serie di
funzioni per il parsing dei file RDF.
Nell’implementazione, coerentemente con i principi imposti dal paradigma
della programmazione ad oggetti, si è prestata attenzione alla suddivisione
in classi e packages: in particolar modo sono stati opportunamente suddivisi i compiti relativi alla gestione dell’interfaccia grafica e dei vari pannelli,
della gestione della lettura/scrittura dei vari formati supportati, della struttura dati implementata per la gestione dei grafi e, infine, delle funzionalità
di ricerca. Le operazioni relative al caricamento/salvataggio dei file, esecuzione degli algoritmi e delle ricerche sono state implementate in modo tale
che venissero eseguite in thread separati. Poiché l’interfaccia grafica è implementata mediante le librerie Swing di Java e poiché tali librerie è noto che
non siano thread-safe si è tenuto conto anche di ciò per evitare problemi di
visualizzazione dovuti all’aggiornamento della GUI in fase di esecuzione dei
thread [33].
43
Bibliografia
[1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A
(Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE
Trans. Pattern Anal. Mach. Intell., 26(10):1367–1372, 2004.
[2] J. Madadhain, D. Fisher, P. Smyth, S. White, and Y. B. Boey. Analysis
and visualization of network data using JUNG. Journal of Statistical
Software, 10:1–35, 2005.
[3] Paul Shannon, Andrew Markiel, Owen Ozier, Nitin S. Baliga, Jonathan T. Wang, Daniel Ramage, Nada Amin, Benno Schwikowski,
and Trey Ideker.
Cytoscape: A Software Environment for Integra-
ted Models of Biomolecular Interaction Networks. Genome Research,
13(11):2498–2504, November 2003.
[4] Michael Himsolt. GML: A portable Graph File Format. http://www.
infosun.fim.uni-passau.de/Graphlet/GML/gml-tr.html, 1997.
[5] XGMML 1.0 Draft Specification. http://www.cs.rpi.edu/~puninj/
XGMML/draft-xgmml.html, June 2001.
[6] World Wide Web Consortium.
Resource Description Framework
(RDF) Model and Syntax Specification. http://www.w3.org/TR/1999/
REC-rdf-syntax-19990222/, February 1999.
44
Appendice
45
[7] Eric Miller. An Introduction to the Resource Description Framework.
D-Lib Magazine, May 1998.
[8] World Wide Web Consortium. RDF Primer. http://www.w3.org/TR/
rdf-primer/, February 2004.
[9] Tim Berners-Lee, R. Fielding, and L. Masinter.
Uniform Resource
Identifier (URI): Generic Syntax. RFC 3986 (Standard), January 2005.
[10] World Wide Web Consortium.
Resource Description Framework
(RDF): Concepts and Abstract Syntax. http://www.w3.org/TR/2004/
REC-rdf-concepts-20040210/, February 2004.
[11] World
pes
Wide
in
RDF
Web
and
Consortium.
OWL.
XML
Schema
Dataty-
http://www.w3.org/TR/2006/
NOTE-swbp-xsch-datatypes-20060314/, March 2006.
[12] A. Phillips and M. Davis. Tags for Identifying Languages. RFC 5646
(Best Current Practice), September 2009.
[13] World
Wide
Specification
Web
Consortium.
(Revised).
RDF/XML
Syntax
http://www.w3.org/TR/2004/
REC-rdf-syntax-grammar-20040210/, February 2004.
[14] Dave Beckett. New Syntaxes for RDF. http://www.dajobe.org/2003/
11/new-syntaxes-rdf/paper.html, November 2003.
[15] World Wide Web Consortium. N-Triples. http://www.w3.org/2001/
sw/RDFCore/ntriples/, 2001.
[16] World Wide Web Consortium. Notation3 (N3): A readable RDF Syntax.
http://www.w3.org/DesignIssues/Notation3, March 2006.
Appendice
46
[17] World Wide Web Consortium. Primer: Getting into RDF & Semantic Web using N3. http://www.w3.org/2000/10/swap/Primer.html,
October 2000.
[18] Dave Beckett and Tim Berners-Lee.
Language.
Turtle - Terse RDF Triple
http://www.w3.org/TeamSubmission/turtle/, January
2008.
[19] Jeremy J. Carroll and Patrick Stickler. TriX : RDF Triples in XML.
http://www.hpl.hp.com/techreports/2004/HPL-2004-56.pdf, May
2004.
[20] Chris Bizer and Richard Cyganiak. The TriG Syntax. http://www4.
wiwiss.fu-berlin.de/bizer/TriG/.
[21] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford
Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3
edition, September 2009.
[22] Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, and Oliver Zlotowski. Centrality Indices.
In Brandes and Erlebach [23], pages 16–61.
[23] Ulrik Brandes and Thomas Erlebach, editors. Network Analysis: Methodological Foundations [outcome of a Dagstuhl seminar, 13-16 April
2004], volume 3418 of Lecture Notes in Computer Science. Springer,
2005.
[24] Stanley Wasserman and Katherine Faust. Social network analysis : methods and applications. Structural analysis in the social sciences, 8.
Cambridge University Press, 1 edition, November 1994.
Bibliografia
47
[25] Ulrik Brandes. Drawing on Physical Analogies. In Michael Kaufmann
and Dorothea Wagner, editors, Drawing Graphs, volume 2025 of Lecture
Notes in Computer Science, pages 71–86. Springer, 1999.
[26] Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. In Computer Networks and ISDN Systems,
pages 107–117, 1998.
[27] Jon M. Kleinberg. Authoritative Sources in a Hyperlinked Environment.
Journal of the ACM, 46:668–677, 1999.
[28] Jon M. Kleinberg. Hubs, authorities, and communities. ACM Comput.
Surv., page 5.
[29] Michael R. Garey and David S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness (Series of Books in the
Mathematical Sciences). W. H. Freeman, January 1979.
[30] J. R. Ullmann. An Algorithm for Subgraph Isomorphism. J. ACM,
23(1):31–42, January 1976.
[31] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and
U. Alon. Network motifs: Simple building blocks of complex networks.
Science, 298(5594):824–827, October 2002.
[32] S. Mangan and U. Alon. Structure and function of the feed-forward loop
network motif. Proceedings of the National Academy of Sciences of the
United States of America, 100(21):11980–11985, October 2003.
[33] H. M. Deitel and J. M. Deitel.
Java. Tecniche avanzate di
programmaizone. Apogeo, 3 edition, 2006.
Indice analitico
G
A
Arco incidente . . . . . . . . . . . . . . . . . . . 2 Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Authority . . . . . . . . . . . . . . . . . . . . . . . 29 Graph Modelling Language . . . . . 10
H
B
Barycenter . . . . . . . . . . . . . . . . . . . . . . 28 Hub . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Blank node . . . . . . . . . . . . . . . . . . . . . 16
I
Indegree . . . . . . . . . . . . . . . . . . . . . . . . . 2
C
Centrality . . . . . . . . . . . . . . . . . . . . . . 25 J
Closeness . . . . . . . . . . . . . . . . . . . . . . . 27 JUNG . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Colt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
L
Common-Collections . . . . . . . . . . . . 42
Language . . . . . . . . . . . . . . . . . . . . . . . 15
D
Literal . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Datatype . . . . . . . . . . . . . . . . . . . . . . . 15
Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Degree Centrality . . . . . . . . . . . . . . . 25
Dijkstra Shortest Path . . . . . . . . . . 24
M
Matrice d’adiacenza . . . . . . . . . . . . . . 2
Motif Verification . . . . . . . . . . . . . . . 37
N
E
E-value . . . . . . . . . . . . . . . . . . . . . . . . . 37
N-Triples . . . . . . . . . . . . . . . . . . . . . . . 17
Node Betwenness . . . . . . . . . . . . . . . 26
Notation 3 . . . . . . . . . . . . . . . . . . . . . . 17
F
Feed-forward loop . . . . . . . . . . . . . . . 35
O
48
Bibliografia
49
Object . . . . . . . . . . . . . . . . . . . . . . . . . . 14 VF2 Algorithm . . . . . . . . . . . . . . . . . 32
Outdegree . . . . . . . . . . . . . . . . . . . . . . . 2
P
X
Xerces . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Page Rank . . . . . . . . . . . . . . . . . . . . . . 29 XGMML . . . . . . . . . . . . . . . . . . . . . . . 12
Peso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 XML . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Predicate . . . . . . . . . . . . . . . . . . . . . . . 14
Q
Query approssimata . . . . . . . . . . . . 33
Query esatta . . . . . . . . . . . . . . . . . . . . 33
R
RDF/XML . . . . . . . . . . . . . . . . . . . . . 16
Relax . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Resource Description Framework 12
S
Sesame . . . . . . . . . . . . . . . . . . . . . . . . . 43
Simple Interaction Format . . . . . . . 8
Statement . . . . . . . . . . . . . . . . . . . . . . 14
Subgraph Matching . . . . . . . . . . . . . 31
Subject . . . . . . . . . . . . . . . . . . . . . . . . . 14
T
TriX . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
U
URI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
V
Z
Z-score . . . . . . . . . . . . . . . . . . . . . . . . . 38