Capitolo 3 RETI COME GRAFI

3.1 Introduzione

In una rete neuronale, come in tutte le reti, vi è una forte relazione tra la struttura della rete e la sua funzione. Da ciò deriva la possibilità di determinare la dinamica e l’attività di una rete analizzando la sua morfologia e la topologia della connettività.

Un modo molto semplice ma efficace per far ciò è quello di modellare matematicamente la rete come un grafo.

In questa maniera è possibile applicare gli operatori matematici della teoria dei grafi per analizzare il sistema sotto indagine e trovare caratteristiche generali comuni a tutti i diversi tipi di reti interne o esterne al sistema nervoso. Infatti, ci si sta sempre più convincendo che diversi sistemi complessi mostrano la stessa architettura governata da leggi universali che valgono sia per i sistemi sociali, che per le cellule e per le reti di computers.

In questo lavoro di tesi si è seguita tale “linea” e si è cercato di comprendere quale fosse, tra i tanti possibili, il modello più adatto per rappresentare una rete neuronale in vitro.

Per far ciò si è reso necessario uno studio approfondito della teoria dei grafi e in questo capitolo verranno presentati molto brevemente alcuni concetti chiave e i differenti modelli di rappresentazione.

3.2 I grafi

3.2.1 Concetti fondamentali

Un grafo è un’entità costituita sostanzialmente da vertici o nodi ed archi o lati o spigoli. I vertici rappresentano gli elementi della rete, mentre gli archi connettono coppie di nodi e rappresentano le relazioni fra gli elementi.[1, 2, 3, 4]

Più formalmente: dati un insieme V di nodi e un insieme E di archi, un grafo G è un insieme G=(V, E).

Ogni arco e ∈ E connette due vertici u ∈ V e v ∈ V, che prendono nome di estremi dell'arco; per questo motivo spesso un arco e viene identificato con la coppia formata dai suoi estremi (u,v).

Un grafo può quindi essere pensato come un insieme di vertici V ed un insieme di coppie E, dove gli elementi di ciascuna coppia appartengono a V .

Spesso conviene rappresentare un grafo con un diagramma, dove ogni vertice è rappresentato da un punto nel piano e ciascun lato da un segmento, eventualmente curvilineo, congiungente due punti distinti (figura 3.1).

Figura 3.1 Rappresentazione di un grafo

Un arco che ha due estremi coincidenti si dice cappio, mentre più archi che connettono gli stessi due estremi danno origine ad un multiarco.

Un grafo sprovvisto di cappi e di multiarchi si dice grafo semplice. In caso contrario si parla di multigrafo.

Lo scheletro sk(G) di G è il grafo che si ottiene da G eliminandone tutti i cappi e sostituendone ogni multiarco con un solo arco avente gli stessi estremi.

Il numero di archi incidenti in un vertice v ∈ V, ovvero il numero di vertici ai quali esso è direttamente connesso (vertici adiacenti), prende nome grado di v.

Si considerano il grado massimo e il grado minimo di un grafo G come, rispettivamente, il grado del vertice di G con il maggior numero di archi incidenti e il grado del vertice di G che ha meno archi incidenti.

Quando il grado massimo ed il grado minimo coincidono con un numero k, si è in presenza di un grafo k-regolare.

Un caso estremo di grafo è un grafo costituito da un solo nodo, detto grafo nullo.

Un percorso (walk) in G è dato da una sequenza di vertici v0, v1,...,

vn, non necessariamente tutti distinti, e da una sequenza di archi che

li collegano (v0, v1), (v1, v2), ..., (vn-1, vn). I vertici v0 e vn si dicono

estremi del percorso.

Un percorso con nodi tutti distinti prende il nome di cammino o path.

Un cammino chiuso (v0 = vn) si chiama ciclo (cycle).

3.2.2 Connettività

Dato un grafo G=(V, E) due vertici v ∈ V e u ∈ V si dicono connessi se esiste un cammino con estremi v e u.

Se tale cammino non esiste, v e u sono detti sconnessi.

Un vertice isolato è un vertice che non è connesso a nessun altro vertice.

Per i = 1....k (k classi di equivalenza) sono definibili i sottografi Gi=(Vi, Ei), che prendono il nome di componenti connesse di G, la

