VKフレンズの推奨事項：エゴグラフのML

友情は、ソーシャルネットワークの最も重要なメカニズムの1つです。インタラクションの大部分は、友達であるユーザー間で発生します。フィード内のお互いの投稿を表示してコメントし、友達リストにアクセスして知人を見つけ、メッセージを書き込みます。これが、ソーシャルグラフの成長が非常に重要である理由です。

私の名前はZhenyaZamyatinです。VKontakteのCoreMLチームで働いています。ロシアのインターネット上で最大のソーシャルネットワークにユーザーを近づけるための推奨事項がどのように配置されているかをお伝えしたいと思います。 

概要概要

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

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