用圖技術搞定附近好友、時空交集等 7 個典型社交網路應用

語言: CN / TW / HK
時間 2023-03-17 02:02:13
主題:

兩個月之前，我的同事拿了一張推特的互動關係圖（下圖，由 STRRL 授權）來問我能不能搞一篇圖技術來探索社交互動關係的文章，看看這些圖是如何通過技術實現的。

我想了想，自己玩推特以來也跟隨大部隊生成了不少的社交關係組圖，當中有複雜的社交群體劃分：

我在技術圈，看在金融、數學圈的大佬在彼岸緊密貼貼。當然也有比較簡單的關係圖：

看誰和你互動比較多，而他們又和誰關係比較密切。那麼問題來了，像上面這種常見的社交關係圖，甚至是別的更復雜的基於社交網路的圖是如何生成的呢？在本文我將用圖資料庫 NebulaGraph 來解決社交網路問題，而上面的社交關係組圖也被包含在其中。btw，文中介紹的方法提供都了 Playground 供大家學習、玩耍。

簡單剖析社交網路的選型

從上面的圖我們可以知道，一個典型的社交網路拓撲圖便是使用者的點和關係的邊組成的網狀結構。

因此，我們可以用圖資料庫來表示使用者和他們的連線關係，來完成這個社交網路的資料模型。基於圖資料庫，我們可以對使用者間的關係進行查詢，讓各類基於社交網路連線關係的查詢、統計、分析需求變得更便捷、高效。

例如，利用圖形資料庫來識別網路中的“有影響力的使用者”；根據使用者之間的共同點對新的連線（好友關係、感興趣的資訊）進行推薦；更甚者尋找社群中聚集的不同人群、社群，進行使用者畫像。

以 NebulaGraph 為代表的圖資料庫不僅能支撐複雜的多跳查詢，同時也支援實時寫入、更新資料，因此非常適合用來探索使用者關係不斷變化的社交網路系統。

圖建模

上文說過社交網路天然就是一種網路、圖的結構形態，為了分析常見社交場景的應用示例，本文的例子採用了典型的小型社交網路。因此，我在 NebulaGraph 官方資料集 basketballplayer 之上，增加了：

三種點：

  • 地址
  • 地點
  • 文章

四種邊：

  • 發文
  • 評論
  • 住在
  • 屬於（地點）

它的建模非常自然：

schema_sketch

資料匯入

匯入資料集

首先，我們載入預設的 basketballplayer 資料集，匯入對應的 schema 和資料。

如果你使用的是命令列，那你在 console 之中執行 :play basketballplayer 就可以匯入資料。如果你使用了視覺化圖探索工具 NebulaGraph Studio / NebulaGraph Explorer，我們需要在歡迎頁點選下載、部署這份基礎資料集。

basketballplayer_studio_starter

建立社交網路 schema

通過下面語句建立新加入的點、邊型別 schema：

CREATE TAG IF NOT EXISTS post(title string NOT NULL);
CREATE EDGE created_post(post_time timestamp);
CREATE EDGE commented_at(post_time timestamp);
CREATE TAG address(address string NOT NULL, `geo_point` geography(point));
CREATE TAG place(name string NOT NULL, `geo_point` geography(point));
CREATE EDGE belong_to();
CREATE EDGE lived_in();

寫入新資料

在等待兩個心跳（20秒）以上時間之後，我們可以執行資料插入：

INSERT VERTEX post(title) values \
    "post1":("a beautify flower"), "post2":("my first bike"), "post3":("I can swim"), \
    "post4":("I love you, Dad"), "post5":("I hate coriander"), "post6":("my best friend, tom"), \
    "post7":("my best friend, jerry"), "post8":("Frank, the cat"), "post9":("sushi rocks"), \
    "post10":("I love you, Mom"), "post11":("Let's have a party!");

INSERT EDGE created_post(post_time) values \
    "player100"->"post1":(timestamp("2019-01-01 00:30:06")), \
    "player111"->"post2":(timestamp("2016-11-23 10:04:50")), \
    "player101"->"post3":(timestamp("2019-11-11 10:44:06")), \
    "player103"->"post4":(timestamp("2014-12-01 20:45:11")), \
    "player102"->"post5":(timestamp("2015-03-01 00:30:06")), \
    "player104"->"post6":(timestamp("2017-09-21 23:30:06")), \
    "player125"->"post7":(timestamp("2018-01-01 00:44:23")), \
    "player106"->"post8":(timestamp("2019-01-01 00:30:06")), \
    "player117"->"post9":(timestamp("2022-01-01 22:23:30")), \
    "player108"->"post10":(timestamp("2011-01-01 10:00:30")), \
    "player100"->"post11":(timestamp("2021-11-01 11:10:30"));

