(Laboratorio di )
Sistemi Informatici Avanzati
Giuseppe Manco
SEARCH
Approcci alle reti di grandi dimensioni
Heavy-tails e power laws (su scale di grandi imensioni):
•
forte eterogeneità locale, mancanza di struttura
•
base per i modelli preferential attachment
Local clustering/structure (su scale di piccole dimensioni):
•
situazioni locali hanno una struttura “geometrica”
•
punto di partenza per modelli small world che partono con
una “geometria” globale e aggiungono link random per
ottenere un diametro piccolo e preservare la geometria a
livello locale
Le problematiche di interesse
• Quali sono le statistiche di base (degree distributions,
clustering coefficients, diametro, etc.)?
• Ci sono raggruppamenti/partizioni naturali?
• Come evolvono/rispondono alle perturbazioni le reti?
• Come avvengono I processi dinmaici - search, diffusion,
etc. – nelle reti?
• Come fare classificazione, regressione, ranking, etc.?
Osservazioni sulle reti reali
• Diametro
– Costante
• Coefficiente di clustering
– Costante
• Degree distribution
– Power-law
Applicazioni: Search
• Small world
– È possibile navigare la rete
• Preferential attachment
– Ci sono alcuni grossi hubs
• Come sfruttare tali informazioni?
Singular Value Decomposition
• Tecnica di decomposizione matriciale
• Basata sull’analisi spettrale
• Tante applicazioni
La Singular Value Decomposition (SVD)
• Data una matrice A, m x n, essa può essere decomposta come
prodotto di tre matrici:
•
•
•
p: rango di A
U, V: matrici ortogonali (UTU=Im,
VTV=In) contenenti
rispettivamente i vettori singolari destri e sinistri di A
∑: matrice diagonale contenente i valori singolari di A, in ordine
non-crescente σ1≥σ2≥... ≥σp ≥0
Interpretazione a Layer della SVD
mxn
A
mxn
=
σ1 u1vT1
+
σ2 u1vT1
Importanza decrescente
+...
Vettori Singolari, Intuizione
I cerchi blu rappresentano m punti nello
spazio euclideo.
La SVD della matrice mx2 sarà costituita
da:
- Primo vettore singolare (destro):
direzione della varianza max
- Secondo vettore singolare (destro):
direzione della max varianza dopo aver
rimosso la proiezione dei dati lungo il
primo vettore singolare
Vettori Singolari, Intuizione
•
•
σ1: misura quanta varianza dei dati
è “catturata/spiegata” dal primo
vettore singolare
σ2: misura quanta varianza dei dati
è “ catturata/spiegata ”
dal
secondo vettore singolare
Low Rank Approximation
• Si tronca la SVD ai primi k termini:
•
•
•
k= rango della decomposizione
Uk, Vk: matrici ortogonali contenenti rispettivamente i primi k
vettori singolari destri e sinistri di A
∑k: matrice diagonale contenente i primi valori k singolari di A
Proprietà
• Anche per matrici con dati positivi, la SVD è mista in segno
+
+
•
•
•
+/-
+/-
U e V sono dense
Unicità: nonostante ci siano diversi algoritmi, questi
producono la stessa SVD (A troncata)
Proprietà: mantenere i primi k valori singolari di A fornisce la
migliore rank-k approximation di A rispetto alla Frobenius
norm
Low Rank Approximation
• Usa Ak al posto di A
VT
A
mxn
≈
UkmUmm
∑kk
kxn
∑
VT
mxn
nxn
nxn
Sommario della Truncated SVD
• Pro:
– Usare Ak al posto di A implica un aumento delle performance
generale degli algoritmi di mining
– la riduzione del rumore isola le componenti essenziali della
matrice dati
– Best rank-k approximation
– Ak è unica e ottima secondo la Frobenious norm
• Contro:
– Storage (Uk e Vk sono dense)
– L’interpretazione di U e V è difficile perchè hanno segno
misto
– Un buon punto di troncamento k è difficile da determinare
Applicazioni della SVD all’analisi dei
dati
•
Dimensionality reduction: la truncated SVD fornisce una
rappresentazione compressa di dati ad alta dimensionalità
(con molti attributi).
•
•
•
La compressione SVD minimizza la perdita di informazione,
misurata secondo la Frobenious norm
Se i dati originali contengono rumore, la riduzione di
dimensionalità può essere considerata come una tecnica di
attenuazione del rumore
Se fissiamo k=2 o k=3, allora è possibile plottare le righe di
U. La rappresentazione grafica rende possibile
un’interpretazione visuale della struttura del dataset
SVD - Example
SVD e Latent
Semantic Indexing
T
• A = U L V - example:
retrieval
inf.
lung
brain
data
CS
MD
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
Faloutsos, Miller, Tsourakakis
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-23
SVD - Example
SVD e Latent
Semantic
Indexing
T
• A = U L V - example:
retrieval CS-concept
inf.
lung
MD-concept
brain
data
CS
MD
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
Faloutsos, Miller, Tsourakakis
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-24
SVD - Example
SVD e Latent
Semantic
Indexing
T
• A = U L V - example:
retrieval CS-concept
inf.
lung
MD-concept
brain
data
CS
MD
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
Faloutsos, Miller, Tsourakakis
Affinità documento-concetto
P1-24
SVD - Example
SVD
e
Latent
Semantic
Indexing
T
• A = U L V - example:
retrieval CS-concept
inf.
lung
MD-concept
brain
data
CS
MD
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
5.29
0
Faloutsos, Miller, Tsourakakis
Importanza del concetto
x
0
0.58 0.58 0.58 0
0.71 0.71
0
0
0
P1-24
SVD - Example
SVD e Latent
Semantic
Indexing
T
• A = U L V - example:
retrieval CS-concept
inf.
lung
MD-concept
brain
data
CS
MD
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
Faloutsos, Miller, Tsourakakis
Affinità termine-concetto
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-24
CMU SCS
Riduzione di dimensionalità
SVD - Interpretation #2
• A = U L VT - example:
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
Faloutsos, Miller, Tsourakakis
x
v1
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-38
SVD - Interpretation
#2
Riduzione
di dimensionalità
• A = U L VT - example:
variance (‘spread’) on the v1 axis
Varianza lungo l’asse v1
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
Faloutsos, Miller, Tsourakakis
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-39
CMU SCS
Riduzione
di dimensionalità
SVD - Interpretation
#2
••
•
•
Eliminiamo
More detailselementi a bassa varianza
Q: how exactly is dim. reduction done?
A: set the smallest singular values to zero:
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
Faloutsos, Miller, Tsourakakis
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-42
SVD
Interpretation
#2
Riduzione di dimensionalità
• Eliminiamo gli elementi a bassa varianza
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
~
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
0
Faloutsos, Miller, Tsourakakis
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
P1-44
CMU SCS
SVD - Interpretation
#2
Riduzione
di dimensionalità
• Eliminiamo gli elementi a bassa varianza
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
~
0.18
0.36
0.18
0.90
0
0
0
x
9.64
Faloutsos, Miller, Tsourakakis
x
0.58 0.58 0.58 0
0
P1-45
CMU SCS
SVD
Interpretation #2
Riduzione
di-dimensionalità
• Eliminiamo gli elementi a bassa varianza
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
~
1
2
1
5
0
0
0
1
2
1
5
0
0
0
1
2
1
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Faloutsos, Miller, Tsourakakis
P1
•
•
Applicazioni della SVD all’analisi dei
dati
Clustering: nello spazio della trasformazione SVD troncata, la
relazioni tra i punti sono più evidenti e il processo di clustering ne
trae diretto vantaggio
Applicazioni al clustering:
•
•
Clustering sul nuovo spazio
Utilizzo diretto delle proprietà dell’SVD
•
•
Spectral clustering: i punti che giacciono nel cono intorno al
primo asse (prodotto con il primo asse <1/2) sono
raggruppati in un cluster
Quelli con la stessa proprietà rispetto al secondo asse
vengono raggruppati nel secondo cluster e così via
SVD - Interpretation #3
Raggruppamenti, blocchi
• finds non-zero ‘blobs’ in a data matrix
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
Faloutsos, Miller, Tsourakakis
P1-54
SVD - Interpretation #3
Raggruppamenti, blocchi
• finds non-zero ‘blobs’ in a data matrix
1
2
1
5
0
0
0
1
2
1
5
0
0
0
KDD'09
1
2
1
5
0
0
0
0
0
0
0
2
3
1
0
0
0
0
2
3
1
=
0.18
0.36
0.18
0.90
0
0
0
0
0
0
0
0.53
0.80
0.27
x
9.64 0
0
5.29
x
0.58 0.58 0.58 0
0
0
0
0
0.71 0.71
Faloutsos, Miller, Tsourakakis
P1-55
Raggruppamenti, blocchi
•
Applicazioni della SVD all’analisi dei dati
Ranking:
•
•
•
•
•
•
Ogni riga di U può essere rappresentata come un punto nello spazio kdimensionale. Supponiamo di tracciare una freccia dall’origine verso
ciascuno dei punti
L’angolo (coseno) tra i due vettori denota la correlazione tra i punti
Oggetti altamente correlati o altamente non correlati con altri punti
tendono a piazzarsi intorno all’origine
Punti collocati lontano dall ’ origine corrispondono ad oggetti che
esibiscono una correlazione inusuale con altri oggetti
Punti collocati vicino all’origine sono meno “interessanti”
Il rank degli oggetti può essere effettuato tenendo conto della distanza
dall’origine
Proprietà (A)
U U = Im
T
V V = In
T
(
L = diag s , s ,..., s
k
AT = V LU T
k
1
k
2
k
r
)
Proprietà (B)
AA = UL U
T
2
T
• Similarità documento-documento
A A = VL V
T
2
• Similarità termine-termine
T
Proprietà (B)
( A A)
T
k
= VL V
2k
T
• Inoltre:
( A A)
T
k
» vs v
2k T
1 1 1
• v1 autovettore relativo a σ1 (l’autovalore più
grande)
Proprietà (C)
( A A) v » l v
T
k
T
1
• Per qualsiasi vettore v
– Conseguenza: procedura iterativa per il calcolo
degli autovettori
Proprietà (C)
Ax = b
• Ammette soluzione
-1
x = VL U b
T
Proprietà (C)
Av1 = s 1u1
u A = s 1v1
T
1
• conseguentemente
A Av1 = s 1 v1
T
2
PCA e MDS
Principal Components Analysis (PCA)
• Dati{Xi}i=1,…,n con Xi vettori reali,
trova il sottospazio k-dimensionale P e il mapping Yi=PXi
t.c.. Variance(Y) è massima (o Error(Y) è minimo)
• SVD sulla matrice di covarianza C =XXT
Multidimensional Scaling (MDS)
• Dati {Xi}i=1,…,n con Xi vettori reali,
trova il sottospazio k-dimensionale P e il mapping Yi=PXi
t.c. Dist(Yi-Yj) = Dist(Xi-Xj) (ovvero distanze preservate)
•SVD sulla matrice matrix G = XT X
LSI/SVD e power laws
• Gli autovalori più grandi della matrice di
adiacenza di un grafo scale-free sono
distribuiti con una power-law.
Caso di Studio: Social Network Analysis
• Obiettivo: identificare proprietà e relazioni tra i membri di al
Qaeda
• Il dataset fornito da Marc Sageman contiene informazioni su
366 membri dell’associazione terorristica all’inizio del 2004
• Attributi:
al Qaeda Dataset
• Grafo delle relazioni: 366 nodi e 2171 archi.
• Il grado massimo del grafo è 44, mentre
quello medio è 6.44.
• Il diametro è 11
• Bavelas-Leavitt Centrality: rapporto tra la
somma dei cammini geodesici aventi come
sorgente/destinazione il nodo considerato e
la somma dei cammini geodesici dell’intero
dataset
al Qaeda Dataset:
al Qaeda Dataset: Link Analysis
• Analisi della matrice di adiacenza 366 x 366
– Contatti e relazioni tra i membri
Algerians
South East Asian
•
•
•
Leaders and core Arabs
Plot of the low rank (3) SVD of al Qaeda members using only
relationship attribute
4 cluster
Hambali ha
connessione
un
ruolo
di
bin Laden non è l’elemento
estremo del cluster che
identifica la leadership
SVD e centralità
Misura l’importanza di un nodo
• degree centrality – numero di link di un nodo
• betweenness centrality –numero di cammini che lo
contengono
• closeness centrality - potenziale di comunicazione
indipendente
• eigenvector centrality – connessioni a nodi con highdegree, iterativamente
Eigenvector centrality
N
x j » å aij xi
i=1
• Riformulato, risulta essere
Ax = s x
IL WEB
Struttura del Web
395
13.6. EXERCISES
1
5
4
2
3
10
6
8
9
7
16
15
11
12
13
14
17
18
Figure 13.8: A direct ed graph of Web pages.
(b) Name an edge you could add or delete from t he graph in Figure 13.8 so as t o
Source: David Easley, increase
Jon Kleinberg
Networks, Crowds, and Markets, Cambridge University Press (2010)
t he size of t he set IN.
(c) Name an edge you could add or delete from t he graph in Figure 13.8 so as t o
Struttura del web
13.3. THE WEB AS A DIRECT ED GRAPH
387
I'm a student
at Univ. of X
I'm a applying to
college
Univ. of X
My song
lyrics
Classes
USNews:
College
Rankings
I teach at
Univ. of X
Networks
USNews:
Featured
Colleges
Networks
class blog
Blog post about
college rankings
Blog post
about
Company Z
Company Z's
home page
Our
Founders
Press
Releases
Contact Us
Figure
13.6: A direct
ed graph
wit h it s st rongly
connected component
s identified.
Source: David Easley, Jon Kleinberg Networks,
Crowds,
and
Markets,
Cambridge
University
Press (2010)
Bow-Tie
Source:A. Broder, et at.. Graph structure in the Web. In Proc. WWW, pages 309–320, 2000.
Il problema della Ricerca
• Inserisci un termine nella pagina di google
– Analizza i risultati
• Il primo elemento è quello che ti aspettavi?
• Come ha fatto google a calcolare il risultato?
Search
• Un problema difficile
– Information retrieval: ricerca in grosse repositories, sulla
base di keywords
– Keywords limitate e inespressive, e:
• sinonimia (modi multipli per dire la stessa cosa: casa, abitazione)
• Polisemia (significati multipli per lo stesso termine: Jaguar, Apple)
– Differenti modalità di authoring
• Esperti, novizi, etc.
– Estrema dinamicità del web
– Shift
• Scarcity -> abundance
Hubs, Authorities
• Un problema di links
– Perché wikipedia è in cima agli elementi suggeriti?
Hubs, authorities
• Molte pagine contengono il termine “reti
sociali”
– Perché wikipedia è più rilevante?
• Indicheresti wikipedia come riferimento?
Hubs, authorities
CHAPTER 14. LINK ANALYSIS AND WEB SEARCH
400
• Votazione
SJ Merc
News
Wall St.
Journal
New York
Times
USA Today
Facebook
Yahoo!
Amazon
2 votes
2 votes
4 votes
3 votes
1 vote
3 votes
3 votes
Figure 14.1: Count ing in-links t o pages for t he query “ newspapers.”
Source: David Easley, Jon Kleinberg Networks, Crowds, and Markets, Cambridge University Press (2010)
Hubs, authorities
402
CHAPT ER 14. LINK ANALYSIS AND WEB SEARCH
• Compilazione di liste
SJ Merc
News
– Ogni pagina “rappresenta”
quelle che la puntano
new score: 19
8
Wall St.
Journal
11
7
New York
Times
new score: 19
new score: 31
3
6
5
6
USA Today
new score: 24
3
Facebook
3
Yahoo!
Amazon
new score: 5
new score: 15
new score: 12
Figure 14.3: Re-weight ing vot es for t he query “ newspapers” : each of t he labeled page’s new
score is equal t o t he sum of t he values of all list s t hat point to it .
of links t o on-line newspapers; for “ Cornell,” one can find many alumni who maint ain pages
Hubs, authorities
• Miglioramento iterativo
• Normalizzazione
• Authorities
– Le pagine che rappresentano gli end-points
• Hubs
– Le pagine che rappresentano molte altre pagine (e
il cui voto conseguentemente conta tanto)
Hubs, authorities
• Hubs
• Authorities
Kle
Authority value
• Dato un nodo i:
ai = hk + hl + hm
• Generalizzando su ogni nodo:
k
i
l
m
a =A h
T
KDD'09
CMU SCS
Hub value
Klein
• Dato un nodo i:
hi = an + a p + aq
sy
i
n
p
• Generalizzando su ogni nodo:
q
h =Aa
KDD'09
tha
hi
(
or
h=
Algoritmo HITS
• In conclusione, stiamo cercando due vettori h
e a tali che
a =A h
T
h = Aa