2012/05/08

社交網路資料庫設計:怎麼找共同朋友、朋友的朋友

在 facebook 內當你點朋友時,你可以知道彼此共同朋友有哪些,另外在網頁右欄有個"你可能認識"的專區,這個功能是怎麼做的?

先來分析這兩個語意:
1. 共同的朋友:"自己的朋友"跟"朋友的朋友"重疊的部分
2. 你可能認識的人:把朋友的朋友全部列出來,依據重疊次數來排序,越高的表示你越可能認識的人,如果是你還沒加到名單的,facebook 就會主動推薦給你


在 stackoverflow 找到兩篇參考文章:


關連式資料庫
用一般的關連式資料庫 (relational database)來找共同朋友
table: friends
--------------------------
 user_id | friend_id
---------+----------------
 1       | 2
 1       | 3
 1       | 4
 2       | 4
 3       | 1
 3       | 2
 4       | 3

若要找 1 跟 3 的共同朋友,可以下 sql query:
SELECT user_id FROM friends AS A, friends AS B
  WHERE A.user_id = B.user_id AND A.friend_id = 1 AND B.friend_id = 3
-- 用中文解釋就是,同一個人,擁有朋友1而且還擁有朋友3

得到結果就是 user 2
似乎很容易取得,而且 query 不會太複雜。



但如果要找"你可能認識的人"呢?這就有點難了...
分階段來作:

a) 朋友的朋友,但不是自己
參考 mysql - "people you may know" sql query - Stack Overflow
SELECT DISTINCT(F2.friend_id) FROM friends AS F1 
  INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id 
  WHERE F1.user_id = 1 AND F2.friend_id != 1 

b) 朋友的朋友,但不是自己,且還不是我的朋友
SELECT DISTINCT(F2.friend_id) FROM friends AS F1 
  INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id 
  WHERE F1.user_id = 1 AND F2.friend_id != 1 AND 
    F2.friend_id NOT IN (SELECT friend_id FROM friends WHERE user_id = 1)

c) 朋友的朋友,但不是自己,且還不是我的朋友,並統計重疊的次數
SELECT F2.friend_id, COUNT(F2.friend_id) FROM friends AS F1 
  INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id 
  WHERE F1.user_id = 1 AND F2.friend_id != 1 AND 
    F2.friend_id NOT IN (SELECT friend_id FROM friends WHERE user_id = 1)
  GROUP BY F2.friend_id
  ORDER BY count DESC

Well ~ 看樣子還是辦得到!
但這些 query 的複雜度一定很大,如果每次 user refresh 就去 query,database 肯定會忙死,所以變成要 offline 執行,並且把結果存起來,一但有變動就要再重新 query,不過相對即時性就沒那麼高了。



圖形資料庫
從另一種角度思考,這個問題可以映射到圖學理論中的 bidirected graph,人是 vertex,關係是 edge。graph 要怎麼用 database 來存?於是找到了 graph database - neo4j,官網是這麼介紹的:
Neo4j
The World’s Leading Graph Database
Neo4j is a high-performance, NOSQL graph database with all the features of a mature and robust database.
找共同朋友
java - How to calculate mutual friends with neo4j? - Stack Overflow 用中文來解釋就是:vertex A 與 vertex B 的 shortest path,而且只過一個 hop

找你可能認識的人
(目前還沒研究)




3 則留言:

  1. 原來facebook得graph api就是指這個阿...?

    回覆刪除
  2. 請教一下 b) 可以這樣寫嗎
    SELECT DISTINCT(F2.friend_id) FROM friends AS F1
    INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id
    WHERE F1.user_id = 1 AND F2.friend_id != 1 AND
    F2.user_id != 1

    回覆刪除