# Community detection on weighted graphs?

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?

• The next version of IGraph/M will have many community detection functions that work with weighted graphs, and could use some testing before release ... github.com/szhorvat/IGraphM Commented Sep 30, 2015 at 10:33

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]]


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}]


• Two questions: EdgeWeights have to be between 0 and 1? Vertices connected with larger EdgeWeights are considered closer or farther (that is, larger EdgeWeights pull vertices to the same community or to distinct communities)?
– a06e
Commented Nov 17, 2014 at 16:56
• @becko, They don't have be between 0 and 1; the weights seem to be automatically scaled/normalized (try multiplying the weights by any number). Re larger vs. smaller EdgeWeights, I don't know what the convention is - but my intuition is that weights indicate "strength of connection" rather than "distance", so I would expect larger edge weight between two nodes would make more likely that they will be in the same community, but I am not sure (We can experiment with the numbers in the posted example).
– kglr
Commented Nov 17, 2014 at 17:05
• I think this interpretation of EdgeWeights in FindGraphCommunities is inconsistent to that in WeightedAdjacencyGraph. In WeightedAdjacencyGraph a weight of Infinity means that the vertices are not linked, whereas in WeightedAdjacencyGraph it means that they are strongly connected!
– a06e
Commented Nov 17, 2014 at 21:25
• @becko, right. It seems there is not a single context-free interpretation of EdgeWeight`s.
– kglr
Commented Nov 18, 2014 at 7:49
• ... in fact, EdgeWeight>>Details says: The weight Subscript[w, i] can be interpreted as cost or capacity, or can have other special meanings for different graph computation functions.
– kglr
Commented Nov 18, 2014 at 7:50