Web Communities and their
identificaton
Giorgio Zoppi
[email protected]
Web Communities
1-25
Mining Dati Web
Problema con le ricerche sul web!
I motori di ricerca odierni (Yahoo!, AltaVista, Google)
restituiscono piu informazioni di quelle richieste.
Per esempio se cercate Wassily Kandinsky otterrete 1.320.000
di pagine Web da Google, circa 681.000 da Yahoo!...come
restringere i risultati?
Web Communities
2-25
Mining Dati Web
Problema con le ricerche sul web!
I motori di ricerca odierni (Yahoo!, AltaVista, Google)
restituiscono piu informazioni di quelle ricieste.
Per esempio se cercate Wassily Kandinsky otterrete 1.320.000
di pagine Web da Google, circa 681.000 da Yahoo!...come
restringere i risultati?
Agli utenti interessa solo un sottoinsieme rilevante dei risultati
della ricerca.
Web Communities
2-25
Mining Dati Web
Problema con le ricerche sul web!
I motori di ricerca odierni (Yahoo!, AltaVista, Google) restituiscono piu
informazioni di quelle richieste.
Per esempio se cercate Wassily Kandinsky otterrete 1.320.000 di pagine
Web da Google, circa 681.000 da Yahoo!...come restringere i risultati?
Agli utenti interessa solo un sottoinsieme rilevante dei risultati della ricerca.
Occorre ottenere un buon bilanciamento tra la precision e la recall dei
risultati di una query.
I motori tendono a fornire alta recall (quanti rilevanti su tutti quelli rilevanti?) e
bassa precision ( quanti rilevanti su tutti?) perche' fanno il rank dei risultati.
Web Communities
2-25
Mining Dati Web
Problema con le ricerche sul web!
I motori di ricerca odierni (Yahoo!, AltaVista, Google)
restituiscono piu informazioni di quelle richieste.
Per esempio se cercate Wassily Kandinsky otterrete 1.320.000
di pagine Web da Google, circa 681.000 da Yahoo!...come
restringere i risultati?
Agli utenti interessa solo un sottoinsieme rilevante dei risultati
della ricerca.
Occorre ottenere un buon bilanciamento tra la precision e la
recall dei risultati di una query. I motori tendono a fornire alta
recall alle spese della precision
I motori di ricerca non possono comprire tutto il web, e hanno
risultati non aggiornati date le dimensioni
Risulta necessario costruire web communities.
Web Communities
2-25
Mining Dati Web
Che cosa è una web community?
Definizione: A community consiste di membri che
hanno più link all'interno della community che fuori
dalla community.
Esempio: Un sito su Molierè è tale che collega o è
collegato da più siti che parlano di Moliere rispetto a
siti web che non parlano di Moliere.
L'identificazione di una community cosi definita è un problema NP-completo,
perche rientra nei problemi di ripartizionamento dei grafi.
balanced-minimum-cut graph partition: rimuovi un insieme di archi in
maniera tale che il numero rimosso sia minimale, assicurando che i due
sottografi disconnessi rimanenti abbiano almeno m vertici ciascuno
Web Communities
3-25
Mining Dati Web
E allora come le trovo?
Proviamo a rilassare il problema come:
Assumiamo l'esistenza di semi (sicuri
rappresentanti di una community) che
possono trovati mediante HITS.
Sfruttiamo le regolarita del grafo web (bowtie).
Usando questo due ipotesi possiamo
riformulare il problema come un problema di
flusso massimo. Vedremo il perche.....:)
Web Communities
4-25
Mining Dati Web
Definizione formale
Definizione: Sia G=<V,E> un grafo orientato
con |V| = n nodi e |E| = m archi, tale che:
•
•
Ogni vertice corrisponde ad una pagina web e
ciascun arco orientato corrisponde ad un hyperlink.
Ogni arco e = (u,v) ha un peso w(e) = w(u,v)
Una web community è un insieme di nodi C⊂V tale
che:
wu, v 
 wu,v  > 
 
