6
$\begingroup$

With the help of several people in this community I have been wetting my feet in clustering some social network data using igraph's implementation of modularity-based clustering.

I am having some trouble interpreting the output of this routine and how to use it to generate lists of members of each community detected.

This routine outputs a two-column matrix and a list of modularity values. From the docs:

merges: A matrix with two column, this represents a dendogram and contains all the merges the algorithm performed. Each line is one merge and it is given by the ids of the two communities merged. The community ids are integer numbers starting from zero and the communities between zero and the number of vertices (N) minus one belong to individual vertices. The first line of the matrix gives the first merge, this merge creates community N, the number of vertices, the second merge creates community N+1, etc.

modularity: A numeric vector containing the modularity value of the community structure after performing every merge.

Working with this explanation and looking at the example at the bottom of the man page, I think the communities in this graph are

1st community: 0 1 2 3 4
2nd community: 10 11 12 13 14
3rd community: 5 6 7 8 9

Can someone who has used this method before confirm whether the right approach produces this result? I have basically (i) ignored the last two merges and (ii) gone over each row in the 'merges' matrix, combining each pair of vertices into a set while watching out for vertex values that are larger than the number of vertices (and therefore refer to another row in the 'merges' matrix).

$\endgroup$
3
$\begingroup$

The function which is used for this purpose: community.to.membership(graph, merges, steps, membership=TRUE, csize=TRUE) this can be used to extract membership based on the fastgreedy.community function results. You have to provide number of steps - how many merges should be performed. The optimal number of steps(merges) is the one which produce the maximal modularity.

$\endgroup$
  • $\begingroup$ @user1396: many thanks! I was thinking I had to do this 'by hand'. : ) I ran community.to.membership(ag, z$merges, steps=12) on the output of running fastgreedy.community() with the graph provided as an example in the docs and the output was $membership [1] 2 2 2 2 2 0 0 0 0 0 1 1 1 1 1 $csize [1] 5 5 5 I am confused by the repeated values in the $membership vector. How should I read them? I thought this would contain the vertice names. many thanks! $\endgroup$ – laramichaels Sep 23 '10 at 0:41
  • $\begingroup$ @user1396: I think I got it; a '2' in the i-th element in the membership vector is telling me the i-th vertex belongs to community 2. correct? :) $\endgroup$ – laramichaels Sep 23 '10 at 0:47

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.