Clustering algorithm for unweighted graphs

问题:

I am having unweighted and undirected graph as my network which is basically the network of proteins.I want to cluster this graph and divide this graph in to disjoint clusters. Can any 1 suggest clustering algorithms which i can apply on the biological network which is unweighted and undirected graph.

回答1:

Several graph partitioning algorithms exist, they use different paradigm to tackle the same problem.

The most common is the Louvain's method optimizing Newman's modularity. In python using Networkx as graph library you can use community to partition your graph.

The fastest graph partitioning uses Metis. It is based hierarchical graph coarsening.

You also have N-cut originally designed to segment images.

Finally, you can partition graphs using stochastic block-model techniques. A very good python implementation of Louvain and several block-model techniques can be found in Graph-tool.

My favorite is the latter, it is fast (based on the Boost graph library), relatively easy to use and tuneable.

EDIT: Note that in graph-tool, what we call Louvain modularity is indeed Newman's algorithm, the docs are here.