Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Structure et dynamique

des graphes de terrain bipartis :

liens internes et prediction de liens

Oussama Allali

Clemence Magnien et Matthieu Latapyhttp://complexnetworks.fr

LIP6 CNRS-UPMC

Liens internes et prediction de liens 1 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

1 Contexte

2 Analyse : liens et pairs internes

3 Dynamique : prediction des liens

4 Conclusion et perspectives

Liens internes et prediction de liens 2 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Plan

1 Contexte

2 Analyse : liens et pairs internes

3 Dynamique : prediction des liens

4 Conclusion et perspectives

Liens internes et prediction de liens 3 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Graphes de terrain bipartis

Graphe biparti

A B C D E F

2 3 41

Acteurs-films.

Auteurs-publications.

Acheteur-produit.

...

Liens internes et prediction de liens 4 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Projection

Graphe biparti → Graphe classique

A

B

E

D

C F

A B C D E F

2 3 41

34

1

2

B⊤ B B⊥

Perte d’information.

Liens internes et prediction de liens 5 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Projection

Graphe biparti → Graphe classique

A

B

E

D

C F

A B C D E F

2 3 41

34

1

2

B⊤ B B⊥

Perte d’information.

Liens internes et prediction de liens 5 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Projection valuee

Nombre de voisins en commun dans le biparti

A

B

E

D

C F

A B C D E F

2 3 41

34

1

2

3

1

1

1

1

12

1

11

B⊤ B B⊥

Autres projections valuees

Fraction de voisins en commun dans le biparti (Jaccard).

Somme des votes des voisins en commun dans le biparti.

Liens internes et prediction de liens 6 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Projection valuee

Nombre de voisins en commun dans le biparti

A

B

E

D

C F

A B C D E F

2 3 41

34

1

2

3

1

1

1

1

12

1

11

B⊤ B B⊥

Autres projections valuees

Fraction de voisins en commun dans le biparti (Jaccard).

Somme des votes des voisins en commun dans le biparti.

Liens internes et prediction de liens 6 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Contexte d’etude

Analyse des graphes de terrain bipartis :liens internes.

Liens internes et prediction de liens 7 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Plan

1 Contexte

2 Analyse : liens et pairs internes

3 Dynamique : prediction des liens

4 Conclusion et perspectives

Liens internes et prediction de liens 8 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Liens internes

Exemple d’un lien ⊥-interne.

A B C D E

i j k

A B C D E

i j k

A

B

D E

C

B B ′ = B − (B , j) B ′⊥ = B⊥

Retirer le lien ne change pas la projection.

Liens internes et prediction de liens 9 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Pairs internes

Exemple d’une pair ⊥-interne.

i j k l

A B C D E

i j k l

A B C D E

A

B

D E

C

B B ′ = B + (B , l) B ′⊥ = B⊥

Ajouter le lien ne change pas la projection.

Liens internes et prediction de liens 10 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Datasets

Flickr-comts

Flickr-favorites

P2P-files

PRL-papers

Liens internes et prediction de liens 11 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Statistiques des liens et pairs internes

fEI(⊥) PI (⊥)

P∗

I(⊥)

EI (⊥)E∗

I(⊥) fEI

(⊤) PI (⊤)P∗

I(⊤)

EI (⊤)E∗

I(⊤)

Flickr-comts 0.398 0.258 4.22 0.002 0.151 22.0Flickr-favorites 0.172 0.574 2.02 0.002 0.704 12.4P2P-files 0.337 0.082 8.53 0.136 0.092 1430

PRL-papers 0.718 0.033 7.17 0.487 0.001 11.2

fEI: fraction de liens internes.

PI : nombre de paires internes.

EI : nombre de liens internes.

P∗I et E ∗

I : valeurs pour des graphe aleatoire memedistributions des degres.

Liens internes et prediction de liens 12 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Correlation entre le nombre de liens internes

et le degre des nœuds

Flickr-comts Flickr-favorites P2P-files PRL-papers

100

101

102

103

104

105

100 101 102 103 104 105

