Recommandations de VK Friends: ML sur les graphiques de l'ego

L'amitié est l'un des mécanismes les plus importants de tout réseau social. La grande majorité des interactions se produisent entre des utilisateurs amis: nous voyons et commentons les messages de chacun dans les flux, nous allons dans la liste d'amis pour trouver des connaissances et rédiger un message. C'est pourquoi la croissance du graphe social est si importante.

Je m'appelle Zhenya Zamyatin, je travaille dans l'équipe Core ML sur VKontakte. Je veux vous dire comment les recommandations sont organisées pour rapprocher les utilisateurs du plus grand réseau social sur Internet russe. 

Aperçu

, . — ( ). . — . . , — , . — .

, : k , . , , — recall@k. : , .

, , . — . . .

— Adamic/Adar. , : «» . , .

, . : VK. — . , .

EGOML

Adamic/Adar. E(u, v)



, , u



v



. — : ez_c(u, v)



.

«» ez_c(u, v)



. , c



: « , , u



v



, ?» , . , c



, : « , , ». u



v



( c



) 1/log(n)



, n



— . Adamic/Adar. c



?

, , ez_c(u, v)



c



. , . , . , E(u, v)



. E(u, v)



MapReduce:

• . c
  
  
  
  , . , Adamic/Adar .

  
  
  
  
  

• Map. «» c
  
  
  
  , . , ez_c(u, v)



(u, v) → ez_c(u, v)



u, v in N(c)
  
  
  
  . Adamic/Adar: (u, v) → 1/log|N(c)|
  
  
  
  .

  
  
  
  
  

• Reduce. (u, v)
  
  
  
  . , u



v
  
  
  
  .

  
  
  
  
  

E(u, v)



. : , E(u, v) > 0



, — u



v



.

c



ez_c



, . -. , - x



— , x



x



, — . - .

ez_c



, . c



, - u



, v



, :

• u



v
  
  
  
  - c
  
  
  
  ;

  
  
  
  
  

• u



c
  
  
  
  ;

  
  
  
  
  

• v



c
  
  
  
  ;

  
  
  
  
  

• , u
  
  
  
  - - c
  
  
  
  ;

  
  
  
  
  

• - c
  
  
  
  ;

  
  
  
  
  

• .

  
  
  
  
  

. . T



. , T



, T + △T



. — , , . : , , T



, , .

:

• u



v
  
  
  
  , c
  
  
  
  , - c
  
  
  
  ;

  
  
  
  
  

• u



v
  
  
  
  , ;

  
  
  
  
  

• T
  
  
  
  ;

  
  
  
  
  

• u



v
  
  
  
  — T
  
  
  
  .

  
  
  
  
  

ez_c



. pairwise , u



.

, ez_c(u, v)



. : pairwise- . , ez_c(u, v)



«» , , E(u, v)



, . — , E(u, v)



. :

. , . : - — . . , , : u



, v



. : A



, u



, B



— v



. :

, - . A



B



, . , - n



O(n^2)



O(n)



. , ? :

1. , u



v
   
   
   
   . , « u



v
   
   
   
   - c
   
   
   
   » .

   
   
   
   
   

2. A
   
   
   
   , u
   
   
   
   , c
   
   
   
   - c
   
   
   
   .

   
   
   
   
   

3. B



v
   
   
   
   , c
   
   
   
   - c
   
   
   
   . A
   
   
   
   .

   
   
   
   
   

A



B



, : u



, — v



. , B



«» A



. . ez_c(u, v)



E(u, v)



:

E

, E(u, v)



:

— , , — . u



— . 

. key-value . E(u, v)



. E(u, v)



.

EGOML :

1. . O(|E|)
   
   
   
   , |E|
   
   
   
   — . 250 .

   
   
   
   
   

2. E(u, v)
   
   
   
   . O(|N(u)| + |N(v)|)
   
   
   
   .

   
   
   
   
   

3. , ( , , ) . , , , , .

   
   
   
   
   

Adamic/Adar EGOML E(u, v)



. .

Core ML , Core ML — .