Modeling Algorithmic Bias in Opinion Dynamics: simplicial complexes, and evolving network topologies

UNIVERSIT `A DI PISA Dipartimento di Informatica

Corso di Laurea Magistrale in Data Science and Business Informatics

TESI DI LAUREA

MODELING ALGORITHMIC BIAS IN OPINION DYNAMICS: SIMPLICIAL COMPLEXES, AND EVOLVING NETWORK

TOPOLOGIES

RELATORI

Prof. Giulio ROSSETTI Dr. Letizia MILLI

CANDIDATO Valentina PANSANELLA

Sommario

Ad oggi, il modo in cui le persone interagiscono `e altamente influenzato dagli algoritmi di filtraggio che si trovano sugli online social networks, che selezionano le informazioni e gli utenti da mostrare al target, in base alla popolarit`a e alla vicinanza. Questo crea un bias algoritmico che influenza la realt`a che gli utenti possono vedere e con cui possono interagire e questo di crede che promuova la frammentazione la polarizzazione del dibattito sociale. Inoltre, gli utenti stessi tendono a creare legami con chi `e pi`u simile a loro e a romperli con chi `e troppo diverso. Infine, le persone interagiscono in gruppo, creano le condizioni per la peer-pressure. Per studiare l’influenza che questi elementi hanno sull’evoluzione delle opinioni degli individui, il presente lavoro comincia dallo studiare un modello di opinion dynamics che include l’algorithmic bias (AB-model) su reti random e scale-free; partendo da questo modello, sono stati creati e studiati diversi modelli che includono la peer-pressure; inoltre ad ogni modello `e stata poi aggiunta la possibilit`a di eseguire il rewiring degli archi. I risultati ottenuti per l’AB-model sono in linea con quelli del mean-feald, sottolineando per`o come tali reti contribuiscano ad aumentare la frammentazione gi`a creata dall’algorithmic bias. Le interazioni di gruppo con la peer-pressure, invece, sembrano spingere verso il consenso, al contrario di ci`o che si pensava inizialmente.

Indice

1 Introduzione 4

2 Stato dell’arte 8

2.1 Social Network Analysis . . . 8

2.1.1 Teoria dei grafi . . . 10

2.2 Opinion dynamics . . . 20

2.2.1 Modelli discreti . . . 22

2.2.2 Modelli continui . . . 23

2.2.3 Oltre le interazioni binarie . . . 27

3 I modelli 33 3.1 Algorithmic bias model su reti complesse . . . 33

3.2 Algorithmic bias model con peer pressure e reti adattive . . . 34

3.2.1 Peer pressure . . . 34

3.2.2 Peer pressure con rewiring . . . 40

4 Analisi e risultati 44 4.1 Organizzazione degli esperimenti . . . 44

4.1.1 Reti impiegate . . . 44

4.1.2 Parametri modelli . . . 46

4.1.3 Analisi effettuate . . . 46

4.2 Discussione dei risultati . . . 47

5 Conclusioni 71 5.1 Sviluppi futuri . . . 73

Elenco delle figure

2.1 Complessi simpliciali. (Fonte: Wikipedia) . . . 28 3.1 Peer-pressure. Dal momento che n2 e n3 sono concordi, ma n1 `e discorde,

questo viene attirato dalla maggioranza adottando la loro opinione media. 36 3.2 Peer-pressure. Dal momento che n2 e n3 sono concordi, e anche n1 `e

concorde i tre nodi adottano l’opinione media del gruppo. . . 37 3.3 Peer-pressure. Nel modello ABSC2 nel momento in cui n2 e n3 sono

concordi, mentre n1 `e discorde, questo adotta l’opinione media degli altri due. Allo stesso modo anche n2 e n3 adottano la loro opinione media. 38 3.4 Algorithmic Bias. Anche il terzo nodo viene scelto in base al parametro

γ secondo l’equazione 2.19. . . 39 3.5 Peer pressure. Viene ricercata una qualunque maggioranza tra i nodi che

formano il complesso simpliciale, la quale poi esercita la peer pressure sul rimanente soggetto. . . 40 3.6 Rewiring. . . 42 4.1 Rete random e rete scale-free. Sottografi di due reti create con gli

stes-si parametri utilizzati per i modelli di opinion dynamics analizzati nel presente capitolo con le relative degree distributions. . . 45 4.2 Confronto tra rete random e rete scale-free per il DW-model (γ = 0). . 48 4.3 Numero medio di cluster. Il grafico mostra il numero medio di cluster

nell’AB-model su una rete random in funzione dei due parametri del modello ( e γ). Come si pu`o notare il numero di cluster aumenta con γ e diminuisce con . . . 49 4.4 Numero medio di cluster. Il grafico mostra il numero medio di cluster

nell’AB-model su una rete scale-free in funzione dei due parametri del modello ( e γ). Come si pu`o notare anche in questo caso il numero di cluster aumenta con γ e diminuisce con . . . 50 4.5 Evoluzione delle opinioni per  ∈ {0.2, 0.3, 0.4} fino a γ = 1.6 su una

rete random. . . 51 4.6 Evoluzione delle opinioni per  ∈ {0.2, 0.3, 0.4} fino a γ = 1.6 su una

rete scale-free. . . 51 4.7 Numero medio di cluster. Il grafico mostra il numero medio di cluster

nell’AB-model su una rete random in funzione dei due parametri del modello ( e γ), ponendo come restrizione γ ≤ 1.2, in modo da riuscire ad apprezzare meglio la dipendenza da  della misura. . . 52

4.8 Numero medio di cluster. Il grafico mostra il numero medio di cluster nell’AB-model su una rete scale-free in funzione dei due parametri del modello ( e γ), ponendo come restrizione γ ≤ 1.2, in modo da riuscire ad apprezzare meglio la dipendenza da  della misura. . . 53 4.9 Numero medio di cluster nelle due diverse reti per diversi valori di .

Il grafico mostra il numero medio di cluster nell’AB-model sulla rete random (in blu) e sulla rete scale free (in arancione) in funzione di γ. . 54 4.10 Numero medio di cluster nella rete random per diversi valori di  e

γ ≤ 1.6. Il grafico mostra il numero medio di cluster nell’AB-model sulla rete random (in blu), con una probabilit`a random di rewiring degli archi (in arancione) e facendo sempre il rewiring degli archi (in verde), in funzione di γ. . . 55 4.11 Numero medio di cluster nella rete scale-free per diversi valori di  e

γ ≤ 1.6. Il grafico mostra il numero medio di cluster nell’AB-model sulla rete random (in blu), con una probabilit`a random di rewiring degli archi (in arancione) e facendo sempre il rewiring degli archi (in verde), in funzione di γ. . . 56 4.12 Numero medio di cluster. Il grafico mostra il numero medio di cluster

nell’ABSC-model sulla rete random e sulla rete scale-free in funzione dei due parametri del modello ( e γ). . . 58 4.13 Numero medio di cluster confrontato tra le due reti e per i diversi valori

di pr, fissato  al variare di γ. Il grafico mostra il numero medio di cluster nell’ABSC-model sulla rete random e sulla rete scale-free (linea tratteggiata) per pr = 0 (in blu), con pr = 0.5 (in arancione) e pr = 1.0 (in verde). . . 60 4.14 Numero medio di cluster confrontato tra i diversi modelli e per i diversi

valori di pr fissato  al variare di γ per la rete random. . . 61 4.15 Numero medio di cluster confrontato tra i diversi modelli e per i diversi

valori di pr fissato  al variare di γ per la rete scale-free. . . 62 4.16 Distanza media tra le opinioni nell’AB-model (pr = 0.0) nella rete

random e nella rete scale-free. . . 63 4.17 Numero di iterazioni medio per la convergenza nell’AB-model (pr = 0.0)

nella rete random e nella rete scale-free. . . 66 4.18 Numero medio di iterazioni nell’AB-model confrontato tra le due diverse

reti e per i diversi valori di pr con  fissato e al variare di γ. . . 67 4.19 Numero medio di iterazioni nei vari modelli e nelle due reti, per pr = 0.0 68 4.20 Numero medio di iterazioni nei tre modelli su complessi simpliciali, per

1

Introduzione

Negli ultimi anni lo studio di fenomeni di polarizzazione e frammentazione delle opinioni ha visto crescere notevolmente l’interesse della comunit`a scientifica. Grazie all’esplosione delle piattaforme di discussione online, `e infatti facile osservare come su molteplici temi la societ`a civile si divida in pi`u fazioni, le cui opinioni risultano spesso diametralmente opposte. Basti pensare, ad esempio, ai fenomeni di polarizzazione po-litica, per cui gli individui tendono ad abbandonare posizioni moderate e ad adottare opinioni sempre pi`u estreme (che siano esse a destra o a sinistra), o anche alla discus-sione sull’affidabilit`a dei vaccini (esplosa negli ultimi anni) dalla quale emergono due schieramenti contrapposti in termini di opinioni e tra i quali `e difficile che si instauri un dialogo costruttivo.

Studi scientifici suggeriscono che ci sono molteplici cause per tale fenomeno, ma l’idea che si sta radicando recentemente `e che gli online social media giochino un ruolo fondamentale in questo meccanismo. La popolazione, infatti, utilizza sempre meno i media tradizionali per ottenere informazioni e sempre pi`u gli online social net-works. Inoltre, i dialoghi e le discussioni si sono moltiplicate grazie ai nuovi media, che permettono a persone che non si sarebbero mai incontrate, di interagire.

