机器学习

图机器学习中传统方法 - 结点特征 - 集聚系数

本文主要是介绍图机器学习中传统方法 - 结点特征 - 集聚系数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

集聚系数（clustering coefficient）

用来描述一个图中的顶点之间结集成团的程度的系数。具体来说，是一个点的邻接节点之间相互连接的程度。集聚系数分为整体，局部两种。整体集聚系数可以给出一个图中整体的集聚程度的评估，而局部集聚系数则可以测量图中的每个结点附近的集聚程度。

整体集聚系数：定义在闭点三点组之上。假设图中有一部分点是两两相连的，那么可以找出很多个“三角形”，其对应的三点两两相连，成为闭三点组。除此之外，还有开三点组，也就是三个点中只有两条边（三角形缺少一条边）。这两种三点组构成了所有的连通三点组。整体的集聚系数定义为一个图中所有闭三点组数量与所有连通三点组（开三点组数量+闭三点组数量）的总量之比。

假设图G=(V,E)，V = \{v_{1},v_{2},...,v_{n}\}表示顶点的集合，E=\{e_{ij}:(i,j)\in S\subset [1,...,n^{2}] \}表示边的集合（e_{ij}表示连接顶点v_{i}与v_{j}的边​​​​​​）。每个顶点连接的顶点有多少，可以用L(i)表示与顶点v_{i}相连的边的集合：

L(i)=\{v_{i}:e_{ij} \in E \wedge e_{ji} \in E\},L(i)中边的数量就是顶点v_{i}的度，记作k_{i}:k_{i}=\left | L(i) \right |。

C_{total}(G)表示整体集聚系数，G_{\bigtriangleup }表示图中闭三点组的个数，G_{\wedge }表示图中开三点组的个数，则

C_{total} (G)= \frac{ 3 \times G_{\bigtriangleup }}{3 \times G_{\bigtriangleup} + G_{\wedge }}

或者用k_{i}来表示：

C_{total} (G)= \frac{ 3 \times G_{\bigtriangleup }}{ \sum_{i=1}^{n} \binom{k_{i}}{2} }

从n个物品中选择k个物品，选择的顺序无所谓，那么选择的方式共有：

C(n,k) = \frac{n!}{(n-k)!k!}, 可以写作：\binom{n}{k}

局部系数：图中一个顶点v_{i}的局部集聚系数C(i)等于所有与它相连的顶点之间所连的边的数量，除以这些顶点之间可以连出的最大边数。一般来说，对应无向图，这个最大边数等于\frac{k_{i} (k_{i}-1)}{2}，对于有向图，由于每两个顶点之间可以连两条边，最大边数等于k_{i}(k_{i}-1)，这时候k_{i}表示的是指向顶点v_{i}的边与从顶点v_{i}指出去的边的总数。

在无向图中，如果一个顶点v_{i}\in V的相连的闭三角数量为\lambda_{G}(v_{i})，也就是G中所有包括了顶点v_{i}的闭三点组（三点中连有三条边）的数目；v_{i}的相连的开三角数量为T_G(v_{i})，也就是G中所有包括了顶点v_{i}，且满足两条边都与v_{i}相连的开三点组（三点中恰好连有两条边）。这是时候，无向图中顶点v_{i}的局部聚集系数：

C(i) = \frac{\lambda_{G}(v_{i})}{T_{G}(v_{i})+\lambda_{G}(v_{i})}

或 C(i) = \frac{2\left | {e_{jk}:v_{j},v_{k} \in L(i), e_{jk} \in E } \right |}{ k_{i}(k_{i-1}) }，

T_G(v_{i}) + \lambda_G(v_{i}) = \frac{1}{2} k_{i}(k_{i}-1)

有向图中局部聚集系数：

C(i) = \frac{\left | {e_{jk}:v_{j},v_{k} \in L(i), e_{jk} \in E } \right |}{ k_{i}(k_{i-1}) }

一个顶点v_{i}的局部聚集系数C(i)总是在[0,1]，C(i)越是接近1，则表示v_{i}的邻居越是抱成一团，接近完全图。C(i)越接近0，则结点v_{i}的邻接结点之间不相连，整个结构接近树状。

 

参考文献：

[1] https://zh.wikipedia.org/wiki/%E9%9B%86%E8%81%9A%E7%B3%BB%E6%95%B0

 

 

这篇关于图机器学习中传统方法 - 结点特征 - 集聚系数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航