3
$\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$
1
  • $\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, 2015 at 10:33

1 Answer 1

2
$\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$
5
  • $\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$
    – a06e
    Nov 17, 2014 at 16:56
  • 1
    $\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, 2014 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$
    – a06e
    Nov 17, 2014 at 21:25
  • 1
    $\begingroup$ @becko, right. It seems there is not a single context-free interpretation of EdgeWeights. $\endgroup$
    – kglr
    Nov 18, 2014 at 7:49
  • 1
    $\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, 2014 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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