Appunti corso Reti Complesse

#Communities – Clustering#

Alla ricerca di piccole comunità (cliques, plexes, motifs) oppure di grandi comunità (partizioni di grafi, clustering).

Maxiproteina è costituita da tanti pezzi (come un clique); plexes: alleggerimento dei vincoli dei clique.

Motif: strutture che si ripetono, come piccole comunità. Macrogruppi: proteine (membrana, nucleari, trasporto…).

Es. Barabasi: The human disease network (database omin) —> con approccio a network, ha guardato tutte

patologie. Alcune patologie possono avere geni alterati o mutati in comune. Costruì un network bipartito dove

ho malattia e i geni coinvolti. Potrei costruire una rete d’interazioni

tra patologie (legame tanto più forte quanti geni sono in comune)

o rete di interazione tra geni (GxG).

Es: patologie cancerose: mutazioni o effetti su alcuni geni sono comuni.; oppure malattie che hanno a che fare

comorbidità

con mente (ritardo mentale, epilessia..); oppure metaboliche: obesità, diabete.. si mostra la “ ”= chi ha

una certa patologia è probabile che abbia anche altre patologie.

Propagazione di una mutazione di un gene su altri geni -> Fare del clustering su questo network dovrebbe

dare un’idea su quelli che sono i gruppi di patologie collegate.

Già in un sotto gruppo, non si vedono molti motifs, è struttura prevalentemente ramificata, pochi loop; ci sono

più coppie di patologie che condividono dei geni e quindi una struttura ad albero. Capire proprietà di questi

network può dare info che sono comprensibili e giustificabili anche biologicamente.

* Clustering Gerarchizzato *

Occorre avere una metrica che definisca quando due nodi sono lontani o vicini, e andiamo a vedere quando

tutti i nodi sono vicini tra loro. Poi vedo distanza tra gruppetti, e creo gruppetto più grande —> ricorsivamente,

ottengo un dendrogramma in cui ci sono raggruppamenti degli elementi in gruppi sempre più grande.

Vi è una partizionamento ricorsivo, per cui i cluster più vicini vengono

progressivamente uniti insieme dendrogramma. Un taglio nel dendrogramma

!

porta alla formazione dei clusters.

Posso fare stesse cose per raggruppare altri tipi di dati(vettori)

anche con nodi. La differenza sta nella distanza definita tra vicini.

1- metrica: distanza tra nodi = shortest path (pesati) tra nodi (successivamente, si definisce la distanza

tra cluster come shortest distance tra cluster, con dove il peso è dato dal numero dei link presenti). Definire

cluster quando distanza è al di sotto di un certo valore; ho tanti modi di definire distanza tra 2 cluster però

—> altre scelte successive oltre alla distanza tra nodi (esiste link tra 2 nodi? qual è il suo peso?).

=> Definendo una metrica, definisco una funzione di distanza.

2 – struttura equivalente: Considero la distanza tra 2 nodi come distanza tra intera riga o colonna

relativa ai nodi. Guardo quanti vicini hanno in comune. Se due nodi hanno esattamente stessi primi vicini la

loro distanza è 0. Altrimenti posso basarmi su distanza

euclidea (o correlazione) tra righe e colonne del network.

I nodi con i vicini simili sono vicini.

3 – topological overlap: numero degli N-vicini comuni

(generalizzazione della correlazione).

Guardo non quanti primi vicini hanno in comune, ma

quanti ennesimi primi vicini hanno in comune.

Funzione costruita in modo che non diverga, che sia

normalizzata ecc ecc.. Individuo relazioni di similitudine,

ottenendo metriche ! (a = rimuovo link diretto e lo vado ad aggiungere al numeratore.)

ij

Se sono in una comunità (gruppo di nodi con max 1-2 nodi in comune) => ho stessa vicinanza.

Via via trovo strutture sempre più ampie e sempre più larghe. Aumentando il numero di ennnesimi vicini è

chiaro che vado a trovarmi vicino a tutti. La misura di quale livello di ennesima vicinanza, dipende dal tipo di

network che considero. 1

4 – define a merging rule:

a) single linkage: unire i cluster la cui distanza tra i geni più vicini è la più piccola

b) complete linkage: unire i cluster la cui distanza tra i geni più lontani è la più piccola

c) average linkage: unire i cluster la cui distanza media tra i geni è la più piccola

Linkage: distanza tra 2 cluster. Tipicamente, a parità di elementi, questi

network tendono a formare dei cluster diversi.

Effetti di diversi metodi di linkage:

a) single linkage: i cluster formati tendono a essere lunghe catene (1 nodo alla volta);

