Pavia, 6 Maggio 2014
Almo Collegio Borromeo
Teoria dei giochi e centralità in un
network
Giulia Cesari
Politecnico di Milano
Université Paris Dauphine
[email protected]
…
Array1
Array2
Array3
array1
array2
array3
gene1
0
1
0
gene2
1
1
0
gene3
1
0
1
•Il gruppo {gene2, gene3} è vincente due volte su tre;
•Il gruppo {gene1, gene2} è vincente una volta su tre
•Così via per tutti i possibili gruppi…
Esempio:
A questa matrice corrisponde il
g1
Array1
Array2
Array3
0
1
0
g2
1
g3
1
1
0
microarray game <{g1,g2,g3},v> tale
che
0
v()=v({g1})=v({g2})=0
1
v({g1,g3})=v({g1,g2})=v({g3})=1/3
v({g2,g3})=2/3
v({g1,g2,g3})=1.
Il valore Shapley è:
Shg1=1/6
Shg2=1/3
Shg3=1/2
Il valore Shapley come indice di rilevanza di geni
• Perché possiamo usare il valore Shapley in questo
contesto?
 Approccio assiomatico: giustifichiamo l’uso del valore Shapley
attraverso alcune proprietà che esso soddisfa
 Proprietà con interpretazione biologica
• Come possiamo calcolare il valore Shapley di
miglialia di geni?
 Decomposizione del microarray game tramite giochi di
unanimità
Partnership di geni
Un gruppo di geni S tale che non esiste un sottoinsieme proprio ()
di S in grado di contribuire al cambiamento del valore del gruppo
esterno ad S.
Esempio
a1 a2 a3
Questi due
insieme sono
partnership di geni
nel gioco di
microarray
corrispondente
g1
0
1
1
g2
0
1
1
g3
1
0
1
Assiomi per il valore Shapley sui microarray games
Proprietà 1: Gene Nullo (NG)
Un indice di rilevanza deve attribuire rilevanza nulla ai geni che
non sono mai anormalmente espressi nelle cellule malate.
Proprietà 2: Equal Splitting (ES)
Tutti gli esperimenti devono essere considerati ugualmente affidabili e
quindi avere lo stesso peso nel calcolo del potere dei geni.
Proprietà 3: Monotonia delle Partnership (PM)
Se si hanno due partnerships di geni S e T, con |T||S| e che siano
disgiunte (ST=), equivalenti v(S)=v(T) ed esaustive
(v(ST)=v(N)), i geni nella partnership meno numerosa S
devono ricevere più rilevanza di quelli in T.
Proprietà 4: Razionalità di partnership (PR)
Il valore totale di rilevanza ricevuta da una partnership S dovrebbe
essere non inferiore a v(S)
Proprietà 5: Fattibilità di partnership (PF)
Il valore totale di rilevanza ricevuta da una partnership S dovrebbe
essere non superiore a v(N)
Teorema (Moretti, Patrone, Bonassi (2007)):
Il valore Shapley è l’unico indice che
soddisfa le proprietà NP, ES, PM, PR, PF
sulla classe dei giochi di microarray.
microarray game: definizione formale
Calcolo del valore Shapley sui microarray games
Esercizio:
gene1
gene2
gene3
gene4
gene5
gene6
gene7
gene8
gene9
gene10
sample1
sample2
sample3
sample4
0
1
0
1
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
1
0
0
0
0
0
1
0
1
•Calcolare il valore Shapley del
gioco di microarray associato a
questa tabella.
•La coalizione {gene2, gene3,
gene 4} è una partnership?
•La coalizione {gene2, gene 8} è
una partnership?
Teoria dei giochi
&
network
Network di comunicazione
• Un gioco cooperativo descrive una situazione in cui
tutti i giocatori possono liberamente interagire tra
loro
 tutte le coalizioni sono ammissibil
• Facciamo cadere questa ipotesi:
 introduciamo una restrizione sulle possibilità di
interazione tra i giocatori
• Come possiamo rappresentare questa restrizione
delle coalizioni di giocatori?
 attraverso un network
Network
Esempio: (N,E) con
o N={1,2,3,4,5,6,7}
o E={{1,2}, {2,6}, {5,6}, {1,5}, {3,7}, {4,7}}
1
5
2
3
6
7
4
Situazione di comunicazione
( communication situation )
• E’ una terna (N,v,Γ):
 (N,v) è un gioco di coalizione: rappresenta le
possibilità “economiche” delle coalizioni
 Γ=(N,E) è un network di comunicazione:
