Conteggio esatto ed approssimato
di cicli da quattro in grafi non diretti
Marco Mulas
Cicli da quattro
Reti sociali
Reti ferroviarie
Topologia e caratteristiche
di un grafo
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 2/20
Definizioni
Chiameremo quadrato una qualsiasi sequenza (a,b,c,d) di nodi del
grafo G se e solo se essa forma un ciclo di lunghezza quattro in G,
ossia se e solo se {a,b}, {b,c}, {c,d}, {d,a} sono presenti nell’insieme
degli archi di G.
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 3/20
Definizioni
Chiameremo 2path (a,x,b) un cammino di
lunghezza due all’interno del grafo.
Chiameremo 3path (a,x,y,b) un cammino di
lunghezza tre all’interno del grafo.
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 4/20
Algoritmi di conteggio esatto mediante vertici
mediante Ricerca Esaustiva
INPUT: G=(V,E)
count = 0
for each a  V
for each b  V (b≠a)
for each c  V (c≠b, c≠a)
for each d  V (d≠c, d≠b, d≠a)
if {a,b},{b,c},{c,d},{d,a}  E then
count = count + 1
OUTPUT: count/8
Tempo: (n4)
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 5/20
Algoritmi di conteggio esatto mediante vertici
mediante Backtracking
INPUT: G=(V,E)
count = 0
for each a  V
for each b  adj(a)
for each c  adj(b) (c≠a)
for each d  adj(c) (d≠b, d≠a)
if {d,a}  E then
count = count + 1
OUTPUT: count/8
Tempo:  (n2) + O(nd3)
Tempo:  (n2) per istanze reali
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 6/20
Algoritmi di conteggio esatto mediante 2path
INPUT: G=(V,E)
count = 0
P=
for each 2path (a,x,b) in G
P = P U (a,b)
for each (c,d)  P
calcola la molteplicità k di (c,d) in P
if k ≥ 2 then
æ k ö
count = count + çè 2 ÷ø
OUTPUT: count/2
dv (dv -1)
= O(nd 2 )
2
vÎV
P= å
Tempo: O(nd2 log n)
Tempo: O(n log n) per istanze reali
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 7/20
Algoritmi approssimanti
Un algoritmo probabilistico per un problema di conteggio
è (-)-approssimante se ,  (0,1) produce, con una
probabilità maggiore o uguale a 1-, una stima X
e che dista
al più un fattore  dal conteggio esatto di X.
X-X
X
(
X+X
)
P X - X > eX < d
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 8/20
Campionamento mediante quattro vertici
[CQV]
INPUT: G=(V,E)
=0
Scegli a caso una possibile quadrupla (a, b, c, d)
if {a,b}, {b,c}, {c,d}, {d,a}  E then
=1
OUTPUT: 
E[ b ] =
8Q
Q
=
æ n ö
æ n ö
24 ç
÷ 3ç
÷
4
4
è
ø
è
ø
æ n ö
Q = 3ç
÷ E[ b ]
è 4 ø
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 9/20
Algoritmi approssimanti
Teorema
Siano 1, 2,. . . , S variabili aleatorie identicamente distribuite a
valori nell’intervallo [0,1] con valore medio E[].
Se
allora
3
1
2
S³ 2
log
e E[ b ] d
æ1 S
ö
P çç å bi - E[ b ] > e E[ b ]÷÷ < d
è S i=1
ø
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 10/20
Campionamento mediante quattro vertici
[CQV]
INPUT: G=(V,E)
=0
Scegli a caso una possibile quadrupla (a, b, c, d)
if {a,b}, {b,c}, {c,d}, {d,a}  E then
=1
OUTPUT: 
E[ b ] =
8Q
Q
=
æ n ö
æ n ö
24 ç
÷ 3ç
÷
4
4
è
ø
è
ø
æ n ö1 S
Q = 3ç
÷ å bi
4
è
ø S i=1
æ n ö
ç
÷
4
9è
2
ø
S³ 2
log
e Q
d
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 11/20
Campionamento mediante 2path e un vertice
[CPV]
INPUT: G=(V,E)
=0
Scegli a caso un 2path (a,b,c) e un vertice d t.c. d  {a,b,c}
If {c,d}, {d,a}  E then
=1
OUTPUT: 
E[ b ] =
S³
4Q
P (n - 3)
3 P (n - 3)
2
log
e 2 4Q
d
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 12/20
Campionamento mediante 3path
[CTP]
INPUT: G=(V,E)
=0
Scegli a caso un {a,b}  E
Fra gli adj(a) scegli a caso un vertice d
Fra gli adj(b) scegli a caso un vertice c
if d≠b  c≠a  {d,c}  E then
d .d
 = a4 b
