The documentation for cluster_optimal() in igraph says it maximizes modularity "over all possible partitions". However, there seem to be cases where other cluster_ functions can find partitions with higher modularity. Here's an example using the Zachary Karate Club:
library(igraph)
library(igraphdata)
data(karate)
optimal <- cluster_optimal(karate)
modularity(optimal)
[1] 0.4449036
louvain <- cluster_louvain(karate, resolution = 0.5)
modularity(louvain)
[1] 0.654195
In this case, cluster_louvain() finds a partition with a substantially higher modularity.
Am I misunderstanding what cluster_optimal() does? Or could it be because my version of igraph wasn't compiled with GLPK support (how would I know)?
In this case, cluster_louvain() finds a partition with a substantially higher modularity.
This is not true. In the second case you compute a generalized modularity with a resolution parameter that is different from 1. You are not comparing apples to apples—not computing the same quantity in the two cases. Please see the definition of modularity here:
https://r.igraph.org/reference/modularity.igraph.html
https://igraph.org/c/html/latest/igraph-Community.html#igraph_modularity
In the first case you are using γ=1, in the second, γ=0.5.
Note that modularity(louvain) just extracts the generalized modularity value stored in the louvain community object, without computing anything. To recompute modularity, we need to use the syntax modularity(graph, membership). If we compute the standard modularity (with resolution of 1), we get a lower value:
> modularity(karate, louvain$membership)
[1] 0.3714661
Compare modularity(karate, louvain$membership, resolution=0.5), which will give you the same number that you got.