(LABORATORIO DI )
SISTEMI INFORMATICI AVANZATI
Giuseppe Manco
LINK PREDICTION
OUTLINE

Overview

Link Prediction Variants

Deterministic Methods

Probabilistic Methods

Supervised Learning Approaches
PROBLEM DEFINITION

Data una snapshot della social network al tempo
t, cerchiamo di predire accuratamente quali archi
verranno aggiunti alla rete durante l’intervallo di
tempo da t fino ad un istante futuro t’
APPLICAZIONI

Identificazione della struttura di una rete
criminale:
I dati a disposizione sono incompleti
 Cerchiamo di ricostruire i collegamenti all’interno
della rete criminale

APPLICAZIONI

Superare il problema della sparsità nei
recommender systems basati sul collaborative
filtering

Chi compra:

Comprerà anche:
APPLICAZIONI

Accelerare il formarsi di link che altrimenti si
sarebbero formati in maniera spontanea ma
molto più lentamente (serendipity).
Rete della ricerca scientifica
 Rete di lavoro

APPLICAZIONI

Analizzare la storia di navigazione degli utenti di
internet al fine di incrementare l’efficienza di
navigazione

Predictive server prefetching
APPLICAZIONI

Monitorare e controllare virus che viaggiano su
reti di poste elettroniche
LINK COMPLETION


Problema

I dati a disposizione di una rete sociale potrebbero
essere incompleti

Un link potrebbe unire più di una coppia di nodi
Obiettivo

Dato un nodo (o una serie di nodi) connesso (connessi)
tramite un link, determinare quali altri nodi fanno
parte del link
LINK COMPLETION

Esempio

Un cliente compra 5 libri online, e durante il
trasferimento in rete dei nodi si perde l’informazione
sul titolo di uno dei libri

Un algoritmo di Link Completion potrebbe inferire il
nome del libro mancante basandosi sul profilo
dell’utente e sugli altri libri acquistati
LINK COMPLETION

Esempio

Maria, Marco ed una terza persona partecipano ad un
meeting

A partire dalle precedenze co-occorrenze a meeting
della base di utenti cui appartengono Maria e Marco,
determinare il nome della terza persona
SOLUZIONE SEMPLICE

Associamo ad ogni entità A un punteggio score

Co-occorrenze:


Score(A) = somma del numero di co-occorrenze
precedenti tra A e gli altri nodi del link
Popolarità

Score(A) = numero di occorrenze di A in altri link
PROBLEMI NELLA LINK DISCOVERY




Il numero di coppie da analizzare è quadratico
rispetto al numero di nodi del grafo
Reti sparse  pochi casi osservati di interesse
Scoperta di link inattesi e/o anomali all’interno
dei dati osservati (outliers)
Pochissimi comuni vicini o troppo distanti fra loro
LINK PREDICTION
TECNICHE DI LINK PREDICTION


Tutte le tecniche che analizzeremo associano uno
score(x,y) a tutte le coppie di nodi (x,y) della rete,
in base all’organizzazione del grafo in input
L’output è una lista di probabili archi che si
formeranno in futuro, ordinati per score(x,y)
decrescenti
SHORTEST PATH

Lo score(x,y) è la lunghezza del percorso minimo
tra x e y

score(x,y) = spl(x,y)
COMMON NEIGHBORS

Lo score(x,y) è la cardinalità dell’intersezione dei
vicinati di x e y
score( x, y)  ( x)  ( y)

Newman 2001: La probabilità che uno scienziato
A collabori con un altro scienziato B, aumenta
condizionalmente al numero di collaboratori che
hanno in comune.
JACCARD SIMILARITY

Bilanciamento della misura Common Neighbors
tramite le dimensioni dei vicinati
score ( x, y ) 

( x)  ( y )
x e y condividono molti vicini perché
probabilmente hanno vicinati estesi


( x)  ( y )
Si pesano solo i vicinati aderenti al link in analisi
Rispetto al Common Neighbors è una misura
relativa e non assoluta
ADAMIC/ADAR

Lo score(x,y) dipende da quante feature
condividono x e y
1
score( x, y) 

z: feature shared by x , y log( frequency( z ))

Nel caso in cui le feature siano altri nodi
score ( x, y ) 
1

z ( x )  ( y ) log(  ( z ))
PREFERENTIAL ATTACHMENT

Nel preferential attachment lo score è definito:
score( x, y)  ( x)  ( y)

Newman 2001: La probabilità che x sia coatore di
y è correlata al prodotto del numero di
collabaratori di x e y
KATZ CENTRALITY (1953)

Secondo la Katz Centrality:

score ( x, y )    l  pathsx , y
l
l 1
 pathsx , y indica l’insieme dei percorsi di lunghezza
pari ad l tra x e y
l


Alla somma dei pesi dei percorsi nel caso di grafo
pesato
La centralità di Katz è una misura che somma i
pesi di tutti i path tra due nodi bilanciadoli sulla
lunghezza tramite un fattore esponenziale
HITTING TIME
1.
2.
3.
H x, y
H x, y   y
H x, y  H y , x
4.
H x, y   y  H y , x   x

Dove

H x , y è il tempo atteso per un random walk da x a y

 x è la porzione di tempo in cui si staziona in x
ROOTED PAGERANK

Modello Hitting Time con passi random