INSERT EDGE commented_at(post_time) values \
    "player105"->"post1":(timestamp("2019-01-02 00:30:06")), \
    "player109"->"post1":(timestamp("2016-11-24 10:04:50")), \
    "player113"->"post3":(timestamp("2019-11-13 10:44:06")), \
    "player101"->"post4":(timestamp("2014-12-04 20:45:11")), \
    "player102"->"post1":(timestamp("2015-03-03 00:30:06")), \
    "player103"->"post1":(timestamp("2017-09-23 23:30:06")), \
    "player102"->"post7":(timestamp("2018-01-04 00:44:23")), \
    "player101"->"post8":(timestamp("2019-01-04 00:30:06")), \
    "player106"->"post9":(timestamp("2022-01-02 22:23:30")), \
    "player105"->"post10":(timestamp("2011-01-11 10:00:30")), \
    "player130"->"post1":(timestamp("2019-01-02 00:30:06")), \
    "player131"->"post2":(timestamp("2016-11-24 10:04:50")), \
    "player131"->"post3":(timestamp("2019-11-13 10:44:06")), \
    "player133"->"post4":(timestamp("2014-12-04 20:45:11")), \
    "player132"->"post5":(timestamp("2015-03-03 00:30:06")), \
    "player134"->"post6":(timestamp("2017-09-23 23:30:06")), \
    "player135"->"post7":(timestamp("2018-01-04 00:44:23")), \
    "player136"->"post8":(timestamp("2019-01-04 00:30:06")), \
    "player137"->"post9":(timestamp("2022-01-02 22:23:30")), \
    "player138"->"post10":(timestamp("2011-01-11 10:00:30")), \
    "player141"->"post1":(timestamp("2019-01-03 00:30:06")), \
    "player142"->"post2":(timestamp("2016-11-25 10:04:50")), \
    "player143"->"post3":(timestamp("2019-11-14 10:44:06")), \
    "player144"->"post4":(timestamp("2014-12-05 20:45:11")), \
    "player145"->"post5":(timestamp("2015-03-04 00:30:06")), \
    "player146"->"post6":(timestamp("2017-09-24 23:30:06")), \
    "player147"->"post7":(timestamp("2018-01-05 00:44:23")), \
    "player148"->"post8":(timestamp("2019-01-05 00:30:06")), \
    "player139"->"post9":(timestamp("2022-01-03 22:23:30")), \
    "player140"->"post10":(timestamp("2011-01-12 10:01:30")), \
    "player141"->"post1":(timestamp("2019-01-04 00:34:06")), \
    "player102"->"post2":(timestamp("2016-11-26 10:06:50")), \
    "player103"->"post3":(timestamp("2019-11-15 10:45:06")), \
    "player104"->"post4":(timestamp("2014-12-06 20:47:11")), \
    "player105"->"post5":(timestamp("2015-03-05 00:32:06")), \
    "player106"->"post6":(timestamp("2017-09-25 23:31:06")), \
    "player107"->"post7":(timestamp("2018-01-06 00:46:23")), \
    "player118"->"post8":(timestamp("2019-01-06 00:35:06")), \
    "player119"->"post9":(timestamp("2022-01-04 22:26:30")), \
    "player110"->"post10":(timestamp("2011-01-15 10:00:30")), \
    "player111"->"post1":(timestamp("2019-01-06 00:30:06")), \
    "player104"->"post11":(timestamp("2022-01-15 10:00:30")), \
    "player125"->"post11":(timestamp("2022-02-15 10:00:30")), \
    "player113"->"post11":(timestamp("2022-03-15 10:00:30")), \
    "player102"->"post11":(timestamp("2022-04-15 10:00:30")), \
    "player108"->"post11":(timestamp("2022-05-15 10:00:30"));

INSERT VERTEX `address` (`address`, `geo_point`) VALUES \
    "addr_0":("Brittany Forge Apt. 718 East Eric  WV 97881", ST_Point(1,2)),\
    "addr_1":("Richard Curve Kingstad  AZ 05660", ST_Point(3,4)),\
    "addr_2":("Schmidt Key Lake Charles  AL 36174", ST_Point(13.13,-87.65)),\
    "addr_3":("5 Joanna Key Suite 704 Frankshire  OK 03035", ST_Point(5,6)),\
    "addr_4":("1 Payne Circle Mitchellfort  LA 73053", ST_Point(7,8)),\
    "addr_5":("2 Klein Mission New Annetteton  HI 05775", ST_Point(9,10)),\
    "addr_6":("1 Vanessa Stravenue Suite 184 Baileyville  NY 46381", ST_Point(11,12)),\
    "addr_7":("John Garden Port John  LA 54602", ST_Point(13,14)),\
    "addr_8":("11 Webb Groves Tiffanyside  MN 14566", ST_Point(15,16)),\
    "addr_9":("70 Robinson Locks Suite 113 East Veronica  ND 87845", ST_Point(17,18)),\
    "addr_10":("24 Mcknight Port Apt. 028 Sarahborough  MD 38195", ST_Point(19,20)),\
    "addr_11":("0337 Mason Corner Apt. 900 Toddmouth  FL 61464", ST_Point(21,22)),\
    "addr_12":("7 Davis Station Apt. 691 Pittmanfort  HI 29746", ST_Point(23,24)),\
    "addr_13":("1 Southport Street Apt. 098 Westport  KY 85907", ST_Point(120.12,30.16)),\
    "addr_14":("Weber Unions Eddieland  MT 64619", ST_Point(25,26)),\
    "addr_15":("1 Amanda Freeway Lisaland  NJ 94933", ST_Point(27,28)),\
    "addr_16":("2 Klein HI 05775", ST_Point(9,10)),\
    "addr_17":("Schmidt Key Lake Charles AL 13617", ST_Point(13.12, -87.60)),\
    "addr_18":("Rodriguez Track East Connorfort  NC 63144", ST_Point(29,30));

