图计算之聚类系数算法
图计算的框架简单介绍完后, 可以跟着编写某个具体的图算法来具体熟悉一下图计算本身, 除了之前最典型的 PageRank 作为代表, 今天来看看聚类相关的代表算法之一 — 聚类系数 (Clustering Coefficient)
0x00. 前言
大部分的图算法的上文都有两个方面, 一个是这个图算法是什么意思, 另一个是这个算法对应在图论中的数学定义 / 公式, 为了方便理解, 一般侧重前者, 对数学定义 / 抽象给出参考链接感兴趣可以再细究. (图论可从 wiki 里了解一下)
然后 Neo4j
有出一本图算法的介绍的书, 觉得对入门图计算学习还是有很大帮助的, 网上很多资料也是从这摘取拼凑的, 建议直接阅读官方 PDF 版本

另外, 我自己归纳画了个简图, 合并简化了一些不常用的算法, 大家也可以基于 md
源码自行修改调整.
graph LR a(Graph Algorithm)-->b(Path - 路径类)-->b1(ShortestPath - 最短路径) b-->b2(MST - 最小生成树) b-->b3(CycleDetection - 环路检测) a(Graph Algorithm)-->c(Community - 社群/聚类)-->c1(ConnectedComponents - 连通分量) c-->c2(LabelPropagation - 标签传播) c-->c3(Louvain - 社群发现) c-->c4(SSC/WCC - 强/弱连通分量) c-->c5(TriangleCount - 三角计数) c-->c6(ClusteringCoefficient - 聚集系数) a(Graph Algorithm)-->d(Centrality - 中心性)-->d1(PageRank - ) d-->d2(Betweenness/Closeness Centrality - 中介/紧密中心性) a(Graph Algorithm)-->e(Classification - 分类)-->e1 a(Graph Algorithm)-->f(GNN/ML - 炼金)-->f1(RandomWalk - 随机游走) f-->f2(Node2Vector - ) a(Graph Algorithm)-->g(Similarity - 相似性)-->g1(余弦/Jaccard/Pearson 相似性等)
Greate trend…….
A. 基本概念
聚类系数 (又名聚集系数, 集聚系数), 简单说是表示 Graph 中顶点(Vertices) 聚集程度的一个指标
它另外从图算法的分类中, 聚集系数算属于聚类算法, 另外它可认为是 “三角计数” 的加强版, 实际应用中具有类似的含义, 不过要注意的是不同于三角计数的定义很明确, 就是统计一个点附近有多少个与其相连组成的三角形, 聚类系数的计算公式有多种变化, 这里我们选取图计算框架常用的计算方式/ Wiki 中的来谈.
B. 数学定义
图论原始定义中有一些比较拗口学究的名词说法, 给普通人理解算法本身增加了门槛, 这里我在不影响正确性的前提下, 会对原数学定义 / 名词做一个简单转换和说明, 比如把字母换成更好理解记忆的版本, 详细的形式化证明和各种原名称可查阅原始 paper.
1. 局部聚类 (子图)
首先局部聚类的计算方式和全局有区别, 它更为简洁直接, 以某个点 V 出发, 分母是当前点的出边数, 分子是
对于一个节点来说,紧密性中心性是节点到所有其他节点的最小距离的和的倒数 (1/)
C(v) = 2Tv / Dv(Dv - 1), 其中v 代表当前出发的顶点, Tv (Triangle) 代表此点的三角△计数和, Dv (Degree) 代表当前点的出边数. 也就是如果已知当前点 V 的三角计数结果和它的出度, 算它的聚类系数就是 O(1)
的操作了.
基本的公式介绍就说到这足矣, 详细的算法示例见后文算法核心. (思考: 聚类系数为何是两倍三角数 ÷ 近似出边的平方呢? A: 它是由原始公式化简得来的)
2. 全局聚类 (全图)
简单说这是统计某整个 Graph 中的密集/聚集性, 比如最典型的判断一个图是稠密还是稀疏图, 这就是一个参考依据, 根据计算结果得出的系数, 越大代表图中点分布越稠密, 越低代表图中点分布越稀疏/离散, 它有两种计算的方式:
计算图中每个点的聚类系数, 然后取平均值则视为全图的聚类系数 (又称做平均聚集系数, 少见)
计算图中的闭环, 和开环/所有三角形的数相除 ==>
C = 闭环三角形个数 / 所有三角形个数
(常见)
这里闭环和开环如何来定义区分呢? 简单说闭三角形就是三边齐全, 开三角形就是缺了1条边的情况, 如下图简单所示:
graph LR subgraph Open Triangle a1(a)-->b1(b) a1-->c1(c)-.缺失.->b1 end subgraph Closed Triangle a-->b a-->c--连通-->b end
另外要注意的是, 从图中我们需要注意有个比较关键的地方, 就是如何计算三角形, 我们实际的图都是基于有向图来创建, 那么有 3 种判定方式:
- 三点之间任意有边相连通, 既认为构成一个三角形 (常用)
- 三点之间必须有序首尾相连
a—>b—>c—>a
认定为三角形 - 三点之间必须双双互联(双向边), 才认定三角形
最后, 聚集系数显然是一个 “局部/全局” 的除法, 当结果为1, 则说明图中每个点之间都是相连的, 结果为 0 说明图中点完全离散, 没有三角/连通性.
0x01. 算法核心
参考 Graph Algorithm 书中 Chapter 6.2 中举的具体例子, 还挺直观易懂的, 给出下面 4 个图, 分别计算它们的三角数和聚集度:
(以上都是无向图) 最左侧的是代表的是最离散的形式, U 顶点的所有出边间没有任何联系么; 最右侧代表是最密集的方式, U 顶点周围的点边完全关联, 来看看聚集系数计算方式:
首先以图1(最左)为例, C = 0个三角形 / 5条出边
= 0, 然后
在实际的属性图中, 基本都是有向图, 那么聚集系数的算法有和区别呢? 最关键还是在于闭环三角形的判断是否有差异, 也就是说当三个点互相有连接时, 有两类判断:
- 仅允许形成环路, 满足
A<-->B<-—>C<-->A
才能算为一个闭环三角 - 只要 A, B, C 三点相互有边连接, 即使没有形成环路, 也认为是闭环三角
(麻烦引用此图的同学, 明确在文中或文尾注明原图出处, 至少请勿在图上打上自己的水印….)
0x02. 具体实现
下面来到正式开发的环节, HugeGraph 里的图计算框架沿用经典的 MR / Pregel 里的设计, 新增任何算法, 都有核心的:
- 输入: 当前算法需要什么输入 (通常是读取全图的点边信息)
- 计算 (core): 当前算法拿到了每个点边之后如何计算
- Woker 端 (必选): 这里定义每个顶点要做的主要逻辑, 比如计算它的三角形个数
- Master 端 (可选): 这里之所以可选也很好理解, 如果我们只需要计算全图每一个点的三角形, 那无需汇聚过程, 就不用编写逻辑, 如果我们需要统计全图或者某个 Label 点的三角形个数, 就需要 Worker 统计后汇聚到 Master 进行汇总.
- 输出: 计算完成后是否需要汇聚, 是否需要回写图数据库, 具体输出格式/位置等.
1. Worker 计算逻辑
定义一个算法, 实现核心的 Computation
接口, 它有2个最核心的方法需要实现:
compute0(ComputationContext c, Vertex v)
: 每个顶点都会执行的第 1 次计算步骤, 这个阶段没有消息分发, 方法只执行一次 (所有点都会被标记为 active)compute(ComputationContext c, Vertex v, Iterator msg)
: 只计算标记为 active 的顶点, 是编写核心计算过程的地方, 每轮迭代都会重复执行, 通过迭代器的变化进行消息接收 & 传递.
如果某个算法无需迭代, 直接在第一次初始化计算的时候就可以完结, 那自然就不需要 compute
的编写, 然后还有 name 和 category 的方法需要实现, 这个就是传一个名字和分类标识当前算法, 就不单独说了. 另外有几个可选默认函数: (入参都是 WokerContext
)
- init: 算法初始化方法, 类似 MR 中的 init, 可以把一些初始化做的工作放进来
- beforeSuperStep: 在每个超级步开始前做的操作,
- afterSuperStep:
- close: 算法结束方法, 类似 MR 里的 close, 在所有 superstep 结束后执行1次, 可以做一些收尾操作
下面说一下计算接口里的核心参数 –> ComputationContext 提供的主要方法:
- 提供 sendMessage/sendMessages 相关方法, 给指定的顶点 / 邻接顶点 / 全部顶点发送(带条件过滤)的消息, 接收端会在下一个超级步中收到请求
- 提供方法返回图中的总顶点/边的数目 (这是谁返回的? master 么)
- 提供 superstep 方法返回当前的 superstep 轮数(编号), 从 0 开始 (第1轮的编号是0)
- 提供 combiner 方法返回算法的消息合并器, 用于合并一个顶点消息, 在有
Reduce
逻辑的算法里更好理解
n. 测试用例
首先在 computer-test
对应的算法包下创建对应的算法测试类, 例如 PageRankTest
, 然后编写相关逻辑, 最后在 AlgorithmTestSuite
中添加对应的测试类名, 这样启动测试时就会带入运行.
这里就先放一下核心的实现代码, 在有三角计数的基础上也容易实现:
1 |
|
上面就是计算的主逻辑, 为了简单实现, 可以直接在输出时使用原本的结果做一个 O(1)
的计算即可:
1 |
|
0x03. 运行算法
简单写了个算法 demo 之后, 如何运行它呢? 在已有 GraphServer + Etcd + K8s 的基本环境之后, 先尝试来运行一下单元测试, 它里面有最简单的环境模拟, 下面以长江的 twitter-2010 近14亿数据为例, 其他可自行调整:
1 | apiVersion: hugegraph.baidu.com/v1 |
其他文档在 wiki, 日后转移
0x04. 应用场景
聚类系数在学术上的应用定义可以参考 Wiki 的 Small-World-Network, 基于经典的社交 6度分隔网络为起点, 延伸来做复杂分析, 引入了过多其他的图论概念, 这里不详细描述, 感兴趣可自行了解.
聚类系数在实际生产环境应用和三角计数比较相似(通常是结合选一个), 全图聚类系数可以用于判断图的稀疏, 稠密, 用得不多, 更多的是用于局部范围来分析某个点/子图的紧密度 / 关联性, 下面用一个简单和一个具体的例子来一起了解聚类系数的用法
1. 社交关系 (简单)
首先以 QQ/Wechat/Weibo 这类大家耳熟能详的社交关系为例, 至少有两个使用场景:
推荐好友/文章 / 动态等
找出“僵尸”号, 黑灰产号加以定时清理
先算出 QQ 全图的聚类系数, 比如是
0.2
数据清洗, 按照各类用户标签(活跃度, 在线时间, 输入字数, 性别, 年龄段) 构建几个典型的子图, 算出聚类系数, 例
0.5
遍历疑似黑号的清单, 算出聚类系数, 与全图 & 分类子图做对比, 同时满足大量好友 + CC远低于平均值, 认定“僵尸”号
如何实现呢, 简单的说, 通过三角计数可以获取某个人(账户)常联系的好友圈,
2. 电信实时反欺诈中的应用 (具体)
比如典型的例子就是以前 TigerGraph 在 slides 中曾举例用于 在“AI标记电信号码中的诈骗号码” 中的 case:
本质就是区分普通电话, 和诈骗电话的行为习惯, 然后加以打分标记, 超过阈值则标记为可疑/诈骗
首先, 普通电话和诈骗电话有个最明显的区别,
- 普通电话呼入多, 呼出很少
- 诈骗电话呼出很多, 呼入很少
上述的判断方式简单但是比较粗, 会误伤到比如客服人员, 外卖/快递小哥, 这类服务人员, 它也是 AI 训练里常说的噪点数据, 那么利用图算法之后如何大幅减少这类小比例的特例呢? 我们就需进一步分析两类电话的呼出子图特征:
正常电话: 它通常有一个比较固定的电话拨出圈, 比如
小明 —> 父母
+小明 —> 妹妹
+妹妹—>父母
, 从而会在局部构成数个(三角/多角)的环型子图. 用聚集系数 / 三角计数来计算, 它应该具有一定的稠密度 / 三角数诈骗电话: 因为诈骗电话一般为了隐匿都不会真实使用, 它的拨出会非常离散, 很难在多个拨出之间形成稳定密集环状, 那么它的聚集系数/三角数一般就会很低.
那么上面的案例, 就是典型的简单易理解, 相比直接从原始通话数据进行训练存在噪音和误伤的情况, 运用了聚类图算法之后, 从图上进行预处理过滤后, 达到更好的训练效果的代表.
0x05. 性能实测
大数据量下性能测试
数据在 wiki, 日后转移
0x06. 后续优化
复用三角计数核心, 只需要在输出时计算即可, 后续可以先算三角计数后, 直接计算聚集系数 (短期内无需重新加载数据)
参考资料:
- Graph Theory - Wikipedia
- Cluster Coefficient - Wikipedie
- Graph Algorithm - Chapter6.2 Triangle Count and Clustering Coefficient - Neo4j/ORelly
- 图算法整体概览 - ZhiHu
- Neo4j-CC-Test
- Graph Algorithm CC - TigerGraph Doc v3.2
- Algorithm Tutorial for TigerGraph - Beader book
- AI in Graph Computing - TigerGraph Slide (link miss:)