algorithm - Efficiently building a thresholded similarity graph -

a thresholded similarity graph set of nodes , edges, nodes connected edge iff similarity between 2 nodes higher given threshold.

building such graph of n nodes easy: create n x n matrix m, place each node in both column , rows, fill each cell c[i,j] similarity between node i , node j iff result higher given threshold. complexity here o(n^2).

this complexity can improved not computing c[i, j] if i == j, or if c[j, i] has been computed (assuming similarity between nodes i , j same similarity between nodes j , i). however, complexity being o(n * (n - 1) / 2) still equivalent o(n^2).

given similarity function used either metric or cosine similarity (although info may not relevant), there way compute such thresholded similarity graph complexity better o(n^2)?

thanks, romain.

i think can complexity o(m) m number of edges. if edge between , j doesn't exist, don't have put result in new graph. matrix representation, can achieve o(m), if use sparse matrix representation, or adjacency list.

of course in (not exceptionnal) cases yours, m = n^2.