图论:计算聚类系数

Question

我正在做一些研究,我已经达到了计算图形的聚类系数的程度.

根据这篇论文直接与我的研究有关:

聚类系数C(p)的定义如下.假设顶点v具有k _v个邻居; 那么它们之间最多可以存在(k _v*(k _v -1))/ 2个边缘(这发生在v的每个邻居连接到v的每个其他邻居时).设C _v 表示实际存在的这些允许边的分数.将C作为所有v 的C _v的平均值

但这篇关于这个主题的维基百科文章说的不同:

C =(闭合三元组的数量)/(连接的三元组的数量)

在我看来,后者的计算成本更高.

所以我的问题是:它们是否相同？

应该注意的是,该论文被维基百科文章引用.

谢谢你的时间.

Answer 1

这两个公式不一样; 它们是可以计算全局聚类系数的两种不同方式.

一种方法是平均所有节点的聚类系数(C_i [1])(这是您从Watts和Strogatz引用的方法).然而,在[2,p204]中,纽曼认为这种方法不如第二种方法(你从维基百科得到的方法)更好.他指出,由于C_i的分母[1],全局聚类系数的值如何由低度节点支配.因此,在具有许多低度节点的网络中,您最终得到全局聚类系数的大值,纽曼认为这将是不具代表性的.

然而,许多网络研究(或者,根据我的经验,至少许多与在线社交网络有关的研究)似乎都使用了这种方法,所以为了能够将你的结果与他们的结果进行比较,你需要使用相同的方法.此外,纽曼提出的批评并不影响对全球聚类系数进行比较的程度,只要采用相同的方法进行测量即可.

这两个公式是不同的,并在不同的时刻提出.你从Watt和Strogatz引用的那个更老,这也许是为什么它似乎更常用.纽曼还解释说,这两个公式远非等价,不应该这样使用.他说他们可以为给定的网络提供截然不同的数字,但是没有解释原因.

[1] = C_I(对邻居的数目我被连接)/(对邻居的数目我)

[2]纽曼,MEJ.网络:介绍.牛津纽约:牛津大学出版社,2010年.打印.

编辑:

我在这里包括一系列相同ER随机图的计算.您可以看到这两种方法如何给出不同的结果,即使对于无向图也是如此.(使用Mathematica完成)

Answer 2

我认为它们是等价的.您链接到的维基页面提供了一个证据,证明三元组公式等于计算局部聚类系数时可能的边缘公式的分数,即仅在顶点计算.从那里看起来你只需要表明这一点

sum_v lambda(v)/tau(v) = 3 x # triangles / # connected triples

其中lambda(v)是包含v的三角形的数量,并且tau(v)是连接的三元组的数量,其中v是中间顶点,即与其他2个边缘中的每一个相邻.

现在每个三角形在LHS的分子中计数三次.但是,每个连接的三元组仅对LHS的中间顶点计数一次,因此分母是相同的.