概述
局部聚集系数(Local Clustering Coefficient)是指将一个点的所有邻居配对后,邻居对有边相连的概率。
局部聚集系数用来考察节点自我中心网络的紧密程度。例如,在社交关系网中,可以体现一个人的朋友之间彼此认识的程度,帮助区分社交群体类型,如亲友、社团、代理等。
基本概念
自我中心网络
自我中心网络(Ego Network)是指由一个中心节点(Ego)及其所有一步邻居(Alter)构成的子图。关于子图的介绍,请阅读子图拼接算法。
指定上图的红色节点为中心节点时,其自我中心网络为包括红色节点、绿色节点以及所有红色边。
局部聚集系数
局部聚集系数是用一个节点的有边相连的邻居对的数量除以该节点所有邻居对的数量:
上式中 x
表示待计算的节点,i
、j
表示 x
的自我中心网络中互异的任意两个邻居;i
、j
之间有边相连时 δ(i,j)
为 1,否则为 0;k
为 x
的自我中心网络中的节点数量,(k-1)(k-2)/2
为 i
、j
节点对的数量。
上面红色节点的自我中心网络中,所有只有黄绿、蓝紫邻居节点对有边,因此红色节点的局部聚集系数为 2 / 6 = 0.3333
。
特殊处理
孤点、不连通图
孤点不与任何其它节点相连,其局部聚集系数为 0,孤点也不会参与到任何局部聚集系数的计算中。
一个连通分量内的节点一定不会参与其它连通分量内节点的局部聚集系数的计算中。
自环边
节点的自环边不会增加节点的邻居数。
有向边
对于有向边,本算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面包含 7 位用户的社交网络图为例(已忽略边的方向),运行局部聚集系数算法:
计算结果:计算用户 Lee(UUID = 1)和 Choi(UUID = 2)的局部聚集系数,根据算法执行方式,返回 _id
、centrality
两列或 _uuid
、centrality
两列
_uuid | _id | centrality |
---|---|---|
1 | Lee | 0.26666668 |
2 | Choi | 1.0000000 |
算法统计值:无
命令和参数配置
- 命令:
algo(clustering_coefficient)
params()
参数配置项如下:
名称 |
类型 | 默认值 |
规范 | 描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 待计算节点的 ID 或 UUID;忽略表示计算全部点 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC/DESC,大小写不敏感 | 对返回结果进行排序;忽略表示不排序 |
示例:计算节点 UUID = 1,2,3 的局部聚集系数
algo(clustering_coefficient).params({
uuids: [1,2,3]
}) as lcc
return lcc
算法执行
任务回写
1. 文件回写
配置项 |
各列数据 |
---|---|
filename | _id ,centrality |
示例:计算用户 Lee 和 Choi 的局部聚集系数,将算法结果回写至名为 centrality 的文件
algo(clustering_coefficient).params({
ids: ["Lee", "Choi"]
}).write({
file:{
filename: "centrality"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | centrality |
点属性 | float |
示例:计算用户 Lee 和 Choi 的局部聚集系数,将算法结果回写至名为 lcc 的点属性
algo(clustering_coefficient).params({
ids: ["Lee", "Choi"]
}).write({
db:{
property: "lcc"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其局部聚集系数 | _uuid , centrality |
示例:计算所有点的局部聚集系数,将算法结果定义为别名 results 并返回
algo(clustering_coefficient).params() as results
return results
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其局部聚集系数 | _uuid , centrality |
示例:计算所有点的局部聚集系数,将算法结果定义为别名,返回所有局部聚集系数非 0 的结果
algo(clustering_coefficient).params().stream() as results
where results.centrality > 0
return results
实时统计
算法无统计值。