Evolving Networks
Daniele Contarino
University of Catania
Department of Mathematics and Computer Science (DMI)
Executive summary
Introduzione
I modelli Barabási-Albert e Bianconi-Barabási
Evolving Networks
Fitness Model
Perché Google+ non ha (ancora) battuto Facebook?
Introduction
Google è stato inventando 6 anni dopo la
diffusione del WWW ed esistevano altri motori di ricerca. Come ha fatto a batterli?
Facebook come si è imposto come il più grande Social
Network nonostante non è
È vero il detto ‘chi prima arriva, meglio alloggia’?
First means better?
La risposta giusta è: ANCHE, ma non solo!
La storia insegna che il successo dipende dal tempo di presenza sul mercato e dalla attrattività
Modelliamo la realtà del mercato come un grafo bipartito
Reality as Network
Società Clienti
Utenti Link
Il successo dipende dalla capacità di una società di acquisire consumatori; oppure l’abilità di un sito web di fidelizzare tanti
visitatori unici giornalieri.
Tale capacità la chiameremo
Fitness propriety
Executive summary
Introduzione
I modelli Barabási-Albert e Bianconi-Barabási
Evolving Networks
Fitness Model
Cercando di realizzare il nostro modello di mercato, analizziamo quindi i due passi:
Growth (crescita)
Ogni slot di tempo, un nodo j-esimo con m link e una fitness η viene aggiunto al sistema
Preferential Attachment (Affezione preferenziale)
La probabilità che un nodo si connetta a un nodo preesistente con un determinato numero di link
Growth of the Network
Growth (lineare) 𝑘 = 2𝑚 Preferential attachment (lineare) Π 𝑘𝑖 ∝ 𝑘𝑖
Barabàsi-Albert Model
Usato per generare delle reti scale-free casuali, il modello Barabàsi-Albert descrive la probabilità che un nuovo nodo aggiunto al sistema di
connetta con gli altri nodi. Tale probabilità e data dalla seguente
Barabàsi-Albert Model
𝚷 = 𝒌𝒊
# di connessioni
Il modello di Barabàsi-Albert però non tiene conto della fitness che è
intrinseca ogni nodo.
Occorre modificare il nostro modello
Fitness in BA Model
La probabilità di connessione di un nuovo nodo i- esimo è data dal seguente modello di Bianconi- Barabàsi
Bianconi-Barabàsi Model
𝚷𝒊 = 𝜼𝒊𝒌𝒊 𝜼𝒋 𝒋𝒌𝒋
Il nostro interesse è osservare come la rete si possa evolvere nel futuro. Esattamente come possiamo misurare l’accelerazione
derivando la velocità rispetto al tempo, possiamo applicare la teoria del continuo al BB model.
Degree dynamics
Degree dynamics
𝝏𝒌𝒊
𝝏𝒕 = 𝒎 𝜼𝒊𝒌𝒊 𝜼𝒋 𝒋𝒌𝒋
𝒌𝜼𝒋(𝒕, 𝒕𝒊) = 𝒎 𝒕 𝒕𝒊
𝜷(𝜼𝒊)
𝜷(𝜼𝒊) = 𝜼 𝑪
𝑪 = 𝝆 𝜼 𝜼
𝟏 − 𝜷 𝜼 𝒅𝜼
Possiamo considerare il BB Model come il caso generale del AB Model. Infatti, nell’AB Model, possiamo considerare la fitness di tutti i nodi uniforme pari a 1, ergo
Degree dynamics
𝜷(𝜼) = 𝟏
𝟐 𝒌𝜼𝒋(𝒕, 𝒕𝒊) = 𝒎 𝒕 𝒕𝒊
𝟏𝟐
Π𝒊 = 𝒌𝒊 𝒌𝒋 𝒋
Executive summary
Introduzione
I modelli Barabási-Albert e Bianconi-Barabási
Evolving Networks
Fitness Model
I modelli visti fino ad ora (BA, BB e SW) sono dei modelli minimali e
Ancora non riescono ad rappresentare la realtà
Evolving Networks
Mentre gli altri modelli rappresentano una realtà
"istantanea", le Evolving Networks considera l’evoluzione della rete nel tempo
Evolving Networks
Processi a cui sono soggette le reti nel tempo
Attrattività iniziale
Link interni
Eliminazione di nodi
Crescita accelerata
Invecchiamento
Evolving Networks
Per BA Model, un nuovo nodo senza link ha una probabilità pari a 0 di acquisire nuovi link.
Nella realtà invece esiste una probabilità concreta che permette a un nuovo
nodo di acquisire collegamenti.
Initial Attractiveness
BA Model 𝚷 𝒌 = 𝒌
𝒌𝒋 𝒋
𝑷𝒌~ 𝒌𝟑 𝜸 = 𝟑
Evolving Network
𝜫 𝒌 = 𝑨 + 𝒌 𝑷𝒌~ 𝑪(𝒌 + 𝑨)−𝜸
𝜸 = 𝟑 + 𝑨 𝒎
Initial Attractiveness
In molte reti, dei nuovi link sono aggiunti tra nodi preesistenti (eg. una nuova relazione di amicizia tra due persone su un social network).
Internal Links
Che preferential attachment
seguono i questi due nuovi link?
𝜫(𝒌, 𝒌′) ∼ (𝑨 + 𝑩𝒌)(𝑨′ + 𝑩′𝒌′)
Double Preferential Attachment
𝐴 = 𝐴
′= 0
In questo caso, gli estremi dei collegamenti sono scelti in base al grado del nodo a cui si
connettono.
Di conseguenza, il collegamento seguirà il BA Model
Π 𝑘, 𝑘′ ∼ 𝐵𝑘 𝐵′𝑘′ 𝛾 = 2 + 𝑚
Random Internal Attachment
𝐵 = 𝐵
′= 0
In questo caso, ai link interni viene nascosto il grado dei nodi a cui si connettono, quindi essi si collegano a nodi casuali. Considerato il BA Model, otteniamo
Π 𝑘, 𝑘′ ∼ 𝐴𝐴′
2𝑛
Nelle reti reali, spesso succede che a un
determinato tempo t viene rimosso un link.
Basti pensare a dei dipendenti che lasciano un’azienda o dei documenti
che vengono rimossi dal web
Node Deletion
Per analizzare l’impatto dell’eliminazione di un nodo, consideriamo il nodo con m link e con una probabilità r circa la rimozione dello stesso.
La topologia osservata dipenderà dal valore di r.
Node Deletion
Se r < 1 significa che il numero di nodi rimossi è minore ai nodi che si aggiungono, ergo la rete continuerà ad ingrandirsi.
Scale-free phase
𝛾 = 3 + 2𝑛 𝑚
Se r = 1 la rete rimarrà con un numero di nodi
costante, ergo a questo punto la rete non sarà più scale-free.
Exponential phase
𝛾 = ∞
Se r > 1 indica che il numero di nodi rimossi è superiore ai nodi che vengono aggiunti. Questo indica che la rete si sta'
contraendo.
Eg. Le ricerche sull’Alzheimer cercano di capire la riduzione di neuroni con l’avanzare dell’età
Declining networks
Eliminazione di un nodo non sempre è
casuale, ma può dipendere dal grado del nodo
(eg. è improbabile che sparisca il nodo di Google, è più probabile che sparisca una pagina web personale)
Finché la rete continua a crescere, essa non perde la sua natura scale-free
Il grado dell’esponente (γ ) dipende dalle politiche di rimozione dei nodi
Node Deletion Note
Fino ad ora abbiamo ipotizzato che il # di link cresceva in maniera proporzionale rispetto al # di nodi e indipendente dal tempo.
Per alcune reti invece il tasso di crescita dei link è:
Superiore o inferiore risp. al
# di nodi
Dipendente dal tempo
Accelerate Growth
Prima abbiamo ipotizzato che ogni nodo poteva avere m link.
Adesso, ipotizziamo che il # di link sia in funzione del tempo
Accelerate Growth
BA Model 𝒎 = 𝒄𝒐𝒏𝒔𝒕
Evolving Network 𝒎 𝒕 = 𝒎𝟎𝒕𝜽
𝜃 =
= 0
> 0
= 1
Accelerate Growth
Crescita costante (AB Model) Crescita accelerata
𝛾 = 3 + 2𝜃 1 − 𝜃
Grado divergente, crescita ultra accelerata, lineare risp. al tempo
Mentre in alcune reti un nodo viene eliminato senza alcun "segnale", nelle reti che meglio
rappresentano la realtà i nodi preparano la loro uscita di scena.
eg. un ricercatore alla fine della carriera ridurrà il numero di pubblicazioni in
Aging
Consideriamo la probabilità che un nuovo nodo si connetta a un nodo con preferential attachment pari
Aging
Π 𝑘, 𝑡 − 𝑡′ ∼ 𝑘 𝑡 − 𝑡′ −𝜐
Aging
𝜐 =
< 0
> 0
> 1
I nuovi nodi tendono a collegarsi con i nodi più vecchi
I nuovi nodi tendono a collegarsi con i
nodi più giovani La rete perde la natura scale-free
Evolving Network Conclusion
Coffee Break
Executive summary
Introduzione
I modelli Barabási-Albert e Bianconi-Barabási
Evolving Networks
Fitness Model
Osserviamo le reti evolutive con la funzione di fitness usando come esempio un modello
proveniente dalla fisica quantistica.
Fitness Model
Il modello in questione è il
Condensato di Bose-Einstein
Nella mondo delle particelle, come si osserva l’iterazione di due o più particelle?
Tale iterazione è descritta tramite le Statistiche quantiche
Maxwell-Bolzmann
Bose-Einstein
Fermi-Dirac
Quantum Statistics
Fermi-Dirac
Due particelle non posso stare nello stesso stato quantico
Rispondono a questa statica gli elettroni, protoni, neutroni e altre particelle a spin semintero.
Questa statistica è la base del principio di esclusione di Pauli
Bose-Einstein
Tutte le particelle tendono a stare nello stesso stato quantico
Rispondono a questa statica i fotoni e fononi
Quantum Statistics
Fermi-Dirac
𝑛(𝜀) = 1
𝑒(𝜀−𝜀𝐾𝐵𝑇𝐹) + 1
Bose-Einstein
𝑛(𝜀) = 1
𝑒(𝜀−𝜇)𝐾𝐵𝑇 − 1
Quantum Statistics Distribuition
Il condensato di Bose-Einstein è uno stato della materia i cui una frazione non trascurabile di bosoni sono portati a una temperatura prossima a 0°K. Cosi facendo essi si portano nello stato quantistico
di più bassa energia e mostrano a livello macroscopico gli effetti
Bose-Einstein Condensation
Possiamo considerare un gas quantico come una rete?
Mapping to a quantum gas
Decisamente SI!
Fitness
Preferential Attachment Links
Nodi
Mapping to a quantum gas
Energia
Particelle
Livelli di energia
𝜼 = 𝒆−𝜷𝜺
𝜫𝒊 = 𝒆−𝜷𝜺𝒊𝒌𝒊 𝒆−𝜷𝜺𝒋𝒌𝒋
𝒋
From Fitness to BE Condesation
deriviamo risp.
al tempo
𝛱𝑖 = 𝑒−𝛽𝜀𝑖𝑘𝑖 𝑒−𝛽𝜀𝑗𝑘𝑗
𝑗
𝜕𝑘𝑖
𝜕𝑡 = 𝑚 𝑒−𝛽𝜀𝑖𝑖𝑘𝑖(𝜖𝑖, 𝑡, 𝑡𝑖) 𝑒−𝛽𝜀𝑗𝑘𝑗(𝜖𝑗, 𝑡, 𝑡𝑗)
𝑗
𝑘𝑖(𝜖𝑖, 𝑡, 𝑡𝑖) = 𝑚 𝑡 𝑡𝑖
𝑓(𝜖𝑖)
𝑓 𝜖𝑖 = 𝑒−𝛽 𝜀−𝜇
𝜌 𝜖 1
𝑒𝛽 𝜀−𝜇 − 1𝑑𝜖 = 1
Che a sua volta soddisfa il seguente integrale
La probabilità che il nodo ha l’energia 𝜀 e la fitness 𝜂
From Fitness to BE Condesation
Osserviamo due casi
𝒕 → ∞ la fitness è mappata dentro il gas di Bose
Se è un gas ideale (tutti i livelli sono occupati) abbiamo 𝜌 𝜖 𝑛 𝜖 𝑑𝜖 = 1
In conclusione, possiamo dire che la fitness segue la statistica di Bose-Einstein
1
BA Model vs BB Model
Bose-Einstein condensation Fit-gets-rich
Non esiste un esponente che caratterizza tutte le reti
La crescita e il preferential attachment sono i responsabili della caratterizzazione delle reti e se emerge la natura scale-free
Per modellare le reti reali si deve
Identificare i processi microscopici che prendono parte al sistema
Sviluppare modelli dinamici che posso
Conclusion
I modelli ER e WS sono modelli statici.
modellano reti con un numero fisso di nodi, che spesso sono artefatte e non rappresentano dei sistemi reali
I modelli BA ed Evolving Network sono modelli dinamici
Mirano a riprodurre l’origine di una rete e la sua evoluzione , ma non la struttura. Dalla sua
applicazione, si ottiene la topologia
Conclusion
1. A. Barabàsi, Evolving Network,
http://barabasilab.neu.edu/networksciencebook/
(Chapter 6), 2014
2. G. Bianconi A. Barabàsi, Bose-Einstein Condensation in Complex Networks, University of Notre Dame,
Indiana, 2001
3. F. Simone, Appunti di Fisica Moderna, INFN, Università di Catania, 2013
