Les algorithmes de Facebook - seocampus 2015

Sylvain Peyronnet

LES ALGORITHMES UTILISÉS PAR .

SYLVAIN PEYRONNET

Co-fondateur et responsable des ix-labs Professeur des Universités (on leave)

Co-fondateur nalrem médias @speyronnet

http://www.peyronnet.eu

http://live.ix-labs.org

[email protected]

ALGORITHMES ET FACEBOOKEn quelques années,

Facebook est devenu l’un des acteurs majeurs en

algorithmique pour le web

ALGORITHMES ET FACEBOOK

Aujourd’hui :

Créer un fil personnalisé

Chercher le graphe social

Afficher de la pub personnalisée

ALGORITHMES ET FACEBOOK

Aujourd’hui :

Créer un fil personnalisé

Chercher le graphe social

Afficher de la pub

Avec des invités : Alice

BobHector

Juliette

UN FIL PERSONNALISÉ

Comment Facebook choisit de

nous montrer un post spécifique ?


Comment Facebook choisit de

nous montrer un post spécifique ?

Avant 2013, le edgerank

UN FIL PERSONNALISÉSur Facebook, un

inscrit à en moyenne 300

amis

Posts des amis



amis

On ne peut voir que 10% des posts produits par

les amis

Posts des amis



amis

On ne peut voir que 10% des posts produits par

les amis

Comment trouver les meilleurs pour que Bob soit content ?

EDGERANK

score(p) = A⇥ T ⇥ F

A la création d’un post :

Affinité !

Fidélité de Bob envers Alice

!!!

Score du post fait par Alice, pour le fil de Bob

Type !

Une photo ou vidéo vaut plus

qu’un petit texte ou qu’un share d’un buzztruc

!

Fraicheur !!!!!!!

⇡ 1

age du post

EDGERANKA chaque interaction, le score est recalculé

Hector commente le post

Juliette like le post

Chaque interaction créée un lien entre les « interacteurs » et Bob !

EDGERANKscore(p) =

X

liens l

Al ⇥ Tl ⇥ Fl

Dès que les interactions s’arrêtent, le score diminue très vite (à cause de la

fraicheur)

On affiche sur le fil de Bob les posts dans l’ordre des scores

décroissants


Depuis 2013, l’edgerank a disparu au profit du

« newsfeed », qui utilise plus de 100k critères différents


!# de commentaires

!# de likes

!« dynamisme »

!nouveauté (nouveau contenu)

!interactions

!appartenance à des groupes

identifiés

post avec liens spammy !

post avec uniquement du texte !

contenu publicitaire !

click et link baiting !

contenu « memesque »

Quelques critères pour le newsfeed


!# de commentaires

!# de likes

!« dynamisme »

!nouveauté (nouveau contenu)

!interactions

!appartenance à des groupes

identifiés

post avec liens spammy !

post avec uniquement du texte !

contenu publicitaire !

click et link baiting !

contenu « memesque »

Quelques critères pour le newsfeed

CHERCHER LE GRAPHE SOCIAL

Comment chercher des informations dans un

graphe énorme ?

CHERCHER LE GRAPHE SOCIAL

Comment chercher des informations dans un

graphe énorme ?

En utilisant des signaux sociaux

pour personnaliser les résultats

FACEBOOK GRAPH SEARCH

Tom Stocky

Lars Rasmussen

Avant, chez

Avant, créateur de


Moteur de recherche sémantique Depuis Mars 2013

Pas encore en France

Cherche dans le graphe de Facebook, et utilise des

résultats de BING en plus

Alice Bob Hector Juliette


Alice

Bob

je cherche un ami capable de faire un

barrage

je cherche une belle célibataire au poil soyeux


Alice

Bob

Hector

Juliette

je cherche un ami capable de faire un

barrage

je cherche une belle célibataire au poil soyeux


Bob

Quels sont les films aimés par mes amis au poil

aussi soyeux que le mien?


Curtiss, Michael, et al. "Unicorn: A system for searching the social graph." Proceedings of the VLDB Endowment 6.11 (2013): 1150-1161.

Facebook graph search est réalisé grâce au système Unicorn


Curtiss, Michael, et al. "Unicorn: A system for searching the social graph." Proceedings of the VLDB Endowment 6.11 (2013): 1150-1161.

Facebook graph search est réalisé grâce au système Unicorn

Il s’agit d’un « outil » qui sélectionne des parties du « social graph » selon des requêtes portant sur les connexions


Connexions ou liens

amis

taggé dans

like

liker

Et bien d’autres encore…

attended


Requêtes

(and friend:Alice friend:Bob)

(or friend:Alice friend:Bob)

(difference friend:Alice friend:Bob)

Les amis d’Alice qui ne sont pas des amis de

Bob

Les amis communs d’Alice et Bob

Les amis d’Alice et Bob


Requêtes

(weak-end friend:Alice (term friend:Bob :optional-weight 0.2))

(strong-or (term live-in:Paris :optional-weight 0.1)

(term live-in:Rouen :optional-weight 0.1))

Un groupe d’amis d’Alice dont au moins 80% sont aussi amis de Bob

Des gens qui vivent à Paris ou Rouen. Au moins 10% dans chaque ville.


Requêtes

(apply friend: (and friend:Alice friend:Bob))

Les amis des amis communs de Alice et Bob

FACEBOOK GRAPH SEARCHPoints divers

!

• « we might want to prioritize results for individuals who are close in age to the user typing the query »

!

• pour la recherche « standard », les algorithmes usuels sont utilisés

!

• Le graph search est plus une prouesse technique qu’algorithmique

DE LA PUB PERSONNALISÉE

Une pub personnalisé serait plus efficace

qu’une pub standard


Une pub personnalisé serait plus efficace

qu’une pub standard

Ce n’est pas la discussion du jour, mais

cette phrase est largement douteuse


On va estimer le CTR de chaque

pub pour chaque utilisateur

utilisateur : genre, age, amis, likes, localisationannonceur : critère de ciblage, bid pour l’enchère

enchère : on classe les pubs par bid * CTR estimé

+

+

= 10%

= 0,01%

DE LA PUB PERSONNALISÉEOn place

l’utilisateur et les pubs dans l’espace

des concepts

Parfum

Pêche

On crée un estimateur par

proximité géométrique

DE LA PUB PERSONNALISÉEOn place

l’utilisateur et les pubs dans l’espace

des concepts

Parfum

Pêche

On crée un estimateur par

proximité géométrique

Technique très similaire au Cosinus de Salton utilisé par les moteurs pour l’analyse de la pertinence d’un texte

par rapport à une requête


Placer l’utilisateur dans l’espace des concepts :

extraire un modèle

Lecture du statut : « j’aime la pêche au gros »

Les likes (sur une page sur la pêche à la mouche)

Les commentaires : « Bob, tu étais encore à la pêche hier ? »

L’âge, l’endroit, etc.

Les pubs précédemment cliquées

Etc…


Placer la pub dans l’espace des concepts : extraire un modèle par classification de texte

!Algos de classification supervisé (Dekel et al. 2004 par

exemple)

Shopping/clothing : 80%

Art/Fashion : 30%

Pêche à la morue : 0%

QUESTIONS ? !

Engineering

Les algorithmes de Facebook - seocampus 2015