Si potrebbe pensare che dato che internet e i social network permettono un’acquisi-zione di informazioni pi`u vasta e aumentano le possibilit`a di contatto e comunicazione tra gli individui, tali strumenti dovrebbero promuovere il consenso intorno a certi ar-gomenti. Tuttavia questo non accade. Una delle cause principali di questo fenomeno `e stata individuata nel fatto che il flusso di informazioni da cui `e costantemente bom-bardato l’utente non `e organizzato in modo imparziale intorno ad un determinato argomento: al contrario, l’obiettivo degli algoritmi che determinano i contenuti con

cui l’utente va ad interagire `e quello di massimizzare l’utilizzo della piattaforma e per-tanto mostrer`a pi`u spesso informazioni e utenti che piacciono all’utente e con cui `e presumibilmente d’accordo. Questo significa che l’utente medio spesso non viene in contatto con narrative diverse dalla propria, se non per esplicita contrapposizione di contenuti. Si ritiene quindi che polarizzazione e frammentazione siano, almeno in par-te, dovuti/amplificati dalla presenza di un bias algoritmico capace di guidare l’accesso alle informazioni e esacerbare contrapposizioni esistenti, pur non essendo introdotto con tale fine.

Tale fenomeno `e oggetto di studio nel campo dell’Opinion Dynamics, un ambito di ricerca interdisciplinare che si occupa di studiare la propagazione delle opinioni in contesti sociali, modellandole come risultato di interazioni di agenti. Il campo dell’O-pinion Dynamics muove i suoi primi passi alcuni decenni fa e, nel corso degli anni, ha visto la definizione di innumerevoli modelli finalizzati a catturare diversi aspetti delle dinamiche sociali, come ad esempio l’omofilia degli agenti, la presenza di informazioni esogene, e cos`ı via.

Un importante aspetto delle dinamiche sociali, spesso trascurato nei modelli di opinion dynamics, riguarda l’esistenza di dinamiche di gruppo. La maggior parte dei modelli, infatti, compreso quello su cui si basa il presente lavoro di tesi, parte dall’as-sunzione che le interazioni tra gli utenti della rete siano solo binarie. In realt`a tali interazioni possono essere di diverso ordine e possono pertanto dare origini a fenomeni come la peer-pressure, per cui la maggioranza del gruppo esercita una forte influenza sul singolo individuo, portandolo a compiere delle scelte che altrimenti non avrebbe compiuto. In letteratura, tuttavia, ben pochi modelli considerano interazioni di ordine superiore al secondo e quando lo fanno, considerano solo opinioni binarie, cio`e l’even-tualit`a che ogni agente possa assumere solo una opinione positiva o negativa, ignorando quindi lo spettro continuo.

Un altro aspetto molto spesso trascurato `e il fatto che le interazione tra gli utenti di un social network evolvono nel tempo e che molto spesso `e il contenuto discusso che influenza quest’evoluzione, insieme ad altri fattori. `E infatti vero che i social network

tendono a mostrarci ci`o che `e in linea con le nostre credenze, ma `e altres`ı vero che molto spesso siamo noi ad escludere dalla nostra rete di contatti coloro che hanno delle opinioni troppo distanti dalle nostre, con i quali non abbiamo intenzione di costruire alcun dialogo. In conseguenza a tali considerazioni, con il presente elaborato si `e cercato di sviluppare diversi modelli che includessero questi aspetti.

Il punto di partenza di questo lavoro `e un modello, gi`a esistente in letteratura, che include e analizza le conseguenze dell’algorithmic bias. Tale modello si basa a sua volta su uno precedente: il modello Deffuant-Weisbuch, che rientra nella categoria dei bounded confidence models. Il parametro fondamentale di questo modello `e , che indica la distanza di opinione entro la quale due nodi devono rientrare per potersi confrontare. Qualora fossero pi`u distanti anche un’eventuale interazione non produce alcun risultato. In lavori successivi, al fine di catturare l’algorithmic bias, a tale modello viene aggiunto un ulteriore parametro γ, che indica quanto sia selettivo l’algoritmo di filtraggio delle informazioni proposto dal sistema di raccomandazione di contenuti: pi`u `e alto e pi`u l’individuo tender`a ad interagire con i nodi pi`u simili a se stesso. Un limite di tale studio `e indubbiamente dato dal setting sperimentale, impostato completamente sull’analisi del modello su reti complete (mean field scenario). Tale approccio, utile per comprendere gli effetti del bias introdotto sulla dinamica, ignora completamente gli effetti di una componente fondamentale della diffusione delle opinioni: la topologia descritta dalle interazioni tra gli utenti/agenti. Nella realt`a, infatti, `e impensabile che un gran numero di individui possano essere tutti connessi tra loro. A partire da tale osservazione, nel presente lavoro di tesi, `e stata effettuata un’ulteriore analisi di questo modello su topologie di rete pi`u complesse: in particolare, `e stato studiato il suo comportamento su reti random e scale-free.

Successivamente si `e deciso di definire ed implementare quattro diversi modelli che catturassero l’effetto espresso da dinamiche di gruppo. In tali modelli il “gruppo” con-siderato ha cardinalit`a minima: un sottografo completo di 3 nodi o triangolo. Ogni triangolo `e qui considerato un 2-simplesso, ovvero si ritiene costituito da tutte le inte-razioni di primo e secondo ordine, tra i nodi che lo compongono (e.g., non `e sufficiente

l’esistenza della relazione ternaria ma `e necessaria anche la presenza, indipendente, di tutte le binarie tra i vertici del triangolo). Sfruttando i 2-simplessi si `e quindi modellato il meccanismo della peer-pressure in un contesto di opinioni continue. Per modellare la peer-pressure si `e deciso che qualora ci fosse una maggioranza sul triangolo e un nodo fosse discorde, questo sarebbe stato attirato dalla maggioranza. Tale meccanismo `e chiaramente in contrasto con quello della bounded confidence. Dalle analisi effettuate sempre sulla rete random e sulla rete scale-free `e emerso come in realt`a le interazioni di gruppo promuovano il consenso e riducano la frammentazione.

Infine, si `e deciso di testare tutti i modelli definiti su reti adattive: reti il cui numero di nodi e di link rimane costante nel tempo, ma dove eventi di edge-rewiring (giustificati da particolari condizioni) consentono di perturbare nel tempo la topologia del sistema. La tesi `e organizzata come segue:

• Nel capitolo 2 vengono introdotte le nozioni fondamentali di Social Network Analysis e teoria dei grafi necessarie ai fini della comprensione del presente lavoro. Viene inoltre presentata una breve rassegna dei principali modelli di opinion dynamics, in particolare di quelli utilizzati come baseline al presente lavoro. • Il capitolo 3 delinea il quadro formale dei modelli, descrivendo nel dettaglio le

regole secondo cui avvengono le interazioni e si evolve la dinamica.

• Nel capitolo 4 si analizzano i risultati delle simulazioni dei modelli precedente-mente descritti su una rete random e su una rete scale-free.

• Nel capitolo 5 viene riassunto il lavoro di tesi e vengono presentate possibili estensioni future.

2

Stato dell’arte

2.1

Social Network Analysis

Uno dei framework teorici alla base del presente lavoro di tesi `e l’analisi delle reti sociali (o social network analysis), che nasce per rispondere a delle research questions provenienti dalla sociologia e dalla scienza comportamentale, dando precise definizioni formali su molti aspetti dell’ambiente sociale.

Le reti sociali sono infatti l’insieme dei legami sociali che collegano le persone le une alle altre. Oggi tale espressione evoca a molti immagini di Facebook, Twitter e altri siti internet che servono a mettere in contatto le persone, ma le reti sociali sono in realt`a sempre esistite e sono sempre state studiate in maniera multidisciplinare da sociologi, psicologi comportamentali, matematici e informatici. Tradizionalmente, legami e reti sociali si basavano sull’interazione personale, ma oggi internet offre alcuni chiari vantaggi ai fini della loro costruzione e del loro mantenimento. Gli online social network offrono nuove opportunit`a per comunicare e creano nuovi modi di interagire tra un gran numero di individui, per molti sono un’opportunit`a di trovare persone con interessi comuni senza che sia necessario incontrarsi di persona. Le reti sono di dimensioni molto differenti e variano, fra le altre caratteristiche, per la forza dei loro legami, per le caratteristiche di chi ne fa parte, per la distanza fisica tra i membri e per il tipo di interazione che caratterizza il legame.

Gi`a i primi studi sulle reti sociali hanno rivelato come sia pi`u probabile che nella nostra rete si trovino persone simili a noi. Secondo il principio dell’endogamia sociale, infatti, il contatto sociale avviene in percentuale maggiore fra persone simili che fra persone diverse [MS01]. Genere, et`a, religione, classe sono caratteristiche importanti

