Suche nach gemeinsamen Freunden für eine riesige Datenmenge

Question

wo ich einen großen Datensatz der Form userId haben folgt userId

1 -> 2 (dh) 1 folgt 2

1 -> 3

3 -> 5

2 -> 3

Die Idee ist, ich herausfinden wollen, wie viele gemeinsame Anhänger zwei Menschen haben zum Beispiel in th Im obigen Fall ist die Anzahl der gegenseitigen Follower zwischen Benutzer 1 und Benutzer 2 gleich 1, da (Benutzer 1 und Benutzer 2 folgen Benutzer 3)

Was ist der beste Weg, um es für einen großen Datensatz zu implementieren Einfaches Sammeln nach Benutzer-ID und anschließendes Ausführen einer Verknüpfung würde nicht funktionieren. Ich denke daran, einige Graph-Ansätze zu verwenden.

Answer 1

Nehmen wir an, Sie haben ein Diagramm als Adjazenzliste dargestellt. Und Sie haben eine Operation in diesem Diagramm get a list of the neighbors of a given vertex. Der Scheitelpunkt P1 ist die erste Person, der Scheitelpunkt P2 - die zweite Person. Jetzt können Sie als nächstes tun (sollten einen Hash-Set für die schnelle Schnitt verwenden):

p1_follows = HashSet(neighbors(P1)) 
p2_follows = neighbors(P2); 
mutual_followers = p1_follows.intersect(p2_follows) 

Wenn Sie verwenden GraphFrame, können Sie mit Motif finding gehen - hier ist ein Beispiel Motif Finding: Counting Mutual Friends.