b) complete linkage: performante se gli elementi formano spontaneamente “clumps” distinti;

c) average linkage: performante con entrambe le distribuzioni; particolarmente

sensibile a metriche simili. (con complete e average posso ottenere più nodi alla volta)

Altri metodi di linkage:

• Bottom-up approach: creazione di cluster – blocks – merging blocks.

parto dai singoli elementi separati e a poco a poco arrivo al tutto.

La soluzione che mi interessa dovrebbe essere nel mezzo. Come definire un block?

Cutpoint o ponti sono troppo restrittivi.

• Newman- Girwan Clustering (top-down): invece deiponti, trovo i picchi con alta Betweennes

Centrality (o altra feature) e ordino. Elimino i picchi con rank più alto, e poi cerco componenti disconnesse.

Questo approccio Top – Down va dai blocchi più grandi ai più piccoli, ma è dispendioso dal punto di vista

computazionale (perché bisogna ricalcolare ogni volta la BC). Alternativa: random-walk betweennes, network

global efficency. top —> down: parto da tutto il link e con una regola spezzo il tutto in parti che poi si

spezzano secondo la stessa regola in parti ancora più piccole.

Con la betweenness possiamo trovare dei nodi con bassa connettività ed elevata BC, potevano essere nodi ai

margini dei cluster, all’interfaccia —> nodi isolati ma per i quali passano molti percorsi. Approccio empirico di

questo meccanismo di Newman: prendo e cavo i nodi che hanno più alta BC ed elevata C e vado a vedere

cosa succede; il network si dovrebbe essere disgregato parecchio. Se non ho formato componenti, procedo

ricorsivamente. Poco alla volta dovrei trovare blocchi separati tra loro. Posso ogni volta ricalcolare BC

(algoritmo pesante), o tenere i valori che ho calcolato al primo step, visto che BC può cambiare molto in vari

step. I bottom-up sono i più agili, mentre i up-bottom sono meno agili ma ottengono risultati più buoni in

generale.

La domanda è: quando mi fermo allora tra up-down o down-up? Come decido qual è il miglior punto? Non

univoca la soluzione, ma posso stimare il coefficiente di modularità Q (per N communities). E = matrice (NxN).

Q = numero di intracommunity – numero di link inter community.

Q = 1 = buono; Q circa 0 = cattivo. Ottimo stop per ottimo Q.

Valore elevato di Q, se ho spezzato bene il netwok. Connettività media

tra due cluster meno connettività tra i due cluster. Più i cluster sono

piccoli, più all’interno i nodi sono collegati tutti allo stesso modo

(modularità bassa). Favorisce il formarsi di pochi cluster con elevato numero di nodi.

SLIDE NUOVA

( )Se voglio fare bisezione: Q= sBs, con s=[-1,1] minimizzo hamiltoniana

con metodi numerici (annealing) per il vettore s. Assegno indice +1 ai nodi di un gruppo,

-1 ai nodi dell’altro, per cui questo valore è moltiplicato per 2, -2 o 0.

Ottengo Q tot con questa combinazione. Se trovo che c’è un link più probabile di quanto atteso,

e io ho assegnato i nodi allo stesso cluster, ottengo un valore positivo molto grande.

Se i due nodi sono connessi anche se la faccenda era improbabile e li associo a due

cluster diversi => ottengo 0

-k •k / A toglie la probabilità che quel link sia lì per caso.

i j ij

Q = (A -k •k. / A )(1s +s ) = sBs. Massimizzare questa funzione energia corrisponde a ottenere una

ij i j ij i j

bisezione (nodi con valori -1 appartengono a un cluster, gli altri a un altro). Voglio allineare (dare steso

valore) ai nodi che sono connessi in maniera più di quanto mi aspetterei in modo casuale e allineare con

valore -1 quelli che sn connessi in modo minore rispetto al corrispettivo casuale. 2

• Greedy Algorithm: guarda ricorsivamente a tutte le partizioni che massimizzano Q. Computationally demanding

for all classes => metodi subottimali: partono da piccolo cluster e scalano su.

• Metodi Spettrali: autovalori secondi laplaciano: bisezioni (componenti positive e negative); possono essere ripetuti

ricorsivamente, approccio top-down, la via veloce è quella di considerare solo il primo autovalore/vettore (è

sufficiente calcolare solo primo e/o secondo autoval/vett.).

SLIDE NUOVA : Laplaciano generalizzato: termine cinetico e “potenziale” V: [∆-V]ø A—>L = A-D-V.DIAG.

Teorema punti nodali e modi vibrazionali (autofunzioni) ∆ø=lambdaø ø|. =ƒ.

