rsocial-networkingigraphcomplex-networks

calculate the modularity on each step


library(igraph)
g=graph.famous("Zachary")
c=edge.betweenness.community(g)
a=membership(c)
c$merges
b=community.to.membership(g,c$merges,steps=33)

[1] 1 1 2 1 3 3 3 1 4 5 3 1 1 1 4 4 3 1 4 1 4 1 4 4 2 2 4 2 2 4 4 2 4 4

[1] 9 4 0 0 0 0 5 0 3 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 6 0 0 0 0 7 0 0 8

I expect b is same with membership(c) because there are 33 steps. But why is b different from membership(c)?


Solution

  • This seems to be a bug in igraph because even the following does not work:

    > library(igraph)
    > g <- graph.full(3)
    > c <- edge.betweenness.community(g)
    > community.to.membership(g, c$merges, steps=1)$membership
    

    This gives me a membership vector of 1 2 0, which is clearly wrong; the correct result should be 1 0 0 or 0 1 1. Actually, you can fix the bug by subtracting 1 from the merge matrix:

    > g <- graph.famous("zachary")
    > c <- edge.betweenness.community(g)
    > membership(c)
    [1] 1 1 2 1 3 3 3 1 4 5 3 1 1 1 4 4 3 1 4 1 4 1 4 4 2 2 4 2 2 4 4 2 4 4
    > community.to.membership(g, c$merges-1, steps=29)$membership
    [1] 0 0 2 0 3 3 3 0 1 4 3 0 0 0 1 1 3 0 1 0 1 0 1 1 2 2 1 2 2 1 1 2 1 1
    

    These two membership vectors are essentially the same (with a bit of reindexing). Note that you only need 29 steps to reach the same membership vector because there are 34 vertices in the graph and you have 5 communities, so you need to perform 34-5=29 merges. Performing 33 steps would get you a single community only.

    I will file a bug report for this in igraph's bug tracker.