Fabio RinnoneMatricola 667/001087

Università di CataniaFacoltà di SS. MM. FF. NN.

Dipartimento di Matematica e InformaticaCorso di Laurea di Primo Livello in Informatica

Relatore: Prof.ssa GiugnoCorrelatore: Dott. Pigola

Un tool per la visualizzazionee l'analisi direti biologiche e sociali

Graphtool

Visualizzazione ed analisi di retiReti Sociali

Reti Biologiche

Resource Description FrameworkSviluppato in linguaggio Java

Portabilità

Estendibilità

JUNGJava Universal Network/Graph Framework

Interfaccia utente

Resource Description Framework

Standard proposto da W3CDescrizione/modellazione di risorse disponibili nel WebRisorse identificate tramite URI

StatementsTriple subject predicate objectLiteralsURIBlank Nodes

Resource Description Framework

Sintassi per RDF

RDF/XMLNotazione basata su XMLBlank Node IdentifierTyped Literals/Plain Literals

Notation3Notazione testualeFormato compatto e leggibileMaggiore espressività rispetto a RDF/XML

Altre notazioniN-TriplesTurtleTriGTriX

Centralità: esempio

Classe di 30 studenti che devono eleggere il proprio rappresentante

Si costruisce la rete che rappresenta i risultati delle votazioni

Uno studente è più centrale se più studenti lo hanno votatoMisura dipendente dal numero di archi entranti

Indegree centrality

Degree Centrality

Misura calcolata in funzione del grado (degree) di un vertice

Inoutdegree

Indegree

Outdegree

Usata per network statistiche

Misura locale

Dipende solo dai nodi vicini

Closeness Centrality

Trovare la posizione ottimale per un centro commercialeMinimizzare la distanza totale dai clientiOttimizzazione dello spostamento dei clienti

Trovare i vertici con minima distanza totale

Centralità

Betwenness Centrality

Barycenter

Centralità orientate al Web

Page Rank

Hub & Authority

Subgraph Matching

Ricerca di sottostrutture all'interno di un grafo

Problema NP-Completo

Algoritmo VF2 modificato

query target

Proprietà delle Query

Self-loops

Archi multipli

Network labeled/not labeled

Network directed/not directed

Tipi di Query

Query esatte

Query approssimate

NODO

ARCO

LABELED

UNLABELED

Motifs

Feed-Forward Loop

Match totali e distinti

Due match sono distinti se sono diversi in almeno un nodo

query target

match 1match 1match 2match 2

Trovati 2 match totali

Trovati 1 match distinto

Match statisticamente significativiMatch statisticamente significativi

Motif verification

È possibile generare reti casuali con le stesse caratteristiche della rete input

Numero di vertici

Numero di archi

Grado dei vertici

Scambio degli archiDefault: 100 switch/edge

Generazione di network casualiDefault: 100 network

Calcolo del numero di occorrenze della query in ogni networkCalcolo di alcuni indici statistici

E-Value/Z-Score

Ringrazamenti

Prof.ssa Giugno

Dott. Pigola

La mia famiglia

I miei amici