randomreal

slope=0.86slope=0.66

100

101

102

103

104

105

100 101 102 103 104 105

randomreal

slope=0.75slope=0.67

100

101

102

103

104

105

100 101 102 103 104

randomreal

slope=0.63100

101

102

103

104

100 101 102 103

randomreal

slope=0.93slope=0.78

Degre moyen en fonction du degre ⊥-interne.

Liens internes et prediction de liens 13 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Suppression des liens internes

Exemple de suppression d’un lien ⊥-interne.

i j k l

A B DC

i j k l

A B DC

A

B

D

C

B B ′ = B − (A, i) B ′⊥ = B⊥

{(A, i), (B , j), (C , k), (D, l)} sont liens ⊥-internes de B .

La suppression du lien (A, i) =⇒ {(B , j), (C , k), (D, l)} nesont plus des liens internes.

Liens internes et prediction de liens 14 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Suppression des liens internes

P2P-files

⊥-internal links ⊤-internal links

0

104

2.104

3.104

4.104

5.104

0 104 2.104 3.104 4.104 5.1040

104

2.104

3.104

4.104

0 104 2.104 3.104 4.104

Nombre de liens internes restants en fonction du nombrede liens supprimer.

La ligne rouge : processus de suppression aleatoire.

La ligne bleue : borne superieure theorique.

Liens internes et prediction de liens 15 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Plan

1 Contexte

2 Analyse : liens et pairs internes

3 Dynamique : prediction des liens

4 Conclusion et perspectives

Liens internes et prediction de liens 16 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Prediction de liens

a cbprediction

treference

Methodologie

En entree : B graphe de reference, periode [a, b[.

En sortie : P liens predits comme apparaissant dans laperiode [b, c[.

Validation

E les liens apparus dans la periode ]b, c]

Precision|P∩E ||P| .

Rappel|P∩E ||E | .

Liens internes et prediction de liens 17 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Fraction des pairs internes dans E

Periode de prediction

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0 10 20 30 40 50 60

% pairs internes en fonction de la periode de prediction.

periode de reference : [0, 1jour[.

periode de prediction : [1, x [, pour x = 2, ..., 55 jours.

Liens internes et prediction de liens 18 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Prediction des liens internes

Methode de prediction

Ensemble de liens dans le projete tels que :L = {(u, v) ∈ E⊥, poids(u, v) ≥ seuil}.

On predit les paires internes de B qui ont au moins un lieninduit par ces derniers dans L : P .

Liens internes et prediction de liens 19 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Prediction des liens internes

Exemple de prediction d’une paire interne

A B C D E

lkji

A

C

DE

B

1/3

1/3

1/22/3

1/4

1/4

1/3

1/4

A

C

DE

B

B B⊥,Jaccardles liens induits

par (B , l)

A

C

DE

B

A

C

DE

B

A

C

DE

B

seuil τ = 14 seuil τ = 1

3 seuil τ = 23

Liens internes et prediction de liens 20 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Impact des methodes de ponderation

prediction de liens internes filtrage collaboratif

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35

sumjaccard

deltaattachment

cosineoverlap

0

0.01

0.02

0.03

0.04

0.05

0.06

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4

sumjaccard

deltaattachment

cosineoverlap

Precision en fonction du rappel.

Liens internes et prediction de liens 21 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Plan

1 Contexte

2 Analyse : liens et pairs internes

3 Dynamique : prediction des liens

4 Conclusion et perspectives

Liens internes et prediction de liens 22 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Conclusion et Perspective

Conclusion

Un nouveau type de liens : les liens internes.

Approche par graphe valuee pertinente.

Comparer au filtrage collaboratif.

Perspectives.

Autres jeux de donnees.

Autres methodes de ponderation.

Prediction de paires non-internes.

Liens internes et prediction de liens 23 / 24

Liens internes

et prediction

de liens

Contexte

Analyse : lienset pairsinternes

Dynamique :prediction desliens

Conclusion etperspectives

Merci

Liens internes et prediction de liens 24 / 24