實(shí)戰(zhàn)SQL：微信、微博等社交網(wǎng)絡(luò)的友好、粉絲關(guān)系分析
如今，社交軟件已經(jīng)成為了我們生活必不可少的一部分。相信絕大多數(shù)人每天起來(lái)，都少不了會(huì)打開(kāi)微信、QQ 刷刷朋友圈，或者打開(kāi)微博、知乎看看最新熱點(diǎn)。那么，今天我們就來(lái)看看這些軟件如何建立網(wǎng)絡(luò)社交關(guān)系。簡(jiǎn)單來(lái)說(shuō)，網(wǎng)絡(luò)社交關(guān)系主要分為兩類(lèi)：
- 好友關(guān)系。在微信、QQ、Facebook 等軟件中，兩個(gè)人可以互加好友，從而和朋友、同事、同學(xué)以及周?chē)娜吮３只?dòng)交流。
- 粉絲關(guān)注。在微博、CSDN、知乎、Twitter 等軟件中，我們可以通過(guò)關(guān)注成為其他人的粉絲，了解他/她們的最新動(dòng)態(tài)。關(guān)注可以是單向的，也可以互相關(guān)注。
那么對(duì)于微信、微博等這些社交軟件而言，它們?nèi)绾未鎯?chǔ)好友或者關(guān)注關(guān)系呢？利用這些存儲(chǔ)的數(shù)據(jù)，我們又能夠進(jìn)行哪些分析、獲取哪些隱藏的信息呢？
數(shù)據(jù)結(jié)構(gòu)
社交網(wǎng)絡(luò)是一個(gè)復(fù)雜的非線性結(jié)構(gòu)，通常使用圖（Graph）這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行表示。
好友關(guān)系圖
對(duì)于微信好友這種關(guān)系，每個(gè)用戶是一個(gè)頂點(diǎn)（Vertex）；兩個(gè)用戶之間互加好友，就會(huì)在兩者之間建立一條邊（Edge）。以下是一個(gè)簡(jiǎn)單的示意圖：
顯然，好友關(guān)系是一種無(wú)向圖（Undirected Graph）；不存在 A 是 B 的好友，但 B 不是 A 的好友。另外，一個(gè)用戶有多少個(gè)好友，連接到該頂點(diǎn)的邊就有多少條。這個(gè)也叫做頂點(diǎn)的度（Degree），上圖中“劉一”的度為 5（微信中表示好友數(shù)）。
對(duì)于 QQ 中的好友關(guān)系而言，還包含了額外的信息，就是好友親密度。這種關(guān)系可以使用加權(quán)圖（Weighted Graph）表示，其中的邊可以分配一個(gè)數(shù)字，表示權(quán)重。
其中，“張三”和“李四”的關(guān)系最親密，權(quán)重是 99。
加權(quán)圖常見(jiàn)的應(yīng)用還包括飛機(jī)航線圖；機(jī)場(chǎng)是頂點(diǎn)，航線是邊，邊的權(quán)重可以是飛行時(shí)間或者機(jī)票價(jià)格。另一個(gè)例子是地鐵換乘路線圖，每個(gè)站點(diǎn)是頂點(diǎn)，地鐵軌道是邊，時(shí)間是權(quán)重。
粉絲關(guān)系圖
對(duì)于微博這種粉絲關(guān)注關(guān)系而言，需要使用有向圖（Directed Graph）表示。因?yàn)殛P(guān)注是單向關(guān)聯(lián)，A 關(guān)注了 B，但是 B 不一定關(guān)注 A。這種有向圖的示意圖如下：
如果 A 關(guān)注了 B，圖中就會(huì)存在一條從 A 到 B 的帶箭頭的邊。上圖中，“劉一”關(guān)注了“周八”，“劉一”和“李四”相互關(guān)注。對(duì)于有向圖而言，度又分為入度（In-degree）和出度（Out-degree）。入度表示有多少條邊指向該頂點(diǎn)，出度表示有多少條邊是以該頂點(diǎn)為起點(diǎn)。“劉一”的入度為 4（微博中表示粉絲數(shù)），出度為 2（微博中表示關(guān)注的人數(shù)）。
數(shù)據(jù)存儲(chǔ)
對(duì)于圖的存儲(chǔ)而言，我們只要把頂點(diǎn)和邊儲(chǔ)存起來(lái)，那么圖的所有信息就保存完整了。所以，一般有兩種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣（Adjacency Matrix）和鄰接列表（Adjacency List）。
鄰接矩陣就是一個(gè)二維數(shù)組。對(duì)于上面的好友關(guān)系可以使用下面的矩陣表示：
對(duì)于無(wú)向圖，如果頂點(diǎn) i 與頂點(diǎn) j 之間有邊那么 A[i][j] 和 A[j][i] 都為 1；上面的 A[1][2] 表示“劉一”和“陳二”是好友。
對(duì)于有向圖，如果存在從頂點(diǎn) i 指向頂點(diǎn) j 的邊，那么 A[i][j] 就為 1；如果也存在從頂點(diǎn) j 指向頂點(diǎn) i 的邊，那么 A[j][i] 也為 1。對(duì)于加權(quán)圖，數(shù)組中存儲(chǔ)的數(shù)字代表了應(yīng)的權(quán)重。
鄰接矩陣雖然方便計(jì)算，獲取兩個(gè)頂點(diǎn)之間的關(guān)系時(shí)非常高效，但是存儲(chǔ)空間利用率太低。首先，無(wú)向圖中 A[i][j] 和 A[j][i] 表示相同的意義，只需要存儲(chǔ)其中一個(gè)；因此浪費(fèi)了一半的空間。其次，大多數(shù)的社交關(guān)系都屬于稀疏矩陣（Sparse Matrix），頂點(diǎn)很多但是邊很少。例如，微信用戶數(shù)量已經(jīng)超過(guò) 10 億，但是大多數(shù)人的好友在幾百人；意味著鄰接矩陣中絕大多數(shù)都是零，浪費(fèi)了大量的存儲(chǔ)空間。
實(shí)際上我們能夠在社交網(wǎng)絡(luò)穩(wěn)定交往的人數(shù)是大概是 150，參考鄧巴數(shù)字。同時(shí)，許多社交軟件也設(shè)置了好友人數(shù)上限，目前普通 QQ 用戶通過(guò) QQ 客戶端添加好友的最高上限1500人。
我們?cè)賮?lái)看看鄰接列表。上面的粉絲關(guān)注可以使用下面的列表描述：
其中，每個(gè)頂點(diǎn)都有一個(gè)記錄著與它相關(guān)的頂點(diǎn)列表。“劉一”關(guān)注了“李四”和“周八”，所以上面是一個(gè)關(guān)注列表。我們也可以創(chuàng)建一個(gè)逆向的鄰接列表，存儲(chǔ)了用戶的粉絲。
對(duì)于好友關(guān)系這種無(wú)向圖，可以認(rèn)為每條邊都是雙向的，同樣可以使用鄰接列表存儲(chǔ)。
鄰接列表的存儲(chǔ)更加高效，大部分操作也更快，例如增加頂點(diǎn)（用戶）、增加邊（增加好友、關(guān)注某人）；但是查找兩個(gè)頂點(diǎn)是否相鄰時(shí)，可能需要遍歷整個(gè)列表，效率相對(duì)低一些。
具體到數(shù)據(jù)庫(kù)，我們可以為頂點(diǎn)創(chuàng)建一個(gè)表，為頂點(diǎn)之間的邊創(chuàng)建一個(gè)表，從而實(shí)現(xiàn)鄰接表模型。以下內(nèi)容在 MySQL、Oracle、SQL Server、PostgreSQL 以及 SQLite 數(shù)據(jù)庫(kù)中進(jìn)行了驗(yàn)證。
好友關(guān)系分析
我們首先創(chuàng)建一個(gè)用戶表和好友關(guān)系表：
create table t_user(user_id int primary key, user_name varchar(50) not null);
insert into t_user values(1, '劉一');
insert into t_user values(2, '陳二');
insert into t_user values(3, '張三');
insert into t_user values(4, '李四');
insert into t_user values(5, '王五');
insert into t_user values(6, '趙六');
insert into t_user values(7, '孫七');
insert into t_user values(8, '周八');
insert into t_user values(9, '吳九');
create table t_friend(
user_id int not null,
friend_id int not null,
created_time timestamp not null,
primary key (user_id, friend_id)
);
insert into t_friend values(1, 2, current_timestamp);
insert into t_friend values(2, 1, current_timestamp);
insert into t_friend values(1, 3, current_timestamp);
insert into t_friend values(3, 1, current_timestamp);
insert into t_friend values(1, 4, current_timestamp);
insert into t_friend values(4, 1, current_timestamp);
insert into t_friend values(1, 7, current_timestamp);
insert into t_friend values(7, 1, current_timestamp);
insert into t_friend values(1, 8, current_timestamp);
insert into t_friend values(8, 1, current_timestamp);
insert into t_friend values(2, 3, current_timestamp);
insert into t_friend values(3, 2, current_timestamp);
insert into t_friend values(2, 5, current_timestamp);
insert into t_friend values(5, 2, current_timestamp);
insert into t_friend values(3, 4, current_timestamp);
insert into t_friend values(4, 3, current_timestamp);
insert into t_friend values(4, 6, current_timestamp);
insert into t_friend values(6, 4, current_timestamp);
insert into t_friend values(5, 8, current_timestamp);
insert into t_friend values(8, 5, current_timestamp);
insert into t_friend values(7, 8, current_timestamp);
insert into t_friend values(8, 7, current_timestamp);其中，t_user 表用于存儲(chǔ)用戶信息；t_friend 表存儲(chǔ)好友關(guān)系，每個(gè)好友關(guān)系存儲(chǔ)兩條記錄。
如果是單向圖結(jié)構(gòu)（組織結(jié)構(gòu)樹(shù)），可以使用一個(gè)表進(jìn)行存儲(chǔ)。通常是為 id 增加一個(gè)父級(jí)節(jié)點(diǎn) parent_id。
查看好友列表
微信中的通訊錄，顯示的就是我們的好友。同樣，我們可以查看“王五”（user_id = 5）的好友：
select u.user_id as friend_id,u.user_name as friend_name
from t_user u
join t_friend f on (u.user_id = f.friend_id and f.user_id = 5);
friend_id|friend_name|
---------|-----------|
2|陳二 |
8|周八 |“王五”有兩個(gè)好友，分別是“陳二”和“周八”。
查看共同好友
利用好友關(guān)系表，我們還可以獲取更多關(guān)聯(lián)信息。例如，以下語(yǔ)句可以查看“張三”和“李四”的共同好友：
with f1(friend_id) as (
select f.friend_id
from t_user u
join t_friend f on (u.user_id = f.friend_id and f.user_id = 3)),
f2(friend_id) as (
select f.friend_id
from t_user u
join t_friend f on (u.user_id = f.friend_id and f.user_id = 4))
select u.user_id as friend_id,u.user_name as friend_name
from t_user u
join f1 on (u.user_id = f1.friend_id)
join f2 on (u.user_id = f2.friend_id);
friend_id|friend_name|
---------|-----------|
1|劉一 |上面的語(yǔ)句中我們使用了通用表表達(dá)式（Common Table Expression）定義了兩個(gè)臨時(shí)查詢(xún)結(jié)果集 f1 和 f2，分別表示“張三”的好友和“李四”的好友；然后通過(guò)連接查詢(xún)返回他們的共同好友。關(guān)于通用表表達(dá)式以及各種數(shù)據(jù)庫(kù)中的語(yǔ)法可以參考這篇文章。
可能認(rèn)識(shí)的人
很多社交軟件都可以實(shí)現(xiàn)推薦（你可能認(rèn)識(shí)的）好友功能。一方面可能是讀取了你的手機(jī)通訊錄，找到已經(jīng)在系統(tǒng)中注冊(cè)但不屬于你的好友的用戶；另一方面就是找出和你不是好友，但是有共同好友的用戶。
以下語(yǔ)句用于找出可以推薦給“陳二”的用戶：
with friend(id) as (
select f.friend_id
from t_user u
join t_friend f on (u.user_id = f.friend_id and f.user_id = 2)),
fof(id) as (
select f.friend_id
from t_user u
join t_friend f on (u.user_id = f.friend_id)
join friend on (f.user_id = friend.id and f.friend_id != 2))
select u.user_id, u.user_name, count(*)
from t_user u
join fof on (u.user_id = fof.id)
where fof.id not in (select id from friend)
group by u.user_id, u.user_name;
user_id|user_name|count(*)|
-------|---------|--------|
4|李四 | 2|
7|孫七 | 1|
8|周八 | 2|我們同樣使用了通用表表達(dá)式，friend 代表了“陳二”的好友，fof 代表了“陳二”好友的好友（排除了“陳二”自己）；最后排除 fof 中已經(jīng)是“陳二”好友的用戶，并且統(tǒng)計(jì)了他們和“陳二”的共同好友數(shù)量。
根據(jù)查詢(xún)結(jié)果，我們可以向“陳二”推薦 3 個(gè)可能認(rèn)識(shí)的人；并且告訴他和“李四”有 2 位共同好友等。
最遙遠(yuǎn)的距離
在社會(huì)學(xué)中存在一個(gè)六度關(guān)系理論（Six Degrees of Separation），指地球上所有的人都可以通過(guò)六層以?xún)?nèi)的關(guān)系鏈和任何其他人聯(lián)系起來(lái)。在社交網(wǎng)絡(luò)中，也有一些相關(guān)的實(shí)驗(yàn)。例如 2011年，F(xiàn)acebook 以一個(gè)月內(nèi)訪問(wèn) 的 7.21 億活躍用戶為研究對(duì)象，計(jì)算出其中任何兩個(gè)獨(dú)立的用戶之間平均所間隔的人數(shù)為4.74。
我們以“趙六”和“孫七“為例，查找任意兩個(gè)人之間的關(guān)系鏈：
with recursive t(id, fid, hops, path) as (
select user_id, friend_id, 0, CAST(CONCAT(user_id , ',', friend_id) AS CHAR(1000))
from t_friend
where user_id = 6
union all
select t.id, f.friend_id, hops+1, CONCAT(t.path, ',', f.friend_id)
from t join t_friend f
on (t.fid = f.user_id) and (FIND_IN_SET(f.friend_id, t.path) = 0) and hops < 5
)
select *
from t where t.fid = 7
order by hops;
id|fid|hops|path |
--|---|----|-------------|
6| 7| 2|6,4,1,7 |
6| 7| 3|6,4,3,1,7 |
6| 7| 3|6,4,1,8,7 |
6| 7| 4|6,4,3,1,8,7 |
6| 7| 4|6,4,3,2,1,7 |
6| 7| 5|6,4,1,2,5,8,7|
6| 7| 5|6,4,3,2,1,8,7|
6| 7| 5|6,4,3,2,5,8,7|查詢(xún)結(jié)果顯示，“趙六”和“孫七“之間最近的距離是通過(guò)兩個(gè)人（”李四“和”劉一“）進(jìn)行聯(lián)系。我們也可以統(tǒng)計(jì)示例表中任何兩個(gè)用戶之間的平均間隔人數(shù)：
with recursive t(id, fid, hops, path) as (
select user_id, friend_id, 0, CAST(CONCAT(user_id , ',', friend_id) AS CHAR(1000))
from t_friend
where user_id = 6
union all
select t.id, f.friend_id, hops+1, CONCAT(t.path, ',', f.friend_id)
from t join t_friend f
on (t.fid = f.user_id) and (FIND_IN_SET(f.friend_id, t.path) = 0) and hops < 5
)
select avg(hops)
from t
order by hops;
avg(hops)|
---------|
3.5116|對(duì)于 QQ 這種加權(quán)圖，可以在 t_friend 表中增加一個(gè)權(quán)重字段，從而分析好友的親密度。
粉絲關(guān)系分析
對(duì)于微博這種有向圖，對(duì)應(yīng)的表結(jié)構(gòu)可以設(shè)計(jì)如下：
-- 粉絲
create table t_follower(
user_id int not null,
follower_id int not null,
created_time timestamp not null,
primary key (user_id, follower_id)
);
insert into t_follower values(1, 2, current_timestamp);
insert into t_follower values(1, 3, current_timestamp);
insert into t_follower values(1, 4, current_timestamp);
insert into t_follower values(1, 7, current_timestamp);
insert into t_follower values(2, 3, current_timestamp);
insert into t_follower values(3, 4, current_timestamp);
insert into t_follower values(4, 1, current_timestamp);
insert into t_follower values(5, 2, current_timestamp);
insert into t_follower values(5, 8, current_timestamp);
insert into t_follower values(6, 4, current_timestamp);
insert into t_follower values(7, 8, current_timestamp);
insert into t_follower values(8, 1, current_timestamp);
insert into t_follower values(8, 7, current_timestamp);
-- 關(guān)注
create table t_followed(
user_id int not null,
followed_id int not null,
created_time timestamp not null,
primary key (user_id, followed_id)
);
insert into t_followed values(1, 4, current_timestamp);
insert into t_followed values(1, 8, current_timestamp);
insert into t_followed values(2, 1, current_timestamp);
insert into t_followed values(2, 5, current_timestamp);
insert into t_followed values(3, 1, current_timestamp);
insert into t_followed values(3, 2, current_timestamp);
insert into t_followed values(4, 1, current_timestamp);
insert into t_followed values(4, 3, current_timestamp);
insert into t_followed values(4, 6, current_timestamp);
insert into t_followed values(7, 1, current_timestamp);
insert into t_followed values(7, 8, current_timestamp);
insert into t_followed values(8, 5, current_timestamp);
insert into t_followed values(8, 7, current_timestamp);其中，t_follower 存儲(chǔ)粉絲，t_followed 存儲(chǔ)關(guān)注的人。每次有用戶關(guān)注其他人，往這兩個(gè)表中插入相應(yīng)的記錄。
由于粉絲相對(duì)于好友是一種弱關(guān)系，能夠分析的內(nèi)容相對(duì)簡(jiǎn)單一些。
我的關(guān)注
我們看看“劉一”關(guān)注了哪些用戶：
select f.followed_id, u.user_name
from t_followed f
join t_user u on (u.user_id = f.followed_id)
where f.user_id = 1;
followed_id|user_name|
-----------|---------|
4|李四 |
8|周八 |“劉一”關(guān)注了“李四”和“周八”。
共同關(guān)注
我們還可以進(jìn)一步獲取和“劉一”具有相同關(guān)注的人的用戶：
select r.follower_id, r.user_id
from t_followed d
join t_follower r on (r.user_id = d.followed_id and r.follower_id != d.user_id)
where d.user_id = 1;
follower_id|user_id|
-----------|-------|
7| 8|結(jié)果顯示，“劉一”和“孫七”共同關(guān)注了“周八”。
我的粉絲
我們?cè)賮?lái)看看哪些用戶是“劉一”的粉絲：
select f.follower_id, u.user_name
from t_follower f
join t_user u on (u.user_id = f.follower_id)
where f.user_id = 1;
follower_id|user_name|
-----------|---------|
2|陳二 |
3|張三 |
4|李四 |
7|孫七 |“劉一”有 4 個(gè)粉絲。
相互關(guān)注
最后，我們看看哪些用戶之間互為粉絲，或者互相關(guān)注：
select r.user_id, r.follower_id
from t_follower r
join t_followed d on (r.user_id = d.user_id and r.follower_id = d.followed_id and r.user_id < r.follower_id);
user_id|follower_id|
-------|-----------|
1| 4|
7| 8|結(jié)果顯示，“劉一”和“李四”互為粉絲，而“孫七”和“周八”則互相關(guān)注。
總結(jié)
本文介紹了如何將微信、微博這類(lèi)圖結(jié)構(gòu)的社交網(wǎng)絡(luò)數(shù)據(jù)使用鄰接列表進(jìn)行描述，并且最終存儲(chǔ)為結(jié)構(gòu)化的關(guān)系表。利用 SQL 語(yǔ)句中的連接查詢(xún)、通用表表達(dá)式的遞歸查詢(xún)等功能對(duì)其進(jìn)行分析，發(fā)行其中隱藏的社交關(guān)系。
除了社交網(wǎng)絡(luò)關(guān)系分析之外，這些 SQL 功能也可以用于飛機(jī)航班查找、地鐵換乘路線查詢(xún)，甚至用于實(shí)現(xiàn)各種推薦系統(tǒng)，例如產(chǎn)品的猜你喜歡與電影推薦。