rappresenta le restrizioni di comunicazione tra i
giocatori
Situazione di comunicazione (Myerson 1977)

Il gioco ristretto al grafo (N,vΓ) è definito da
per ogni S2N\{}.
Ricordiamo che:
è l’insieme delle componenti
connesse in
, dove
è il grafo indotto (N,ES), con
ES insieme dei link in S.
Grafo(N,E): N={1,2,…,8}, E={{1,2},{2,4},{4,5},{4,7},{3,4},{6,7},{7,8}}
5
S
6
1
4
8
2
7
3
={{2},{5},{6,7}}
Esempio
Consideriamo un gioco di maggioranza pesata ({1,2,3},v)
con quota q=2/3. I voti dei giocatori 1, 2, e 3 sono,
rispettivamente, 40%, 20%, e 40%.Allora, v(1,3)=v(1,2,3)=1
e v(S)=0 per tutte le restanti coalizioni.
Il network di comunicazione è:
1
2
3
Allora, vΓ(1,2,3)=1, e vΓ (S)=0 per tutte le rimanenti
coalizioni.
Soluzioni per le situazioni di comunicazione


Myerson (1977) è stato il primo a studiare soluzioni per le
situazioni di comunicazione.
Una soluzione Ψ è una mappa definita per ogni situazione di
comunicazione (N,v,Γ) a valori in ℝN.
Proprietà 1 Component Efficiency (CE)
Per ogni situazione di comunicazione (N,v,Γ) e C  CΓs vale che:
iC Ψi(N,v,L) = v(C).

La proprietà 1 è una condizione di “efficienza” che si suppone
valida solo per le coalizioni I cui giocatori sono in grado di
comunicare tra loro e non sono connessi ad altri giocatori.
(componenti connesse massimali)
Soluzioni per le situazioni di comunicazione (2)
Proprietà 2 Fairness (F) Per ogni situazione di comunicazione
(N,v,Γ) e per ogni {i,j}  E vale che
Ψi(N,v,Γ) −Ψi(N,v,Γ\{{i, j}}) = Ψj(N,v,Γ)− Ψj(N,v,Γ\{{i, j }}).

La proprietà 2 dice che due giocatori dovrebbero ottenere lo
stesso guadagno (o perdita), quando si aggiunge (o si
elimina) un link diretto tra di loro.
Il valore Myerson
Teorema (Myerson (1977))
Esiste un’unica soluzione (N,v,Γ) che soddisfi CE e
F sulla classe delle situazioni di comunicazione.
Inoltre,
(N,v,Γ)= (vΓ)
dove (vΓ) è il valore Shapley del gioco ristretto al
grafo vΓ.
Esempio
Consideriamo un gioco di maggioranza pesata ({1,2,3},v)
con quota q=2/3. I voti dei giocatori 1, 2, e 3 sono,
rispettivamente, 40%, 20%, e 40%.Allora, v(1,3)=v(1,2,3)=1
e v(S)=0 per tutte le restanti coalizioni.
Il network di comunicazione è:
1
2
3
Allora, vΓ(1,2,3)=1, e vΓ (S)=0 per tutte le rimanenti
coalizioni.
(v)=(1/2,0,1/2) e (N,v,Γ)= (vL)=(1/3,1/3,1/3).
Tornando ai geni…
• Un gioco cooperativo descrive una situazione in cui tutti i
giocatori possono liberamente interagire tra loro
 tutte le coalizioni sono ammissibili
• Facciamo cadere questa ipotesi:
 introduciamo una restrizione sulle possibilità di
interazione tra i giocatori
 Qual è il significato di imporre una restrizione sulle
possibilità di interazione tra geni?
 Quali informazioni ci fornisce un network di geni al fine di