vC
Web Communities
v V \ C
5-25
Mining Dati Web
Trovare le communities: Teorema.
Dato un grafo orientato G = (V,E), C⊂V :
Siano #(s) il numero di archi da s ad ogni altro nodo in C \ {s}.
Siamo #(t) il numero di archi da t ad ogni atro nodo V \ C \ {s}
Una community puo essere identificata calcolando il minimo taglio
T di G tra s e t tale che #(s) > | T | e #(s) > | T |
La condizione su #s non funziona sul web ( causa rumore):
uso semi multipli collegati ad una sorgente virtuale.
Per scegliere il pozzo, scelgo un sito tale che sia
genericamente collegato all'intero web.
Loro hanno usato Yahoo!.
Web Communities
6-25
Mining Dati Web
s-t Flusso Massimo
Dato un grafo orientato pesato G = (V,E) e dati due nodi s
(sorgente) e t(pozzo) trovare il flusso massimo che puo' essere
instradato dalla sorgente s al pozzo t:
Intuizione: pensate ad un acquedotto
Flusso massimo = Taglio di capacita minima
Possibili soluzioni:
Algoritmo sui Preflussi: e' la soluzione piu efficiente ma
non e' addattabile al nostro caso perche' non conosco la
topologia
Cammini Aumentanti: Trovo il cammino minimo tra
sorgente e pozzo ed aumento la capacita'
Web Communities
7-25
Mining Dati Web
Communities con Flusso Massimo
Web Communities
8-25
Mining di dati W
Come calcolare le communities:
Tutti i metodi richiedono un insieme di siti semi:
•
•
•
Esatto: Prendere una sito al centro del grafo
web come pozzo (es. Yahoo!) e svolgere il
flusso massimo sull'intero web.
Approssimato: Usare un sottografo con una
dimensione fissata di profondita del crawl.
Iterato (EM): Trovare una comunita
approssimata e utilizzare i risultati per
migliorare l'iterazione successiva.
Web Communities
9-25
Mining di dati Web
Exact Flow communities
"" Let G = (V,E), S is a subset of V ""
def exact_flow(G, S, k):
"" create artificial vertices, s and t, and add to V ""
foreach v in S:
add(s,v) in E with c(s, v) = infinite
foreach (u,v) in E:
c(u,v) = k
if (v,u) is not in E:
add(u,v) in E with c(u,v) = k
ExtendedS = add(S,s,t)
foreach v in V, v is not in ExtendedS:
add(v,t) in E with c(v,t) = 1
Cut = AugmentedMax-Flow(G,s,t) # Cut are all v in V connected to
S
return Cut
Web Communities
10-25
Mining di dati Web
Approximate Flow
communities
"" Let G = (V,E), S is a subset of V, d depth of the crawl ""
def approximate_flow(S, k):
"" h max iterations ""
while i<=h:
"" crawl the web until depth d ""
G = crawl_web(S,d)
k=|S|
C=exact_flow(G, S, k)
"" rank all v in c by number of edges in C""
rankedSet = rank(C)
add(Highest_Rank_NotSeed(rankSet),S)
return C
Web Communities
11-25
Mining di dati W
Max Flow Focused Crawler
∞
∞
∞
Sorgent
e
Web Communities
Siti
semi
+1
+2
12-25
Pozzo
Mining di dati Web
Espansione del grafo
Usa un pozzo artificiale che e' connesso a tutti i vertici
molto distanti dalla sorgente, perche'?
Supponiamo di poter trovare il seguente taglio usando il
centro del grafo:
Obiettivo: approssimare il taglio non conoscendo il
centro del grafo
Web Communities
13-25
Mining Dati Web
Espansione del grafo
Obiettivo: approssimare il taglio non conoscendo il
centro del grafo
Per approssimare il taglio:
Il pozzo virtuale t e' connesso con tutti i nodi
in V, eccetto i semi S e se stesso con capacita
1
Moltiplico tutte le capacita degli archi per un
fattore k.
Sotto quali condizioni riesco a produrre lo
stesso partizionamento?
Web Communities
14-25
Mining Dati Web
Teorema approssimazione del taglio
Il taglio approssimato e' identico a quello ideale
anche quando il centro del grafo non e' noto,
se vale la seguente condizione: 1<k<Nt/c
virtual sink
outside of the community
community
source
graph center
cut set
Web Communities
15-25
Mining Dati Web
Espansione del grafo
Obiettivo: approssimare il taglio non conoscendo il
centro del grafo
Per approssimare il taglio:
Il pozzo virtuale t e' connesso con tutti i nodi
in V, eccetto i semi S e se stesso con capacita
1
Moltiplico tutte le capacita degli archi per un
fattore k.
Sotto quali condizioni riesco a produrre lo
stesso partizionamento?
Web Communities
16-25
Mining Dati Web
Expect Maximization ( Iterated Flow)
Problema: Con un numero limitato di semi, solo
un limitato sottoinsieme della community puo'
essere trovato, per le limitazioni poste nel
trovare il taglio.
Abbiamo bisogno di un metodo per trovare
nuovi semi.
Expect : Uso l'algoritmo di flusso massimo per trovare
un sottoinsieme della community.
Maximization: Quelli che hanno outdegree massimo
diventano i nuovi semi. Ripeto l'algoritmo
approssimato con questi nuovi semi.
Web Communities
17-25
Mining Dati Web
Seeds: SVM community
Web Communities
18-25
Mining Dati Web
Results: SVM community
Web Communities
19-25
Mining Dati Web
Seeds: Internet Archive community
Web Communities
20-25
Mining Dati Web
Results: Internet Archive community
Web Communities
21-25
Mining Dati Web
Problema: come determino le capacita degli archi?
Le capacita degli archi sono importanti e loro non dicono come
determinarle
se sono impostate tutte allo stesso valore: non riesco in
alcuni casi a determinare nuovi membri perche' anche un
link valido per estendere la community diventa un arco di
taglio per l'algoritmo di flusso massimo.
Altri (Kitsuregawa,Imafujii) hanno dimostrato alcune
proprieta' sulle capacita degli archi:
Aumentare la capacita degli archi puo' aumentarare la dimensione
della community introducendo rumore.
E' difficile determinare una adeguata capacita degli archi, loro hanno
comunque notato un punto fisso detto quantum jump point:.
Quando la capacita degli archi e' minore del quantum jump point, la
web community, basata su un insieme di nodi e' troppo piccola..
Quando la capacita degli archi e' maggiore o uguale al quantum jump,
l'intero grafo sara la web community.
22-25
Mining Dati Web
Web Communities
Stimo il quantum jump point q
Siano tutti gli archi con capacita' q-1.
Considera un nodo v tale che abbia il grado piu
grande d, allora:
Allora: d
V
V
V
s
1
2
(
q

1
)

VV

1

1

q

V
s
s
V

1
q

1

s
V

Web Communities
23-25
Mining Dati Web
Come assegno le capacita' agli archi?
Uso HITS per trovare i punteggi di authority e hub.
rh
v

ra
v


h
a
i
j
c
(
v
v



i
j)
2 



avl e hvk sono rispettivamente i punteggi di hub e
autority.
rh =max(avk)/max(hvl).
ra =q.
Test hanno dimostrato che usando questo modo, si riduce il
rumore.
Web Communities
24-25
Mining Dati Web
Conclusioni
Abbiamo definito un nuovo tipo di web
community.
Abbiamo usato il flusso massimo per
calcolarlo.
Abbiamo usato il focused crawler per
approssimare le community.
Abbiamo notato che impostare le
capacita del grafo aumentato usando gli
score di HITS, riduce il rumore
Web Communities
25-25
Mining Dati Web
Reference
Efficient Identification of Web Communities Gary William Flake,
Steve Lawrence, C. Lee Giles
Self-Organization and Identification of Web Communities
(2002) Gary William Flake, Steve Lawrence, C. Lee Giles,
Frans M. Coetzee
Finding a web community by maximum flow algorithm with
HITS score based capacity N.Imafuji, M.Kitsuregawa