Graph modularity measure

Question

There are several metrics for the quality of a graph clustering, e.g. Newman modularity. These enable you to compare two candidate clusterings of the same graph.

Does anyone know a metric that will answer the question "how modular is this graph"? For example the first of these two graphs is more modular than the second: o===o-----o====o o----o===o-----o

It would be possible to choose a clustering algorithm, run it, and compute your preferred modularity metric for the best clustering found. But this is only a lower bound, so it doesn't seem very satisfactory.

The question matters. For example, the work of life scientists will be easier if the molecular organisation of life is modular than if it is not. It would be good to have a robust test - some of the discussion so far seems to involve wishful thinking.

My best attempt at this is: - a tree is more modular if the edges near leaves are higher weight - the modularity of a graph is the modularity of its min cut spanning tree Does anyone know of an established answer to this question?

Answer 1

I am not sure there is a clear answer to this, especially as the problem does not seem to be well-defined right now - your "figure" seems to indicate edge weights but you then mention node weights, something significantly different.

If the question is whether you can find a way to split a graph into two smaller modules, then you might want to look into applying Sparsest Cut techniques - a cut with low cost would imply (?) high modularity. I believe these can be easily modified to account for either unlabeled, edge-labeled or node-labeled graphs.

Answer 2

There is no single answer. Part of the reason why there are different clustering algorithms is that there are different criteria for a cluster. One is the number of triangles within a cluster, compared with the number that cross the boundary - but this is useless in a bipartite graph. Infomap has a subtle one that sometimes gives good results. One criterion compares the number of edges within the cluster (divided by the size of the cluster) to the number of edges that leave the cluster (divided by the size of the rest of the graph). Cuts, as suggested by the previous answer, are very appropriate if the edge weight can reasonably be thought of as the capacity for a flow of something between nodes, e.g. information. In that case, the min cut spanning tree is an reasonable summary of the graph. Strong links near leaves of the tree and weak links near the centre would indicate modularity.