che legano o separano le persone. Di conseguenza, la maggior parte delle reti sociali `e molto pi`u omogenea della popolazione presa nel suo insieme. L’endogamia sociale influenza ci`o che sappiamo della nostra societ`a perch´e tendiamo a condividere e raffor-zare la nostra visione del mondo con coloro che sono vicini a noi [ML93]. Per quanto riguarda la forza dei legami tra gli individui - intesa come in [Gra73] come combinazio-ne di tempo, intensit`a emotiva, intimit`a e scambio che caratterizza il legame -, alcune delle reti sono formate da amici intimi, famiglia o da altre persone con cui il legame risulta essere molto forte. `E normale voler passare con loro il nostro tempo e, in genere, questo desiderio `e reciproco. Pi`u forti sono i nostri legami con le persone, pi`u `e proba-bile che esse ci forniscano un sostegno. Gran parte del nostro supporto sociale deriva da un numero relativamente esiguo di legami molto forti che possono avere un’impor-tanza fondamentale in tempi di crisi. Altre reti sono formate da persone che hanno un legame reciproco relativamente debole, ma anche queste reti possono essere un aiuto (forza dei legami deboli di Granovetter [Gra73]). Secondo [Gra73] i legami deboli sono importanti perch´e sono “ponti” che forniscono l’accesso a risorse e informazioni oltre e al di l`a del gruppo sociale di appartenenza e inoltre forniscono agli individui occasioni di “mobilit`a” (intesa come migliorament di status e classe sociale).

A prescindere dalle domande socio-economiche a cui si cerca di rispondere tramite l’analisi di queste reti, il punto di partenza dal punto di vista di matematici e infor-matici `e l’analisi della struttura della rete stessa. Tale ambito di ricerca fa parte della pi`u ampia network science, che `e la scienza che studia sistemi complessi, rappresentati tramite reti. Tale rappresentazione li rende pi`u comprensibili e ne definisce le intera-zioni tra i componenti. Infatti, la caratteristica distintiva dei sistemi complessi `e che `e difficile derivare il comportamento collettivo dalla conoscenza dei singoli componenti del sistema, per via di dipendenze, competizioni, relazioni o altri tipi di interazioni tra le loro parti o tra il sistema e l’ambiente. Le reti arrivano in aiuto in questo contesto permettendo di rappresentare sia i singoli componenti, tramite nodi, che le relazioni tra essi, tramite link e di catturare un certo numero di caratteristiche altrimenti incom-prensibili. Questo tipo di rappresentazione ha la sua naturale traduzione matematica

nella struttura del grafo, in cui ogni nodo viene rappresentato da un vertice e ogni link viene rappresentato da un arco.

Qui di seguito verranno perci`o introdotte alcuni aspetti fondamentali della teoria dei grafi, indispensabili per comprendere le successive analisi condotte sulle reti.

2.1.1

Teoria dei grafi

In matematica e informatica la teoria dei grafi `e la disciplina che si occupa dello studio dei grafi. Un grafo `e una struttura matematica discreta G, composta da vertici (anche chiamati nodi), di cui alcune coppie sono connesse tramite archi (o link). Quan-do tra due vertici esiste un arco i vertici vengono definiti vicini (o neighbours). Nella presente trattazione i termini vertice/nodo e arco/link vengono considerati sinonimi.

In simboli, un grafo viene definito come la coppia G = (E, V ), dove V = {v1, v2, ..., vN}

`e l’insieme dei vertici di G e E = {(u, v) | u, v ∈ V } `e l’insieme degli archi di G. Un tipico modo di rappresentare graficamente un grafo `e con dei piccoli cerchi che rappresentano i nodi e una linea che unisce ogni coppia di nodi vicini.

In base alla tipologia di arco i grafi possono essere suddivisi in grafi indiretti (undi-rected ), in cui la relazione tra i nodi `e simmetrica, cio`e se il nodo 1 `e collegato al nodo 2 allora anche il nodo 2 `e collegato al nodo 1, e grafi diretti (directed ), in cui invece la relazione `e asimmetrica pertanto se esiste un link tra il nodo 1 e il nodo 2 non `e detta che il nodo 2 sia collegato al nodo 1; possiamo inoltre distinguere grafi pesati e grafi non pesati, in cui nei primi a ogni link `e assegnato un valore che ne indica il peso, mentre nei secondi ogni link ha lo stesso peso (normalmente 1); infine possiamo dividere i grafi in completi, in cui esiste un arco tra ciascuna coppia di nodi, e non completi. Il numero di vertici o nodi viene normalmente indicato con N .

Nel presente lavoro di tesi sono stati sfruttati grafi indiretti, non pesati e non completi.

Le misure base

Le misure base che sono la chiave per la descrizione, l’analisi e il confronto dei grafi sono la distribuzione del grado (degree distribution), il diametro della rete (network diameter), le misure di clustering e le componenti connesse. Di seguito verranno intro-dotte quelle necessarie per comprendere le successive analisi.

Grado di un nodo

Una propriet`a chiave di un nodo `e il numero di altri nodi a cui `e connesso. Definiamo pertanto come grado di un nodo (node degree) il numero di archi che un nodo ha con gli altri nodi del grafo e indichiamo con ki il degree dell’i-esimo nodo. Nel caso dei

grafi diretti `e chiaro che bisogna distinguere tra grado entrante (in-degree) kin

i e grado

uscente (out-degree), kout

i . Il grado totale del nodo `e dato dalla somma di questi due

ki = kini + kouti . Chiaramente, a partire dal grado dei singoli nodi possiamo risalire al

numero totale degli archi del grafo dal momento che

L = 1 2 N X i=0 ki (2.1) L = N X i=0 kin_i = N X i=0 kout_i (2.2)

rispettivamente per i grafi indiretti e per i grafi diretti. La connettivit`a della rete `e indicata dal grado medio (average degree), che pu`o essere anche espresso in funzione del numero totale di nodi N e del numero totale di archi L, essendo

hki 1 N N X i=0 ki = 2L N (2.3)

per i grafi non diretti e

hkin_i i = 1 N N X i=0 k_iin = hk_iouti = 1 N N X i=0 k_iout= L N (2.4) pk = Nk N (2.5)

.

Chiusura triadica e clustering coefficient

Uno dei ruoli principali giocati dalle reti `e quello di connettere il locale e il globale, di offrire spiegazioni di come semplici processi a livello di singoli nodi o link possono avere effetti complessi che si diffondono sulla popolazione. Al di l`a della connettivit`a globale della rete, di cui il grado `e un indicatore fondamentale, ci sono altre propriet`a che sono necessarie per capire le dinamiche del network. Una di queste propriet`a `e la transitivit`a, anche chiamata chiusura triadica (triadic closure). La chiusura triadica `e una formulazione matematica della dinamica sociale secondo cui: “L’amico del mio amico, non `e detto che sia mio amico, ma `e pi`u probabile che lo sia rispetto ad un perfetto sconosciuto”. `E chiaro che nelle reti reali non `e mai presente una transitivit`a perfetta, poich´e questo implicherebbe che ciascun nodo della rete avesse un collega-mento verso tutti gli altri nodi della rete, cio`e che tutti fossero amici di tutti; tuttavia, soprattutto nelle reti sociali, molto spesso il fatto che il nodo 1 sia “amico” del nodo 2 e che il nodo 2 sia “amico” del nodo 3, non garantisce che il nodo 1 sia “amico” del nodo 3, ma lo rende pi`u probabile. Quella che si viene a creare `e una struttura chiamata triangolo, che non `e altro che un sottografo completamente connesso di 3 nodi. Il ruolo fondamentale della triadic closure nelle reti sociali ha motivato la formulazione di sem-plici misure che catturino la sua prevalenza, una di queste `e il coefficiente di clustering locale. Per un nodo i con degree ki, il coefficiente di clustering locale (local clustering

coefficient) `e definito come la probabilit`a che, preso il nodo i, due vicini selezionati casualmente siano vicini tra loro. In simboli:

Ci =

2Li

ki(ki − 1)

(2.6)

dove Li rappresenta il numero di link che connettono i ki vicini del nodo i tra loro.

Nota che Ci `e compreso tra 0 e 1. In sostanza ki misura la densit`a locale di link della

rete: pi`u densamente interconnesso `e il vicinato dei nodi i, maggiore `e il suo clustering coefficient. Come per il grado, per ottenere una misura della densit`a locale generale del grafo possiamo calcolare il coefficiente di clustering medio, che indica la probabilit`a

che due vicini di un nodo scelto casualmente siano connessi l’uno all’altro: hCi = 1 N N X i=0 Ci (2.7)

Una definizione alternativa di clustering coefficient, anch’essa ampiamente usata, `e stata data da Watts e Strogatz[WS98]:

Ci =

numero di triangoli connessi al vertice i

numero di triplette centrate sul vertice i (2.8)

dove per triangolo si intende un sottografo di 3 nodi completamente connesso centrato nel vertice i e per tripletta si intende un sottografo di 3 nodi, sempre centrato nel vertice i, intendendo per centrato che entrambi gli altri nodi sono vicini di i.