individuare geni rilevanti all’interno di un contesto
biologico?
… network biologici
• I meccanismi di interazione tra geni, RNA e proteine sono
molto complessi e oggetto di grande interesse nel campo
della ricerca biomedica e epidemiologica.
• Tali meccanismi sono descritti da reti di regolazione genica:
gene regulatory network o gene regulatory pathway.
• La ricostruzione dei meccanismi di regolazione a livello
cellulare sulla base dei dati di espressione genica è
fondamentale per la comprensione delle funzioni di geni nella
determinazione di una certa condizione biologica di interesse,
come l’insorgere di una malattia genetica.
• L’interpretazione dell’interazione tra geni all’interno di network
biologici rende dunque necessaria l’individuazione di misure
dell’importanza di geni all’interno di tali network.
Centralità di geni in un network biolgico
• Diversi approcci sono stati proposti per
l’identificazione di geni ‘centrali’ all’interno di pathway
biolgici.
• I network di coespressione di geni (gene coexpression network), sono sempre più usati per
studiare il ruolo di geni e proteine all’interno dei
meccanismi di regolazione che avvengono a livello
cellulare.
Rilevanza di geni in un network biolgico
Jeong, Mason, Barabasi, Oltvai. Lethality and centrality in protein networks. Nature 2001;411:41-42.
Forte correlazione positiva tra il grado del gene/proteina e la sua
letalità (Jeong et al. Nature 2001; Provero [arXiv:condmat/0207345], 2002; Carlson, BMC Genomics, 2006).
Centralità in un network biologico
• Cosa si intende con centralità in un network?
• Quali sono possibili misure di centralità di geni in un network
biologico?
Social network
Social network
• Un social network è una struttura sociale fatta di nodi
(generalmente rappresentano individui o
organizzazioni) che sono messi in relazione a coppie
a rappresentare una o più tipologie di
interdipendenza, come
– Valori, ideali, scambi finanziari, amicizia, antipatia, conflitto,
parentela, commercio …
• La struttura che ne risulta può essere rappresentata
mediante un grafo
• Il corpus teorico e i modelli usati per lo studio delle reti
sociali sono compresi nella cosiddetta social network
analysis
• La ricerca condotta nell'ambito di diversi approcci
disciplinari ha evidenziato come le reti sociali operino a più
livelli (dalle famiglie alle comunità nazionali) e svolgano un
ruolo cruciale nel determinare le modalità di risoluzione di
problemi e i sistemi di gestione delle organizzazioni,
nonché le possibilità dei singoli individui di raggiungere i
propri obiettivi
• La metafora dei social network è stata utilizzata per più di
un secolo per rappresentare insiemi di complesse
interrelazioni tra i membri di un sistema sociale su varie
scale, da quelle interpersonali a quelle internazionali
Analisi dei social network
• Lo studio dei network sociali si è trasformata
dall’essere una suggestiva metafora per diventare un
approccio analitico vero proprio, con i suoi enunciati
teorici, metodi di ricerca specifici e ricercatori
specializzati.
• Vengono utilizzati in diversi settori della scienza
applicata: antropologia, biologia, studi di
comunicazione, economia, geografia, informatica,
organizzazione, psicologia sociale e socio-linguistica.
Metodi di misura nei social networks
 Hanno lo scopo di studiare diverse proprietà:
 Centralità, coesione …
 Coefficienti di clustering ('cliquishness‘) …
 Coefficienti strutturali …
 CENTRALITÀ: indicazione del potere sociale dei
nodi basato sulla loro capacità di rendere
“connesso” il network
La centralità cerca di misurare
l’importanza di un vertice
• Centralità  grado: “quanti nodi sono
conessi a me?”
• Centralità  vicinanza: “quanto vicino
sono a tutti gli altri nodi?”
• Centralità  intermediazione: “quanti
nodi hanno bisogno di me come
intermediario nelle loro comunicazioni?”
Primi studi sulla centralità
• L’idea di centralità applicata alla comunicazione tra
individui fu introdotta dallo studioso di psicosociologia
americano Bavelas nel 1948.
• Studi riguardante la comunicazione in piccoli gruppi di
individui: ipotesi di relazione tra centralità strutturale e
influenza all’interno di processi di gruppo.
• Le ricerche evidenziarono legame tra centralità e
efficienza del gruppo in processi di problem-solving,
percezione della leadership e personale soddisfazione
dei partecipanti al gruppo
Freeman “Centrality in social networks:
conceptual clarification.”
Il sociologo L. Freeman scrive, nel 1979: “L'idea di
centralità è viva ed è stata mobilitata in una varietà di
applicazioni sempre più ampia. Tutti concordano, a quanto
pare, sul fatto che la centralità sia un importante attributo
della struttura di un network sociale. Tutti convengono sul
fatto che essa sia fortemente legata ad altre importanti
proprietà e processi all'interno di un gruppo. Ma qui il
consenso finisce. Non vi è sicuramente accordo su cosa sia
esattamente la centralità o sulle sue radici concettuali, e vi è
poco consenso sulle corrette procedure per la sua
misurazione.”
Centralità in un network: misure classiche
Tutte le misure di centralità attribuiscono centralità massima
al fulcro di una stella (hub).
Cos’è che rende unica la posizione di i?
• Possiede il massimo grado possibile
• Giace sul massimo numero di geodetiche che
collegano gli altri vertici
• Si trova alla minima distanza da tutti gli altri vertici
Cos’è che rende centrale un individuo i in un dato
network?
•
Può comunicare con molti altri nodi
•
Vi sono molti altri nodi che necessitano di i come
intermediario nelle loro comunicazioni
•
È vicino a molti altri nodi
Misure di centralità
• Può comunicare con molti altri nodi
Degree centrality
Misure di centralità
• Vi sono molti altri nodi che necessitano di i
come intermediario nelle loro comunicazioni
Betweeness centrality
Misure di centralità
• È vicino a molti altri nodi
Closeness centrality
(Shaw, 1954, and Nieminen, 1974)
Degree centrality
[4]
[3]
[5]
Quanti nodi
sono connessi
a me?
(Beauchamp, 1965 and Sabidussi, 1966)
Closeness centrality
[44]
[33]
[27]
Quanto vicino
sono a tutti gli
altri nodi?
Un esempio: misure di centralità
Misure di centralità classiche
• Le misure di centralità classiche assegnano ad ogni
nodo di un network un valore che corrisponde in
qualche modo all’importanza di tale nodo per
l’applicazione in esame.
• Esempio: nella progettazione di un network di
infrastrutture che sia il meno possibile vulnerabile al
guasto di un nodo, una misura di centralità classica
potrebbe assegnare un valore ad ogni nodo in modo
proporzionale ai danni conseguenti dal suo guasto.
Misure di centralità classiche: limitazioni
• Poiché i nodi vengono valutati separatamente, vi è
l’assunzione implicita che i guasti dei nodi
avvengano indipendentemente gli uni dagli altri. Di
conseguenza, fenomeni comuni come i guasti di
nodi a cascata sfuggono ad una tale analisi.
• Considerando solamente il guasto di nodi singoli, si
ignorano situazioni più realistiche in cui diversi nodi
possono venire meno contemporaneamente
Misure di centralità classiche: limitazioni
Misure di centralità classiche: limitazioni
• Le misure di centralità classiche possono rivelarsi
inefficaci nel riflettere il ruolo delle coppie di nodi o
più in generale di sottoinsiemi di nodi
Misure di centralità classiche: limitazioni
• Misure di centralità classiche non sono in grado di
riconoscere che in molte applicazioni reali non è
sufficiente considerare i nodi come entità a sé stanti.
• Un requisito importante consiste nella comprensione
dell’importanza di ciascun nodo in termini della sua
utilità congiunta con altri nodi.
Toeria dei giochi e centralità in un network
•Idea di base: definire un gioco cooperativo in cui i
giocatori siano i nodi del network in esame.
•Indice di potere di un nodo come misura di centralità,
in quanto rappresenta il contributo marginale atteso di
ogni nodo ad ogni possibile combinazione di altri nodi.
Teoria dei giochi e centralità in un network sociale
• La centralità di un individuo viene misurata
come variazione di potere dovuta alla struttura
sociale a cui appartiene (i.e. alla restrizione delle
possibilità di comunicazione).
• In effetti è basato su un network sociale e sui
“giochi ristretti al grafo” (Myerson (1977), Slikker
(2001))
Centralità 
 (N,E) è un grafo che rappresenta un social network
 (N,v) è un gioco di coalizione dato a priori
 Si definisce un gioco ristretto al grafo vΓ (Myerson (1977))
 i(v, E) = i(vΓ) - i(v)
 Rappresenta l’incremento (o decremento) del potere del
giocatore i dovuto alla sua posizione nel grafo.
  soddisfa proprietà interessanti relative al contesto della
centralità per social network …
Desiderata for centrality measures:
1) Centrality of a node in a disconnected graph should coincide with the
centrality of that node in the connected sub-graph to which it belongs
2) Isolated nodes should have minimal centrality
3) If the graph is a chain, centrality should increase from the end node
to the median node
4) Of all connected graphs with n nodes, the minimal centrality should
be attained by the end nodes in a chain
5) Of all graphs with n nodes, the maximal centrality should be attained
by the hub of a star
6) Removing and edge should decrease (or at least, not increase) the
centrality of both nodes incident on that edge
7) Any measure of centrality should be symmetric, i.e. if p is a
permutation of N which preserves the graph, then a node i should
have the same centrality as node p(i)
Esempio
Se (N,v) è tale che v(S)=1 per ogni S
sottoinsieme non vuoto di N, vΓ (S)=|
({1,2,3,4},E)
|
2
1
4
3
S
v
vΓ
(v) (vΓ )

