Università di Pisa
Area di Scienze, Matematiche, Fisiche e della NaturaDipartimento di Informatica
Corso di Laurea in Scienze dell'Informazione
Tesi di Laurea
Implementazione in Visual SPiM di modelli matematici per
l'incentivazione dei Moderati in un Conflitto Ideologico
Candidato
Sergio Medde
Relatori Contro Relatore
Professor Pierpaolo Degano Professoressa Maria Grazia Scutellà
Professor Valter Bencivelli
Indice
1 : Introduzione
1.1 : Presentazione del problema
1.2 : Sistemi di Equazioni Differenziali vs Simulazioni Stocastiche 1.3 : Obiettivo della Tesi
2 : Formalismi alla base dello Strumento Visual SPiM 2.1.1 : Il CCS Calculus for Communicating System
2.1.2 : Il Pi-Calcolo
2.1.3 : L'algoritmo di simulazione stocastica di Gillespie
2.2 : Il linguaggio di programmazione SPiM Stochastic Pi-calculus Machine 2.3 : Il tool grafico Visual SPiM
3 : Il caso di studio in esame 4 : Modello base
4.1 : Cerchiamo di ottenere gli stessi risultati teorici con la simulazione stocastica 4.1.1 : Modello matematico del modello base
4.2 : Implementazione del modello base in Visual SPiM 4.2.1 : Programma base lenta
4.2.2 : Programma base veloce
5 : Primo tentativo, rendere i moderati più testardi
5.1 : Implementazione del modello moderati+testardi in Visual SPiM 5.1.1 : Programma moderati+testardi base lenta
5.1.2 : Programma moderati+testardi base veloce
6 : Variante del modello moderati+testardi, squilibrio a favore della popolazione B
6.1 : Modello matematico della variante
6.2 : Implementazione della variante in Visual SPiM 6.2.1 : Programma variante moderati+testardi base lenta 6.2.2 : Programma variante moderati+testardi base veloce
7 : Secondo tentativo, evangelizzazione dei moderati
7.1 : Implementazione del modello evangelizzazione moderati in Visual SPiM 7.1.1 : Programma evangelizzazione moderati base lenta
7.1.2 : Programma evangelizzazione moderati base veloce 8 : Variante del modello evangelizzazione moderati 8.1 : Modello matematico della variante
8.2 : Implementazione della variante in Visual SPiM
8.2.1 : Programma variante evangelizzazione moderati base lenta 8.2.2 : Programma variante evangelizzazione moderati base veloce 9 : Terzo tentativo, de-radicalizzazione non sociale
9.1 : Implementazione del modello de-radicalizzazione non sociale in Visual SPiM 9.2.1 : Programma de-radicalizzazione non sociale base lenta
9.2.2 : Programma de-radicalizzazione non sociale base veloce 10 : Variante del modello de-radicalizzazione non sociale 10.1 : Modello matematico della variante
10.2 : Implementazione della variante de-radicalizzazione non sociale in Visual SPiM
10.2.1: Programma variante de-radicalizzazione non sociale base lenta 10.2.2: Programma variante de-radicalizzazione non sociale base veloce 11 : Quarto modello, forze equilibrate
11.1 : Modello matematico per forze equilibrate
11.2 : Implementazione del modello forze equilibrate in Visual SPiM 11.2.1: Programma forze equilibrate base lenta
11.2.2: Programma forze equilibrate base veloce 12 : Varianti al modello forze equilibrate 12.1 : Forze equilibrate & moderati+testardi
12.1.1: Modello matematico di forze equilibrate & moderati+testardi
12.1.2: Implementazione di forze equilibrate & moderati+testardi in Visual SPiM 12.1.3: Programma forze equilibrate & moderati+testardi base lenta
12.1.4: Programma forze equilibrate & moderati+testardi base veloce 12.2 : Forze equilibrate & evangelizzazione moderati
12.2.1: Programma forze equilibrate & evangelizzazione moderati base lenta 12.2.2: Programma forze equilibrate & evangelizzazione moderati base veloce 12.3 : Forze equilibrate & de-radicalizzazione non sociale
12.3.1: Programma forze equilibrate & de-radicalizzazione non sociale base lenta 12.3.2: Programma forze equilibrate & de-radicalizzazione non sociale base veloce
13 : Tripolarismo Italiano con forze equilibrate & de-radicalizzazione non sociale controllata
13.1 : Implementazione del modello tripolarismo Italiano in Visual SPiM 13.1.1: Programma tripolarismo Italiano base lenta
13.1.2: Programma tripolarismo Italiano base veloce Conclusioni
Appendice A :Versione integrale della “lettera dei fisici” e del materiale supplementare
Appendice B :Sintassi del linguaggio di programmazione SPiM Bibliografia
1 Introduzione
1.1 presentazione del problema
Un problema comune che si presenta spesso in biologia, in biochimica, in chimica cinetica, ma anche in scienze sociali, economia, informatica e in molte altre discipline, è studiare il comportamento di una o più popolazioni di elementi (siano essi cellule, atomi, molecole chimiche, individui o processi) che interagendo tra di loro attraverso degli appositi canali di comunicazione (lo spazio di collisione tra due molecole di gas, la memoria condivisa tra due processi di sistema, la rete Ethernet o WiFi tra processi distribuiti e concorrenti, il telefono, i messaggi email, o
semplicemente il parlarsi di persona fra due individui), fanno evolvere il sistema [ambiente, popolazione] nel tempo in maniera discreta e in accordo a certe leggi che regolano le dinamiche di tali comportamenti nel loro specifico ambiente, e in
occorrenza con eventi che si possono o no presentare.
Generalmente, in un determinato istante di tempo, il sistema si trova in uno stato di equilibrio stabile e vi rimane indefinitamente a meno che non si verifichi un evento che ne alteri l'equilibrio.
Questi eventi possono essere causati volontariamente (per esempio in
esperimenti in laboratorio, aumentando la temperatura o la pressione del recipiente che contiene i gas o l'introduzione di un nuovo tipo di gas, l'inserimento all'interno di una cellula di un enzima sintetizzato, la modifica di un valore di una locazione di memoria condivisa) o essere totalmente casuali (una nuova invenzione o una scoperta scientifica, una nuova moda, una nuova ideologia, un nuovo virus o la ricomparsa di uno già esistente).
Il verificarsi del nuovo evento porta il sistema ad adattarsi al cambiamento, che ha generato lo squilibrio, tramite l'interazione tra gli elementi attraverso i canali di comunicazione.
Queste interazioni causano a loro volta nuovi eventi in cascata (la creazione di un nuovo composto chimico o di una nuova molecola, la risposta ad un messaggio, l'adozione o la contrapposizione dell'ideologia, il propagarsi del virus) che portano al cambiamento dello stato del sistema (creazione di nuove sotto-popolazioni e/o
spostamento di elementi da una popolazione all'altra, creazione di nuovi canali di comunicazione o restrizione di alcuni di questi per certe sotto-popolazioni) fino ad arrivare ad un nuovo equilibrio del sistema.
Determinare quale sarà lo stato finale di un sistema reale, che subisce variazioni della propria stabilità, in generale non è di facile soluzione perché non sempre è possibile effettuare esperimenti in natura o in laboratorio o in un sistema a regime perché troppo complessi da realizzare, troppo costosi in termini di tempo e/o risorse, troppo invasivi (alterano il sistema in maniera non reversibile) o persino
pericolosi, quindi si rende necessario ricorrere a dei modelli che cercano di simulare il più fedelmente possibile il comportamento del sistema in esame, ma che comunque approssimano tale sistema ad un certo livello di astrazione, cercando però di
preservare alcune caratteristiche di interesse e semplificando o trascurando le altre (in genere per diminuirne la complessità).
1.2 Sistemi di equazioni differenziali vs Simulazioni Stocastiche
Il modello più comunemente usato è quello matematico, tipicamente sistemi di equazioni differenziali o alle differenze, perché la teoria fornisce una base formale con la quale è possibile dare una formulazione esatta delle proprietà qualitative che la soluzione del problema dovrebbe avere, come esistenza, unicità, regolarità, e possono dare una stima più o meno precisa di proprietà quantitative, come cardinalità delle popolazioni dopo un determinato periodo di tempo o il tempo minimo necessario affinché si raggiunga una configurazione cercata del sistema.
Per poter utilizzare questa teoria però è necessario soddisfare delle ipotesi che possono essere molto restrittive, ad esempio per ottenere la modellazione delle dinamiche dei problemi in esame (che fanno variare il numero di elementi delle popolazioni del sistema in modo discreto nel tempo), per le equazioni differenziali devono essere funzioni continue e derivabili nel tempo, applicabili solo per grandi dimensioni degli elementi delle popolazioni e per il limite del tempo che va
all'infinito.
In questo modo le dinamiche sono viste come variazioni continue che dipendono dalle dimensioni delle popolazioni in ogni istante di tempo.
Partendo da certi valori delle condizioni iniziali, certi valori dei parametri e delle costanti in gioco si ottiene un unica soluzione e un costante tempo di calcolo perciò ripetere il procedimento con gli stessi dati iniziali porta agli stessi risultati e nello stesso tempo.
Le possibili interazioni tra elementi delle popolazioni possono essere di vari tipi (e se ne può sceglie solo uno in istanti diversi) e la scelta avviene in modo casuale in accordo alla distribuzione di probabilità tra tutte le possibili alternative e questo genera il non determinismo degli stati raggiungibili da uno stato iniziale.
Questa distribuzione di probabilità può essere uniforme per tutto il tempo o variare se si verificano certe condizioni con la conseguenza che un certo tipo di interazione verrà favorita rispetto alle altre influenzando la possibile scelta.
Le condizioni a loro volta possono essere casuali o dipendere dallo stato del sistema in un determinato istante.
Ripetere un esperimento in natura o in laboratorio, partendo dagli stessi dati iniziali, porta a risultati sempre differenti (e in tempi differenti) ma simili o
paragonabili a quelli ottenuti dai modelli matematici e, in generale, aumentando il tempo del esperimento (quando è possibile) la distanza tra i due risultati tende a diminuire.
Questi risultati anomali possono dipendere o da un errata modellazione del problema oppure perché il non determinismo gioca un ruolo fondamentale non catturabile dalle normali equazioni differenziali.
Per poter avere dei modelli con cui poter studiare il comportamento di questa classe di problemi il più fedelmente possibile alla realtà è necessario disporre di formalismi che integrino al proprio interno il calcolo delle probabilità, indispensabile per modellare il non determinismo.
Due tecniche che sono state seguite sono: (1) La “Master Equation”
(2) Le simulazioni stocastiche
La Master Equation è una complessa equazioni differenziale che vuole rappresentare l'andamento nel tempo della “Grande Funzione di Probabilità”
P(nA(t),nB(t),..,nZ(t);t) che rappresenta la probabilità che un sistema si possa trovare in uno stato con nA elementi di tipo A, nB elementi di tipo B,.., nZ elementi di tipo Z al tempo t .
La Grande Funzione di Probabilità al tempo t+dt è calcolata come la somma (o l'integrale) di tutte le probabilità di tutte le possibili scelte degli stati raggiungibili dal sistema partendo dallo stato attuale al tempo t, e come avviene nei processi
Markoviani le condizioni dello stato al tempo t+dt dipendono solo dalle condizioni dello stato al tempo t e non dalla storia evolutiva, e questo porta ad avere una distribuzione di probabilità di tipo esponenziale negativo.
Tuttavia il numero delle possibili scelte può crescere esponenzialmente con l'aumentare della popolazione e questo rende la risoluzione della Master Equation molto difficile se non impossibile o applicabile ad una sottoclasse ristretta dei problemi.
Le simulazioni stocastiche si basano sul concetto di “traiettoria” cioè partendo dallo stato iniziale al tempo t si sceglie uno solo dei possibili stati raggiungibili in accordo con una distribuzione di probabilità e si calcola il tempo necessario per arrivare a questo nuovo stato e la traiettoria è la sequenza di queste scelte fino ad arrivare allo stato finale.
Questo modo di procedere rispecchia verosimilmente l'andamento di un singolo esperimento reale.
La scelta dello stato successivo può essere calcolata per esempio utilizzando l'Algoritmo di Simulazione Stocastica di Gillespie o SSA (Stochastic Simulation Algorithms) [Gillespie, 1977] che calcola anche il tempo necessario per la
transizione.
Questo algoritmo è stato proposto per dare una formulazione esatta delle
reazioni chimiche che avvengono tra molecole all'interno di un volume e utilizza una coppia di numeri casuali per determinare quando avvera la prossima reazione e di che tipo sarà, approfondiremo nel paragrafo 2.1.3.
Queste simulazioni oggigiorno vengono realizzate perlopiù con il computer e questo a reso necessario la creazione e lo sviluppo di nuovi formalismi più flessibili e/o più efficienti per poter rappresentare al meglio le nuove problematiche.
D'altra parte si è visto che formalismi nati in ambito informatico possono essere adattati con successo anche in altre discipline [Degano & Bracciali, 2012].
Per esempio il CCS Calculus for Communicating System [Milner, 1980,1999] proposto per dare una semantica formale ai sistemi di processi concorrenti e
distribuiti che si scambiano messaggi, è stato adattato per ideare specifici linguaggi di programmazione usati in biologia.
In questo modo si è potuto modellare e studiare il comportamento di complesse reti di cellule che rilasciano enzimi nel ambiente per comunicare con le cellule vicine, vedremo nel dettaglio il CCS nel secondo capitolo paragrafo 2.1.1.
Il π-calcolo [Milner et al, 1997] che estende il CCS e permette di dare dei “nomi” ai canali di comunicazione e mandare questi nomi come messaggi attraverso i canali stessi.
Con questo formalismo si possono rappresentare e analizzare i sistemi a compartimenti dove i processi di un comparto comunicano tra di loro attraverso i canali interni (non visibili dall'esterno) e se volessero comunicare con processi di un altro compartimento devono poter ricevere in un messaggio il nome del nuovo canale esterno per l'interazione.
Utilizzato per descrivere formalmente i sistemi mobili è stato adattato per modellare il complesso comportamento delle membrane cellulari, approfondiremo il π-calcolo nel paragrafo 2.1.2 .
Entrambi questi formalismi sono stati estesi per integrare nella semantica meccanismi per modellare aspetti quantitativi e meccanismi per simulare il comportamento stocastico, in modo da poter studiare le performance del sistema [Hillston, 1996], [Priami et al, 2004].
Questi meccanismi prevedono l'uso di variabili aleatorie per ogni azione e una distribuzione di probabilità, di tipo esponenziale, che servono per modellare il ritardo stocastico dato dalla realizzazione di ogni azione per ogni specifico canale in quanto non sono ammesse più di un'azione per un singolo canale nello stesso istante e bisogna aspettare che un'azione sia terminata prima di avere la possibilità di
effettuare una nuova azione nello stesso canale (un comportamento che si riscontra anche nei fenomeni naturali).
Il ritardo stocastico influenza sia la scelta che la sincronizzazione tra processi in parallelo e di conseguenza l'intero procedimento.
In particolare se si può scegliere tra due processi quale utilizzare e quale scartare si sceglierà quello che mediamente termina prima (la scelta non è più puramente casuale come succede nel CCS), mentre per la sincronizzazione quando due processi sono pronti il primo a trasmettere l'altro a ricevere per lo stesso canale ognuno dei due deve comunque aspettare che anche l'altro abbia terminato la
Per modellare il ritardo stocastico sono stati usati sia approcci simili alla Master Equation e la semantica vista come Catene di Markov a Tempo Continuo (CTMC, Continuous Time Markov Chain) sia con le simulazioni stocastiche come l'algoritmo SSA di Gillespie e la semantica vista come Sistemi a Transizioni Etichettate (LTS, Labelled Transition System).
La semantica di tutti questi formalismi è anche “operazionale” e questo ha permesso la creazione di molti strumenti software utilizzabili per simulare al computer la classe di problemi sopra citati, in particolare il Visual SPiM che
implementa in un tool grafico il linguaggio di programmazione Stochastic Pi-calculus Machine [Phillips & Cardelli, 2007] sarà lo strumento utilizzato in questa tesi, nei paragrafi 2.2, 2.3 del capitolo 2 presenteremo questo strumento più dettagliatamente.
1.3 Obiettivo della Tesi
L'obiettivo principale di questo elaborato è quello di prendere in esame un caso di studio che rientra nei problemi sopra descritti e che è stato trattato nel modo
classico, puramente matematico, e creare un modello equivalente utilizzando il
linguaggio di programmazione SPiM, in fine effettuare una serie di simulazioni con il tool grafico Visual SPiM e confrontare i risultati ottenuti con quelli teorici derivati dalla risoluzione del sistema di equazioni differenziali.
Il caso di studio in esame è descritto in una pubblicazione scientifica proposta da Seth A. Marvel e altri nel 2012 [Marvel et al, 2012] dal titolo emblematico
“Encouraging Moderation: Clues from a Simple Model of Ideological Conflict” in cui vengono descritte le dinamiche di un semplice modello di conflitto ideologico e vengono proposte plausibili variazioni per incentivare la crescita della popolazione dei moderati tra due fazioni estremiste e in conflitto tra loro, vedremo più in dettaglio nel capitolo 3.
Nella seconda parte della Tesi, capitolo 13, espanderemo il modello proposto in [Marvel et al, 2012] per modellare il panorama politico Italiano che prevede tre fazioni in conflitto e vedremo se anche in questo caso le tecniche proposte consentono ai moderati di sopravvivere.
Capitolo 2
Formalismi alla base dello strumento Visual SPiM
In questo capitolo presenteremo più dettagliatamente i formalismi che hanno permesso l'ideazione del tool grafico Visual SPiM creato da Andrew Phillips e Luca Cardelli nel 2007 [Phillips & Cardelli, 2007] .
Questo tool è stato progettato esplicitamente per poter creare e visualizzare graficamente (creando automaticamente il grafo dal testo del programma e viceversa) modelli di sistemi biologici su cui poter effettuare simulazioni stocastiche, e sfrutta la potenza del π-calcolo (che permette di dimostrare formalmente la correttezza dei processi in parallelo che si scambiano messaggi) esteso con l'algoritmo SSA di Gillespie (che regola in modo formale la scelta di un azione tra possibili alternative).
È quindi lo strumento adatto per modellare il comportamento della classe di problemi che stiamo trattando in questo elaborato in quanto ogni elemento della popolazione può essere rappresentato da un processo che procede in parallelo e che cambia stato (o classe di appartenenza) in risposta ad un eventuale messaggio che riceve dall'ambiente o ad un altro processo.
Il π-calcolo è un estensione del CCS, Calculus for Communicating System, quindi presentiamo prima questo formalismo, per capire meglio i concetti di base, e successivamente lo estenderemo fino a inglobare le variabili aleatorie e il calcolo delle probabilità.
2.1.1 : Il CCS Calculus for Communicating System
Questo formalismo è stato ideato da Robin Milner negli anni '80 [Milner, 1980] per dare una specifica ai sistemi concorrenti e distribuiti che si scambiano messaggi attraverso canali di comunicazione.
Astraendo su cosa calcolano i processi e sul tipo di messaggi che si possono scambiare il CCS si concentra sull'effetto che la ricezione /trasmissione del
segnale/messaggio causa al processo stesso (transizione da uno stato ad un altro). Vediamo in dettaglio la sintassi del linguaggio:
Sia dato un insieme di canali di comunicazione etichettati con lettere greche minuscole
∆ ::= α | β | .. | ω
contrassegnare i canali in trasmissione (complementare due volte riporta alla condizione precedente).
Indichiamo con Λ l'insieme delle etichette utilizzate.
Λ⊂∆∪ ¯∆
Un Agente CCS è un termine ottenuto per composizione dalla grammatica in forma BNF che descrive i processi.
Un'azione generica (o mossa) viene descritta usando il formalismo LTS,
Labelled Transition System, e ha la forma P →μ Q dove P è il processo sorgente e
Q il processo obiettivo μ indica il tipo dell'azione.
Le azioni sono etichettate con τ per indicare una azione interna (o non visibile), con la stessa etichetta dei canali se sono azioni visibili
τ ∉ Λ
μ∈Λ∪{τ } azione generica (anche interna)
Una Traccia è la registrazione delle etichette di una delle possibili sequenza di azioni che un Agente CCS può fare per arrivare la processo obiettivo.
Traccia ( P →μ 1 P1 →μ 2 ... →μn Q ) = { μ1,μ2,.. ,μn}
I termini minimi (detti anche produzioni) per un generico processo P sono :
P ::= N | nil | μ.P | P+P | P|P | N:=P | P\λ | P[Φ]
dove :
N = {A,B,C,...} serve per dare un nome a un processo
nil è il processo nullo ( o terminazione)
Φ è una funzione di ridefinizione delle etichette dei canali in Λ (con α-conversioni) La semantica è data dalle seguenti regole di inferenza:
(Azione) __________ μ.P →μ P
P →μ Q P →μ Q (scelta) ______________ _______________ P+R →μ Q R+P →μ Q P →μ Q P →μ Q (parallelo) _____________ _____________ P|R →μ Q|R R|P →μ R|Q P →λ Q R →¯λ S (sincronizzazione) _________________________ P|R →τ Q|S P →μ Q R:=P (definizione) ___________________ R →μ Q P →μ Q (restrizione) _________________ μ≠α , ¯α P\α →μ Q\α P →λ Q
(ridefinizione) __________________ Φ(λ) funzione di ridefinizione di Λ P[Φ] →(Φ(λ)) Q[Φ]
Descriviamo più dettagliatamente queste regole di inferenza:
(azione) : è l'azione base , il processo esegue l'azione generica μ e diventa P
(scelta) : se il processo P può fare una mossa μ e diventare Q allora i processi P+R o R+P possono fare la stessa mossa e diventare Q , il processo R viene
scartato.
Questa scelta è puramente casuale.
(parallelo) : se il processo P può fare una mossa μ e diventare Q allora il processo
P|R (o R|P) può fare la stessa mossa e diventare Q|R (rispettivamente R|Q) e il processo R resta inattivo (o continua a fare operazioni interne).
(sincronizzazione): se il processo P è pronto a fare una mossa λ e diventare Q e contemporaneamente il processo R è pronto a fare la mossa complementare ¯λ e diventare S allora il processo P|R diventa
Q|S effettuando una mossa interna τ .
(definizione) : se il processo P può fare una mossa μ e diventare Q e se definiamo il processo con nome R come P allora il processo R può fare la stessa mossa μ e diventare Q. Da notare che se il nome del processo R sta in un sotto-termine guardato del processo P si ottiene la ricorsione. (esempio : R:= α.R+nil esegue l'azione α indefinitamente o termina) (restrizione) : se il processo P può fare una mossa μ e diventare Q allora il processo P\α può fare la stessa mossa e diventare Q\α se μ≠α , ¯α
Questo ha l'effetto di nascondere il canale α.
(ridefinizione) : se il processo P può fare una mossa visibile λ e diventare Q allora il processo P[Φ] può fare la mossa ottenuta da Φ(λ) e diventare Q[Φ]. Con P[Φ] si intende il processo in cui ogni occorrenza delle
etichette modificate dalla funzione [Φ] vengono sostituite in P. Questo ha l'effetto di cambiare le etichette dei canali, per esempio il processo P[ ω/ α, γ/ β] \ ω\ γ cambia ogni occorrenza dell'etichetta del canale α in P con ω, e ogni occorrenza dell'etichetta del canale β in P con γ e nasconde i nuovi canali.
Con questo meccanismo si possono creare canali privati tra processi.
2.1.2 Il Pi-Calcolo
Il Pi-Calcolo è una estensione del CCS proposta da Robin Milner, Joachim Parrow e David Walker nel 1992 [Milner et al, 1992] per dare un formalismo capace di descrivere e analizzare i sistemi mobili cioè sistemi concorrenti e distribuiti che si scambiano messaggi e che possono cambiare la configurazione della rete di
Rispetto al CCS quello che cambia è il concetto di messaggio che può essere inviato lungo un canale di comunicazione che ora può essere il nome stesso di un canale.
Quindi sono previsti costrutti per dare dei nomi ai canali, per crearne di nuovi, e per condividerli, questo permette di ampliare la rete di comunicazione dando la possibilità ai sottotermini di un processo di sincronizzarsi su un canale interno o non visibile dopo che il nome del canale è stato inviato in una precedente
sincronizzazione.
L'introduzione di nuovi nomi può creare problemi se questi sono già stati utilizzati in sotto-termini quindi è necessario considerare l'insieme dei nomi liberi e l'insieme dei nomi legati per ogni termine.
Questi insiemi si ottengono per induzione sui sotto-termini. Vediamo come cambia la sintassi del CCS :
I canali di comunicazione ora sono nomi indicati da lettere greche minuscole ∆ ::= α | β | .. | ω
e con l'operatore complemento per indicare un canale in trasmissione. L'azione generica visibile λ è ora una coppia di nomi :
x indica il nome del generico canale di comunicazione y indica il nome oggetto della comunicazione
x ( y) indica la ricezione dal canale x di un nome che viene legato al nome y
¯x⟨ y ⟩ indica la trasmissione dal canale x del nome y
τ azione interna
μ = {x ( y ), ¯x ⟨ y⟩}∪{τ } azione generica. Modifichiamo la grammatica del CCS :
P ::= N | nil | P+P | P|P | x ( y) .P | ¯x ⟨ y ⟩ .P | (υx) P | !P
dove :
x ( y) .P = riceve dal canale x un nome e lo lega al nome y e poi diventa P
¯
x ⟨ y ⟩ .P = trasmette dal canale x il nome y e poi diventa P
(υx ) P = crea un nuovo nome x che sarà legato in P !P = ripete una copia del processo P.
Congruenze strutturali :
La nozione di congruenza strutturale è fondamentale sia per la semantica di riduzione che per la semantica di transizione etichettata LTS.
Due processi sono strutturalmente congruenti, se sono identici fino alla struttura.
Per esempio, la composizione parallela è commutativa e associativa.
Più precisamente, la congruenza strutturale è definita come la minima relazione di equivalenza che si conserva con la composizione dei sotto-termini e che soddisfa i seguenti assiomi:
α-conversioni :
P ≡ Q se Q può essere ottenuto da P rinominando uno o più nomi legati in P.
assiomi per la composizione parallela:
P|Q ≡ Q|P
(P|Q)|R ≡ P|(Q|R) P|nil ≡ P
assiomi per la restrizione:
(υx)(υy)P ≡ (υy)(υx)P (υx)nil ≡ nil
assioma per la ripetizione:
!P ≡ P|!P
assioma per la relazione tra restrizione e composizione parallela:
(υx)(P|Q) ≡ (υx)P|Q se x non è un nome libero di Q
Questo ultimo assioma è noto come l'assioma "estensione del campo di
applicazione", ed è fondamentale, in quanto descrive come il nuovo nome x legato in P può essere spedito da una successiva azione di sincronizzazione, causando
l'estensione del campo di applicazione di x, consentendo quindi una possibile sincronizzazione con Q.
Nei casi in cui x è un nome libero di Q, può essere utilizzata un α-conversione per consentire la prosecuzione del processo.
Vediamo la semantica con le nuove regole di inferenza:
(Azione) _______________ _________________ x ( y) .P →x( y ) P ¯x⟨ y ⟩ .P →( ¯x⟨ y ⟩) P
P →μ Q P →μ Q (scelta) ______________ _______________ P+R →μ Q R+P →μ Q P →μ Q P →μ Q (parallelo) _____________ _____________ P|R →μ Q|R R|P →μ R|Q x ( y) .P →x( y ) P ¯x⟨ z ⟩ .Q →( ¯x⟨ z⟩) Q (sincronizzazione) _________________________________ x ( y) .P | ¯x⟨ z ⟩ .Q →τ P[z/y]|Q
Nella sincronizzazione P[z/y] denota il processo P in cui il nome libero z sostituisce ogni occorrenza del nome legato y in P.
Se un occorrenza di y si verifica in P in un sotto-termine in cui z non sarebbe un nome libero, può essere necessaria un α-conversione.
Ecco un piccolo esempio di un processo che consiste di tre componenti parallele e una scelta.
Il nome del canale α è conosciuto solo dai primi due componenti.
(υα )( α ⟨ β ⟩¯ . nil | (α(γ) . γ ⟨α⟩¯ . α(γ) . nil)+(α(ε) . ¯ε⟨ α⟩ .α(ε).nil)) | β(δ). δ ⟨δ ⟩¯ .nil
Le prime due componenti sono in grado di comunicare sul canale α, si può scegliere in modo casuale quale strada seguire o passando per il canale γ o per il canale ε , scegliamo γ ,viene trasmesso con una sincronizzazione il nome β che va a sostituire ogni nome legato γ nel sotto-termine (facendo attenzione che in α(γ) il nome γ non va sostituito con β in quanto è un nome libero definito in un ambito interno) .
La riduzione successiva del processo è quindi
(υα )( nil | ¯β ⟨α ⟩ . α(γ) . nil ) | β(δ). δ ⟨δ ⟩¯ .nil
Il secondo e terzo componente del parallelo possono ora comunicare attraverso il canale β e si passano il nome del canale α con un altra sincronizzazione, il nome viene legato a δ e ogni occorrenza del nome legato δ nel sotto-termine viene sostituito con α.
La riduzione successiva del processo è ora
(υα )( nil | α(γ) . nil | α ⟨α ⟩¯ .nil )
Va notato che, poiché il nome locale α è stato trasmesso nelle precedenti sincronizzazioni , il campo di applicazione di α è stato esteso al terzo componente del parallelo che inizialmente non conosceva. Infine, il canale α può essere utilizzato per inviare il nome α .
Dopo l'ultima sincronizzazione il processo termina con (υα )( nil | nil | nil )
2.1.3 : L'algoritmo di simulazione stocastica di Gillespie
L'algoritmo di simulazione stocastica di Gillespie o SSA ,Stochastic Simulation Algorithm, è stato proposto nel 1977 da Dan Gillespie [Gillespie , 1977] per
descrivere in modo formale (esatto) il comportamento di un sistema di reazioni chimiche.
Descriviamo il problema e il procedimento seguito.
Il sistema è formato da un recipiente di volume V in cui avvengono collisioni casuali di N specie diverse di molecole chimiche S1 , .. , SN che possono reagire
in M modi diversi attraverso elementari canali di reazione R1 , .. , RM .
Inizialmente il sistema è in equilibrio termico e possiamo assumere che le molecole sono distribuite uniformemente all'interno di V
Assumiamo che la reazione RJ sia un singolo istantaneo evento fisico dei tipi base
unimolecolare Si →Rj qualcosa
(decadimento spontaneo , o reazione indotta dall'esterno (aumento temperatura)) bimolecolare Si + Sj →Rz qualcos'altro
(reazione dovuta dalla collisione di due molecole)
che cambia la popolazione di almeno una singola specie in un determinato istante. Per esempio :
RJ : S1 + S2 →Rj 2 S2 (1)
la collisione di una molecola di tipo S1 con una di tipo S2 genera due molecole di tipo S2 quindi la popolazione S2 aumenta di uno ,la popolazione S1 diminuisce di uno.
Gli altri tipi di eventi (che comprendono cioè tre o più molecole) sono molto meno probabili e comunque si possono ottenere da combinazioni dei tipi base.
Definiamo il sistema come
dove nSi (t) è il numero delle molecole della specie Si al tempo t.
Per studiare come evolve nel tempo la popolazione all'interno di V è necessaria conoscere tre cose:
(1) Lo stato del sistema al tempo t S(t)
(2) Il tipo RJ della prossima reazione che avverrà nell'intervallo t+dt (3) L'effetto che questa reazione ha nel sistema
Definiamo con x un vettore che rappresenta lo stato del sistema al tempo t.
Definiamo con aJ(x) l'effetto che una reazione di tipo RJ apporta al sistema. Definiamo con aJ(x)dt la probabilità che una reazione di tipo RJ avverrà nell'intervallo di tempo t+dt.
Definiamo con ViJ la matrice stechiometrica dei cambiamenti di stato del
sistema S(t) formata da N righe che rappresentano le specie Si e M colonne che rappresentano i tipi di reazione RJ
Questa matrice è la codifica di tutte le reazioni del sistema, cioè per ognuna di queste aumento o diminuisce il numero delle molecole delle specie coinvolte.
Per l'esempio (1): RJ : S1 + S2 →Rj 2 S2 (1)
x1 = nS1 (t), x2 = nS2 (t)
vJ =(-1,1,0,..,0)
vJ ≡ ( v1 J .. vNJ ) è il vettore dei cambiamenti di stato causati da una reazione di tipo RJ
Allora RJ induce x → x + vJ
riprendiamo l'esempio (1):
S1 + S2 →Rj 2 S2 ; vJ =(-1,1,0,..,0), aJ(x)dt = ( cJdt )* x1x2
questo implica che aJ(x) = cjx1x2
x1x2 = tutte le possibili combinazioni tra le molecola delle specie coinvolte un altro esempio unimolecolare:
questo implica che aJ(x) = cJx1
Cioè l'effetto che una reazione di tipo RJ causa al sistema dipende da un
valore cJ tipico per ogni tipo di reazione e dal numero di tutte le possibili combinazioni di molecole interessate dalla reazione al tempo t.
Dobbiamo ricavare una formula per cJ .
Consideriamo il numero di collisioni reattive e non-reattive per istante di tempo.
Collisioni reattive = scontro frontale e a velocità elevata Collisioni non-reattive = scontro non frontale o a bassa velocità In questo modo possiamo semplificare i calcoli considerando che una
successiva collisione reattiva può avvenire solo dopo molte collisioni non-reattive. Vediamo in dettaglio le collisioni reattive:
per semplicità consideriamo le molecole s1 , s2 come sfere di raggio r1 , r2
che viaggiano l'una contro l'altra a velocità v12 e chiamiamo δ Vcoll il minimo
spazio di collisione sferico che contiene entrambe le sfere al tempo t , allora la collisione avviene quando
δ Vcoll = π r122 v12dt
con r12 = r1+r2
Quindi la probabilità che una qualsiasi collisione avviene nell'istante dt all'interno di V è data da:
Pcoll = δVcoll
V
La probabilità che il tipo di reazione causato dalla collisione sia di tipo
Rj ≡ Pj quindi Pcoll * Pj è la probabilità che una reazione di tipo Rj avvenga nell'intervallo di tempo t+dt
Per l'esempio bimolecolare abbiamo:
Rj : S1 + S2 →Rj 2 S2 ; x = ( x1 , x2 ,..) ; x1 = nS1 (t), x2 = nS2 (t) aJ(x)dt ≡ Pcoll * Pj = (π r12 2 v12dt) V * PJx1x2 = (π r12 2 v12Pj) V x1x2dt
chiamo cj = (π r122 v12Pj)
V questo implica Pcoll * Pj = cjx1x2dt
e quindi aJ(x)dt ≡ cjx1x2dt implica aJ(x) = cjx1x2
Questi risultati possono essere usati per ricavare la “Master Equation” che racchiude in un unica grande equazione differenziale la funzione di probabilità che il sistema si trovi in uno stato x = S(t) al variare di t partendo da uno stato iniziale S( t0 ) .
Il calcolo della “Master Equation” è molto complicato e diventa intrattabile al crescere della popolazione di elementi in quanto cresce esponenzialmente il numero di stati possibili che il sistema può raggiungere partendo da un determinato stato.
L'approccio delle simulazioni stocastiche è più semplice da calcolare in quanto segue un unica traccia di tutte le possibili traiettorie di scelta per passare da uno stato del sistema all'altro.
Vediamo ora l'idea alla base del algoritmo SSA di Gillespie: Definiamo
p(τ , j | x , t)dτ = la probabilità che dato il sistema S(t) = x al tempo t la prossima reazione avverrà nell'intervallo di tempo [t+ τ , t+ τ+dτ) e sarà di tipo Rj
S(t) = ( nS1 (t), nS2 (t),.., nSN (t) ) = x
p(τ , j | x , t)dτ = P0(τ ) * aJ(x)dt (1)
dove P0(τ ) è la probabilità che non è avvenuta nessuna reazione al tempo τ P0(τ +dτ) = P0(τ ) *( 1−a0(x)dτ ) (2)
è la probabili che nell'intervallo [ t+τ ,t+τ+dτ) non avvengano altre reazioni reattive dove a0(x ) =
∑
j=1 M
aj(x ) è la somma di tutte le combinazioni possibili generate da
tutte le reazioni fra tutte le molecole del sistema al tempo t moltiplicate per le rispettive costanti cinetiche.
Quindi a0(x )dτ è la probabilità che avvengano collisione reattive tra tutte le molecole al tempo τ.
( 1−a0(x)dτ ) è la probabilità complementare cioè che non avvengano reazioni attive
Derivando la (2) per dτ si ha: (∂ P0(τ +dτ)) (∂ τ) = - a0(x ) P0(τ ) ricaviamo P0(τ ) la soluzione è P0(τ ) = e−(ao(x)τ) sostituendo nella (1) p(τ , j | x , t) = e−(ao(x)τ) * a j(x) = a0(x ) e −(ao(x)τ) * (aj(x )) (a0(x ))
in questo modo τ è una variabile aleatoria continua esponenziale con media 1
(a0(x ))
j è una variabile aleatoria discreta con probabilità (aj(x ))
(a0(x ))
L'algoritmo è formato da quattro passi
1 : dato i sistema S(t) = x al tempo t calcolare a1(x ), a2(x ),.. , aM(x)
e calcolare a0 (x) =
∑
j=1 M
aj(x )
2 : generare una coppia uniforme di numeri casuali n1 , n2 nell'intervallo (0,1) tali che 0< n1 <1 , 0< n2 <1 e calcolare
τ = 1
(a0(x ))
ln( 1
n1
)
j = il minimo intero tale che
∑
k=1 j
ak(x) > n2a0(x )
calcolare p(τ , j | x , t)
3 : aggiornare il tempo t ← t + τ , e il nuovo stato del sistema x ← x + vJ
4 : Tornare al passo 1 o terminare la simulazione.
L'algoritmo SSA è esatto in quanto ottenuto da operazioni matematiche, è calcolabile ed è applicabile a una più ampia classe di problemi rispetto alla “Master Equation”.
Non approssima l'intervallo di tempo dt come succede con le equazioni differenziali.
Resta comunque lento se il sistema è di grosse dimensioni, per questo sono state studiate delle varianti che, con opportune approssimazioni, velocizzano il procedimento.
2.2 : Il linguaggio di programmazione SPiM Stochastic Pi-calculus Machine
Vediamo ora come il formalismo π-calcolo è stato esteso per riuscire a modellare il comportamento stocastico degli eventi che possono avvenire in un sistema.
Come accennato nell'introduzione ogni azione lungo un canale di
comunicazione genera dei ritardi stocastici che possono influenzare l'andamento del sistema nel tempo in quanto modificano le possibili scelte tra i sotto-processi, e le possibili sincronizzazioni.
Per poter rappresentare questi ritardi ogni canale di comunicazione avrà associato un rate cioè un variabile aleatoria che indica il tasso di interazione e che servirà per determinare la probabilità della scelta di quel canale rispetto ad altre possibilità.
Questa scelta verrà determinata dall'applicazione dell'algoritmo SSA o sue varianti, che determinerà anche il tempo necessario per la transizione (il ritardo).
Modifichiamo la sintassi del π-calcolo introducendo il rate per ogni azione: Mostriamo brevemente la sintassi proposta da Cardelli e Radu
[Cardelli & Radu, 2012].
I canali di comunicazione ora sono nomi indicati da lettere greche minuscole
∆ ::= α | β | .. | ω
e con l'operatore complemento per indicare un canale in trasmissione. L'azione generica visibile λ è ora una coppia di nomi :
x indica il nome del generico canale di comunicazione y indica il nome oggetto della comunicazione
x ( y) indica la ricezione dal canale x di un nome che viene legato al nome y
¯x⟨ y ⟩ indica la trasmissione dal canale x del nome y
τ azione interna
μ = {x ( y ), ¯x ⟨ y ⟩}∪{τ } azione generica.
r è il rate associato ai canali di comunicazione
r ∈ℚ
I termini minimi per un generico processo P diventano :
P ::= nil | P+P | P|P | a.P | (x@r)P | (υx)P | !P
a ::= x ( y) | ¯x ⟨ y ⟩
Le regole di congruenze strutturali: 1: P |Q ≡ Q|P 2: (P|Q)|R ≡ P|(Q|R) 3: P|nil ≡P 4: P+Q ≡ Q+P 5: (P+Q)+R ≡ P+(Q+R) 6: P+P ≡ P
Se P ≡ Q allora P|R ≡ Q|R , P+R ≡ Q+R , a.P ≡ a.Q , (x@r)P ≡ (x@r)Q , !P ≡ !Q Se x ≠ z allora (x@r)(z@r)P ≡ (z@r)(x@r)P , (x@r)nil ≡ nil
Se x non è un nome libero di P allora (x@r)(P|Q) ≡ P|(x@r)Q e (x@r)(P+Q) ≡ P+(x@r)Q
!nil ≡ nil !(P|Q) ≡ !P | !Q (x@r)P ≡ (z@r)P[z/x]
Il rate associato ai canali dipende dal Ambiente: E ::= ε | E,x@r
e viene calcolato il rate apparente per ogni azione in un determinato ambiente. Vediamo ora come tutti questi formalismi sono stati implementati nel linguaggio di programmazione SPiM.
Nella dichiarazioni dei canali di comunicazione è possibile specificare il rate : new Name {@ Value }: Type
Crea un nuovo canale con rate dato da Value (opzionale ) e del tipo Channel e lo associa al nome Name .
Il rate è un numero in virgola mobile, e rappresenta il tasso di interazione del canale, se non specificato si considera infinito.
Nella dichiarazione dei processi c'è la possibilità di dichiarare un azione seguita da un eventuale processo, del parallelo tra due o più processi, della scelta tra due o più processi e la ripetizione di un numero intero di processi.
Composizione parallela :
( Process1 | . . | Processn )
Azione :
Action {; Process }
Tenta di eseguire l'azione Action e poi esegue il processo Process , se nessun processo viene specificato dopo l'azione allora termina l'esecuzione.
Scelta :
do Action1 {; Process1 } or . . or Actionn {; Processn }
Tenta di eseguire una tra due o più azioni che sono in competizione tra loro contemporaneamente. Una volta scelta l'azione Actioni le altre vengono scartate ed eseguita l'azione viene eseguito l'eventuale processo associato Processi .
Se nessun processo è associato all'azione scelta allora termina l'esecuzione.
Ripetizione :
Integer of Process
Esegue zero o più coppie del dato processo Process contemporaneamente, specificato dal numero intero dato Integer .
Le azioni possono essere: un ritardo stocastico, la trasmissione/ricezione per un dato canale di una lista di valori (opzionale) con possibilità di modificare localmente il rate basico del canale.
Action ::= delay@ Value
| !Channel {( Value1 ,.., Valuen )}{* Value } | ? Channel {( Pattern1 ,.., Patternn )}{* Value } Ritardo :
delay@ Value {; Process }
Aspetta un periodo di tempo calcolato in modo stocastico in relazione al valore dato Value , e dopo esegue l'eventuale prossimo processo.
Trasmissione :
Tenta di spedire zero o più valori nel canale specificato Channel .
Se esistono uno o più processi in parallelo che sono in ascolto nello stesso canale Channel allora può avvenire la sincronizzazione e i valori vengono spediti, e
dopo viene eseguito l'eventuale prossimo processo.
Il rate basico del canale può essere moltiplicato per un dato valore Value . In questo modo si può modificare localmente il tasso di interazione del canale durante la simulazione, per influenzare la scelta del processo con cui sincronizzarsi. Ricezione :
? Channel {( Pattern1 ,.., Patternn )}{* Value }{; Process } Tenta di ricevere zero o più valori nel canale specificato Channel .
Se esistono uno o più processi in parallelo che sono pronti a trasmettere nello stesso canale Channel allora può avvenire la sincronizzazione e i valori ricevuti
vengono assegnati ai rispettivi Pattern , e dopo viene eseguito l'eventuale prossimo
processo.
Il rate basico del canale può essere moltiplicato per un dato valore Value . La sincronizzazione tra due processi in parallelo per ogni canale di
comunicazione viene vista come una reazione e la scelta tra più alternative viene calcolata dal algoritmo SSA di Gillespie.
Per una più ampia visione della sintassi del linguaggio si può consultare l'appendice B.
2.3 : Il tool grafico Visual SpiM
Introduciamo le caratteristiche principali del tool grafico Visual SPiM
figura 2.3.1 : Finestra principale di Visual SPiM
La finestra principale, come mostra la figura 2.3.1, è suddivisa in due sezioni, la parte a sinistra per l'inserimento del modello (in formato testo o grafico), la parte a destra per i risultati della compilazione ed esecuzione del modello.
La sezione inserimento è formata da due sottosezioni denominate code e
graph.
La sezione code è un normale Editor di testi dove poter inserire il codice dei programmi e prevede i consueti pulsanti, new per creare un nuovo programma, Load per caricare un programma precedentemente salvato, save per salvare un programma, i pulsanti find e replace per cercare una stringa all'interno del testo ed eventualmente sostituirla con un'altra stringa, i pulsanti cut, copy, past e delete per modificare il testo, i pulsanti undo, redo per annullare l'ultima modifica o ripristinarla, i pulsanti
outdent, indent, line number per l'indentazione del testo e per mostrare il numero
Figura 2.3.2 sezione graph
La sezione graph, come mostra la figura 2.3.2, è formata da due sottosezioni
directive e graph.
Agendo sul tasto text to graph del menù principale, tutte le direttive e i dati del programma vengono riportati automaticamente nella sezione directive e viene creato automaticamente il grafo del modello visibile nella sottosezione graph.
Tutti i dati nella sezione directive possono essere modificati per eventuali successive simulazioni, o per modificare il modello stesso, e queste modifiche
possono essere rese definitive agendo sul tasto graph to text del menù principale che le riporta nel testo del programma.
Anche il grafo può essere modificato, cambiandone l'aspetto visivo spostando gli elementi e/o gli archi, o modificando il modello creando nuovi elementi e/o nuovi archi, e rendere effettive le modifiche riportandole nel formato testo.
L'intero modello può essere inserito direttamente in modo grafico e
successivamente ottenere il codice automaticamente con il tasto graph to text per poterlo salvare.
Il programma viene compilato agendo sul tasto built e se non vengono riscontrati errori tipo può essere eseguito agendo sul tasto simulate.
La sezione a destra nella finestra principale e suddivisa in quattro sottosezioni denominate reaction, table, plot, debug .
Ad ogni simulazione in queste sezioni vengono riportati i risultati ottenuti nei rispettivi formati.
Per la sezione reaction vengono riportati i tipi di reazioni avvenute nella simulazione in formato “lista di transizioni etichettate” nella sezione list, in formato tabella nella sezione table, in formato grafico nella sezione graph, in formato SBML System Biology Markup Language nella sezione SBML.
Per la sezione table vengono riportati i risultati numerici in formato .csv
(comma separate value) e inseriti nella tabella ad iniziare dal tempo di simulazione e seguito dai nomi dei processi o canali registrati.
La sezione plot mostra il grafico della simulazione con colori diversi per ogni tipo di processo o canale registrato, permette di modificare questi colori e nascondere o mostrare il singolo grafico di ogni registrazione.
La sezione debug mostra il risultato della compilazione.
Nel menù principale sono presenti anche altri tre pulsanti pause, resume, step che consentono di fermare una simulazione , farla ripartire o procedere un passo alla volta.
Sono riportati anche una serie di esempi di modelli chimici , biochimici e biologici scritti in SPiM, di complessità crescente per mostrare le potenzialità del linguaggio.
Si possono caricare agendo sul pulsante examples e scorrendo il menù a cascata.
Nelle figure successive mostreremo il semplice esempio Lotka1 che descrive il modello “curva di Lotka-Volterra”, dove la preda Y1 si moltiplica se mangiano il cibo X, o muore se mangiata da un predatore, il predatore Y2 si moltiplica se mangia una preda Y1 o muore di vecchiaia.
figura 2.3.3 : esempio lokta1 programma e simulazione
Nella figura 2.3.3 si può vedere a sinistra il programma in formato testo e a destra il risultato della simulazione in formato grafico.
figura 2.3.4 : esempio Lokta1, sezione directive
La figura 2.3.4 mostra la sottosezione directive della sezione graph, dove sono stati riportati automaticamente tutti i dati del programma utilizzando il tasto text to
figura 2.3.5 : esempio lokta1 grafo
La figura 2.3.5 mostra la sottosezione graph della sezione graph dove viene visualizzato il grafo del modello.
figura 2.3.6 : esempio lokta1 lista reazioni
La figura 2.3.6 mostra la sottosezione list della sezione reaction dove viene riportata la lista del tipo delle reazioni avvenute ,in formato transizioni etichettate.
Figura 2.3.7 : esempio lokta1 tabella reazioni
La figura 2.3.7 mostra la sottosezione table della sezione reaction dove vengono riportati i tipi di reazioni in formato tabella.
figura 2.3.8 : esempio lokta1 , grafo delle reazioni
La figura 2.3.8 mostra la sottosezione graph della sezione reaction che riporta il tipo di reazioni in formato grafico o grafo delle reazioni.
figura 2.3.9 : esempio lokta1 reazioni in formato SBML
La figura 2.3.9 mostra la sottosezione SBML della sezione reaction dove viene generato automaticamente il listato in SBML delle reazioni del modello.
Figura 2.3.10 : esempio lokta1 tabulato risultati numerici
La figura 2.3.10 mostra la sezione table dove vengono riportati i risultati numerici per ogni passo di tempo di ogni processo o canale registrato.
Figura 2.3.11 : esempio lokta1 risultati debug
La figura 2.3.11 mostra la sezione debug con i risultati del debug del programma.
Capitolo 3
Il caso di studio in esame
Esaminiamo più accuratamente i contenuti della pubblicazione scientifica proposta da Seth A. Marvel e altri nel 2012 [Marvel et al, 2012].
Nella prefazione si legge:
“Alcuni dei momenti più cruciali della storia intellettuale si verificano quando una nuova ideologia spazia attraverso una società, soppiantando un sistema stabilito di credenze in una rapida rivoluzione di pensiero.
Ma in molti casi la nuova ideologia è cosi estrema come la vecchia. Come mai è allora che le posizioni moderate prevalgono cosi raramente? Qui, nel contesto di un semplice modello di opinione diffuso, testiamo sette strategie plausibili per de-radicalizzare una società e scoprire che in un solo caso la sotto-popolazione moderata si espande in modo significativo senza rischiare la sua estinzione nel processo.”
Nel lungo corso della storia sociale si sono verificate diverse rivoluzioni Ideologiche e tutte hanno in comune lo stesso andamento.
Inizialmente c'è un periodo di stabilità dove la popolazione accetta e giustifica l'Ideologia corrente che serve alle istituzioni comunitarie per governare le pratiche comuni.
Poi un piccolo gruppo di incrollabili sostenitori di una nuova dottrina emerge dalla massa e inizia a convertire costantemente una porzione della popolazione.
Se la nuova ideologia ha presa nella popolazione, tanto da aumentare il gruppo di sostenitori, si arriva ad una situazione di criticità e alla inevitabile “rivoluzione” che finisce per soppiantare la vecchia ideologia.
In qualche caso la nuova situazione porta notevoli miglioramenti rispetto alla precedente e in questi casi il consenso è molto più duraturo.
Negli altri casi la nuova ideologia è talmente estremista come la precedente tanto che l'intero procedimento si ripete più frequentemente con l'arrivo di nuove, giovani e alternative dottrine.
In [Marvel et al, 2013] si concentrano su questo ultimo aspetto cioè quando a confrontarsi sono due “ideologie estremiste” e le domande che si sono posti sono :
“Come mai le comunità, e a volte intere società, attraversano queste oscillazioni da un estremo ideologico all'altro quando se ne offre loro una soluzione sostenibile?
Come mai la popolazione dei moderati non riesce a prevalere tra le due ideologie estremiste cercando di fondere il meglio di entrambe ?”
Per rispondere a queste domande [Marvel et al, 2012] hanno utilizzato l'approccio puramente matematico:
“L' ambiente delle successive rivoluzioni ideologiche non è favorevole alla moderazione mentale semplicemente dal punto di vista dinamico.
In particolare, quasi tutte le modalità intuitive di incoraggiare la moderazione o non riescono ad espandere la sotto-popolazione moderata o la rendono vulnerabile a comprimersi nel processo di incoraggiarne la crescita.”
Per dare una prova a questa affermazione hanno studiato il comportamento di un semplice “modello minimo di rivoluzione ideologica”.
Ovviamente questo semplice modello non ha le pretese di rappresentare tutte le possibili situazioni che si possono riscontrare in una comunità reale, come apparenti conversioni all'interno della vecchia dottrina o situazioni in qui non vi è alcuna conversione ma una divisione di opinioni o altre situazioni ancora, ma si concentra solo su conversioni ideologiche su larga scala.
Esaminiamo ora il modello proposto rappresentato dal grafo in figura 3.1 :
Figura 3.1
La popolazione viene suddivisa in quattro insiemi disgiunti :
C
: sotto-popolazione di attivisti integerrimi fautori della nuova ideologia estremista, non influenzabili da altre opinioni ( chiamati anche “zeloti”).AB
: sotto-popolazione di individui che non tengono né per A né per B, i moderati.B
: sotto-popolazione che sostiene la vecchia ideologia estremista, concettualmente l'opinione opposta o semplicemente la negazione dell'ideologia A.-x-> : l'arco orientato ed etichettato indica l'effetto su chi ascolta , per esempio
“a ascolta b diventa ab”, l'etichetta indica l'oratore.
Indicheremo con le lettere maiuscole le intere sotto-popolazioni e con le rispettive lettere minuscole i singoli individui di ciascuna di esse.
Questo modello si basa su un precedente lavoro pionieristico nella socio-fisica e si ispira direttamente (ma è diverso da) un modello esaminato in un recente studio sulla dinamica di opinione.
Esaminiamo le dinamiche del modello base:
Il tempo varia in modo discreto e ad ogni passo si suddivide l'intera popolazione in coppie di individui in maniera uniforme e casuale.
Per ogni coppia di individui si decide, sempre in maniera casuale, chi è l'oratore e chi l'ascoltatore.
Si possono verificare le seguenti condizioni:
1 : Se l'oratore è un individuo A (oppure B) e l'ascoltatore è un individuo B
(rispettivamente A) allora quest'ultimo viene persuaso a lasciare la sua posizione estremista e diventa un moderato AB.
2 : Se l'oratore è un individuo A (oppure B) e l'ascoltatore è un individuo AB (un moderato) allora quest'ultimo viene convertito e diventa un estremista A ( o B rispettivamente).
3 : Se l'oratore è un individuo C e l'ascoltatore è un individuo B quest'ultimo diventa un moderato AB.
4 : Se l'oratore è un individuo C e l'ascoltatore è un individuo moderato AB quest'ultimo viene convertito e diventa un estremista A.
Negli altri casi che si possono verificare, quando un individuo parla con un altro individuo della stessa sotto-popolazione o quando a parlare è un moderato o quando un individuo B parla ad un zelota C che non cambia mai idea, non vi è nessun cambiamento in chi ascolta.
ORATORE ASCOLTATORE Effetto sull'ascoltatore A A nessuno A B B diventa AB A C nessuno A AB AB diventa A B A A diventa AB B B nessuno B C nessuno B AB AB diventa B C A nessuno C B B diventa AB C C nessuno C AB AB diventa A AB A,B,C,AB nessuno Tabella 3.1
Per poter modellare le dinamiche appena descritte dal punto di vista
matematico in [Marvel et al, 2013] le hanno approssimate come: deterministiche, continue in un “campo medio” e derivate dal limite di grandi popolazioni.
La teoria del campo medio, sviluppata da Pierre Weiss nel 1907
[Weiss, 1907] per studiare il comportamento ferromagnetico dei materiali, si adatta perfettamente allo studio di fenomeni di transizioni di stato, come questo in esame, e permette di ottenere semplici equazioni sotto opportune semplificazioni.
Partendo da determinate condizioni iniziali l'andamento nel tempo del sistema risulta quindi deterministico nel senso che dalle stesse condizioni iniziali si arriva alla stesse condizioni di equilibrio stabile finali, e [Marvel et al, 2013] hanno studiato come variando queste condizioni iniziali, nello specifico aumentando la
sotto-popolazione C degli zeloti della nuova ideologia, variano sensibilmente le condizioni di equilibrio finali.
Con queste approssimazioni è possibile modellare le dinamiche del modello con il seguente sistema di equazioni differenziali:
(nA)' = (p + (nA))*(nAB) – (nA)*(nB)
(nB)' = (nB)*(nAB) – (p + (nA))*(nB) (1)
Dove nA indica la frazione della sotto-popolazione A rispetto alla popolazione totale, nB la rispettiva frazione della sotto-popolazione B, p la frazione degli zeloti e
nAB quella dei moderati, ( )' indica l'operatore differenziale rispetto al Tempo t.
Per la terza variabile nAB si ha la seguente semplice equazione lineare : (nAB) = 1 – p – (nA) – (nB)
Vedendo più in dettaglio il sistema si afferma che, considerando 1 la totalità della popolazione (1 = #N/#N dove #N indica la cardinalità dell'intera popolazione), la frazione della sotto-popolazione nA ( nA = #A/#N) cresce, nel tempo,
proporzionalmente del fattore dato dallasomma tra la frazione degli zeloti p ed essa stessa per la frazione dei moderati nAB, e decresce proporzionalmente del fattore dato del prodotto della frazione della sotto-popolazione nB per essa stessa per ogni istante di tempo.
La frazione della sotto-popolazione nB cresce, nel tempo, proporzionalmente del fattore del prodotto della frazione dei moderati nAB per essa stessa e decresce proporzionalmente del fattore del prodotto tra la somma della frazione degli zeloti p e la frazione della sotto-popolazione nA per essa stessa per ogni istante di tempo.
La frazione dei moderati è ottenuta per differenza tra la totalità della
popolazione, che è pari ad 1, e le altre frazioni delle sotto-popolazioni p, nA e nB per ogni istante di tempo.
Tutte le frazioni delle sotto-popolazioni sono comprese tra 0, che indica l'insieme vuoto, e 1, che indica l'intera popolazione.
Le condizioni iniziali del sistema vedono individui della sotto-popolazione B dei sostenitori della vigente Ideologia ( nA e nAB = 0, nB = 1 - p), che inizialmente compongono l'intera popolazione (quindi al tempo t=0 p, nA e nAB = 0), ed il
piccolo gruppo degli zeloti della nuova ideologia emergente indicato dal parametro p (inizialmente uguale a zero e cresce fino ad 1).
In [Marvel et al, 2012] è stato osservato che per valori bassi del parametro p le condizioni di equilibrio del sistema variano poco cioè la maggioranza della
popolazione continua a sostenere la vigente Ideologia B e si registra una minima crescita delle sotto-popolazioni dei moderati AB e dei sostenitori della nuova Ideologia A, proposta dal piccolo gruppo costante degli zeloti C.
Ma aumentando questo gruppo degli zeloti, cioè aumentando il parametro p, fino ad arrivare ad un valore critico, che hanno chiamato pc, l'equilibrio del sistema cambia drasticamente, quasi in maniera discontinua.
Chiameremo questo fenomeno “rivoluzione” perché si verifica una crescita repentina della sotto-popolazione A e l'azzeramento totale delle sotto-popolazioni dei moderati AB e dei sostenitori della vecchia ideologia B.
Con uno studio analitico sul grafico ottenuto dalle simulazioni e sul sistema di equazioni differenziali è stato calcolato che il punto di criticità pc = 1 - √3/2 ≈ 0,134.
La figura 3.2 mostra il grafico, inserito in [Marvel et al, 2012], dell'andamento delle frazioni delle sotto-popolazioni nA, nB, nAB in funzione del parametro p.
Figura 3.2 : Grafico Legenda :
linea rossa stellata sotto-popolazione A
linea blu con pallini pieni sotto-popolazione B
linea magenta con pallini vuoti sotto-popolazione AB
Per testare la bontà e la robustezza di questi risultati, ottenuti per simulazione al computer del sistema di equazioni differenziali (1), sono state fatte delle nuove simulazioni del modello base utilizzando delle reali reti di comunicazione e dei social network:
La grande rete che collega i componenti dei Consigli di Amministrazione delle Imprese degli Stati Uniti nel 1994 (a), quattro reti appartenenti alla divisione per la fisica del arXiv.org (b) e due social network per interscambi di amicizie Gowalla e Brightkite (c), purtroppo in [Marvel et al ,2012] non viene specificato il
procedimento seguito per queste ulteriori prove.
figura 3.3 : Grafici delle Simulazioni su Reti e Social Network Nei grafici viene riportato solo l'andamento della frazione della sotto-popolazione nB in funzione del parametro p ed, in tutti i casi, è evidente la somiglianza con i risultati del grafico in figura 3.2.
Le uniche differenza, comuni in tutte queste nuove simulazioni, sono un valore inferiore del punto critico pc reale rispetto a quello calcolato nel modello matematico e una piccola frazione stabile di sostenitori della vecchia ideologia B che resiste anche dopo la rivoluzione.
Utilizzando il sistema di equazioni differenziali (1) come punto di partenza si sono chiesti come si potrebbe modificare il modello base per incoraggiare la
moderazione, in particolare si vorrebbe :
(I) Aumentare la dimensione di equilibrio della sotto-popolazione dei moderati.
(II) Diminuire la probabilità che questa dimensione di equilibrio possa scendere sensibilmente se il parametro di riferimento
(solo p per il modello base ) variasse un poco.
Alla ricerca di una strategia che soddisfi entrambi gli obiettivi
[Marvel et al, 2012] hanno esplorato sette diverse generalizzazioni del modello base.
Primo tentativo.
Come primo tentativo per realizzare i punti (I) e (II) in [Marvel et al, 2012] hanno pensato di rendere i moderati più “testardi” cioè fare in modo che abbiano meno probabilità di essere convertiti in una delle due posizioni radicali da parte degli estremisti.
Per modellare questo nuovo comportamento è stato introdotto il parametro s nel sistema di equazioni differenziali (1) che diventa:
(nA)' = (1 - s)*(p + (nA))*(nAB) – (nA)*(nB)
(nB)' = (1 - s)*(nB)*(nAB) – (p + (nA))*(nB) (2) (nAB) = 1 – p – (nA) – (nB)
Il parametro s indica la “testardaggine” dei moderati a restare nella stessa posizione ideologica anche dopo l'ascolto di un estremista cioè aumentando il parametro s si aumenta la probabilità che questo avvenga.
Per s = 0 si ha il sistema base, al crescere di s fino ad un massimo di 1
intuitivamente ci si aspetterebbe che la sotto-popolazione dei moderati crescesse in maniera sensibile, e questo è vero per bassi valori del parametro, ma quando s supera una certa soglia l'intera sotto-popolazione viene spinta verso l'estinzione, come nel modello base, con l'arrivo della rivoluzione.
Esaminando questo sorprendente comportamento si sono chiesti come il parametro s influenzi il parametro p quando questo si avvicina alla soglia di criticità
pc necessaria affinché avvenga la rivoluzione.
Intuitivamente ci si aspetterebbe che all'aumentare di s, cioè aumentando la testardaggine dei moderati e quindi aumentando la probabilità che resistano alla conversione, servirebbe un numero maggiore degli zeloti, cioè un valore di p maggiore di pc, per poterli convertire tutti.
Invece succede l'esatto opposto, il valore critico pc decresce all'aumentare di s in maniera monotona dal valore 1 - √3/2 per s = 0 fino a zero s = 1.
Quindi aumentare la testardaggine dei moderati rende questa popolazione più vulnerabile, tanto che sono necessari meno zeloti affinché avvenga la rivoluzione.
Questo succede perché con l'aumentare di s si riduce effettivamente il fluire dei moderati verso la sotto-popolazione A ma anche verso la sotto-popolazione B che si indebolisce e rende il lavoro degli zeloti più agevole.
Secondo tentativo.
Come secondo tentativo per incentivare la crescita della sotto-popolazione dei moderati [Marvel et al, 2012] hanno pensato di dargli la possibilità di parlare con gli estremisti delle sotto-popolazioni A e B per cercare di “evangelizzarli” e farli tornare a essere moderati.
Per modellare questo tentativo di promuovere attivamente la moderazione da parte dei moderati stessi il sistema di equazioni differenziali di base (1) è stato modificato introducendo un nuovo parametro r che rappresenta l'intensità dell'evangelizzazione.