INSERT VERTEX `place` (`name`, `geo_point`) VALUES \
    "WV":("West Virginia", ST_Point(1,2.5)),\
    "AZ":("Arizona", ST_Point(3,4.5)),\
    "AL":("Alabama", ST_Point(13.13,-87)),\
    "OK":("Oklahoma", ST_Point(5,6.1)),\
    "LA":("Louisiana", ST_Point(7,8.1)),\
    "HI":("Hawaii", ST_Point(9,10.1)),\
    "NY":("New York", ST_Point(11,12.1)),\
    "MN":("Minnesota", ST_Point(15,16.1)),\
    "ND":("North Dakota", ST_Point(17,18.1)),\
    "FL":("Florida", ST_Point(21,22.1)),\
    "KY":("Kentucky", ST_Point(120.12,30)),\
    "MT":("Montana", ST_Point(25,26.1)),\
    "NJ":("New Jersey", ST_Point(27,28.1)),\
    "NC":("North Carolina", ST_Point(29,30.1));

INSERT EDGE `belong_to`() VALUES \
    "addr_0"->"WV":(),\
    "addr_1"->"AZ":(),\
    "addr_2"->"AL":(),\
    "addr_3"->"OK":(),\
    "addr_4"->"LA":(),\
    "addr_5"->"HI":(),\
    "addr_6"->"NY":(),\
    "addr_7"->"LA":(),\
    "addr_8"->"MN":(),\
    "addr_9"->"ND":(),\
    "addr_10"->"MD":(),\
    "addr_11"->"FL":(),\
    "addr_12"->"HI":(),\
    "addr_13"->"KY":(),\
    "addr_14"->"MT":(),\
    "addr_15"->"NJ":(),\
    "addr_16"->"HI":(),\
    "addr_17"->"AL":(),\
    "addr_18"->"NC":();

INSERT EDGE `lived_in`() VALUES \
    "player100"->"addr_4":(),\
    "player101"->"addr_7":(),\
    "player102"->"addr_2":(),\
    "player103"->"addr_3":(),\
    "player104"->"addr_0":(),\
    "player105"->"addr_5":(),\
    "player106"->"addr_6":(),\
    "player107"->"addr_1":(),\
    "player108"->"addr_8":(),\
    "player109"->"addr_9":(),\
    "player110"->"addr_10":(),\
    "player111"->"addr_11":(),\
    "player112"->"addr_12":(),\
    "player113"->"addr_13":(),\
    "player114"->"addr_14":(),\
    "player115"->"addr_15":(),\
    "player116"->"addr_16":(),\
    "player117"->"addr_17":(),\
    "player118"->"addr_18":();

資料初探

完成 schema 建立和資料匯入之後，我們來看看資料統計：

[basketballplayer]> SUBMIT JOB STATS;

+------------+
| New Job Id |
+------------+
| 10         |
+------------+
[basketballplayer]> SHOW STATS;
+---------+----------------+-------+
| Type    | Name           | Count |
+---------+----------------+-------+
| "Tag"   | "address"      | 19    |
| "Tag"   | "place"        | 14    |
| "Tag"   | "player"       | 51    |
| "Tag"   | "post"         | 10    |
| "Tag"   | "team"         | 30    |
| "Edge"  | "belong_to"    | 19    |
| "Edge"  | "commented_at" | 40    |
| "Edge"  | "created_post" | 10    |
| "Edge"  | "follow"       | 81    |
| "Edge"  | "lived_in"     | 19    |
| "Edge"  | "serve"        | 152   |
| "Space" | "vertices"     | 124   |
| "Space" | "edges"        | 321   |
+---------+----------------+-------+
Got 13 rows (time spent 1038/51372 us)

查一下所有的資料：

MATCH ()-[e]->() RETURN e LIMIT 10000

因為資料量太小了，這裡可以把所有資料在 NebulaGraph Explorer 中進行渲染出來：

match_all

社交網路典型應用

找出網路中的關鍵人物

要識別社交網路中的有影響力的關鍵人物們（Influencer）需要使用上各種指標和方法，而 KOL 的識別對很多業務場景都有幫助，比如：用於營銷或研究網路中的資訊傳播。

識別他們的方法有很多，具體的方法和考量資訊、關係、角度也取決於這些關鍵人物的型別和獲取他們的目的。

識別 Influencer 常見的方法包括看他們的粉絲數、內容瀏覽量，內容（包括帖子、視訊）上讀者的參與度，以及他們的內容影響力（轉發、引用）。這些思路如果用圖資料庫實現也沒啥問題，不過太普通太普通了，我們搞點高科技的——用評估、計算節點重要性的圖演算法，在圖上得出這些關鍵人物。

PageRank

PageRank 是一個非常“古老的”圖演算法，它計算圖上點之間的關係數量得到每個點的得分（Rank），最初由 Google 的創始人 Larry Page 和 Sergey Brin 提出並應用在早期的 Google 搜尋引擎中，用來排序搜尋結果，這裡的 Page 可以是 Larry Page 的姓和 Web Page 的雙關了。

在現代、複雜的搜尋引擎中，PageRank 早就因為其過於簡單的設計而被棄用，但是在部分圖結構網路場景中，PageRank 演算法仍然在發光發熱。在社交網路中，我們姑且粗略地認為所有連線的重要程度相同，去執行 PageRank 演算法找到那些 Influencer。

在 NebulaGraph 中，我們可以利用圖計算工具 NebulaGraph Algorithm、NebulaGraph Analytics 在全圖上執行 PageRank，這是因為資料量小。但在日常的分析、驗證、設計截斷時，我們不需要在全量資料上跑結果，在一些很小的子圖上（最多上萬個節點），我們可以輕鬆地在瀏覽器裡邊執行各種圖演算法得到業務可用的資料。

這裡，我們就用 NebulaGraph Explorer 內建的圖演算法功能，在瀏覽器上點選一下滑鼠執行 PageRank 看看，具體方法這裡略去，可以參考文件。

PageRank