cui cardinalità spesso si indica con γ(G). Se γ(G) = 1, G si dice connesso.

Un ponte e uno snodo sono, rispettivamente, un arco ed un vertice che, se soppressi, sconnettono il grafo.

La connettività di un grafo G = (V, E) è definita come la cardinalità dell'insieme non vuoto S ⊂ V tale che G \ S (G dal quale sono stati eliminati tutti i nodi di S) risulta sconnesso o è un nodo isolato.

Allo stesso modo, l'arcoconnettività viene definita come la cardinalità dell'insieme non vuoto A ⊂ E tale che G \ A (G dal quale sono stati eliminati tutti gli archi di A) risulta sconnesso.

I cappi risultano ininfluenti nel computo dell'arcoconnettività, mentre i multiarchi vanno contati per il numero di archi che comprendono.

3.2.3 Grafi orientati e non orientati

Si distinguono due tipi basilari di grafi, i grafi orientati e i grafi non orientati.

Un grafo orientato D, detto anche digrafo o grafo diretto, è un insieme D=(V,A), dove V è l'insieme dei vertici di D e A è l'insieme degli archi orientati di D. Un arco orientato è un arco caratterizzato da una direzione. In particolare, è composto da una testa, rappresentata solitamente dalla punta di una freccia, che si dice raggiunge un vertice in entrata, e una coda, che lascia un vertice in uscita.

Un grafo non orientato D è un'insieme di vertici e archi dove la connessione i - j ha lo stesso significato della connessione j - i.

Figura 3.2Tipi di grafo: a) non orientato, b) orientato

3.2.4 Rappresentazione dei grafi

Ci sono due modi generali per rappresentare un grafo con una struttura di dati utilizzabile da un programma: la lista delle adiacenze e la matrice delle adiacenze.

In una lista di adiacenze, una lista mantiene un elenco di nodi, ed ad ogni nodo è collegata una lista di puntatori ai nodi collegati da un arco.

La matrice delle adiacenze è una matrice binaria quadrata di dimensione N, dove N è il numero dei nodi, che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto (i,j) della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice i al vertice j, altrimenti si trova uno 0.

E’ facile intuire che, nel caso di grafo non orientato, la matrice delle adiacenze è simmetrica, mentre nel caso di grafo orientato non è più simmetrica in quanto viene messo 1 solo dove l’ arco è percorribile. Se al posto degli 1 nella matrice si trovano dei numeri, questi indicano con quanti archi i due nodi sono connessi.

Ognuna delle due rappresentazioni ha alcuni vantaggi: una lista di adiacenze risulta più adatta a rappresentare grafi con pochi archi, perciò è facile trovare tutti i nodi adiacenti ad un nodo dato e verificare l'esistenza di connessioni tra nodi; una matrice di adiacenze è invece più indicata per descrivere grafi densi e con molti archi, inoltre rende più facile invertire i grafi e individuarne sottografi.

3.2.5 Grafi e raggiungibilità

Un nodo i è raggiungibile da un nodo j se esiste un percorso da j a i. Per rappresentare con estrema semplicità la proprietà di raggiungibilità di un sistema di interesse, si costruisce la cosiddetta matrice di raggiungibilità o di connessione.

La matrice di raggiungibilità è una matrice quadrata di dimensione pari al numero dei nodi (N), il cui generico elemento rij=1 se esiste almeno un percorso, senza condizioni sulla sua lunghezza, da i a j, altrimenti rij=0.

Poiché ogni punto raggiunge se stesso con sequenza nulla, rii=0. Tale matrice indica perciò i punti raggiungibili da ogni nodo i con sequenza <=N.

Nel caso di grafo non orientato rij=rji: il punto i raggiunge il punto j, ma allo stesso tempo è da esso raggiungibile.

3.3 Tipi di grafi

Le reti vengono descritte mediante i grafi per poterne capire il funzionamento e le proprietà.

1) grafi regolari; 2) grafi random; 3) small-world; 4) scale-free.

Per capire meglio i diversi modelli occorre introdurre alcuni concetti base. [5]

9 Lunghezza media di un cammino.

Si definisce distanza tra 2 nodi i e j (dij) o lunghezza del camminoil

numero di archi del più breve cammino che li connette.

