Rekomendasi VK Friends: ML pada grafik ego

Persahabatan adalah salah satu mekanisme terpenting dari jejaring sosial mana pun. Sebagian besar interaksi terjadi di antara pengguna yang menjadi teman: kami melihat dan mengomentari postingan satu sama lain di feed, membuka daftar teman untuk mencari kenalan, dan menulis pesan. Inilah mengapa pertumbuhan grafik sosial sangat penting.

Nama saya Zhenya Zamyatin, saya bekerja di tim Core ML di VKontakte. Saya ingin memberi tahu Anda bagaimana rekomendasi disusun yang mendekatkan pengguna ke jejaring sosial terbesar di Internet Rusia. 

Gambaran

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

, : 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 — .