如圖所示，PageRank 計算之後所有綠色的 player（人）中，"player.name: Tim Duncan" 是最大的一個點。與之相關聯的關係看起來的確不少，我們在圖上選擇他，再右鍵反選，選擇除了 Tim Duncan 之外的所有點，用退格鍵刪除所有其他的點，再以他作為起點雙向探索出 1 到 5 步，可以得到 Tim Duncan 的子圖：

TimDuncan

除了可以看到 Tim Duncan 是個 Influener 之外，我們還可以看到其他受歡迎的隊員和他一樣服役過知名球隊的熱刺（Spurs），這些都印證了 PageRank 的評估方式。

現在，我們再看看其他判定維度下的演算法會不會得出一樣的結論呢？

Betweenness Centrality

作為另一個流行的節點重要性演算法，通過計算一個節點在圖中起到多少橋樑作用來衡量節點的重要性。這裡的橋樑作用是有數學定義的量化演算法，這裡就不展開說了。不過從感官上，可以看出它是另一個符合直覺去評估節點重要性的方法。

我們重新在畫布上查詢所有的點邊之後，在瀏覽器裡執行 Betweenness Centrality 演算法，這次的結果是：

Betweeness_centrality

從它的五跳內子圖可以看出，與之前 PageRank 所得的關鍵人物 Tim Duncan 呈現的星狀不同，Dejounte Murray 的子圖呈現簇狀，在感官、直覺上可以想象 Dejounte Murray 真的在很多節點之間的最小路徑上，而 Tim Duncan 則似乎和更多的重要連線者產生了關聯。

DejounteMurray

在實際的應用場景中，針對不同需求我們會選擇不同的演算法。一般來說，要嘗試各種定義、試驗各種執行結果，以便分析去找到我們關注的關鍵人物產生影響的結構特徵。

找出社群、聚叢集體

社交網路中的社群檢測是一種通過分析社交關係來發現社群結構的技術。社群結構是指在社交網路、圖譜中互相聯絡密切的一組節點，這些節點通常具有相似的特徵。例如，社群結構其中一種表現形式為：都對某類的話題或內容感興趣而聚集的一組使用者。

社群檢測的目的是通過對社交網路進行分析，找出不同社群的邊界，並確定每個社群中的節點。這個過程可以通過各種演算法來完成，例如：標籤傳播演算法、弱聯通分量演算法和 Louvain 演算法等。通過發現社群結構，可以更好地瞭解社交網路的結構和特徵，並有助於社交網路服務方更好地推斷和預測社交網路中的行為，協助治理社交網路、廣告投放、市場營銷等行為。

由於我們的資料集是模擬的，在不同的演算法之下得出的結果未必能展現其真實的面貌，所以本章只是簡單地展示下利用若干圖演算法進行社群識別之後的結果。在真實世界的案例中，我們應該在此基礎之上結合領域知識或者其他技術手段協同給出不同群體、社群的畫像、標籤。

標籤傳播演算法效果：

LPA

Louvain 演算法效果：

Louvain

弱聯通分量演算法效果：

WCC

在後面的章節，我們會在更小、更簡單的子圖上再次驗證這幾個演算法，結果會更具有可解釋性。

好友親密度

通過社群識別演算法，其實能在一定程度上在全域性計算中獲得興趣相近、關聯緊密的好友。那麼，如何獲得一個指定使用者的其他親密好友呢？

我們可以通過計算得到這個使用者的好友，根據該好友和使用者擁有的共同好友數進行排序，最後得到結果。

這裡以 "Tim Duncan" 舉例，他的兩度好友（好友的好友）相關語句是 (:player{name: "Tim Duncan"})-[:follow]-(f:player)-[:follow]-(fof:player)。如果 Tim Duncan 的兩度好友同時也是他的好友的話，那麼這個中間好友就是 Tim Duncan 和這個兩度好友的共同好友 Mutual Friend。我們有理由相信那些和 Tim Duncan 有更多共同好友的人可能跟他有更高的親密度：

MATCH (start:`player`{name: "Tim Duncan"})-[:`follow`]-(f:`player`)-[:`follow`]-(fof:`player`),
(start:`player`)-[:`follow`]-(fof:`player`)
RETURN fof.`player`.name, count(DISTINCT f) AS NrOfMutualF ORDER BY NrOfMutualF DESC;

這個計算結果是，"Tony Parker" 和 Tim 有 5 個共同好友，最為親密。

fof.player.name NrOfMutualF
Tony Parker 5
Dejounte Murray 4
Manu Ginobili 3
Marco Belinelli 3
Danny Green 2
Boris Diaw 1
LaMarcus Aldridge 1
Tiago Splitter 1

下面，咱們通過視覺化來驗證一下這個結果吧！

先看看每一個好友的共同好友 (f:) 都是誰？

MATCH (start:player{name: "Tim Duncan"})-[:`follow`]-(f:player)-[:`follow`]-(fof:player),
(start:player)-[:`follow`]-(fof:player)
RETURN fof.player.name, collect(DISTINCT f.player.name);

結果如下：

fof.player.name collect(distinct f.player.name)
Boris Diaw ["Tony Parker"]
Manu Ginobili ["Dejounte Murray", "Tiago Splitter", "Tony Parker"]
LaMarcus Aldridge ["Tony Parker"]
Tiago Splitter ["Manu Ginobili"]
Tony Parker ["Dejounte Murray", "Boris Diaw", "Manu Ginobili", "Marco Belinelli", "LaMarcus Aldridge"]
Dejounte Murray ["Danny Green", "Tony Parker", "Manu Ginobili", "Marco Belinelli"]
Danny Green ["Dejounte Murray", "Marco Belinelli"]
Marco Belinelli ["Dejounte Murray", "Danny Green", "Tony Parker"]

