直答間 | 十億加節點局部聚類係數能跑出來么？

05-19

來自專欄圖資料庫雜談

前面一篇文章，有朋友留言：十億加節點局部聚類係數能跑出來么？

本期，主要學習和解答這個問題。

1、聚類係數

聚類係數（Clustering coefficient）是表示一個圖中節點聚集程度的係數。

定義有兩種，全局的和局部的（局部的聚類係數中又包含一個平均聚類係數）。

2、全局聚類係數

全局聚類敘述的演算法基於Triplet。

Triplet分為開放的（open triplet）和封閉的（closed triplet）兩種。如果三個節點之間有2條無向邊，則稱為Open triplet；如果存在3條無向邊，則為Close triplet。需要特別注意的是：一個三角形，包含3個closed triplet.

可以用下面結構定義一個triplet

struct triplet { int key; set<int> pair;};

例如下圖 {1, (2,3) } 構成的triplet是封閉的，{3, (4,5) } 構成的triplet是開放的

圖一：Triplet示例

全局的Clustering coefficient的計算方法：

Clustering coefficient(global) = number of closed triplet / number of triplet(closed+open)

以上圖為例:

closed triplet ={1, (2,3) }，{2, (1,3) }，{3, (1,2) }

all triplet = {1, (2,3) }，{2, (1,3) }，{3, (1,2) }，{3, (1,4) }, {3, (1,5) }，{3, (2,4) }，{3, (2,5) }, {3, (4,5) }

number of closed triplet = 3

number of triplet = 8

number of triplet / number of triplet = 3/8

3、局部聚類係數

我們先回顧2個離散數學裡面關於圖論的概念：

1）簡單圖（不含平行邊和環）G=<V,E>中，若每一對結點間都有邊相連，則稱該圖為完全圖。

2）有n個節點的無向完全圖的邊數為n*(n-1)/2。

局部的Clustering coefficient的計算方法：

局部計算是面向節點的，對於節點vi，找出其直接鄰居節點集合Ni，計算Ni構成的網路中的邊數K，除以Ni集合可能的邊數|Ni|*（|Ni|-1）/2。

圖二：Triplet示例（同圖一）

如上圖，局部聚類係數計算為：

1節點的鄰居節點（2,3），他們之間構成的邊有1條，可能構成的邊1條，因此1/1=1; 按照公式為：1/(2*1/2)=1.

2節點的鄰居節點（1,3），他們之間構成的邊有1條，可能構成的邊1條，因此1/1=1; 按照公式為：1/(2*1/2)=1.

3節點的鄰居節點（1,2,4,5），他們之間構成的邊有1條，可能構成的邊(4*3)/2條，因此1/6=1/6; 按照公式為：1/(4*3/2)=1/6 .

4節點的鄰居節點（3），他們之間構成的邊有0條，可能構成的邊0條，因此0; 按照公式為：0/(1*0/2)=0 .

5節點的鄰居節點（3），他們之間構成的邊有0條，可能構成的邊0條，因此0; 按照公式為：0/(1*0/2)=0 .

4、平均聚類係數

平均聚類係數，比較好理解，定義為：

n個節點的局部聚類係數的均值。

上例，5個節點平均 Clustering coefficient = (1+1+1/6)/5=13/30

5、neo4j中的聚類係數計算

5.1、創建一個基礎的社交網路圖

Cypher語句： CREATE (U0: USER {name: "0"}),(U1: USER {name: "1"}), (U2: USER {name: "2"}),(U3: USER {name: "3"}), (U4: USER {name: "4"}),(U5: USER {name: "5"}), (U6: USER {name: "6"}), (U0)-[:KNOWS]->(U1),(U0)-[:KNOWS]->(U2), (U0)-[:KNOWS]->(U3),(U0)-[:KNOWS]->(U4), (U1)-[:KNOWS]->(U5),(U1)-[:KNOWS]->(U6), (U2)-[:KNOWS]->(U3)

圖三：簡單社交網路示例圖

5.2、計算局部聚類係數

我們以計算節點0的局部聚類係數為例。關聯節點4個（1、2、3、4），組成的邊只有1條（2-3），所以局部聚類係數為1/6。

Cypher語句：MATCH (a {name: "0"})--(b)WITH a, count(DISTINCT b) AS nMATCH (a)--()-[r]-()--(a)RETURN n, count(DISTINCT r) AS r

圖四：局部聚類係數的計算

6、豆瓣數據集的驗證

Number of Nodes: 154,907

Number of Edges: 654,188

很打臉，nodes.csv的數據集導入了將近一個小時還沒導完

（本機，MAC MEM 8G），所以最終只選擇了一部分數據集來做驗證。

head nodes.csv

154907123456

head edges.csv

154907,1154907,2154907,3154907,4154907,5

導入到neo4j中：

LOAD CSV FROM "file:///nodes.csv" AS line MERGE (n:DoubanUser {id: toInteger(line[0])})return nLOAD CSV FROM "file:///edges.csv" AS linematch (from:DoubanUser {id: toInteger(line[0])}),(to:DoubanUser {id: toInteger(line[1])})merge (from)-[:KNOWS]->(to)

圖五：豆瓣局部社交網路圖

查詢局部聚類係數

Cypher語句： MATCH (a {id: 154907})--(b)WITH a, count(DISTINCT b) AS nMATCH (a)--()-[r]-()--(a) RETURN n, count(DISTINCT r) AS r

圖六：豆瓣數據局部聚類係數計算

七、結論

所以，對於問題『十億加節點局部聚類係數能跑出來么？』我們的回答是肯定的。計算方法已經給出，但是具體實現還需要提問的朋友落實到自己的業務場景去實際操作下。

友情提示：

1、Neo4j單機版數據容量有限，企業版支持集群。

2、也可以使用其他分散式的圖資料庫，例如JanusGraph來嘗試。

參考

1) https://blog.csdn.net/pennyliang/article/details/6838956

2) http://en.wikipedia.org/wiki/Clustering_coefficient

3) <<Complex Network>> 3.2 properties of real-world networks p25

4) https://baike.baidu.com/item/%E8%81%9A%E7%B1%BB%E7%B3%BB%E6%95%B0/968918?fr=aladdin

5) https://neo4j.com/graphgist/calculating-the-clustering-coefficient-of-a-friend-network