Il diametro è il massimo di tutte le distanze tra ogni coppia di nodi del grafo.

La lunghezza del grafo o lunghezza media di un cammino (L) è la media delle distanze tra coppie di nodi ottenuta come media aritmetica su tutte le coppie di nodi.

E’ una misura dell’efficienza globale della comunicazione interna della rete, perché dice quanti passi in media ci vogliono per andare tra due qualsiasi punti del grafo (-passi + efficienza).

In formule:

∑

∑

−

=

d

N

N

L

)

1

(

1

9 Coefficiente di clustering del grafo.

Il coefficiente di clustering del grafo è calcolato come:

=

∑

N

C

G

C

(

)

dove Cj è il coefficiente di clustering del noto i, dato da:

=

₍

₋

₁

₎

_/

₂

_k

_k

E

C

ki sono gli archi del nodo i, che lo connettono ad altrettanti nodi.

Questi nodi sono i vicini del nodo i.

ki (ki-1)/2 è il numero massimo di archi che esistono tra i vicini del

nodo i, quando ogni vicino del nodo i è connesso ad ogni altro vicino del nodo i.

Ei rappresenta il numero effettivo di archi esistente tra i vicini del

nodo i.

Il coefficiente di clustering è una quantità che varia in [0,1] e praticamente misura la “cliquishness”, ovvero la tendenza a unirsi in gruppi, dei vicini di i.

9 Distribuzione del grado.

Non tutti i nodi hanno lo stesso grado o connettività, ossia lo stesso numero di primi vicini. Prendendo in considerazione un numero sufficiente di coppie di dati: grado del nodo (k) - numero di nodi con quel grado, è possibile ottenere il grafico della distribuzione del grado P(k).

P(k) è una funzione che fornisce la probabilità che un nodo estratto a caso abbia esattamente k connessioni.

3.3.1 Grafi regolari

Il tipo più semplice di grafo è il grafo regolare.

Rientrano in questa categoria i grafi completamente connessi e i reticoli.

In un grafo completamente connesso ogni nodo è direttamente connesso con un arco ad ogni altro nodo: vi sono N nodi e N(N–1)/2 archi.

Nel reticolo bidimensionale (lattice) ogni nodo è connesso con nodi vicini a distanza 1,2, …, K/2, con K pari. Ogni nodo ha K connessioni (figura 3.3).

Figura 3.3 Anello di N nodi e K=4 dove ogni nodo è connesso ai due

immediati vicini e ai due vicini a distanza uno

Un grafo completamente connesso rappresenta reti con C alto (prossimo all’unità) e L piccolo.

I reticoli rappresentano network con C alti, ma si ha L≈N/2<k>, perciò: L → ∞ per N→ ∞.

3.3.2 Grafi random

Il primo modello matematico diverso da un grafo regolare per la rappresentazione di network complessi sono stati i grafi random, introdotti da Erdos e Rényi. [6]

Si possono considerare esattamente come l’opposto dei grafi regolari.

Si considerano N nodi e una probabilità p: per ogni coppia di nodi si definisce un arco con probabilità p. Il numero totale di archi è circa p*N(N-1)/2.

Tali grafi si analizzano in funzione di p: si definisce una particolare proprietà del grafo, ad esempio, se il grafo è connesso, e si vuole sapere per quale valore di p la proprietà sarà verificata con alta probabilità (figura 3.4).

Figura 3.4 Evoluzione di un grafo random.

Dati 10 nodi isolati in (a), si connettono delle coppie di nodi con probabilità (b) p=0.1, (c) p=0.15 e (d) p=0.25, rispettivamente

Il grado medio <k> di un grafo random è pari a p*(N-1), mentre L è circa ln N / <k> , per cui cresce lentamente al crescere di N.

C=p=<k>/N ovvero, C → 0 per N → ∞.

Anche questi grafi sono poco realistici: non rappresentano il fatto che nella maggior parte dei network complessi il coefficiente di clustering non tende a 0.

3.3.3 Small-worlds

Partendo dal presupposto che molti network biologici, tecnologici e sociali presentano caratteristiche intermedie fra il reticolo ordinato ed il grafo random e prendendo spunto dal fenomeno dello small-world [7], D. J. Watts & S. H. Strogatz, hanno sviluppato un nuovo modello di grafi, chiamati appunto “Small-worlds”.[8, 9]

Il grafo small-world è generato come segue.

Dalla configurazione iniziale di reticolo regolare con N nodi e m link, si scorrono in maniera ordinata tutti i nodi del grafo e, per ogni nodo, si considerano tutti i link che si dipartono da esso. Con probabilità p ogni link viene tagliato dalla parte del nodo di destinazione (cioè non quello in esame) e riconnesso in maniera random ad un altro nodo (procedura di rewiring), purché ogni coppia di nodi abbia al più un link che li colleghi e nessun nodo sia direttamente collegato a se stesso (figura 3.5).

Figura 3.5 Fasi della costruzione di Small-worlds

a partire da un reticolo regolare (in alto) e con una probabilità di rewiring pari a pws =0,3 (in basso)

Lo studio dei parametri L e C è effettuato in funzione della probabilità p di rewiring, da p=0 (reticolo regolare) a p=1 (grafo random).

Per piccoli valori di p, è possibile abbassare notevolmente L(p), adeguatamente normalizzato, mantenendo quasi costante la quantità C, anch’essa normalizzata (figura 3.6).

Figura 3.6 Andamento di L e C normalizzate ai valori L(0) e C(0) del reticolo

regolare in funzione della probabilitaÁ di rewiring p. Per p=0.01 si osserva il fenomeno dello small world: il grafo ha

un valore di L simile a quello del grafo random, ma un C grande come quello del reticolo regolare.

Viene così a formalizzarsi la definizione dei grafi introdotti da W&S: gli Small Worlds sono quei grafi caratterizzati da

™ L piccolo: percorsi caratteristici corti, ovvero pochi passi per andare da un nodo a qualunque altro anche se ci sono moltissimi nodi (alta efficienza globale);

™ C grande: elevata aggregazione, ovvero alta tendenza a

formare gruppi locali molto ben connessi (alta efficienza locale). Gli small-world, come i grafi random, sono caratterizzati da una distribuzione del grado di un nodo di tipo esponenziale o, per N grande, di Poisson (figura 3.7).

Figura 3.7 Distribuzione di Poisson In formule:

( )

!

!

)

