0

このビデオで、次のアルゴリズムを使用してスターグラフの中央ノードのクラスタリング係数を計算するのはtheta（n ^ 2）であり、クリークの場合は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)とおりです。2つのネストされたループと1つのin述語で、それぞれが線形時間で単純に実行されます。リンクをハッシュマップに保持する場合（密行列表現ではありません！）、実行時間はO(n^2)単一ノードの場合のみです。しかし、通常、このようなアルゴリズムはノードごとに適用され、ノードに別の要素が追加されますn。

グラフが完全でない場合（そしてより効率的なin述語を使用する場合）、物事ははるかに速くなります。sqrt(n)すべてのノードに隣接ノードがあると仮定すると、アルゴリズムの複雑さはO(sqrt(n)^2)*n（つまり、すべてのノードに対して）なります。これはおそらくそれらのO(n^2)結果です。

すべてのノードに正確に2つの隣接ノードがあると仮定します。そうすれば、複雑さを簡単にに下げることができますO(1) * n。ああ、そしてすべてのノードに0のネイバーがある場合、それはさらに簡単です。

于 2012-12-28T12:38:10.357 に答える