定义
Triangle Count（三角形计数）用来确定图中每个节点的跟其1-hop的点直接能够形成三角的个数。三角形是由三个节点组成的集合，三个节点中的每个节点与其他两个节点都有直接相连的关系。可以通过全局运行三角形计数算法，评估整个数据集的整体聚合情况。具有大量三角形的图网络更有可能表现出小世界性（small-world）。
Clustering Coefficient（聚类系数）用来度量一个图的聚类程度，聚类系数分为局部聚类系数（Local Clustering Coefficient）和全局聚类系数（Global Clustering Coefficient）。一个节点的局部聚类系数表明其邻节点之间也互相连接的程度。局部聚类系数的计算使用需要使用两倍的三角形计数作为分子，使用三元组计数作为分母，来度量出现的三角形数与可能出现的三角形数，某个节点的聚类系数越大，表明这个节点周围的节点之间有关系的程度越高，表明这个群组聚集度越高，最高值为1，表明一个节点周围的所有点之间都有关系。
计算公式
三角形计数的计算公式非常简单，即一个顶点1-hop的邻居节点之间存在的边个数。
其中表示节点
周围任意两个邻居节点之间的关系数。
局部聚类系数的计算公式依赖三角形计数。其计算公式如下：
其中
表示节点
周围任意两个邻居节点之间的关系数，
表示顶点
的度。
全局聚类系数主要是跟三元组相关，计算公式如下：
其中
图 1
如上图（a）所示，，如上图（b）所示，
。
图 2
如上图（c）所示，，如上图（d）所示，
。
至于GCC，由于计算量比较大，我选择一个简单的图，如下图所示。其中
图 3
使用场景
Triangle Count和Clustering Coefficient主要用来评估特定网络的内聚性和节点的聚合度，可以用来进行社交网络分析和欺诈分析。
网友评论