(

k

k

e

k

pN

e

k

P

₌

<

>

≈

Un tal tipo di distribuzione indica che c’è omogeneità nel numero di archi per ogni nodo e che la probabilità che un nodo abbia un grado molto più alto o molto più basso del valore medio decresce in maniera esponenziale.

Esistono moltissime reti Small-Worlds nel mondo che ci circonda: la rete neurale del Caenorhabditis elegans [10], la rete elettrica della parte occidentale degli Stati Uniti [11], il grafo delle collaborazioni di attori cinematografici sono solo alcuni di questi esempi.

3.3.4 Scale-Free

Il modello proposto da Watts e Strogatz in molti casi non riesce a riprodurre tutte le proprietà di una rete reale e si rendono necessari modelli più realistici. [12]

Laszlo Barabasi insieme al suo gruppo di collaboratori di Notre Dame University ha provato, ad esempio, che diverse reti reali sono caratterizzate dalla presenza di alcuni nodi (hubs) con un numero enorme di links rispetto alla maggior parte degli altri nodi. [13] Ha introdotto un nuovo tipo di rete detto scale-free, caratterizzata da una distribuzione del grado che segue una legge di potenza (power law) del tipo:

P )

(

k

= k

Figura 3.8 Distribuzione tipo pawer-law

Le reti con una distribuzione P(k) a legge di potenza sono state battezzate reti scale-free proprio perché sono prive di scala, in quanto contengono nodi appartenenti a tutte le possibili gerarchie di importanza.

Barábasi ed Albert hanno proposto un algoritmo per costruire un grafo scale-free che incorpora due fenomeni osservati nelle reti reali:

™ crescita del network: buona parte dei network reali evolve mediante l’aggiunta di nuovi nodi;

™ connessioni preferenziali: un nuovo nodo tende a connettersi a nodi che hanno già un alto numero di connessioni.

I due fattori devono essere contemporaneamente presenti: non basta solo uno dei due per avere network scale-free.

Esistono due metodi per la costruzione degli scale-free: uno stocastico ed uno deterministico.

Nel primo si parte con un piccolo numero (m0) di nodi e ad ogni

passo viene aggiunto un nuovo nodo con m ≤ m0 link che lo

collegano ai nodi precedentemente esistenti. [14]

La probabilità secondo cui un nuovo vertice sarà connesso al nodo i è data da:

_∏

_∑

Per mezzo di questa costruzione, ripetuta sino a raggiungere un numero di nodi sufficientemente elevato, si ottiene una distribuzione a legge di potenza P(k) ~ 2m2 ⋅ k −3, dove m è il numero di link con i quali, ad ogni passo, viene introdotto il nuovo nodo (figura 3.9).

Figura 3.9 Procedura di realizzazione di uno scale-free secondo il metodo

stocastico: situazione per t = 0, t = 2, t = 3. In figura m0 = 3, m = 2.

La procedura di realizzazione degli scale-free deterministica segue una regola gerarchica, comunemente utilizzata per la costruzione di frattali deterministici. [15]

Il network è realizzato in maniera iterativa: ad ogni passo vengono ripresi e riutilizzati gli elementi presenti al passo precedente (figura 3.10). Si parte da un singolo nodo, la radice del grafo, e ad ogni passo si triplicano gli elementi esistenti e si connettono tutti i nodi alla radice.

Figura 3.10 Procedura di realizzazione di uno scale-free in maniera

deterministica. Con questa procedura si genera una distribuzione a legge di potenza P ( k ) ~ k –γ con γ= ln 2 / ln 3 . Il numero medio di connessioni al

passo n, con n sufficientemente grande, sarà <k>=4n/3.

Non ci sono ancora espressioni analitiche per C ed L ma simulazioni rivelano che L cresce con il logaritmo di N (small world) e C decresce come C≈N0.75.

Le reti scale-free sono in genere anche small-world, in quanto caratterizzate dalla presenza di molti nodi con pochi collegamenti e pochi nodi con molti collegamenti. La presenza di anche solo pochi nodi ben collegati (tipico di scale-free) fa sì che ci siano “scorciatoie” che accorciano drasticamente le distanze e rendono “piccolo il mondo”.

Le reti scale-free hanno un’estrema tolleranza a guasti o danni casuali: se viene rimosso (ucciso) qualche nodo a caso, L cresce (perde efficienza) ma rimane abbastanza basso: è fault tolerant. Ciò può spiegare perché tali network sono così diffusi in natura.

L’inconveniente è l’estrema vulnerabilità ai guasti degli hub.

Se vengono rimossi i vertici di grado alto (attacco mirato), la rete va rapidamente in crisi: non è attack resistant. La rimozione progressiva di tali vertici fa si che l’efficienza globale decresca (molti nodi rimangono isolati), fino al collasso del sistema (failure).

3.4 Stato dell’arte

Watts e Strogatz hanno affermato che moltissime reti biologiche presentano le caratteristiche small-worl, ma solo pochi sistemi sono stati esaminati sperimentalmente.

Per quanto riguarda le reti neurali, esistono solamente due studi in tale direzione.

3.4.1 Studio 1

Il primo studio é quello compiuto dagli stessi Watts e Strogatz.

Essi hanno esaminato la rete neurale del verme Caenorhabditis elegans. [10] I neuroni sono i nodi (102 nodi), le sinapsi e gli assoni sono le connessioni.

Sperimentalmente hanno trovato: • L=2.65 (basso);

• C=0.28 (alto).

Tale rete è perciò un network small-world.

3.4.2 Studio 2

Il secondo studio è quello di Segev, Ben Jacob e altri. [16]

Essi hanno coltivato dei neuroni dissociati dai gangli di locusta e ne hanno seguito il processo di crescita, fino alla formazione di reti

bidimensionali pienamente connesse, dopo circa 6 giorni dalla semina.

Tre reti neurali mature sono poi state mappate in grafi, i cui nodi sono rappresentati dai corpi cellulari dei neuroni e dai punti di diramazione di uno stesso neurite e i cui archi sono le sinapsi (figura 3.11).

La mappatura si basa sulle assunzioni che tutti i nodi siano identici e che tutti i vertici siano identici, ignorandone la direzionalità.

Figura 3.11 Illustrazione dei punti considerati come vertici nelle reti: i numeri

1 e 8 sono i soma dei neuroni e i numeri 2-7 sono i punti di biforcazione di un neurite

Per ognuna delle reti testate, hanno calcolato il coefficiente di clustering, il grado medio dei nodi e la lunghezza media del cammino.

Il coefficiente di clustering e la lunghezza media del cammino di ogni rete sono stati poi confrontati con i valori posseduti da un grafo regolare e un grafo random caratterizzati dallo stesso numero di nodi n e dalla stessa connettività media k (tabella 1).

Tabella 1 Parametri descrittivi misurati per tre reti neuronali mature

coltivate e cresciute sotto condizioni controllate.

Per tutte le reti testate:

ƒ il coefficiente di clustering è molto maggiore di quello del grafo random corrispondente;

ƒ la lunghezza media è molto più vicina a quella del

corrispondente grafo random che a quella del corrispondente grafo regolare (lrandom ≤l <<lregular) e scala con ln(n)/ln(k).

In base a tali risultati, le reti possono essere classificate come small-world.

Questo secondo studio rappresenta un importante punto di partenza di tale lavoro di tesi, dato che è l’unico trovato in letteratura in cui una rete neurale in vitro è stata mappata in un grafo.

Proprio per questo, per le reti neurali da noi realizzate, abbiamo calcolato gli stessi parametri ed effettuato lo stesso tipo di analisi. Rispetto a tale lavoro sono stati fatti però alcuni importanti passi avanti:

9 non sono stati usati neuroni di gangli di locusta, ma neuroni di mammifero, più “vicini” a quelli umani e appartenenti al SNC;

9 il coefficiente di clustering e la lunghezza media del

cammino sono stati calcolati a partire dal primo giorno di coltura, così da studiare l’evoluzione della rete e eventualmente individuare il momento a partire dal quale essa assume le caratteristiche small-world;

9 oltre al test small-world sono stati realizzati altri tipi di analisi.

Bibliografia

1. http://teoriadeigrafi.altervista.org

2. Reinhard Diestel, -Graph Theory, Third Edition, Springer-Verlag, Heidelberg, Graduate Texts in Mathematics, Volume 173

3. Wilson Robin J., -Introduzione alla teoria dei grafi, Cremonese, 1978

4. Marco Burzio, -Teoria dei grafi, Quaderni didattici del dipartimento di matematica, Università di Torino, Anno Accademico 2005-2006

5. Xiao Fan Wang, Guanrong Chen, “Complex Networks: Small-World, Scale-Free and Beyond”, IEEE circuits and systems magazine, first quarter 2003

6. P. Erdos, A. Rényi, “On the evolution of random graphs”, Publ. Math. Inst. Hung. Acad. Sci. , vol. 5, pp.17-60, 1959

7. S. Milgram, “The small world problem”, Psychol. Today 2, 60-67 (1960-67).

8. D. J. Watts, S. H. Strogatz, “Collective dynamics of ‘small world’ networks”, Nature vol. 393, pp. 440-442, June 1998

9. S. H. Strogatz, “Exploring complex networks”, Nature, 410, pp. 268-276, 2001

10. T. B. Achacoso, W. S. Yamamoto, “Neuroanatomy of C.

elegans for Computation”, CRC Press (1992).

11. A. G. Phadke, J. S. Thorp, -Computer Relaying for Power Systems, Wiley (1988).

12. M. E. J. Newman, Models of the small world, J. Stat. Phys., 101 (2000) 819; The structure and function of networks,Comput. Phys. Commun., 147 (2002) 40.

13. R. Albert, A. L. Barabasi, “Statistical mechanics of complex networks”, Rev. Mod. Phys., 74 (2002) 47.

14. A. L. Barabasi, R. Albert, H. Jeong, “Mean-field theory for scale-free random networks”, Phisica A 272, 173-187 (1999)

15. A. L. Barabasi, E. Ravasz, “Deterministic Scale-Free

Network”, cond-mat/0107419 (2001)

16. Orit Shefi, Ido Golding, Ronen Segev, Eshel Ben-Jacob,

Amir Ayali, “Morphological characterization of in vitro neuronal networks”, Physical Review E 66, 021905 (2002)