{1}
1
1
¼
½
¼
{2}
1
1
¼
½
¼
{3}
1
1
¼
½
¼
{4}
1
1
¼
-½
-3/4
{1,2}
1
2
{1,3}
1
2
{1,4}
1
1
{2,3}
1
2
{2,4}
1
1
{3,4}
1
1
{1,2,3}
1
3
{2,3,4}
1
1
{1,3,4}
1
1
{1,2,4}
1
1
{1,2,3,4}
1
1
({1,2,3,4},E)
2
1
4
3
Biologia e network
 Diversi modelli basati su network sono utilizzati in
biologia molecolare,
 protein interaction networks
 gene regulatory networks
 gene co-expression networks
…
 La struttura di un network può essere rappresentata in
maniera formale attraverso un grafo G = (V,E)
 L’insieme dei nodi contiene I geni: V = {xgene, ygene,
zgene,…}
 L’insieme dei lati contiene interazioni.
xgene
ygene
zgene
Co-expression network games
 Un livello di indagine dell’interazione tra geni più
accurato , in quanto il modello tiene conto delle
interazioni tra coppie di geni e non dei livelli di
espressione dei singoli geni, come nell’approccio
con I microarray games.
 Integrazione all’interno del modello della
conoscenza a priori di alcuni geni che rivestono un
ruolo chiave all’interno di un certo processo
biologico in esame.
Steps for constructing a
co-expression network
A) Dati di espressione genica da
microarray
B) Misure di concordanza
dell’espressione genica mediante
correlazione di Pearson
C) Matrice di correlazione di Pearson
D) La matrice di correlazione di
Pearson può essere dicotomizzata
per giungere a una matrice delle
adiacenze  grafo non pesato
Arrays
Correlation matrix
G
1
1
1
2
0.91
3
0.35 0.95
4
0.9
Study-genes N={1,2,3}
2
3
0.91 0.35
1
0.2
a priori selected key-gene 4
0.9
0.95
0.2
1
0.89
0.89
1
2
1
4
3
Genes interaction and centrality
•Classical centrality measures are appropriate under the
assumption that nodes failures occur independently...
•…and the system is sensible to the failure of each single
node.
•On the contrary, in biological complex networks,
assuming that the failure of the nodes (genes/ proteins) is
independent is not realistic and the consequence on the
system can be appreciated only if many nodes fail.
Co-expression network games
Use a co-expression network (N,E) as a
communication network
The set N of players is the set of genes studied
Links in E are co-expression relations
What is an a priori game (N,v)?
a priori game (N,v): the worth v(S) of a coalition of genes in S is
the number of key genes that S correlate, independently* from
genes in N-S.
1
2
3
Genes-players
Key genes
* Means that v(S) is the number of key genes
connected to S and not connected to geneplayers out of S
S
v
(v)
{1}
1
1.5
{2}
0
0
{3}
1
1.5
{1,2}
1
{1,3}
3
{2,3}
1
{1,2,3}
3
Communication network: a co-expression network from
experimental data ({1,2,3},E)
1
2
3
Genes-players
Graph-restricted game
A priori game
S
v
(v)
S
vΓ
(vΓ )