Un’altra metrica importante che determina le interazioni tra le componenti della rete `e la distanza. Prima di definire la distanza va introdotta la nozione di cammino: un cammino `e una sequenza di nodi tali che ciascun nodo `e connesso al successivo da un link e ogni path `e costituito da n + 1 nodi e n link. Il cammino minimo dal nodo i al nodo j `e il cammino con il minor numero di link (o nodi) che inizia in i e termina in j. Tale cammino minimo `e spesso chiamato anche distanza, normalmente indicata con dij che, nel caso delle reti non dirette, `e uguale alla distanza dji. Il cammino minimo

pi`u lungo del grafo `e detto diametro dmax.

Modelli di rete

Uno degli obiettivi della network science `e quello di implementare dei modelli di rete che riescano a riprodurre le propriet`a osservate sulle reti reali. Da una prospettiva di modellazione una rete `e un oggetto relativamente semplice, essendo formato solo da nodi e link. La vera sfida, tuttavia, `e decidere dove mettere i link tra i nodi in modo da riprodurre la complessit`a di un sistema reale. Riguardo a ci`o, diverse assunzioni hanno dato vita a diversi modelli di rete. Nel resto della sezione verranno introdotti i principali presenti in letteratura, ciascuno caratterizzato da una particolare topologia, e verranno approfonditi quelli utilizzati all’interno del presente lavoro di tesi.

Complete network

Un grafo completo `e un grafo semplice in cui ogni coppia di vertici `e connessa da un arco. Se la rete ha N nodi, il numero totale di link presenti `e pari al numero massimo di link possibili Lmax = N 2  = N (N − 1) 2 (2.9)

Ovviamente in un grafo completo il grado di ogni nodo `e uguale al grado medio che `e pari a N − 1. Un grafo completo `e spesso chiamato clique o “cricca”. `E chiaro che nella realt`a non esistono molte reti complete, tuttavia questa approssimazione viene spesso utilizzata per studiare modelli di opinion dynamics partendo dal presupposto che la realt`a modellata non `e tanto quella di un network di individui quanto pi`u la rappresentazione di un gruppo di persone tutte raccolte all’interno di uno stesso luogo o comunque in una situazione tale per cui tutti possano comunicare con tutti. Nella realt`a il numero di nodi N e link L pu`o variare enormemente e nella maggior parte dei casi L  Lmax, che riflette il fatto che la maggior parte delle reti reali `e “sparsa”, cio`e

il numero di link presenti `e solo una piccola frazione del numero atteso per una rete completa con lo stesso numero di nodi.

Random network

Le reti reali, ad un primo sguardo, sembrano essere collegate in maniera casuale. Questa idea `e stata sviluppata per dare vita ad un modello di rete: le reti random, in cui i link vengono inseriti casualmente tra coppie di nodi. Possiamo dare una definizione pi`u precisa di rete random in funzione di L o in funzione di p, che `e la probabilit`a che tra due nodi esista un link. Il modello G(N, L) definisce una rete random come N nodi che sono connessi da L link inseriti casualmente (questo modello `e stato introdotto da Erdos e Renyi [ER59]). Il modello G(N, p), invece, la definisce come N nodi di cui ogni coppia `e connessa con probabilit`a p ed `e stato introdotto da Gilbert [Gil59], utilizzato anche in un successivo lavoro [ER60] dagli autori precedentemente citati. La differenza sostanziale tra questi due modelli sta nella quantit`a che viene fissata: nel primo `e il numero di link L, nel secondo `e la probabilit`a che esista un link p tra due vertici. Il vantaggio del primo modello `e che permette di calcolare facilmente il grado medio, che `e

semplicemente hki = 2L_N. Tuttavia, il secondo `e quello pi`u utilizzato perch´e conoscendo p `e possibile calcolare molte caratteristiche chiave della rete, ma anche perch´e il numero dei link nelle reti reali raramente `e un numero fisso. Per l’importanza dei due studiosi ungheresi, Erdos e Renyi, un random network viene chiamato Erdos-Renyi network.

Per comprendere le caratteristiche di una rete random bisogna innanzitutto calcola-re in funzione dei parametri il numero di link attesi all’interno del grafo. Assumendo che le reti random siano generate utilizzando il modello G = (N, p), tra implementazioni diverse con gli stessi parametri cambia il numero di link. `E pertanto utile determinare quanti link ci aspettiamo per una particolare realizzazione di una rete random, fissati N e p. La probabilit`a che una rete random abbia esattamente L link `e il prodotto di tre termini:

1. la probabilit`a pL che gli L tentativi di connettere le N (N − 1)

2 coppie di nodi abbiano creato un link;

2. la probabilit`a (1 − p)N (N −2)2 −L che i restanti N (N − 2)

2 − L tentativi non abbiano creato un link e 3. un fattore combinatorio N (N −2) 2 L 

che conta il numero di diversi modi in cui possono essere messi L link tra N (N − 2)

2 coppie di nodi

. Pertanto la probabilit`a risultante che la random network abbia esattamente L link `e

pL = N (N −2) 2 L  pL(1 − p)N (N −1)2 −L (2.10)

Dato che tale espressione genera una distribuzione binomiale, il numero atteso di link in un grafo random `e hLi =X L=0 N (N − 1) 2 LpL= p N (N − 1) 2 (2.11)

Da questa formula possiamo derivare il grado medio che `e

hki = 2L

All’aumentare di p la rete diventa pi`u densa in quanto hLi cresce linearmente da 0 a Lmax e hki cresce da 0 a N − 1.

Come ricordato nel paragrafo una delle pi`u importanti quantit`a da misurare per comprendere la struttura di una rete `e la distribuzione del grado dei nodi. In una data realizzazione di una rete random alcuni nodi avranno numerosi link, mentre altri ne avranno pochissimi o nessuno. Queste differenze sono catturate dalla distribuzione del grado, pk. Essendo pkla probabilit`a che un nodo scelto casualmente abbia esattamente

grado k, il suo calcolo deriva dal prodotto di tre termini: 1. pk, cio`e la probabilit`a che k dei suoi link siano presenti

2. (1 − p)N −1−k che `e la probabilit`a che i restanti link manchino e 3. N − 1

k 

, che `e un coefficiente binomiale che indica il numero di modi in cui possiamo selezionare k link da N − 1 potenziali link.

. Conseguentemente la degree distribution di una rete random `e la seguente distribu-zione binomiale: pk = N − 1 k  pk(1 − p)N −1−k (2.13)

Come introdotto la maggior parte delle reti reali sono “sparse” cio`e poco dense. Ci`o significa che p `e piccolo e quindi hLi  Lmax, ma soprattutto che hki  N. In questo

caso la distribuzione del grado viene approssimata bene dalla distribuzione di Poisson:

pk= e−hki

hkik

k! (2.14)

che `e spesso chiamata, insieme alla 2.13 la degree distribution di un random network. La distribuzione binomiale e quella di Poisson descrivono la stessa quantit`a e per questo hanno propriet`a simili. Entrambe hanno infatti un picco intorno a hki: se aumentiamo il parametro p il network diventa sempre pi`u denso, aumentando hki e spostando il pic-co verso destra. La larghezza della distribuzione (dispersione) `e anch’essa controllata da p: pi`u denso `e il network, pi`u ampia `e la distribuzione, pi`u grandi sono le differenze

gree distribution di un random network bisogna ricordare che il risultato esatto `e dato dalla forma binomiale e tale approssimazione `e valida fintanto che il grado medio `e molto minore di N . Ricordando che la maggior parte delle reti reali `e “sparsa” questa condizione `e spesso verificata nella realt`a. Il vantaggio della distribuzione di Poisson `e che alcune caratteristiche chiave hanno una forma pi`u semplice che dipende solo dal parametro hki. La distribuzione di Poisson, come `e possibile vedere dall’equazione 2.14 non dipende esplicitamente dal numero di nodi N , pertanto permette di concludere che la degree distribution di reti di diversa grandezza, ma con lo stesso average degree, sono indistinguibili le une dalle altre.

Nonostante la distribuzione casuale dei link sia un’intuizione fondamentale, il fatto che la maggior parte dei nodi abbiano degree in un intorno di hki non `e realistico, in quanto `e ampiamente dimostrato che all’interno delle reti sociali normalmente coesisto-no (pochi) individui con un grado molto pi`u alto di quello medio e (molti) altri con un grado notevolmente pi`u basso. Andando infatti ad osservare le distribuzioni di alcune delle pi`u note reti reali si nota come la distribuzione di Poisson predice molti pi`u nodi aventi grado vicino a hki rispetto a quanti ce ne sono in realt`a.

Tra le propriet`a delle reti reali che sono invece meglio modellate dalle reti random c’`e la small world property, che `e ben sintetizzata dalla famosa espressione “sei gradi di separazione”, simbolo della teoria secondo cui ogni coppia di individui nel mondo sia separata al massimo da sei gradi di separazione. A prescindere da questa espres-sione simbolo, lo small world phenomenon implica che la distanza tra due nodi scelti casualmente sia corta. Le reti random rispecchiano questa propriet`a poich´e il numero di nodi a distanza d da un certo nodo cresce esponenzialmente con d o, pi`u chiaramen-te, poich´e la distanza media hdi cresce logaritmicamente con N anzich´e linearmente: hdi = ln N

lnhki. Per quanto riguarda il clustering coefficient, invece, mettendo a confronto la previsione fatta tramite una rete random con i dati provenienti dalle reti reali si nota come il coefficiente di clustering medio nella realt`a `e molto pi`u alto di quello atteso per una rete random con simili N e L.

Watts-Strogatz network

Queste discrepanze tra reti reali e reti random vengono eliminate nel modello Watts-Strogatz, anche chiamato modello small-world, che costituisce una via di mezzo tra un reticolo regolare con un alto clustering e una rete random che possiede la small world property. La degree distribution rimane tuttavia approssimata da una Poisson.

