0

我在这个视频中看到，使用以下算法计算星图中心节点的聚类系数是 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))
4

1 回答 1

2

复杂性取决于图形的密度和in谓词的效率。

一个完整图上的简单实现显然是O(n^3)：两个嵌套循环和一个in谓词，每个都在线性时间内天真地运行。如果您将链接保留在哈希图中（而不是密集矩阵表示！），那么运行时仅O(n^2)适用于单个节点。但通常，这样的算法适用于每个节点，为其添加另一个因素n。

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

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

于 2012-12-28T12:38:10.357 回答