下面，我們上視覺化工具——NebulaGraph Explorer 搞一搞這個結果：

首先，我們把 Tim 的兩度好友路徑全查出來

MATCH p=(start:player{name: "Tim Duncan"})-[:`follow`]-(f:player)-[:follow]-(fof:player)
RETURN p

再按照出入度去渲染節點大小，並選中 Tim 和 Tony，並在兩者之間查詢 follow 型別邊、雙向、最多 2 跳的全部路徑：

可以看出 Tim 和 Tony 是最親密的朋友沒跑了，而且他們的共同好友也在路徑之中：

["Dejounte Murray", "Boris Diaw", "Manu Ginobili", "Marco Belinelli", "LaMarcus Aldridge"]

closest_friend

朋友圈子裡的小群體

上面提過由於這份資料集非真實，使得社群發現演算法的結果不能得到其中洞察的內涵。現在我們可以接著這個小的子圖，來看看 Tim 的好友中可以如何區分群組、社群呢？

咱們先跑一個 Louvain 、弱聯通分量、標籤傳播看看：

弱聯通分量

弱聯通分量，可以把 Tim 的朋友們大體分割出兩、三個相互不連通的部分，非常符合連通分量的直觀理解和定義。

Tim_wcc

標籤傳播

標籤傳播，我們可以通過控制迭代次數按需去通過隨機的傳播劃定出不同的劃分度，結果可以有一定的區分度：

這是 20 次迭代的圖：

Tim_LPA

這是 1,000 次迭代

Tim_LPA_1000

Louvain

Louvain，是一個比較高效、穩定的演算法，基本上在這個子圖下我們可以在很小的迭代次數下得到很符合直覺的劃分：

Tim_Louvain

新朋友推薦

接著前面兩度朋友（朋友的朋友）的思路，我們可以很容易把那些還不是朋友的兩度朋友作為推薦新增的好友，而排序規則是他們之間的共同好友數量：

MATCH (start:player{name: "Tim Duncan"})-[:`follow`]-(f:player)-[:`follow`]-(fof:player)
WHERE NOT (start:player)-[:`follow`]-(fof:player) AND fof != start
RETURN fof.player.name, count(DISTINCT f) AS NrOfMutualF ORDER BY NrOfMutualF DESC;
fof.player.name NrOfMutualF
LeBron James 2
James Harden 1
Chris Paul 1
Yao Ming 1
Damian Lillard 1
JaVale McGee 1
Kevin Durant 1
Kyle Anderson 1
Rudy Gay 1
Russell Westbrook 1

顯然，LeBron 最值得推薦！再看看這些共同好友都是誰？

fof.player.name collect(distinct f.player.name)
James Harden ["Dejounte Murray"]
LeBron James ["Danny Green", "Dejounte Murray"]
Chris Paul ["Dejounte Murray"]
Yao Ming ["Shaquille O'Neal"]
Damian Lillard ["LaMarcus Aldridge"]
JaVale McGee ["Shaquille O'Neal"]
Kevin Durant ["Dejounte Murray"]
Kyle Anderson ["Dejounte Murray"]
Rudy Gay ["LaMarcus Aldridge"]
Russell Westbrook ["Dejounte Murray"]

同樣，我們在剛才的子圖裡找找 LeBron James 吧！我們把他倆之間的兩步、雙向路徑找出來，果然只會經過 ["Danny Green", "Dejounte Murray"] 並且，沒有直接的連線：

Tim_newFriend

現在，系統應該給兩邊發提醒：“hey，也許你們應該交個朋友！”

共同鄰居

查詢共同鄰居是一個很常見的圖查詢，它的場景可能根據不同的鄰居關係、節點型別，同構、異構，帶來不同的場景。前面兩個場景的共同好友本質上是兩點之間的共同鄰居，直接查詢這樣的關係用 openCypher 的表達非常簡單。

兩點之間的共同鄰居

這個表達可以查詢兩個使用者之間的共性、交集，結果可能是共同團隊、去過的地方、興趣愛好、共同參與的帖子回覆等等：

MATCH p = (`v0`)--()--(`v1`)
WHERE id(`v0`) == "player100" AND id(`v1`) == "player104"
RETURN p

而限定了邊的型別之後，這個查詢就限定在共同好友的查詢了。

MATCH p = (v0)--(:`follow`)--(v1)
WHERE id(v0) == "player100" AND id(v1) == "player104"
RETURN p

多點之間的共同鄰居：內容推送

下面，我們給出一個多點共同鄰居的場景：我們從一個文章出發，查出所有在這個文章上有互動的使用者，找到這一群體中的共同鄰居。

這個共同鄰居有什麼用處呢？很自然，如果這個共同鄰居還沒有和這個文章有任何互動，我們可以把這個文章推薦給他。

這個查詢的實現很有意思：

  • 第一個 MATCH 是查到所有 post11 文章下留言、點贊之類的同作者互動的總人數
  • 第二個 MATCH 裡我們查詢這群人的一度好友中哪些人同互動使用者的共同好友數量剛好等於文章互動人數，即這些所有參與互動的使用者的共同好友。
MATCH (blog:post)<-[e]-(:player) WHERE id(blog) == "post11"
WITH blog, count(e) AS invoved_user_count
MATCH (blog:post)<-[]-(users:player)-[:`follow`]-(common_neighbor:player)
WITH toSet(collect(users)) AS users, common_neighbor, invoved_user_count
WHERE size(users) == invoved_user_count
RETURN common_neighbor

