十亿加节点局部聚类系数能跑出来么？

前面一篇文章，有朋友留言：十亿加节点局部聚类系数能跑出来么？

本期，主要学习和解答这个问题。

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 pair;

};

例如下图 构成的triplet是封闭的， 构成的triplet是开放的

图一：Triplet示例

全局的Clustering coefficient的计算方法：

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

以上图为例:

closed triplet =，，

all triplet = ，，，, ，，,

number of closed triplet = 3

number of triplet = 8

number of triplet / number of triplet = 3/8

3、局部聚类系数

我们先回顾2个离散数学里面关于图论的概念：

1）简单图（不含平行边和环）G=中，若每一对结点间都有边相连，则称该图为完全图。

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 ),(U1: USER ),

(U2: USER ),(U3: USER ),

(U4: USER ),(U5: USER ),

(U6: USER ),

(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 )--(b)

WITH a, count(DISTINCT b) AS n

MATCH (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

154907

head edges.csv

154907,1

154907,2

154907,3

154907,4

154907,5

导入到neo4j中：

LOAD CSV FROM "file:///nodes.csv" AS line

MERGE (n:DoubanUser )

return n

LOAD CSV FROM "file:///edges.csv" AS line

match (from:DoubanUser ),(to:DoubanUser )

merge (from)-[:KNOWS]->(to)

图五：豆瓣局部社交网络图

Cypher语句：

MATCH (a )--(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) > 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