[igraph] Time complexity comparison between Ward Clustering and fast greedy

[杨扬]

Hello Everyone I am studying the time complexity of different clustering algorithms, and the fast greedy algorithm is claimed to be very fast. That is, for n vertices, the time complexity is O(m d logn),m is the number of edges and d is the depth of dendrogram, and for a sparse and hierarchical matrix d ∼log n and m ∼ n so the complexity is O(n log2 n). There are a lot of papers analyzing time complexity of Ward method, and the results are usually O(n3) for worst cases and O(n2 logn) or O(n2) for best cases. But what is the actual complexity of the 2 algorithms? In my understanding,  depth of dendrogram is the number of joins. When applying the fast greedy to a 39*39 non-sparse matrix there are 39 joins, that is d=39, and there are 39*(39-1)/2 edges, that is m=39*(39-1)/2. Let n=39, so the time complexity is O(n*n*(n-1)* logn /2), which is better than (n3), but the practical running time of fast greedy is  much shorter than Ward method for a same 39*39 non-sparse matrix( 0.000718 sec vs 0.080318,almost 1:30). The theoretical ratio when n=39 should be 1:3, instead of 1:30. So what is the key to the results and what is the real time complexity of fast greedy and Ward method? Thank you.