Community detection on weighted graphs?

Question

The documentation says that FindGraphCommunities works with weighted graphs. I've been playing around with a complete graph with weighted edges, and FindGraphCommunities always returns a single community, as if it wasn't taking into account the weights of the edges.

Can someone explain how I can do a community detection on a weighted graph using Mathematica?

Answer 1

Using a graph similar to the weighted graph example in the documentation FindGraphCommuinities >> Scope:

vl = {1, 2, 3, 4, 5, 6, 7, 8};
el = {1 <-> 2, 1 <-> 3, 2 <-> 4, 3 <-> 4, 3 <-> 5, 4 <-> 6, 
      5 <-> 6, 5 <-> 7, 6 <-> 8, 7 <-> 8};
vc = {{3.24, 0.86}, {3.24, 0.02}, {2.2, 0.88}, {2.2, 0.}, {1.04, 0.88},
      {1.04, 0.}, {0., 0.86}, {0., 0.02}};

ew1 = {0.3, 0.9, 0.1, 0.4, 0.2, 0.5, 1., 0.6, 0.8, 0.7};
g1 = Graph[vl, el, VertexLabels -> Placed["Name", Center], VertexShapeFunction -> "Name", 
   EdgeWeight -> ew1, EdgeLabels -> Thread[el -> ew1], ImagePadding -> 30, ImageSize -> 500];
Row[{g1, Style[FindGraphCommunities[g1], 16, "Panel"]}, Spacer[5]]

Now, randomly re-shuffle the edge weights:

ew2 = RandomSample[ew1];
g2 = Graph[vl, el, VertexLabels -> Placed["Name", Center], VertexShapeFunction -> "Name", 
   EdgeWeight -> ew2, EdgeLabels ->Thread[el -> ew2], ImagePadding -> 30, ImageSize -> 500];
Row[{g2, Style[FindGraphCommunities[g2], 16, "Panel"]}, Spacer[5]]

Update: Addressing the question in the comments:

Vertices connected with larger EdgeWeights are considered closer or farther (that is, larger EdgeWeights pull vertices to the same community or to distinct communities)?

Holding everything else fixed, observe how graph communities change as the EdgeWeight of the edge 3 <-> 5 changes from 0 to 5:

Manipulate[
 ew2 = {0.3`, 0.9`, 0.1`, 0.4`, ew35, 0.5`, 1.`, 0.6`, 0.8`, 0.7`};
 g2 = Graph[vl, el, VertexLabels -> Thread[vl -> 
             (Placed[Style[#, "Panel", 16, Black, Background -> None], Center] & /@ vl)],
   VertexShapeFunction -> "Circle", VertexSize -> .2, 
   EdgeWeight -> ew2, EdgeStyle -> Thick, 
   EdgeLabels -> Flatten[{Thread[el -> (Style[#, "Panel", 16, Red] & /@ ew1)], 
                       el[[5]] -> Style[ew2[[5]], Bold, "Panel", 20, Purple]}],
   ImagePadding -> 30, ImageSize -> 500];
 gc = FindGraphCommunities[g2];
 Column[{Style[gc, 16, "Panel"], HighlightGraph[g2, gc]}, Alignment -> Center], 
{ew35, 0, 5}]