algorithm - 图论 : Calculating Clustering Coefficient

Question

我正在做一些研究，我已经到了计算图的聚类系数的地步。

根据 this paper directly related to my research :

The clustering coefficient C(p) is defined as follows. Suppose that a vertex v has k_v neighbours; then at most (k_v * (k_v-1)) / 2 edges can exist between them (this occurs when every neighbour of v is connected to every other neighbour of v). Let C_v denote the fraction of these allowable edges that actually exist. Define C as the average of C_v over all v

但是this wikipedia article on the subject says differently :

C = (number of closed triplets) / (number of connected triples)

在我看来，后者的计算成本更高。

所以我的问题是:它们是等价的吗？

需要注意的是，该论文被维基百科文章引用。

感谢您的宝贵时间。

Answer 1

两个公式不一样；它们是计算全局聚类系数的两种不同方法。

一种方法是对所有节点的聚类系数 (C_i [1]) 进行平均(这是您从 Watts 和 Strogatz 引用的方法)。但是，在 [2, p204] 中，Newman 认为这种方法不如第二种方法(您从维基百科获得的方法)好。由于 C_i 的分母 [1]，他通过指出全局聚类系数的值如何由低度数的节点支配来证明这一点。因此，在具有许多低度数节点的网络中，您最终会得到一个很大的全局聚类系数值，Newman 认为这不具有代表性。

但是，许多网络研究(或者，根据我的经验，至少有许多与在线社交网络有关的研究)似乎都使用了这种方法，因此为了能够将您的结果与他们的结果进行比较，您需要使用同样的方法。此外，Newman 提出的批评并不影响全局聚类系数比较的程度，前提是使用相同的方法来测量它们。

这两个公式不同，是在不同的时间提出的。您从 Watt 和 Strogatz 那里引用的那个比较旧，这也许就是为什么它似乎更常用的原因。 Newman 还解释说，这两个公式远不等同，不应这样使用。他说他们可以为给定的网络提供截然不同的数字，但没有解释原因。

[1] C_i =(i 的已连接邻居对数)/(i 的邻居对数)

[2] Newman, M.E.J.. 网络:介绍。牛津纽约:牛津大学出版社，2010 年。打印。

编辑:

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