Default algorithm for clustering

Usage
1

Dear all,
I have found IGraph very useful in my studies. However, now I am stuck with a simple question.

The default ig.Graph.clusters(G) returns a list of lists with vertexes by their cluster affiliation.
It works alright.

But what method does it use to clusterize the vertices by default?

It is crucial for me to know it as I am planning to do some studies related to computational performance and would like to have some analytical estimations of the algorithm’s complexity.

Thank you very much!

P.S. I’ve searched through the documentation for hours and found no mentions of the “default method” for the detection of clusters. I’ve found a lot of tutorials for using particular community detection methods, but I feel that default works just fine plus clusters in my system are completely separated with no edges between them (percolation system). Therefore, I don’t feel as there would be any difference in the results while using different standard algorithms.

2

clusters() is simply an alias to “connected components” in the Python interface because this is how the underlying function is named in the C library. If you are interested in community detection methods, use one of the methods starting with community_; an exhaustive list starts here in the documentation.

1 Like
3

Dear Tamas, thank you for the answer.
Could you please also mention what algorithm is used to obtain the “connected components”? It’s not the community detection, but it’s not “just appearing” inside IGraph.

I’ve just seen it has time complexity: O(|V|+|E|), |V| and |E| are the number of vertices and edges in the graph. But may be there is a specific name for this algo?

4

igraph uses the standard breadth first search algorithm to find connected components.

1 Like