I saw in this video that computing clustering coefficient of central node of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct?

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))

Edit: My answer was based on assuming the code given as a pseudo-code, rather than a concrete Python example. For Python, the data structure is a dictionary (hash map) and so finding neighbors (the in) operation will in fact be $O(1)$ on average, giving $\Theta(n^2)$ overall complexity on average for both graphs. Rare worst cases in hash maps can depend on implementation. In general for pseudo-codes, see my original answer below.

The complexity also depends on the data structure being used for storing the graph $G$. If an adjacency list is used, where for every vertex $v$ in the graph, its neighbors are stored in an array/linked list, then the above complexities are valid. Here's how:

For the central node of the star graph, there are $n-1$ neighboring vertices. Then, the pair of neighbors of this central node - the $w$ and $u$ vertices - can be selected in $\Theta(n^2)$ ways. For each such $w$, checking if $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, since each such $w$ only has $1$ neighbor - the central node $v$. This gives overall complexity of $\Theta(n^2)$.

For a clique of size $n$, every node has $\Theta(n)$ neighbors. Then, the pair of neighbors $w$ and $u$ for any node $v$ can be chosen in $\Theta(n^2)$ ways - this is the complexity of the two outer for loops. For every such $w$, checking if $u$ is its neighbor requires going through the list of $\Theta(n)$ neighbors of $w$, and so the if statement has $\Theta(n)$ complexity. This takes the overall complexity of the two nested for loops and the if loop to $\Theta(n^3)$.

However, there are other representations of the graph data structure, which give different (generally better) complexities for the same algorithm. For example, having an adjacency matrix to represent the graph means that the check for $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, even for a clique. Similarly, using a hash set instead of list/array to store neighbors would mean checking for neighbors can be done in $\Theta(1)$ on average. These are the more common representation. You could also choose an arbitrary representation where neighbors are sorted (just to demonstrate how the underlying data structure can affect algorithm complexity). In such a case, checking for neighbors will take $\Theta(\log n)$, giving overall $\Theta(n^2 \log n)$. Each has its pros and cons, and the appropriate data structure must be chosen according to your situation.

  • $\begingroup$ G stored using a dictionary. and the complexity of in operator for dictionary is theta(1). $\endgroup$ – Sajad Rastegar Dec 28 '12 at 15:47
  • $\begingroup$ I barely know python, but it seems that the variable neighbours is a list of neighbors obtained from the dictionary. And search (in) in a list is $O(n)$ according to this. $\endgroup$ – Paresh Dec 28 '12 at 15:53
  • $\begingroup$ This is a sample of graph: { 'a' : { 'b' : True, 'c' : True }, 'b' : { 'a' : True, 'c' : True }, 'c' : { 'a' : True, 'b' : True }} so we are searching in a dictionary not a list. $\endgroup$ – Sajad Rastegar Dec 28 '12 at 16:10
  • $\begingroup$ Doesn't if statement take $\theta(1)$ because its a dictionary? if it takes $\theta(1)$, we have $\theta(n^2)$ for loops and an if statement that takes $\theta(1)$ so it should $\theta(n^2)$ both for star and clique. Am i wrong? $\endgroup$ – Sajad Rastegar Dec 28 '12 at 16:49
  • 1
    $\begingroup$ Aah I see what you mean. Yes, you are correct in that case. I'll edit my answer accordingly. $\endgroup$ – Paresh Dec 28 '12 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.