OUTPUT: 
1
d × d 8Q Q
× a b=
=
(a,b,c,d )con(c,d )ÎE 2m × d × d
4
8m
m
a
b
E[ b ] = å
3 md 2
2
S³ 2
log
e Q
d
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 13/20
Risultati sperimentali
Dataset usato
Grafo
Erdős–Rényi
300,0.035
Vertici
Archi D medio Quadrati
300
1.590
10,6
1.636
as19971109
3.011
5.343
3,5
61.245
as19990923
5.803
11.823
4,1
241.790
as20000102
6.474
7.391
4,1
299.317
Erdős–Rényi
3011,0.045
3.011
204.141
135,6
42.253.872
Email-Enron
36.692
183.831
10,0
36.262.229
Dblp.ungraph
317.080
1.049.866
6,6
55.107.654
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 14/20
Risultati sperimentali
Algoritmi di conteggio esatto
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 15/20
Risultati sperimentali
Con algoritmo di campionamento mediante 2path e un vertice
Grafo
20k
50k
100k
500k
dev. Speedup
dev. Speedup
dev. Speedup
dev. Speedup
E.R. 300,0.035
3,1%
1,00
0,1%
2,44
0,3%
4,66
0,1%
22,65
as19971109
7,0%
0,20
6,8%
0,50
5,6%
1,00
1,0%
5,07
as19990923
7,5%
0,10
3,5%
0,25
2,5%
0,49
2,1%
2,48
as20000102
18,3%
0,30
1,6%
0,74
1,2%
1,43
1,0%
7,44
E.R. 3011,0.045
4,3%
0,003
1,3%
0,007
1,2%
0,014
0,8%
0,071
Email-Enron
9,5%
0,004
4,7%
0,010
4,1%
0,020
1,1%
0,099
dblp.ungraph
9,1%
0,005
8,1%
0,008
5,5%
0,015
1,8%
0,071
dev. =
Q-Q
Q
speedup =
TCPV
TDPT
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 16/20
Risultati sperimentali
Con algoritmo di campionamento mediante 3path
Grafo
100
dev. Speedup
2k
5k
dev. Speedup
dev.
Speedup
10k
dev. Speedup
E.R. 300,0.035
16,4%
0,0143
4,2%
0,0831
2,6%
0,2066
0,9%
0,4057
as19971109
15,5%
0,0029
0,14%
0,0116
0,11%
0,0289
0,10%
0,0697
as19990923
12,9%
0,0006
6,3%
0,0047
3,2%
0,0109
1,0%
0,0211
as20000102
18,8%
0,0028
2,8%
0,0136
2,7%
0,0318
1,5%
0,0673
E.R. 3011,0.045
12,6%
0,0002
4%
0,0005
2,5%
0,0009
1,9%
0,0015
Email-Enron
10,1%
0,0003
1,7%
0,0006
1,5%
0,0011
0,9%
0,0195
dblp.ungraph
6,9%
0,0018
2,1%
0,0020
0,0024
0,001%
0,0029
dev. =
Q-Q
Q
speedup =
1,0%
TCTP
TDPT
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 17/20
Confronto campionamenti
Esperimenti sul grafo Erdős–Rényi 300,0.035
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 18/20
Confronto campionamenti
Esperimenti sul grafo as19971109
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 19/20
Conclusioni e sviluppi futuri
•
Sono stati presentati due tipologie di algoritmo esatto per il
conteggio dei quadrati e tre algoritmi di campionamento per il
conteggio approssimato
•
Mediante l’algoritmo di conteggio esatto basato sui 2path si
riescono ad ottenere risultati esatti in un tempo discreto
•
L’algoritmo di campionamento basato sul 3path risulta il più
efficiente dei tre presentati.
•
Mediante dei buon algoritmi di conteggio approssimanti è possibile
raggiungere un’ottima stima indicativa usando usando tempi
accettabili
•
Con il modello di memoria esterna si può eseguire il conteggio
esatto, basato su 2path mediante mergesort iterativo a k vie su file,
anche su grafi più grandi (n1M e m2M)
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti
Pagina 20/20
Grazie per la cortese attenzione
Conteggio esatto ed approssimato di cicli da quattro in grafi non diretti