Con probabilità a salta ad un nodo qualsiasi della
rete

Con probabilità (a – 1) spostati verso un vicino del
nodo attuale
SIMRANK

Definizione ricorsiva di similarità


Due oggetti sono simili se sono connessi ad oggetti
simili
Definizione nel caso dei link

Due oggetti appartengono ad un link se sono connessi
ad oggetti che appartengono agli stessi link
se x  y
1

score( x, y )   a ( x ) b ( y ) score(a, b)
altrimenti
 
( x )  ( y )

Definita solo per grafi orientati
 γ è una costante compresa tra 0 e 1

UNSEEN BIGRAMS
Supponiamo di avere una funzione di similarità
tra nodi sim(x,y)

S
 Sia x l’insieme dei δ nodi più simili ad x
secondo sim(x,y)
 Lo score(x,y) dipende da quanti nodi, simili ad x,
sono in relazione con y



scoreunweighted ( x, y )  z : z  ( y )  S x

scoreweighted ( x, y )  z ( y )S  sim ( x, z )
x
CLUSTERING
Calcola lo score(u,v) per ogni arco (u,v) della rete
 Rimuovi il k% di archi con lo score più basso
 Calcola lo score(x,y) per ogni coppia di nodi (x,y)

CLUSTERING
Calcola lo score(u,v) per ogni arco (u,v) della rete
 Rimuovi il k% di archi con lo score più basso
 Calcola lo score(x,y) per ogni coppia di nodi (x,y)

CLUSTERING
Calcola lo score(u,v) per ogni arco (u,v) della rete
 Rimuovi il k% di archi con lo score più basso
 Calcola lo score(x,y) per ogni coppia di nodi (x,y)

PERFORMANCE COMPARISON

Liben-Nowell
et al., 2003
OBSERVATIONS


Le misure Adamic/Adar e Common Neighbors si
comportano sorprendentemente bene anche se
molto sono semplici
Le accuratezze di tutte le misure in generale sono
basse  c’è spazio per la definizione di nuove
misure per il miglioramento dell’accuratezza
PROBABILISTIC MODELS

Idea:

La rete sociale è governata da una distribuzione
probabilistica i cui parametri Θ devono essere stimati

L’esistenza di un arco sconosciuto che lega due nodi x
e y dipende quindi da:
Pr(edge( x, y ) | )
PROBABILISTIC MODELS

I dati a disposizione sono:

Struttura della rete sociale


Nodi e archi
Informazioni contestuali

Tipizzazione di nodi ed archi

Contenuto informativo associato a nodi ed archi
PROBABILISTIC MODELS


Vista la natura ibrida dei dati (contestuali +
strutturali) in letteratura sono stati proposti
modelli relazionali
I principali framework per la modellazione
relazionale probabilistica sono:

PRM: probabilistic relational models, basato sul
modello relazionale

DAPER: directed acyclic probabilistic entity
relationship, basato sul modello entità – relazione
PRM


Il PRM cerca di astrarre i dati della rete
osservati in modelli compatti a grafo
Il modello PRM è composto da tre grafi:

Il Data Graph: la rete in input

Il Model Graph: la rappresentazione compatta delle
caratteristiche dei dati

L’Inference Graph: grafo per l’attuazione del modello
su nuovi dati di rete, diversi da quelli di training
PRM
PRM

Il framework prevede diverse varianti ed
implementazioni. Le più note sono:

Relational Bayesian Networks (RBN)

Relational Markov Networks (RMN)

Relational Dependency Networks (RDN)
DAPER

Il Framework DAPER è adatto per rappresentare
contesti Bayesiani

spinge alla rappresentazione esplicita dei parametri e
degli iper – parametri del modello

Il modello può contenere sia parametri globali che
locali:

La parametrizzazione delle prior permette la definizione di
modelli molto flessibili
DAPER



DAPER formula un framework probabilistico per un
database in forma entità – relazione
La componente principale (first class) della
modellazione è l’insieme delle relazioni
Un modello DAPER consiste nella definizione di una
serie di :






entity classes
relationship classes
attribute classes
arc classes
local distribution classes
constraint classes
DAPER
SUPERVISED LEARNING
APPROACHES


La link prediction può essere vista come un
problema di learning supervisionato
Obiettivo:

Addestrare un classificatore binario in grado di
predire se un link esiste tra due nodi della rete
oppure no
EXPERIMENTAL SETUP

Dataset:


Co-authorship Network
Si suddivide il dataset in due partizioni, tra le
quali non esiste sovrapposizione temporale

Training (pubblicazioni passate) & Test
(pubblicazioni recenti)
CLASSIFICATION DATASET

La classificazione si basa sulla scelta di due
autori

Non esiste, nei dati di training, una pubblicazione tra
i due autori

Determinare la probabilità (o meno) che i due autori
pubblicheranno insieme in futuro


Esempio positivo: i due autori selezionati hanno una
pubblicazione comune nel test set
Esempio negativo: altrimenti
EXPERIMENTAL SETUP

Datasets:


DBLP

Train (1990 – 2000)

Test (2001 – 2004)
BIOBASE

Train (1998 – 2001)

Test (2002)
EXPERIMENTAL SETUP

Scelta delle feature
ALGORITHMS

SVM

Decision Trees

Multilayer Perceptron

KNN

Naïve Bayes

RBF

Bagging
RESULTS