Generalizzazione: combinare i primi K autovettori e calcolare la distanza (correlazione, euclidea, others…). Faccio

clustering su queste proiezioni.

* Supermagnetic Clustering *

Supponiamo di avere N vettori K-dimensionali. Consideriamo intera matrice di tutti i vettori, oppure caratterizzo

che relazione c’è tra i vettori; si calcola l’analogo della distanza euclidea (matrice di covarianza) tra i vettori.

Matrice di covarianza = <XiXj> - <Xi><Xj>, se i dati sono distribuiti in modo gaussiano secondo le

componenti. Siccome questa matrice mostra tutti i momenti lungo gli assi principali e lungo le componenti,

ottengo una specie di elissoide lungo assi x,y. Diagonalizzare la matrce di covarianza significa fare una

rotazione degli assi in modo che l’ellisse venga “appoggiato” sugli assi, ovvero che le componenti non diagonali

siano messe = 0. Gli autovalori in quel momento dicono quanto sono lunghi gli assi. Se ellisse è molto

schiacciato su un asse => significa che i dati sono molto sparpagliati lungo un asse, e poco lungo l’altro =>

sono identici lungo quell’altro => i valori lungo asse in cui sono sparpagliati sono i dati più importanti =>

prendo solo proiezione su autovettore relativi ad autovalori più

basterebbero solo quelli per caratterizzarlo =>

grandi => riduzione alle “componenti principali”. Se voglio fare clustering da una A (adj.mat) o da L(lapalciana),

prendo solo info dai primi autovettori anziché fare clustering su tutti gli autovettori. Faccio un clustering su

uno spazio m dimensionale anziché K dimensionale, addirittura arrivando solo a 2-3-4 dimensional space, dove

posso fare clustering su quei vettori lì e spesso individuo direzioni più interessanti degli altri.

Hamiltonian function: H= A.ij•ø.i•ø.j, con ø=1,2,..N

=> Simultated annealing: data una hamiltoniana, e dato un cambio di configurazione che produce una differenza

di energia ∆E, accetto il cambio (o no) in funzione della variazione di energia (><o) della temperatura (a T

alte il cambio “migliore” non è sempre scelto). P proporzinale a exp(-∆E/kt). (vedi anche file reti01 inizio)

Sistema tdm tende a raggiugere il minimo dell’energia libera.

Ipotesi di landau: al di sotto di una temperatura critica, la A = en. libera = E- TS diventa in realtà

A = ax^4 - ßx^2

Se modello è così, è facile calcolare minimo.

Se invece ho modelli antiferromagnetici con frustrazione, la cosa cambia.

Simulated Annealing: Basato sul principio dei potenziali interazioni di tipo ferromagnetico, in sistemi a spin, solo

che tipicamente lo spin magnetico ha 2 valori (1/2 e -1/2), mentre noi possiamo immaginare N valori, N

orientazioni dello spin. Analogia: da un modello ferromagnetico classico di spin, al di sotto della temperatura

critica di Curie, il modello allinea gli spin, alzando temperatura li sparpaglia. In presenza di reticolo e poi una

perturbazione, la probabilità di essere flippato è random. Tipicamente, una sostanza ferromagnete è costituita da

domini ferromagnetici. In più, se le interazioni non sono del tutto omogenee, ma dipende da connettività, quindi

un nodo molto connesso tende a orientarsi come i suoi vicini, l’idea è che se simulo un raffreddamento o un

riscaldamento del mio sistema dove ho messo uno spin su ciascun nodo e l’hamiltoniana di interazione =

Adj.mat, mi aspetto situazioni simili ai domini ferromagnetici (nè tutti allineati, nè tutti sparpagliati a caso). Se

aumento temperatura vedo formazione domini => formazione cluster. Da punto di vista numerico non è facile

come calcolare matrice adj.

Gli spin cioè tendono a mettesi uno opposto all’altro, se sono nel reticolo (di tipo quadratico) esiste soluzione in

cui uno va su e uno va giu, quindi posso soddisfare tutti i constraits, contemporaneamente => esiste un unica

soluzione, dove al di sopra delle temperatura critica e anche al di sotto, la somma = 0 (ma non ci interessa).

Se disgraziatamente mi trovo con un reticolo a triangoli, non potrò mai verificare i miei constraints

contemporanemente! Questo si dice un modello “frustrato”: non riesce mai a soddisfare tutte le possibili 3

interazioni. Questo per dire che nei sistemi frustrati tuti e 3 su o tutti e 3 giu è il peggio possibile, però

tutte le configurazioni con1 su e 2 giu o 2 su e 1 giu, sono energicamente identici, perchè soddisfano 2

