The Directed Closure Process in Hybrid Social-Information Networks
with an Analysis of Link Formation on Twitter
Dario Nardi
Seminario Sistemi Complessi
15 Aprile 2014
Reti d’informazione
Connettono pagine web
Collegamenti fatti da un utente a un altro
Strutture orientate,
Pochi nodi con alto in-degree
Reti sociali
Connettono le persone e le loro nozioni,
Strutture non orientate
Spesso collegamenti reciproci
Meno disparit` a nelle connessioni
Reti sociali:
Rapporti tra le persone
Reti d’informazione Celebrit` a
Generatori automatici di news
Formazione delle connessioni
Triadic closure: Un arco connette due nodi che hanno un vicino in comune
Directed closure: Un arco A-C chiude un percorso two-step (attraverso B)
I
Non dipende solo dalla struttura del grafo ma anche dall’ordine di arrivo degli archi
I
L’arco AC esibisce chiusura se e solo se esistevano in precedenza l’arco
AB e l’arco BC
Microcelebrit` a
Utenti con un numero di followers compreso tra i 10000 e i 50000 L in (c) lista ordinata cronologicamente di followers di C
L out (C ) lista ordinata cronologicamente di following di C
Un arco AC esibisce chiusura se e solo se esiste un nodo B che precede A
in L in (c) e che precede C in L out (A)
Nozioni
closure ratio
Il closure ratio di un nodo ` e il rapporto degli archi entranti che esibiscono chiusura rispetto al numero totale di archi entranti
k-linked
Un utente A ` e k-linked con C, se:
I
A segue C
I
A segue k followers di C S k (C ) utenti k-linkati con C
f k la parte di utenti in S k (C ) che esibiscono chiusura
Test di randomizzazione
??Question??
La directed closure ` e un processo fondamentale per la crezione di collegamenti in twitter?
∀k con |S k | > 10
Approssimiamo il valore di f k assumendo che l’arco ` e arrivato in ordine random
Simulazione con una rete in cui:
I
A e altri k nodi che puntano a loro volta a C
I
Si scelgono a random |S
k| ordinamenti differenti per gli archi della rete.
I
Si determina il numero di archi con cui l’arco A-C esibisce chiusura 100 simulazioni
L’error bar inclusa tra i valori minimi e massimi delle 100 simulazioni
Risultati
Figure :i punti connessi indicano il valore di fx. i cerchi indicano il closure ratio medio durante le 100 simulazioni e i pi`u indicano l’error bar
Propriet` a
Il closure ratio si stabilizza a una costante positiva f
I
Diversa da una microcelebrit` a a un altra
I
Non relativa al in-degree della microcelebrit` a
Figure :Closure ratio in funzione dell’ordine di arrivo dei nodi entranti per 18 microcelebrit`a
Si pu` o simulare il comportamento delle microcelebrit` a senza eseguire una
coppia dei collegamenti?
Attaccamento preferenziale
Fissato α ∈ [0, 1] e D, N ∈ N, il grafo ha N nodi 0,1,...,N-1 A tempo T=0 nel grafo sono presenti solamente i nodi 0 e 1, e un arco che parte dal nodo 1 per il nodo 0
A ogni T=j, il nodo j entra nel grafo con D archi diretti ai nodi 1, 2, ...., j − 1. Il nodo finale di ogni arco ` e scelto nel seguente modo:
I
Con probabilit` a α il punto finale ` e scelto a random da {1, 2, .., j − 1}
I
Con probabilit` a 1 − α il punto finale ` e scelto a random attraverso il
pesi d
i(in-degree del nodo).
Closure ratio in funzione dei vertici arrivati in ordine, dei
10 nodi con pi` u alto in-degree
Calcolo euristico
La somma dell’in-degree dei nodi entranti giocano un ruolo importante per determinare il closure ratio
Etarchi al tempo t Ntnodi al tempo t
dt(j ) in-degree del nodo j al tempo t
Ft(j ) = {x : ∃e = (x1, j ), al tempo t} insieme di nodi che puntano a j
dt(s) =X x ∈S
dt(x ) somma dell’in-degree dei nodi
nell’insieme S St(j ) = α|Ft (j)|
Nt + (1 − α)dt (Ft (j))
Et probabilit`a che un arco dal nodo j+1 al nodo j esibisca chiusura
C N−1 (j ) = 1 − 1 − (1 − S N−1 (j )) D DS N−1 (j )
Fissato il nodo j, un arco e in uscita dal nodo t+1 L’evento V = ∃e0= (t + 1, x ) creato prima di e tale che un arco in uscita dal nodo x punta al nodo j
Ct,e(j ) probabilit`a dell’evento V
I Se e `e il primo arco uscente da t+1 V non `e successo
I Se e `e il secondo arco uscente da t+1Ct,e(j ) = St(j )
I Se e `e il terzo arco uscente da t+1Ct,e(j ) = [1 − (1 − St(j ))2] I Se e `e il d-esimo arco uscente da
t+1Ct,e(j ) = [1 − (1 − St(j ))d −1] Ct,e(j ) =D11 − (1 − St(j ))) +D11 − (1 − St(j ))2] +
· · ·D11 − (1 − St(j ))D−1] = 1 −1−(1−st (j))D DSt (j) La probabilit`a che e esibisca chiusura P(V |e = (t + 1, j ))
In base alla nostra approssimazione, usiamo al probabilit`a incondizionale P(v ) = Ct(j ) Se il lim
t→∞Ct(j ) < ∞ e N `e grande abbastanza il closure ratio del nodo j `e circa CN−1
Attaccamento preferenziale con fitness
Fissato α ∈ [0, 1] e D, N ∈ N, il grafo ha N nodi 0,1,...,N-1 Ogni nodo ha un parametro fitness f i ∈ [0, 1]
A tempo T=0 il grafo ha solo i nodi 0 e 1,con un arco che parte dal nodo 1 per il nodo 0
A ogni T=j, il nodo j entra nel grafo con D archi diretti ai nodi 1,2,....,j-1. Il nodo finale di ogni arco ` e scelto nel seguente modo:
I
Con probabilit` a α il punto finale ` e scelto a random da {1, 2, .., j − 1}
I
Con probabilit` a 1 − α il punto finale ` e scelto a random con il peso dei
nodi i dato da d
if
iRisultati
N = 200, 000, α = .3 e D = 10 La prima figura mostra il closure ratio di 10 nodi in apporto al loro in-degree
Closure ratio per ogni nodo j
Attaccemento preferenziale con comunit` a
Fissato α ∈ [0, 1] , β ∈ [.5, 1] e D, N ∈ N, il grafo ha N nodi 0,1,...,N-1
C comunit` a
A tempo T=0 il grafo ha C comunit` a ognuna con 2 nodi , uno punta all’altro
A ogni T=j, il nodo j entra nel grafo con D archi diretti ai nodi 1,2,....,j-1. Il nodo finale di ogni arco ` e scelto nel seguente modo:
I
con probabilit` a β l’arco punta a un nodo della stessa comunit` a
I
Con probabilit` a 1 − β il punto finale ` e scelto da {1, 2, .., j − 1}
I
Con probabilit` a α il punto finale sar` a scelto in maniera preferenziale (es. il peso dell’in-degree attuale del nodo)
I
