Count clusters in a correlation matrix

Question

You threshold a correlation matrix so that linked[i][j] = 1 when assets i and j are "co-moving" (correlation above your cutoff) and 0 otherwise. The matrix is symmetric with a 1 on the diagonal. Two assets belong to the same cluster if they are linked directly or through a chain of linked assets.

linked = [[1, 1, 0],
          [1, 1, 0],
          [0, 0, 1]]
-> 2      # {0, 1} and {2}

Return the number of clusters. Aim for $O(n^2)$ .

Accepted Answer

This is the islands problem with a different board. Each asset is a node, and the row linked[i] lists its neighbors. Scan assets; each time you meet an unvisited one you have found a new cluster, so increment the count and flood outward, marking everything reachable. On the example, flooding from asset 0 pulls in asset 1 (they are linked), leaving asset 2 to start the second cluster: two clusters. Time O(n^2): for each of the n assets we scan its whole row once. Space O(n) for the visited flags. If the matrix is sparse and stored as adjacency lists instead, this drops to O(n + E). Takeaway. "…

Count clusters in a correlation matrix

Your answer

More Coding questions