algorithm - 计算聚类系数

Question

我在 this 中看到使用以下算法计算星图中心节点的聚类系数的视频是 theta(n^2)，对于 clique，它是 theta(n^3)。对吗？

def clustering_coefficient(G,v):
    neighbors = G[v].keys()
    if len(neighbors) == 1: return 0.0
    links = 0.0
    for w in neighbors:
        for u in neighbors:
            if u in G[w]: links += 0.5
    return 2.0*links/(len(neighbors)*(len(neighbors)-1))

Answer 1

复杂度取决于图形的密度，以及 in 谓词的效率。

一个完整图的简单实现显然是 O(n^3):两个嵌套循环和一个 in 谓词，每个都在线性时间内简单地运行。如果您将链接保存在 HashMap 中(而不是密集矩阵表示形式!)，那么运行时间仅为 O(n^2) - 对于单个节点。但通常情况下，这样的算法应用于每个节点，并为其添加另一个 n 因子。

如果您的图表不完整(并且您使用更高效的 in 谓词)，事情会变得更快。假设每个节点都有 sqrt(n) 邻居，则算法的复杂度将为 O(sqrt(n)^2)*n(对于所有节点，即)，这可能是他们的 O(n^2) 结果。

假设每个节点都有正好 两个邻居。然后复杂度可以很容易地降低到 O(1) * n。哦，如果每个节点都有 0 个邻居，那就更简单了。