而這個人就是...Tony！

+-----------------------------------------------------+
| common_neighbor                                     |
+-----------------------------------------------------+
| ("player101" :player{age: 36, name: "Tony Parker"}) |
+-----------------------------------------------------+

而我們可以很容易在視覺化中驗證它：

MATCH p=(blog:post)<-[]-(users:player)-[:`follow`]-(common_neighbor:player)
WHERE id(blog) == "post11"
RETURN p

渲染這個查詢結果，再在這篇叫做 "Let's have a party!" 的文章與 Tony 之間查詢評論、發帖、關注三類邊的雙向、兩跳查詢，就可以看到這些參與文章的人們無一例外，都是 Tony 的好友，而只有 Tony 自己還沒去文章裡留言！

而 Party 怎麼可以少了 Tony 呢？難道是他的驚喜生日 Party，Opps，我們是不是不應該告訴他？

common_nbrs_tony

資訊流

我在之前寫過《基於圖技術的推薦系統實現方法》，其中講述了在圖譜上實現現代推薦系統中基於內容和協同的過濾，而類似的原理應用在社交網路可以實現個性推薦資訊流。

好友參與的內容

最簡單的資訊流，可能就是朋友圈、微博 feed 上刷到的關注的人建立、參與的內容。先不考慮排序的問題，這些內容一定是：

  • 一定時間段內好友建立的內容
  • 一定時間段內好友評論的內容

我們可以用 Cypher 表達這個查詢使用者 id 為 player100 的資訊流：

MATCH (feed_owner:player)-[:`follow`]-(friend:player) WHERE id(feed_owner) == "player100"
OPTIONAL MATCH (friend:player)-[newly_commented:commented_at]->(:post)<-[:created_post]-(feed_owner:player)
    WHERE newly_commented.post_time > timestamp("2010-01-01 00:00:00")
OPTIONAL MATCH (friend:player)-[newly_created:created_post]->(po:post)
    WHERE newly_created.post_time > timestamp("2010-01-01 00:00:00")
WITH DISTINCT friend,
    collect(DISTINCT po.post.title) + collect("comment of " + dst(newly_commented))
        AS feeds WHERE size(feeds) > 0
RETURN friend.player.name, feeds
friend.player.name feeds
Boris Diaw ["I love you, Mom", "comment of post11"]
Marco Belinelli ["my best friend, tom", "comment of post11"]
Danny Green ["comment of post1"]
Tiago Splitter ["comment of post1"]
Dejounte Murray ["comment of post11"]
Tony Parker ["I can swim"]
LaMarcus Aldridge ["I hate coriander", "comment of post11", "comment of post1"]
Manu Ginobili ["my best friend, jerry", "comment of post11", "comment of post11"]

於是，我們可以把這些評論、文章呈現到使用者的 feed。

一樣的，我們來看看視覺化效果。輸出所有查到的路徑：

MATCH p=(feed_owner:player)-[:`follow`]-(friend:player) WHERE id(feed_owner) == "player100"
OPTIONAL MATCH p_comment=(friend:player)-[newly_commented:commented_at]->(:post)<-[:created_post]-(feed_owner:player)
    WHERE newly_commented.post_time > timestamp("2010-01-01 00:00:00")
OPTIONAL MATCH p_post=(friend:player)-[newly_created:created_post]->(po:post)
    WHERE newly_created.post_time > timestamp("2010-01-01 00:00:00")
RETURN p, p_comment, p_post

在 Explorer 上進行渲染，選擇“神經網路”這個佈局，可以很清晰地看出這些紅色的文章節點，還有代表評論的邊。

feed_from_friends

附近好友的內容

我們再進一步，把地理資訊考慮進來，獲取那些在指定距離範圍內的朋友的相關內容。

這裡，我們用到了 NebulaGraph 的 GeoSpatial 地理功能，ST_Distance(home.address.geo_point, friend_addr.address.geo_point) AS distance WHERE distance < 1000000 的約束條件幫我們表達了距離的限制。

MATCH (home:address)-[:lived_in]-(feed_owner:player)-[:`follow`]-(friend:player)-[:lived_in]-(friend_addr:address)
    WHERE id(feed_owner) == "player100"
WITH feed_owner, friend, ST_Distance(home.address.geo_point, friend_addr.address.geo_point) AS distance WHERE distance < 1000000

OPTIONAL MATCH (friend:player)-[newly_commented:commented_at]->(:post)<-[:created_post]-(feed_owner:player)
    WHERE newly_commented.post_time > timestamp("2010-01-01 00:00:00")
OPTIONAL MATCH (friend:player)-[newly_created:created_post]->(po:post)
    WHERE newly_created.post_time > timestamp("2010-01-01 00:00:00")
WITH DISTINCT friend,
    collect(DISTINCT po.post.title) + collect("comment of " + dst(newly_commented))
        AS feeds WHERE size(feeds) > 0
RETURN friend.player.name, feeds
friend.player.name feeds
Marco Belinelli ["my best friend, tom", "comment of post11"]
Tony Parker ["I can swim"]
Danny Green ["comment of post1"]

這時候，從視覺化這個結果也可以看到住址，以及它們的經緯度資訊。我手動按經緯度把地址的節點在畫布上進行排列（下圖右側橙色部分），可以看到這個 feed 的主人 Tim(player100) 的住址（7，8）剛好在其他好友住址的中間位置，這些鄰近好友的相關的文章和參與評論的內容將被作為資訊流推送給 Tim：