{1}
1
1.5
{1}
1
4/3
-1/6
{2}
0
0
{2}
0
1/3
1/3
{3}
1
1.5
{3}
1
4/3
-1/6
{1,2}
1
{1,2}
1
{1,3}
3
{1,3}
2
{2,3}
1
{2,3}
1
{1,2,3}
3
{1,2,3}
3
Association
game
2
Co-expression
network game
3
1
1
LOSE
1
LOSE
2
LOSE
2
LOSE
3
LOSE
3
LOSE
1
2
2
3
1
3
1
2
LOSE
1
2
LOOSE
2
3
WIN
1
3 WIN
1
3
2
4
Shapley value
LOSE
LOSE
LOSE
3 WIN
Asso Co- Diff.
expr.
1
1/2
1/3
-1/6
2
0
1/3
1/3
3
1/2
1/3
-1/6
Pearson
correlation >0.92
 Most associated
genes: Shapley
value in [0.5,0.16]
Most central
genes: Shapley
difference in
[0.14, 0.009].
SORBS1
45
PRKCG
TP73
TNNI1
SLC6A11
GATA1
DLD
VPS35
C11orf58
CDC42BPA
RPL18A
SMAD6
PTGES3
ATP11A
RPS17
216570_x_at
LOC391132
TP53
Microarray data from neuroblastic tumors (Albino et al. (2008).
Key genes
(selected a priori)
Most associated
genes
Most central
genes
Esercizio:
Calcolare la degree centrality e la misura di centralità  dei
nodi nel network in figura, dove a,b e c sono i geni chiave.
Grazie per l’attenzione!