Geek asks and answers

Algorithm for finding the relationship of two Twitter users

I have a problem with the Kevin Bacon type at 6 degrees. Suppose I have 2 Twitter users and I want to find out their relationship with each other through friends (I use friends to mean when you follow someone against them, following you) and followers on Twitter. I have all id in my database.

So for example:

Joel and Sally

Joel follows Fred, who is friends with Steve, who follows Sally.

There may be several ways to get there, but I want the shortest.

This is similar to the well-known problem of computer science (the shortest path algorihm).

Today I have a table called "influensers" where all my Twitter IDs are stored, then I have the following table, which is my own link table (follower IDs on one side and friends on the other.)

So is this graph theory? If so, someone can point me to any utilities / libraries / approaches that may be useful. Im uses ruby, but can parse most languages.

+5
source share
2 answers

As you said, this is a well-known issue, as you can see on Wikipedia .

Just note that in your case the weights in all edges are 1), so I don’t think that the Jikstra algorithm would be very useful for you.

, . , Twitter , , , (, 20 - 20 , 400, 8000 - Sally, ).

, 100%. , , , , .

, , .

, .

+1

, BFS http://en.wikipedia.org/wiki/Breadth-first_search

-: , , , . : cost runtime O(n) (, , O(1)).

- , O(n*n), n - . O(1) O(logn) , ( , , , O(n) O(n*n)).

, , , . , - , , , , , .

  • - -
  • , ,

</" > 17 . , .

. O(n*n) , , , .

, , .

, - : ( userId). ( - userId). 17 . 17 mio. ( O(n*n)).

Offline BFS , , , BFS . , , . BFS node, .. . , BFS node, O(n*n) runtime. , , .. . , , .

, . " , , ". BFS, O(n), . BFS (userId) , .

Online userId .

+1

More articles:


All Articles