geo_feed

時空關係追蹤

時空關係追蹤，這個圖譜應用是在公共安全、物流、疫情防控等場景下，利用圖遍歷將繁雜、凌亂的資訊充分利用起來的典型應用。當我們建立起這樣的圖譜之後，往往只需要簡單的圖查詢就可以獲得非常有用的洞察。本章節我給大家近距離講下這個應用場景。

資料集

我建立了一個虛擬資料集來構建時空關係圖譜，資料集的生成程式和拿來即用的檔案都放在了 GitHub 上，倉庫地址是：http://github.com/wey-gu/covid-track-graph-datagen。

它的資料建模如下：

data_schema

在一個全新的環境裡，僅用下面的 3 行命令就能準備好這個圖譜：

# 安裝 NebulaGraph + NebulaGraph Studio
curl -fsSL nebula-up.siwei.io/install.sh | bash -s -- v3
# 下載資料集
git clone http://github.com/wey-gu/covid-track-graph-datagen && cd covid-track-graph-datagen
# 匯入資料集
docker run --rm -ti \
    --network=nebula-net \
    -v ${PWD}/:/root \
    vesoft/nebula-importer:v3.2.0 \
    --config /root/nebula-importer-config.yaml

我們在 console 裡檢視一下資料：

~/.nebula-up/console.sh
# 進入 console 了，進到 covid_trace 圖空間（剛才建立的）
USE covid_trace;
# 執行資料統計的任務
SHOW JOB STATS

結果：

(root@nebula) [covid_trace]> SHOW STATS
+---------+------------+--------+
| Type    | Name       | Count  |
+---------+------------+--------+
| "Tag"   | "人"       | 10000  |
| "Tag"   | "地址"     | 1000   |
| "Tag"   | "城市"     | 341    |
| "Tag"   | "村鎮"     | 42950  |
| "Tag"   | "省份"     | 32     |
| "Tag"   | "聯絡方式" | 0      |
| "Tag"   | "行政區"   | 3134   |
| "Tag"   | "街道"     | 667911 |
| "Edge"  | "住址"     | 0      |
| "Edge"  | "到訪"     | 19986  |
| "Edge"  | "同住"     | 19998  |
| "Edge"  | "屬於"     | 715336 |
| "Space" | "vertices" | 725368 |
| "Space" | "edges"    | 755320 |
+---------+------------+--------+
Got 14 rows (time spent 1087/46271 us)

兩人之間的關聯

很自然，利用路徑查詢就可以了：

# 最短
FIND SHORTEST PATH FROM "p_100" TO "p_101" OVER * BIDIRECT YIELD PATH AS paths

# 所有路徑
FIND ALL PATH FROM "p_100" TO "p_101" OVER * BIDIRECT YIELD PATH AS paths | LIMIT 10

最短路徑結果：

paths
<("p_100")<-[:同住@0 {}]-("p_2136")<-[:同住@0 {}]-("p_3708")-[:到訪@0 {}]->("a_125")<-[:到訪@0 {}]-("p_101")>

所有路徑結果：

paths
<("p_100")<-[:同住@0 {}]-("p_2136")<-[:同住@0 {}]-("p_3708")-[:到訪@0 {}]->("a_125")<-[:到訪@0 {}]-("p_101")>
<("p_100")-[:到訪@0 {}]->("a_328")<-[:到訪@0 {}]-("p_6976")<-[:同住@0 {}]-("p_261")-[:到訪@0 {}]->("a_352")<-[:到訪@0 {}]-("p_101")>
<("p_100")-[:同住@0 {}]->("p_8709")-[:同住@0 {}]->("p_9315")-[:同住@0 {}]->("p_261")-[:到訪@0 {}]->("a_352")<-[:到訪@0 {}]-("p_101")>
<("p_100")-[:到訪@0 {}]->("a_328")<-[:到訪@0 {}]-("p_6311")-[:同住@0 {}]->("p_3941")-[:到訪@0 {}]->("a_345")<-[:到訪@0 {}]-("p_101")>
<("p_100")-[:到訪@0 {}]->("a_328")<-[:到訪@0 {}]-("p_5046")-[:同住@0 {}]->("p_3993")-[:到訪@0 {}]->("a_144")<-[:到訪@0 {}]-("p_101")>
<("p_100")-[:同住@0 {}]->("p_3457")-[:到訪@0 {}]->("a_199")<-[:到訪@0 {}]-("p_6771")-[:到訪@0 {}]->("a_458")<-[:到訪@0 {}]-("p_101")>
<("p_100")<-[:同住@0 {}]-("p_1462")-[:到訪@0 {}]->("a_922")<-[:到訪@0 {}]-("p_5869")-[:到訪@0 {}]->("a_345")<-[:到訪@0 {}]-("p_101")>
<("p_100")<-[:同住@0 {}]-("p_9489")-[:到訪@0 {}]->("a_985")<-[:到訪@0 {}]-("p_2733")-[:到訪@0 {}]->("a_458")<-[:到訪@0 {}]-("p_101")>
<("p_100")<-[:同住@0 {}]-("p_9489")-[:到訪@0 {}]->("a_905")<-[:到訪@0 {}]-("p_2733")-[:到訪@0 {}]->("a_458")<-[:到訪@0 {}]-("p_101")>
<("p_100")-[:到訪@0 {}]->("a_89")<-[:到訪@0 {}]-("p_1333")<-[:同住@0 {}]-("p_1683")-[:到訪@0 {}]->("a_345")<-[:到訪@0 {}]-("p_101")>

