2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Szabolcs Sep 30 '15 at 10:33
1
$\begingroup$

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

enter image description here

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

enter image description here

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

enter image description here

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – becko Nov 17 '14 at 16:56
  • $\begingroup$ @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). $\endgroup$ – kglr Nov 17 '14 at 17:05
  • $\begingroup$ 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! $\endgroup$ – becko Nov 17 '14 at 21:25
  • $\begingroup$ @becko, right. It seems there is not a single context-free interpretation of EdgeWeights. $\endgroup$ – kglr Nov 18 '14 at 7:49
  • $\begingroup$ ... 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. $\endgroup$ – kglr Nov 18 '14 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.