Cross-posted to M.SE

I would like to know what method FindGraphCommunities uses with the option Method -> "Centrality" when given an edge-weighted graph.

Based on the name of the Method option value, I think it is not unreasonable to assume that it uses the Girvan–Newman algorithm, described in dx.doi.org/10.1073/pnas.122653799 and also in the review paper https://arxiv.org/abs/0906.0612 (see section V.A).

This method constructs a hierarchical clustering tree by repeatedly removing the graph edge with the highest edge betweenness.

This does not appear to be the case, as evidenced by the following example:

g = Graph3D[{1 <-> 2, 2 <-> 3, 3 <-> 1, 4 <-> 5, 5 <-> 6, 6 <-> 4, 1 <-> 4, 2 <-> 5, 3 <-> 6}, 
  EdgeWeight -> {1, 1, 1, 1, 1, 1, 5, 5, 5}]

FindGraphCommunities[g, Method -> "Centrality"]
(* {{1, 4}, {2, 5}, {3, 6}} *)

This result couldn't have been obtained with a direct application of the Girvan–Newman algorithm because the edges 1 <-> 4, 2 <-> 5, 3 <-> 6 have the highest betweenness, therefore they are removed first.

EdgeBetweennessCentrality[g]
(* {4., 4., 4., 4., 4., 4., 6., 6., 6.} *)

So far I was able to get the following information from WRI: FindGraphCommunities implements methods from the paper https://arxiv.org/abs/0906.0612 However, I do not know which specific method is being used in this particular case, and how Mathematica arrives to this result. The problem of community detection is not precisely defined in network science. There are many different methods which may be reasonable in different situations. Therefore I couldn't possibly use such a result in a published paper without knowing how Mathematica obtained it.

I do not need to know how Mathematica computes e.g. eigenvalues to understand what an eigenvalue is, or even to verify that the result it gave me is correct. The situation with FindGraphCommunities is different: what it computes and how it computes it are basically the same question.

While I tagged this as implementation-details on M.SE, I want to emphasize that this question is really about what this function is doing at all, not how it does it. Of what use is such a function if users don't know what it really does?

If I am misunderstanding something, please do correct me.