我們把所有路徑進行視覺化渲染，標記出起點、終點的兩人，並在其中查到他們的最短路徑。他們之間的千絲萬縷關係就一目瞭然了，無論是商業洞察、公共安全還是疫情防控，有了這個資訊，相應的工作都可以如虎添翼了。

find_path_two_people

當然，在真實的系統上，可能我們只需要關心兩個使用者之間的關係遠近，得出量化的評估：

FIND SHORTEST PATH FROM "p_100" TO "p_101" OVER * BIDIRECT YIELD PATH AS paths |
    YIELD collect(length($-.paths)) AS len | YIELD coalesce($-.len[0], -1) AS len

比如，下面只關心兩點之間最短路徑的長度為：4。

len
4

時空相交的人

再深入一點，我們可以用圖語義勾勒出任何帶有時間與空間資訊的模式，在圖譜中實時查詢出來。比如，找尋 id 為 p_101 的指定使用者在特定時間內有時空相交的人，這意味著那些人在 p_101 訪問某個地方的某段時間內也逗留過：

MATCH (p:人)-[`visit0`:到訪]->(`addr`:地址)<-[`visit1`:到訪]-(p1:人)
    WHERE id(p) == "p_101" AND `visit0`.`start_time` < `visit1`.`end_time` AND `visit0`.`end_time` > `visit1`.`start_time`
    RETURN paths;

我們得到了使用者每一個到訪地點，與他時空相交的人的列表。如下：

addr.地址.name collect(p1.人.name)
閔行仇路q座 255960 ["徐暢", "王佳", "曾亮", "薑桂香", "邵秀英", "韋婷婷", "陶玉", "馬坤", "黃想", "張秀芳", "顏桂芳", "張洋"]
豐都北京路J座 725701 ["陳春梅", "施婷婷", "井成", "範文", "王楠", "尚明", "薛秀珍", "宋金鳳", "楊雪", "鄧麗華", "李楊", "溫佳", "葉玉", "周明", "王桂珍", "段玉華", "金成", "黃鑫", "鄔兵", "魏柳", "王蘭英", "楊柳"]
普陀潛江路P座 210730 ["儲平", "洪紅霞", "沈玉英", "王潔", "董玉英", "鄧鳳英", "謝海燕", "樑雷", "張暢", "任玉蘭", "賈宇", "汪成", "孫琴", "紀紅梅", "王欣", "陳兵", "張成", "王東", "谷霞", "林成"]
普陀武街f座 706352 ["邢成", "張建軍", "張鑫", "戴濤", "蔡洋", "汪燕", "尹亮", "何利", "何玉", "周波", "金秀珍", "楊波", "張帥", "周柳", "馬雲", "張建華", "王麗麗", "陳麗", "萬萍"]
城東貴陽街O座 110567 ["李潔", "陳靜", "王建國", "方淑華", "古想", "漆萍", "詹桂花", "王成", "李慧", "孫娜", "馬偉", "謝傑", "王鵬", "鞠桂英", "莫桂英", "汪雷", "黃彬", "李玉梅", "祝紅梅"]

現在，我們在圖上視覺化這個結果看看：

MATCH (p:人)-[`visit0`:到訪]->(`addr`:地址)<-[`visit1`:到訪]-(p1:人)
    WHERE id(p) == "p_101" AND `visit0`.`start_time` < `visit1`.`end_time` AND `visit0`.`end_time` > `visit1`.`start_time`
RETURN paths;

結果中我們標記 p_101 為不同的圖示，再用標籤傳播演算法識別一下聚集社群，是不是一圖勝千言呢？

time_and_space

最近去過的省份

最後，我們再用簡單的查詢模式表達出一個人在給定時間內的行為路徑。比如：從一個時間點開始，到訪過的所有省份

MATCH (p:人)-[visit:到訪]->(`addr`:地址)-[:屬於*5]-(province:省份)
    WHERE id(p) == "p_101" AND visit.start_time > 1625469000
    RETURN province.省份.name, collect(addr.地址.name);

看起來他/她去過不少地方呢：

province.省份.name collect(addr.地址.name)
四川省 ["閔行仇路q座 255960"]
山東省 ["城東貴陽街O座 110567"]
雲南省 ["豐都北京路J座 725701"]
福建省 ["普陀潛江路P座 210730"]
內蒙古自治區 ["普陀武街f座 706352"]

老規矩，我們在圖上看看這個結果吧。這次，我們選擇 Dagre-LR 這個佈局渲染，結果是不是非常清晰呢？

visited_provinces

總結

社交網路作為天然的圖結構，真的非常適合用圖技術來儲存、查詢、計算、分析與視覺化去解決各式各樣的問題。NebulaGraph 強大的資料處理和視覺化能力，使得它被百家企業採用來處理社交網路問題，這其中包括：網易遊戲、微信、Line、Soul、快手和知乎等等很多行業領先的團隊。希望大家通過本章能對社交領域的圖技術應有有一個初步的認識。

謝謝你讀完本文 (///▽///)

NebulaGraph Desktop，Windows 和 macOS 使用者安裝圖資料庫的綠色通道，10s 拉起搞定海量資料的圖服務。通道傳送門：http://c.nxw.so/c0svX

想看原始碼的小夥伴可以前往 GitHub 閱讀、使用、(^з^)-☆ star 它 -> GitHub；和其他的 NebulaGraph 使用者一起交流圖資料庫技術和應用技能，留下「你的名片」一起玩耍呢~

「」