Scale-free network

Nella restante parte di questa sezione verr`a trattato un modello di rete che invece punta ad approssimare meglio la degree distribution delle reti reali: il modello scale-free. Tale nome `e stato dato in quanto in queste reti manca una scala interna, in conseguenza del fatto che nodi con grado molto diverso coesistono nella stessa rete, mentre gli altri tipi di rete ce l’hanno. Questa caratteristica distingue gli scale-free networks sia dai reticoli, in cui tutti i nodi hanno lo stesso grado, sia dai random networks in cui i nodi sono tutti concentrati intorno al grado medio. Tale modello nasce dall’osservazione delle degree distribution di molte reti reali che viene ben approssimata da

pk ∼ k−γ (2.15)

che `e una distribuzione a coda di potenza (power-law distribution), il cui esponente γ viene chiamato esponente di grado (degree exponent). Applicando il logaritmo ad entrambi i membri si ottiene

log pk∼ −γ log k (2.16)

Pertanto una rete scale-free `e una rete la cui degree distribution segue una power-law. La principale differenza tra una rete random e una rete scale-free sta nella coda della degree distribution, che rappresenta le regioni con alto k di pk: in una rete scale-free

c’`e un grande numero di nodi con basso k, mentre in una rete random non ci sono quasi per niente nodi con basso k; per quanto riguarda invece i nodi con k ≈ hki in una rete scale free sono pochi, mentre in una rete random sono la maggioranza; infine, in una rete scale-free c’`e un’alta probabilit`a di osservare nodi con un degree alto, chiamati hub, mentre nelle reti random la probabilit`a `e ordini di magnitudine inferiore. Per

quanto riguarda proprio quest’ultima categoria di nodi, gli hub, il loro grado dipende linearmente dalla dimensione della rete: pi`u grande `e il network, pi`u grande `e il degree del suo hub maggiore, in quanto

kmax = kminN

1

γ−1 (2.17)

Per quanto riguarda la small-world property, rispettata sia dalle random network che dalle small-world network, in questo caso addirittura per alcuni valori di γ, in parti-colare per 2 ≤ γ < 3 (regime scale-free), gli hub riescono a ridurre ancor di pi`u le distanze all’interno della rete, generando un ultra-small-world in cui hdi ∼ ln ln N . Per γ ≥ 3 si ritorna alla small-world property e quindi al regime delle reti random. Per γ < 2 la rete si trova in un regime anomalo in cui hdi ∼ const. Per quanto riguarda altre propriet`a che dipendono sempre da γ si pu`o osservare come nel regime scale-free hki `e finito e hk2_{i diverge, mentre nel caso del regime random sono entrambi finiti e}

nel caso del regime anomalo divergono entrambi. Chiaramente, la presenza degli hub gioca un ruolo fondamentale nel comportamento di questi sistemi.

La ragione che sta dietro alla presenza della scale-free property in una grande variet`a di reti reali risiede in due fattori fondamentali: la crescita e il preferential attachment, propriet`a che potremmo riassumere con l’espressione “i ricchi diventano pi`u ricchi”. Mentre nelle reti random si assume che un link venga inserito tra due nodi scelti casualmente, la regola del preferential attachment prevede che i nuovi nodi preferiscano collegarsi con i nodi pi`u connessi. Esiste un modello, che rientra sempre nella categoria delle reti scale-free, che implementa questa caratteristica: il Barabasi-Albert model, un algoritmo che genera random scale-free networks utilizzando un meccanismo di preferential attachment [BA99]. In questo caso per costruire la rete si parte da m0

nodi, collegati da link scelti arbitrariamente, purch´e ogni nodo abbia almeno un link, poi ad ogni time step viene aggiunto un nodo con m < m0 link che lo connettono ad

al nodo i dipende dal grado ki secondo Y (ki) = ki P jkj (2.18)

Dopo t step temporali, il modello BA genera una rete con N = t + m0 nodi e m0+ mt

archi. La rete generata avr`a una power-law degree distribution con γ = 3.

Per un’analisi pi`u approfondita delle propriet`a dei grafi e dei modelli di rete si veda [Bar16].

2.2

Opinion dynamics

Il comportamento umano `e governato da diversi aspetti, relativi al contesto sociale, culturale, legislativo e da altri fattori. Le opinioni e le credenze sono alla base del com-portamento e possono essere viste come lo stato interno degli individui che indirizza determinate azioni. Virtualmente, ogni individuo potrebbe avere un’opinione su tutto, pertanto comprendere come le opinioni si formano ed evolvono `e un processo importan-te per spiegare le scelimportan-te umane. Il processo di formazione delle opinioni `e complesso, dipende dalle informazioni che raccogliamo dai nostri pari o da fonti esterne, come ad esempio i mass media. Il campo dell’opinion dynamics nasce per cercare di modellare il comportamento sociale dello scambio di opinioni tra individui e rientra nella pi`u ampia area dei modelli di diffusione. In questo caso, vogliamo comprendere le dinamiche delle opinioni in gruppi di persone che interagiscono le une con le altre e con un contesto di informazioni – cosa causa il cambiamento delle opinioni delle persone e cosa porta i gruppi che supportano o si oppongono a qualcosa a guadagnare o perdere influenza e potere? Lo studio della diffusione delle opinioni tramite modelli matematici non `e nuova, ma risale almeno al 1956 [Fre56]. Pi`u recentemente, ma sempre molti decenni fa, ci sono stati i lavori di DeGroot [DeG74] e Friedkin [Fri86]. Gli anni recenti, tutta-via, sono stati testimoni dell’introduzione di un’ampia gamma di modelli che tentano di spiegare come le opinioni si formano in una popolazione, prendendo in considera-zione diverse teorie sociali (es. bounded confidence o social impact) che cercano di

aggiungere sfumature e complessit`a ai modelli classici e di tenere in considerazione le nuove caratteristiche che la societ`a odierna possiede e che influiscono sulle dinamiche di gruppo (es. social media, algorithmic bias, ...).

Rappresentazione matematica

Prima di addentrarci nei dettagli dei diversi modelli, sono necessarie alcune nozioni di base per comprendere come le opinioni e le loro dinamiche vengono rappresentate matematicamente. Gli elementi che, almeno, devono essere rappresentati in un modello di questo tipo sono: le opinioni, le modalit`a di interazione e il tempo.

Per quanto riguarda le opinioni, queste possono essere rappresentate da variabili discrete o continue, in base al contesto specifico che si vuole modellare. Nei modelli discreti molto spesso le opinioni sono binarie, nel senso che possono assumere un va-lore dell’insieme {0, 1} o {−1, 1}, ma altri modelli discreti potrebbero permettere alle opinioni di assumere qualunque valore nell’insieme dei numeri naturali. Nei modelli continui, invece, lo spazio delle opinioni `e normalmente un intervallo dell’insieme dei numeri reali, come ad esempio [0, 1].

Normalmente le interazioni avvengono su una rete, in cui c’`e un nodo per ogni individuo (che sar`a chiamato agente nel contesto di tali modelli) e un arco che rappre-senta una possibile interazione di coppia tra due agenti. Se tale rete `e rappresentata da un grafo completo ci troviamo nel campo dei mean field models per cui le possibili interazioni sono N (N −1)<sub>2</sub> , con N il numero di agenti; modelli pi`u complessi considerano invece una vera e propria rete sottostante con una particolare topologia, in cui pertan-to il numero di possibili interazioni `e dato dal numero di link presenti nella rete. Va infine ricordato come all’interno dei modelli di opinion dynamics `e possibile inserire la presenza di informazioni esterne alla rete, per esempio provenienti dai mass media, inserendo un agente statico (che non cambia mai la sua opinione) e connesso con tutti gli altri agenti.

Il tempo, infine, pu`o essere continuo o discreto. La scelta che viene fatta maggior-mente in letteratura `e quest’ultima.

Definizioni e notazione

Di seguito introdurremo alcune utili definizioni necessarie per comprendere la suc-cessiva trattazione dei principali modelli di opinion dynamics, cos`ı come del presente lavoro di tesi.

L’insieme di tutte le possibili opinioni (numeriche) `e chiamato spazio delle opinioni. L’opinione dell’agente i al tempo t `e indicata da x(t)_i . Indichiamo inoltre con x(t) = [x(t)₁ , x(t)₂ , ..., x(t)_N] il vettore delle opinioni di tutti gli agenti; in alcuni articoli viene anche chiamato profilo. N indica invece la popolazione della rete. Il valore di consenso `e l’opinione condivisa da tutti gli agenti al termine della dinamica ed `e denotato da x∗. Al contrario, la convergenza `e definita come stato di equilibrio, che pu`o essere o meno uno stato di consenso. La polarizzazione normalmente si riferisce a due gruppi di agenti che hanno opinioni agli estremi opposti dell’opinion space. Tuttavia, in alcuni testi, la polarizzazione semplicemente indica l’esistenza di due gruppi (non necessariamente distanti nello spazio delle opinioni).

2.2.1

Modelli discreti

Nonostante il Voter model sia nato nel contesto della competizione delle specie [CS73], `e risultato subito utile per modellare degli scenari sociali come quello delle elezioni [HL75]. Difatti, il modello assume che l’opinione di un individuo possa essere una variabile discreta nell’insieme {+1, −1}. Lo stato della popolazione varia in base ad una semplice regola di aggiornamento: ad ogni iterazione viene scelto casualmente un individuo che poi copia l’opinione di un vicino scelto a sua volta casualmente. Partendo da qualsiasi configurazione iniziale, su una rete completa, l’intera popolazione converge al consenso su una delle due opinioni. La probabilit`a che il consenso sia raggiunto sull’opinione +1 `e uguale all’iniziale frazione di individui che posseggono quell’opinione [PB10].

