Empfehlungen von VK Friends: ML auf Ego-Graphen

Freundschaft ist einer der wichtigsten Mechanismen eines sozialen Netzwerks. Die überwiegende Mehrheit der Interaktionen findet zwischen Freunden statt, die Freunde sind: Wir sehen und kommentieren die Beiträge der anderen in den Feeds, gehen zur Freundesliste, um Bekannte zu finden und eine Nachricht zu schreiben. Deshalb ist das Wachstum des sozialen Graphen so wichtig.

Mein Name ist Zhenya Zamyatin, ich arbeite im Core ML-Team von VKontakte. Ich möchte Ihnen sagen, wie die Empfehlungen angeordnet sind, die die Benutzer näher an das größte soziale Netzwerk im russischen Internet bringen. 

Überblick

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

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