constraints su 3. In qst situazione non avrei più un unico minimo, ma 6 minimi identici dove il sistema può

andare dall’uno all’altro, ma sono tutti isoenergetici.

Se prendo un network un po’ più complicato, diventa un sistema in cui l’energy landscape è fatto come un

cardiogramma: ci sono tanti minimi diversi e a seconda di dove comincio, finisco in minimi diversi in tempi finiti.

I sistemi fustrati non sono multistabili (ce ne è sempre solo uno), ma sono metastabili: possono stare molto in

minimi che non sono stabili prima di arrivare al minimo stabile. I fisici, anziché usare la discesa del gradiente

o la derivata = 0, hanno deciso di fare quello che si fa per temprare un metallo: per far cristallizare meglio

un acciaio, una spada viene raffreddata e riscaldata ciclicamente => si da possibilità di avvicinarsi al vero stato

stabile. Questa tecnica può venire simulata con questo algoritmo di simulated annealing ed è molto potente per

trovare il minimo di funzioni difficilmente minimizzabili. Ci sono molti problemi che possono essere tradotti in

questo tipo. Anche se non conosco la soluzione analitica del sistema, con questo tipo di simulazione posso

andare a cercare un buon minimo (anche se rimane incerto se sia quello stabile).

Altrimenti si tenta di beccare la configurazione migliore, ma ci sono 2^n possibilità, con n = numero nodi!

Quindi quando ho hamiltoniana del sistema vado a variare il numero di spin, per vedere se l’energia del

sistema diminuisce => se H diminuisce. Se sì, lo tengo così flippato, altrimenti, non lo faccio muovere.

Svantaggio: quando sono in un minimo non vero, non vado più in là => s i introduce temperatura (meccanismo

probabilistico) per cui ho una certa probabilità di fare salto con probabilità di tipo del sistema di boltzmann

secondo distribuzione canonica. Negli ensemble canonici dove ho un’ hamiltoniana, la probabilità di trovarmi in

una certa configurazione è quella scritta prima (exp alla -∆E/(kT) ). Analogamente posso definire una

temperatura del sistema: più temperatura è alta, più la probabilità di ogni stato è uguale (quindi posso fare

salti maggiori), mentre se raffreddo il salto diventa più piccolo (la probabilità di salto dipende da ∆E). Quando

temperatura tende a zero, ho exp(- )

La temperatura bassa estremizza le differenze => verso bassa temperatura, dovrei andare a minimo energia

e stop. Ma salto avviene tra i punti vicini. Se diminuisce, mi muovo con una certa probabilità. Non è detto che

faccio sempre il salto che mi minimizza energia. (es piccola buca tra 2 grandi) => con cicli di temperatura

che si alza e raffredda progresivamente, con temperatura alta mi muovo di molto, se la riabbasso mi muovo

di meno. In generale ci si aspetta che più la buca è profonda più è larga => bisogna finire nelle buche

grandi => con salti più grandi, aumenta probabilità di finirci dentro; poi con abbassamento temperatura arrivo al

minimo.

F = - ∆V (∆ al contrario) => minimizzo eneriga potenziale in

maniera deterministica; qui lo faccio in maniera probabilistica.

Faccio annealing calcolando stato stabile in ogni tempeartura. Siccome

ho sistema fisico (paramagnetico), posso calcolare suscettività, =>

quando sono in una transizione di fase, essa diverge => grafico dice

all’aumentare della T come varia suscettivià sistema. All’aumentare, in

questo caso, ho 2 transizioni di fase: con un sistema con più spin

posso avere infatti più transizioni di fase. Si osservano 2 transizioni

=> in corrispondenza della prima si va a vedere cos’è successo agli

spin dei miei nodi => 2 classe fuse insieme e una dall’altra parte;

2° trans=> i 3 gruppi si seprarano ==> analogo di un clustering

gerarchico fatto in funzione della temperatura. All’aumentare del rumore, vanno tutti progressivamente allineati

=> domini paramagnetici. In OGNI punto sono stati fatti cicli di riscaldamento e raffreddamento, e si è

ottenuto quel punto come MINIMO

Nota: in reticoli con clicli di ordine dispari nessuna soluzione topologica può portare a un unica minimizzazione.

* Modularity and Diffusion *

Perform random walk on the network:

Spectral properties of T: 4

Faccio random walk all’interno del network => ho probabilità di trovare in ciascuno dei miei nodi (®= ro,

vettore) => se parto da un nodo, ® è una delta (tutti zero tranne un 1). Poi ho matrice di transizione tra

stati => probabilità di andare da un nodo a un altro, compreso