Majority rule model

Il Majority rule model `e un modello proposto per descrivere i dibattiti pubblici [Gal02]. Gli agenti possono avere un’opinione discreta nell’insieme {−1, +1}, come nei modelli precedentemente descritti. Ad ogni time step un gruppo di r agenti viene sele-zionato casualmente e assumono tutti l’opinione di maggioranza all’interno del gruppo. La dimensione del gruppo pu`o essere fissa o selezionata ad ogni time step da una spe-cifica distribuzione. Se r `e dispari, allora l’opinione di maggioranza `e sempre definita, tuttavia se r `e pari ci potrebbero essere delle situazioni di stallo. Per selezionare un’o-pinione prevalente, in questo caso, viene introdotto un bias in favore dell’oun’o-pinione +1. Quest’idea `e ispirata dal concetto di inerzia sociale [FF84].

2.2.2

Modelli continui

La maggior parte dei modelli di opinion dynamics sono basati su opinioni binarie aggiornate dagli attori sociali in base all’esperienza sociale (interazioni con gli altri agenti) o alla propria esperienza. Un problema interessante riguarda l’assunzione che le opinioni siano binarie o comunque discrete: cosa succederebbe se le opinioni fossero una variabile continua? Ci sono una serie di modelli che esplorano questa possibilit`a. Di seguito verr`a presentata una classe di modelli, i bounded-confidence models e in particolare il modello Deffuant-Weisbuch [DW00], DW-model, che costituisce il punto di partenza di questo lavoro di tesi.

Deffuant-Weisbuch model

Una classe di modelli largamente studiata `e quella dei cosiddetti “bounded-confidence” models, in cui gli agenti sono influenzati da coloro che hanno opinioni sufficientemen-te simili alle proprie. Questa caratsufficientemen-teristica `e giustificata da teorie sociologiche quali l’omofilia, cio`e la tendenza degli individui di associarsi e legarsi con persone simili a loro, come nel proverbio “birds of the same feather flock together” [MS01], ma anche da constatazioni del fatto che gli individui spesso interagiscono tra loro solo quando le loro opinioni sono gi`a sufficientemente vicine, altrimenti non si disturbano neanche

a discuterne e le ragioni per questo comportamento potrebbero essere ad esempio una mancanza di comprensione, un conflitto di interessi o la pressione sociale.

Il DW-model considera una popolazione di N agenti i con opinioni continue xi ∈

[0, 1] distribuite uniformemente. Ad ogni time step discreto, due agenti (i, j), scelti casualmente tra quelli connessi nella rete sociale, si incontrano e, se la distanza tra le opinioni `e inferiore ad una thereshold , |xi− xj| ≤ , allora i due agenti modificano la

propria opinione secondo la regola di aggiornamento:

xi(t + 1) = xi+ µ(xj − xi)

xj(t + 1) = xj + µ(xi− xj)

dove µ `e un parametro di convergenza che pu`o assumere valori µ ∈ [0, 0.5], mentre  pu`o essere vista come una misura dell’apertura mentale degli individui in una popolazione. Per valori bassi, la popolazione sar`a mentalmente chiusa e pertanto gli individui po-tranno essere influenzati solo da chi avr`a un’opinione molto vicina alla loro; per valori pi`u alti invece, quindi quando la popolazione `e pi`u aperta mentalmente, gli individui saranno influenzati anche da chi possiede opinioni pi`u distanti e diverse. Nonostante non ci sia alcuna ragione per supporre che  sia costante in tutta la popolazione, o quantomeno simmetrico nel caso di incontri binari, in tale modello viene sempre preso come un parametro costante (presupponendo che i risultati rimarrebbero simili se  seguisse una certa distribuzione piuttosto che essere uniforme in tutta la popolazione). Le simulazioni condotte su una rete completa, che non si discostano da quelli sui reticoli bidimensionali, dimostrano come la dinamica qualitativa dipende principalmente dalla thereshold , mentre µ e N influenzano soltanto il tempo di convergenza e l’ampiezza della distribuzione delle opinioni finali. Il parametro  quindi controlla il numero di picchi nella distribuzione finale delle opinioni e il numero massimo di picchi decresce in funzione di .

Il DW-model costituisce il punto di partenza per lo sviluppo di un’ampia gamma di nuovi modelli, il cui obiettivo `e quello di aggiungere elementi al modello di base,

l’Algorithmic Bias model [Sˆır+19].

Algorithmic Bias model

Ad oggi, i social network sono diventati la principale fonte di informazioni e anche una grande piattaforma in cui gli individui possono discutere e scambiarsi opinioni. Tuttavia, il flusso di notizie che ciascun individuo vede `e organizzato da algoritmi che sono costruiti per massimizzare l’utilizzo della piattaforma: si ipotizza che questo crei un algorithmic bias (fenomeno anche descritto come algorithmic segregation) poich´e tali notizie vengono selezionate non solo in base alla popolarit`a (ad esempio, il numero di follower del publisher oppure il numero di like/commenti ricevuti), ma anche in base alle precedenti azioni dell’utente sulla piattaforma. Le persone - in generale - prefe-riscono entrare in contatto con informazioni/contenuti/discussioni che confermano la loro narrativa (un fenomeno noto come confirmation bias) e tendono ad interagire mag-giormente con queste, piuttosto che scontrarsi con evidenze che mettono in discussione le loro convinzioni. `E pertanto nell’interesse del service provider fornire i contenu-ti in maniera targecontenu-tizzata, in base a quella che sa essere l’opinione dell’utente su un determinato argomento.

Non solo, la diffusione delle news avviene sui social network dove i link si formano principalmente come conseguenza dell’omofilia, cio`e lo scambio di informazioni avviene tra persone che hanno visioni simili: condividere credenze, valori ed educazione rendono infatti la relazione e la comunicazione pi`u facile [LM64].

La variet`a delle interazioni di una persona pu`o contribuire alla diversificazione delle fonti delle informazioni, tuttavia, riguardo le visioni politiche, l’omofilia risulta parti-colarmente forte. La condivisione tra utenti che hanno credenze simili risulta essere vera anche nel contesto della diffusione di informazioni errate su Facebook, condu-cendo ad un effetto echo chamber, cos`ı come su Twitter dove “partisan users” hanno dimostrato avere un importante ruolo nella polarizzazione. Per cercare di modellare questa situazione si considera una popolazione di N individui, in cui ogni individuo possiede un’opinione nell’intervallo [0, 1], come nel modello precedentemente descritto.

Gli individui sono connessi da una rete completa e le interazioni sono binarie, come nel DW-model, ma la scelta degli individui con cui interagire `e influenzata dall’algorithmic bias. Per controllare l’intensit`a di questo effetto, cio`e quanto estremo `e il filtraggio all’interno della rete, viene inserito un nuovo paramentro γ ∈ [0, 100]: ad ogni time step viene scelto randomicamente un individuo, mentre il partner di interazione viene selezionato in base ad una probabilit`a che decresce con la distanza delle loro opinioni, secondo la formula: pi(j) = d−γ_ij P k6=id −γ ik (2.19) (per γ = 0 il modello diventa il DW-model).Dopo l’interazione, le due opinioni possono cambiare, in base al parametro di bounded-confidence :

xi(t + 1) = xi(t) + µ(xj(t) − xi(t))

xj(t + 1) = xj(t) + µ(xi(t) − xj(t))

considerando soltanto il caso in cui µ = 0.5, cio`e in cui entrambi gli individui adottano l’opinione media.

Per quantificare il numero di cluster, data l’esistenza di cluster maggiori e minori, viene utilizzata la cluster participation ratio come criterio. Questa tiene in considera-zione non solo il numero di cluster, ma anche la fraconsidera-zione della popolaconsidera-zione in ognuno di essi, misurando l’effettivo numero di cluster. Per fare un esempio, possiamo prendere in considerazione una dinamica che termina in 2 cluster: se la popolazione si divide equamente tra i due cluster, la cluster participation ratio sar`a di 2; se invece tutta la popolazione confluisce in un unico cluster, sar`a di 1; nei casi intermedi la clustering participation ratio sar`a un valore nell’intervallo [1, 2]. Tale esempio vale ugualmente nel caso in cui si abbiano m cluster, assumendo un valore nell’intervallo [1, m]. L’effettivo numero di cluster misurato in questa sezione `e quindi calcolato come:

C = ( P ici)2 P ic 2 i (2.20)

dove ci `e la dimensione del cluster i.

Con questa semplice modifica viene dimostrato che la tendenza verso il consenso diminuisce, cio`e serve un livello di apertura mentale () pi`u alto per raggiungere il con-senso. Inoltre, l’approccio allo stato asintotico `e rallentato tremendamente. Pertanto, il selection bias influenza la formazione di opinioni in 3 modi profondi:

1. Inducendo la frammentazione anche in condizioni dove il modello originale pre-diceva il consenso

2. Esacerbando la polarizzazione aumentando la distanza media tra le opinioni 3. Rallentando il processo di diffusione, che rende il sistema altamente instabile

2.2.3

Oltre le interazioni binarie

Le reti classiche, formate da vertici e archi, catturano soltanto relazioni binarie e ogni dinamica collettiva viene analizzata come scomposizione di dinamiche di coppia. Tuttavia, in molti sistemi `e importante catturare dinamiche di gruppo, in quanto le interazioni binarie possono limitare il potere predittivo dei modelli.

L’idea dell’analisi di interazioni collettive non `e nuova: le prime applicazioni han-no provato ad adattare il linguaggio delle interazioni binarie per descrivere interazio-ni di ordine superiore, ad esempio utilizzando grafi bipartiti o attraverso l’analisi di communities, cliques o sottografi densi.

Ad oggi, i naturali candidati per rappresentare sistemi di ordine superiore sono i complessi simpliciali o gli hypergraphs [Bat+20].

Per descrivere propriamente le interazioni di ordine superiore al secondo `e necessario includerle esplicitamente nella struttura della rete.

Complessi simpliciali

I simplessi sono il pi`u semplice oggetto matematico che permette di farlo in quanto un k-simplex σ `e un insieme di k + 1 nodi σ = [p0, p1, ..., pk]. Il simplesso di dimensione

(a) Questo `e un complesso simpliciale (b) Questo non `e un complesso simpliciale

Figura 2.1: Complessi simpliciali. (Fonte: Wikipedia)

0 `e un singolo nodo, il complesso di dimensione 1 `e un arco, il complesso di dimensione 3 `e un triangolo e cos`ı via.

In matematica e topologia, i complessi simpliciali sono un’aggregazione ordinata di simplessi che si intersecano tra loro solo su facce comuni e che rispettano la seguente propriet`a: un insieme di n simplessi K = {σ0, σ1, ..., σn} `e un valido complesso

sim-pliciale se, per ogni k-simplex σ = [p0, p1, ..., pk] ∈ K tutte le sue sotto-facce di ogni

dimensione appartengono a K. Per esempio, se il triangolo [a, b, c] ∈ K allora anche [a], [b], [c], [a, b], [a, c], [b, c] devono appartenere a K.

I complessi simpliciali sono una struttura sufficientemente adeguata a rappresentare le interazioni sociali in quanto `e abbastanza ragionevole ipotizzare che un’interazione su un gruppo implichi anche tutte le interazioni di ordine inferiore. Per distinguere l’importanza relativa delle diverse interazioni si possono includere pesi sui simplessi.

I processi dinamici che simulano il comportamento umano sono stati il focus di molti studi, dove le relazioni sociali e le interazioni sono tipicamente considerati come una struttura sottostante. Le interazioni sociali sono un terreno naturale per testare gli approcci “higher-order”. Dato che gli individui possono interagire in coppie o gruppi, le dinamiche dovrebbero tenere conto degli effetti che le interazioni non binarie potrebbero avere.

Hypergraphs

Anche se i complessi simpliciali superano alcuni dei problemi riscontrati nelle rap-presentazioni di dimensione inferiore, incorporano una limitazione dovuta al fatto che richiedono l’esistenza di tutte le sottofacce. In alcuni casi, infatti, questo vincolo po-trebbe essere troppo restrittivo. Per esempio, quando si studiano i sistemi sociali, `e importante essere in grado di descrivere interazioni di gruppo. In questo caso l’uso dei complessi simpliciali `e abbastanza “sicuro” dal momento che normalmente le intera-zioni sociali in un gruppo implicano tutte le varie interaintera-zioni di coppia o comunque di ordine inferiore. Tuttavia, in altri casi, questo vincolo potrebbe non essere adatto al contesto: se ad esempio consideriamo un collaboration network non `e detta che se tre autori hanno collaborato in un paper abbiano collaborato anche in coppia su altri lavori.

Gli hypergraph forniscono la pi`u generale e non vincolata descrizione delle inte-razioni di ordine superiore. Formalmente un hypergraph `e definito da un insieme V (G) = {1, ..., N } di N nodi e da un insieme di hyper-edges H che specificano quali nodi partecipano in quale modo in un’interazione. Ciascun hyper-edge `e un sottoinsie-me non vuoto di V . A differenza dei complessi simpliciali, un hypergraph pu`o includere l’interazione [a, b, c] senza che ci siano le interazioni binarie sottostanti.

Adaptive voter model su complessi simpliciali

Nel seguente paragrafo `e descritto un recente modello di opinion dynamics discreto che introduce il superamento dell’assunzione che le interazioni siano binarie.

Questo modello [HK20] `e un’evoluzione dell’adaptive voter model che include in-terazioni di ordine superiore al secondo. Il modello, infatti, parte dall’adaptive voter model classico in cui, in aggiunta ad eventi di “persuasione”, si prendono in consi-derazione anche eventi di “riconnessione” in cui link tra nodi con opinione opposta vengono reindirizzati verso nodi con la stessa opinione (anche in questo caso, infatti, le opinioni possono assumere valori esclusivamente nel set {−1, +1}). Tuttavia, i recenti

cambiamenti nella comunicazione e nei social network sollevano seri dubbi sull’assun-zione che le interazioni da prendere in considerasull’assun-zione nel caso dell’opinion dynamics siano solo quelle binarie e, pertanto, nel presente modello si prendono in considerazio-ne interazioni di ordiconsiderazio-ne superiore al secondo o di gruppo, grazie alle quali pu`o essere modellato il meccanismo sociale della peer-pressure. Secondo tale meccanismo, se tre individui sono connessi da un legame di amicizia e si viene a creare una situazione di disaccordo nel gruppo, `e molto probabile che l’opinione di maggioranza all’interno del gruppo prevalga.

Il modello propone un’estensione minimale dell’adaptive voter model in cui per con-siderare un triangolo di agenti (cio`e un sottografo di 3 vertici completamente connesso) un gruppo di amici, si serve di una struttura aggiuntiva, al di l`a di nodi e vertici. La struttura prescelta `e il 2-simplesso: un triangolo di nodi forma un’amicizia se c’`e un simplesso bidimensionale tra questi, oltre i simplessi monodimensionali (gli archi). Dal momento che i nodi possono avere un’opinione solo nell’insieme −1, +1, all’interno di tale struttura c’`e sempre una maggioranza ben definita nei confronti di una o dell’altra opinione. Ad ogni time step, viene scelto un arco casualmente:

1. Se l’arco non fa parte di un simplesso bidimensionale si applica la regola del-l’adaptive voter model classico, ovvero se i nodi hanno opinioni opposte, allora con probabilit`a p ∈ [0, 1] uno dei vertici (scelto con uguale probabilit`a) ricollega l’arco verso un nodo con la sua stessa opinione, scelto casualmente tra i restanti vertici, altrimenti con probabilit`a 1 − p uno dei due vertici scelto casualmente cambia la propria opinione e la adatta all’opinione dell’altro; se i due nodi hanno la stessa opinione, non succede nulla.

2. Se l’arco fa parte di almeno un simplesso bidimensionale e i due nodi hanno opinioni opposte allora con probabilit`a q ∈ [0, 1] viene scelto casualmente un simplesso di cui l’arco fa parte e la maggioranza persuade la minoranza con probabilit`a p. Con probabilit`a q − 1 viene invece applicato l’adaptive voter model classico e quindi si procede alla riconnessione degli archi.

3. Se l’arco fa parte di almeno un simplesso bidimensionale, ma `e inattivo, non succede nulla.

Per quanto riguarda la creazione di un complesso simpliciale, a partire da una rete (V, E), nel presente modello gli autori hanno scelto di prendere l’iniziale popolazione di triangoli del grafo e, di questi, un insieme S vengono dichiarati simplessi bidimensionali, mentre i restanti rimangono triangoli semplici. Dal momento che tramite un evento di rewiring alcuni dei simplessi potrebbero venire distrutti, ogni volta che questo accade viene scelto un altro triangolo per diventare un simplesso bidimensionale.

Le simulazioni eseguite su tale modello sembrano dimostrare come l’euristica secon-do cui la peer-pressure porti alla polarizzazione sia vera.

Multi-body Interactions and Non-Linear Consensus Dynamics on Networ-ked Systems

Nel sistema multi-body (cio`e che include interazioni di ordine superiore al secondo) descritto in [NML20], la struttura della rete `e rappresentata dall’adjacency tensor A ∈ RN ×N ×N _{con valori} Aijk =        1 if {i, j, k} ∈ T (G) 0 altrimenti (2.21)

In tale ricerca vengono analizzati gli effetti di interazioni non lineari in un modello continuo su una higher-order structure. Viene pertanto proposta una generalizzazione di un modello continuo che tiene in considerazione di interazioni di terzo ordine che catturano due importanti meccanismi sociali: peer-pressure e omofilia.

In tale modello i nodi interagiscono attraverso hyperedges di dimensione 3 su un hypergraph. Nel modello viene definito un sistema in cui esistono solo interazioni a 3, dal momento che A non pu`o descrivere archi. L’evoluzione delle N variabili dinamiche xi `e data da: xi = N X j,k=1 Aijks(|xj − xk|)[(xj− xi) + (xk− xi)] (2.22)

dove l’adjacency tensor Aijk restringe le interazioni ai nodi che condividono un

hy-peredge. Il terzo termine del prodotto, che indica l’influenza dei due nodi j e k su i, `e modulato da un’ulteriore funzione di influenza (il secondo termine del prodotto, s(x)) che dipende dalla differenza tra gli stati di altri nodi che compongono l’hype-redge. In base alla scelta di s(x), questo modello pu`o riprodurre gli effetti rinforzanti o inibitori che due nodi di un 2-simplex possono avere sul terzo. Per esempio se s(|xj − xk|) = exp(λ|xj − xk|) e λ < 0, stati simili di j e k possono accelerare la

dinamica di i (o decelerarla se λ > 0). Come atteso, se s(x) `e costante, cio`e λ = 0, il modello si riconduce allo stato lineare standard e la dinamica conserva l’opinione media al tempo t. Questo non vale quando vengono considerate interazioni non lineari. Nel mean field le interazioni di ordine superiore possono produrre uno spostamento sull’opinione media del sistema in base allo stato iniziale dei nodi. In particolare, per un’inizializzazione binaria non bilanciata (quindi inizialmente la media non `e 0.5) lo stato medio asintotico `e spostato verso la maggioranza se λ < 0 o verso il bilanciamen-to se λ > 0. Questi risultati sono confermati da simulazioni numeriche su hypergraph completamente connessi. Ulteriori analisi sui modular hypergraph hanno sottolineato l’ulteriore ruolo giocato da sottografi locali nel portare il sistema verso una dinamica asimmetrica nel caso in cui vengano considerate delle topologie non banali.

3

I modelli

I contributi del presente lavoro di tesi sono tre: il primo `e testare l’Algorithmic bias model su reti random e reti scale-free, in modo da analizzare la dinamica delle opinioni in un contesto pi`u realistico; il secondo `e ampliare il modello di base considerando non solo interazioni binarie, ma anche di gruppo, in modo da poter modellare l’effetto della peer pressure sul cambiamento delle opinioni dei singoli agenti, modificando il precedente modello, prendendo spunto dal setting dell’Adaptive voter model su com-plessi simpliciali [HK20] descritto nel paragrafo 2.2.3; il terzo `e aggiungere anche la possibilit`a di rewiring degli archi, qualora la differenza di opinioni spinga uno dei nodi a porre fine al rapporto e a cercare qualcuno di pi`u affine con cui collegarsi (come per altro avviene nell’Adaptive voter model).

3.1

Algorithmic bias model su reti complesse

Il mean-field costituisce un ottimo punto di partenza per testare i risultati della diffusione delle opinioni generati da un particolare modello. Tuttavia, l’assunzione che tutti gli individui siano connessi, o comunque possano comunicare, tra loro `e piuttosto forte e, nella realt`a, difficilmente si verifica tale situazione. Ad oggi, infatti, la mag-gior parte degli scambi di opinioni si verificano all’interno degli online social network, come ad esempio Twitter o Facebook, in cui ciascun individuo pu`o leggere e rispon-dere soltanto a chi `e gi`a incluso nella sua rete di contatti, rimanendo all’oscuro delle opinioni espresse da coloro con cui non ha un legame. In letteratura sono presenti risultati riguardanti l’applicazione del DW-model senza algorithmic bias su reti con particolari topologie, come ad esempio reti scale-free [Sˆır+19; Wei04; SM04; For04], che dimostrano che quando le reti contengono un grande numero di archi i risultati

rimangono analoghi a quelli ottenuti sul mean field, mentre, quando la sparsit`a della rete `e molto alta, `e visibile un aumento nel numero di opinion cluster finali. Sulla scia di questa tipologia di analisi, il punto di partenza del presente lavoro di tesi preve-de di testare l’Algorithmic Bias mopreve-del sia su reti random (Erdos-Renyi), sia su reti scale-free (Barabasi-Albert), per poter verificare se la struttura della rete accentua la polarizzazione e la frammentazione generate dalla presenza del selection bias oppure no.

3.2

Algorithmic bias model con peer pressure e reti adattive

3.2.1

Peer pressure

I recenti cambiamenti nella comunicazione e nei social network sollevano seri dubbi sull’assunzione di base del Deffuant-Weisbuch model e dell’Algorithmic bias model che soltanto le interazioni binarie debbano contare nell’evoluzione delle opinioni di una popolazione [HK20; Jia+15; WD07]. All’interno di un social network come Twitter gli individui partecipano a scambi di opinioni “binari” con altri individui, ad esempio tramite messaggi diretti, che possono essere modellati come interazioni binarie, dal momento che nessun altro pu`o parteciparvi. Tuttavia, la possibilit`a di pubblicare tweet e instaurare discussioni al di sotto di essi apre la questione di come i partecipanti vengano influenzati dalle altre opinioni espresse nel thread e di come a loro volta possano influenzare le opinioni degli altri. In ogni caso, anche al di fuori dei social network, quando due individui hanno uno o pi`u amici in comune, `e pi`u probabile che gli scambi di opinioni avvengano all’interno del gruppo come insieme, piuttosto che tra singole coppie in intervalli di tempo diversi. Va inoltre considerato che, se il gruppo che consideriamo `e una cricca (clique), in cui tutti gli individui hanno legami reciproci tra loro, possono entrare in gioco meccanismi sociali come quello della peer pressure. Tale fenomeno consiste nell’influenza che viene esercitata su un individuo da parte del gruppo di pari, portandolo a cambiare i propri comportamenti, valori o opinioni per seguire quelli della maggioranza: per esempio, se tre individui sono connessi tra loro da

legami di amicizia e c’`e un disaccordo nelle opinioni, `e molto probabile che l’opinione di maggioranza all’interno del gruppo prevalga e gli individui in minoranza adottino l’opinione della maggioranza, modificando la propria [HK20].

Alla luce di queste considerazioni, nel presente lavoro viene proposta e studiata un’estensione dell’Algorithmic bias model (AB-model) [Sˆır+19], che aggiunge la possi-bilit`a di interazioni ternarie tra gli agenti, come avviene nel caso dell’Adaptive voter model on simplicial complexes (SC-model) [HK20].

Come nei due modelli di base, anche in questa implementazione si considera un insieme V di N agenti e un insieme E di L archi che li collegano. Le opinioni, invece, vengono mantenute continue come nell’Algorithmic bias model e pertanto ogni indivi-duo i, con i ∈ V , possiede un’opinione continua xi ∈ [0, 1], diversamente da ci`o che

avviene nel Voter model che, essendo un modello discreto, considera solo due possi-bili opinioni xi ∈ {−1, +1}. Vengono fissati poi il parametro di bounded confidence

 ∈ [0, 1] e il parametro di algorithmic bias γ ∈ [0, 100], che sono omogenei in tutta la popolazione.

Dato che le opinioni sono continue i nodi non possono essere giudicati concordi soltanto quando le opinioni sono identiche come nel caso dei modelli discreti. Si `e scelta pertanto la seguente regola: due nodi i, j vengono considerati concordi se |xi− xj| < ,

altrimenti vengono considerati discordi.

Le regole di aggiornamento proposte e testate sono tre e danno vita a tre model-li diversi, tutti basati su una combinazione dell’Algorithmic bias model [Sˆır+19] con l’Adaptive voter model su complessi simpliciali [HK20], ciascuno dei quali cerca di cat-turare sfumature diverse delle dinamiche di gruppo e in particolare ciascuno dei quali modella in maniera leggermente diversa la peer pressure. Tali modelli sono stati deno-minati pertanto Algorithmic bias on simplicial complexes models (ABSC models) 1, 2 e 3. In tutti e tre i modelli viene selezionato casualmente un nodo n1 e successivamente un partner di interazione n2, in base alla probabilit`a determinata dall’algorithmic bias, secondo l’equazione 2.19.

Figura 3.1: Peer-pressure. Dal momento che n2 e n3 sono concordi, ma n1 `e discorde, questo viene attirato dalla maggioranza adottando la loro opinione media.

Algorithmic bias on simplicial complexes 1

L’idea che sta alla base di tale modifica `e che se all’interno di un triangolo, che rap-presenta un’amicizia tra tre individui, due di questi hanno opinioni abbastanza simili da poter essere definiti concordi, o che comunque si trovano pi`u allineati verso una certa idea rispetto al loro interlocutore, spingeranno (secondo la teoria della peer-pressure) il terzo individuo a conformarsi alla loro opinione. Nel voter model su complessi sim-pliciali (tralasciando la componente adattiva del modello), quando due di tre agenti hanno la stessa opinione, il terzo automaticamente la adotta e questo `e possibile es-sendo un modello discreto in cui le opinioni possono essere solo {−1, 1}. Dal momento che nel presente lavoro si `e scelto di mantenere opinioni continue, la conformazione di un individuo al suo gruppo di pari avviene adottandone l’opinione media, mentre l’opinione degli altri due non cambia, come se non interagissero. Quando invece tutti e tre gli agenti sono sufficientemente vicini, il risultato finale sar`a un’unica opinione per i tre nodi, che adotteranno l’opinione media del gruppo. In figura 3.1 e 3.2 sono illustrati i due diversi casi. La regola di aggiornamento nel modello ABSC1 `e descritta nell’algoritmo 1.