Re: [igraph] modularity in dense weighted networks with spinglass.community

[Gábor Csárdi]

Aaron,

sorry for the delay.

On Mon, Apr 26, 2010 at 5:21 PM, Aaron Alexander-Bloch
<address@hidden> wrote:
> To anticipate your response, I think I finally put 2 and 2 together after
> some experimenting.
>
> It seems like the difference between
>
> modularity(graph, spinglass(graph)$community, weights = E(graph)$weight)
>
> and
>
> spinglass(graph)$modularity
>
> is that in spinglass() the m term in modularity is taken to be the number of
> edges as opposed to the sum of the weights, even though Aij, ki, and kj are
> as for modularity().

Yes. Even the gamma parameter is not taken into account.

> This has nothing at all to do with the function that's
> actually optimized in the spinglass code to get the partition. It's another
> null model entirely, which you plan to change.

Yes, the optimization has nothing to do with the modularity
calculation in the spinglass code. I am planning to modify the
spinglass modularity calculation to 1) use the weights for the
normalization and 2) use the gamma parameter. In short, it will report
the generalized modularity value, as in the spinglass paper.

Best,
Gabor

> Is this correct? Really this was pretty clear from your original response; I
> just didn't understand for some reason. Please do correct me if this wrong.
>
> Thanks again,
> Aaron
>
> On Thu, Apr 22, 2010 at 7:37 PM, Aaron Alexander-Bloch
> <address@hidden> wrote:
>>
>> Dear Gabor,
>>
>> Sorry to bring this up again. I thought that I understood your response
>> last month, but I'm trying to interpret my results, and I want to make sure.
>>
>> When you said that the spinglass code normalizes by the number of edges,
>> do you mean -- focusing on the "sum(Aij - ki*kj/2m)" term of modularity --
>> 1) that Aij is the weight of the edge but ki and kj are just the degrees of
>> the nodes? Or 2) is the degree of ki also multiplied by the average weight
>> of the graph? (This as opposed to ki being the sum of the weights of the
>> adjacent edges, as for the modularity code.)
>>
>> I  am pretty sure you meant (2), which I think upholds the relationship
>> Q_spinglass = -H/M where H is the Hamiltonian the code is trying to minimize
>> and M is the number of edges. Because the null model in the Hamiltonian for
>> weighted graphs in that paper replaced every edge's weight with the mean
>> weight of the graph. Basically I think that for my purposes I may want to
>> use the modularity value output by the spinglass.algorithm, with the
>> understanding that it has a different meaning than Newman-type modularity
>> for weighted graphs. But I want to make sure I'm not confused here.
>>
>> Thanks,
>> Aaron
>>
>>
>>
>> On Tue, Mar 16, 2010 at 2:09 PM, Gábor Csárdi <address@hidden> wrote:
>>>
>>> OK, the explanation is pretty simple. In the unweighted case, one has
>>> to give explicitly
>>>
>>> sc2 <- spinglass.community(g, weights=rep(1, ecount(g)))
>>>
>>> otherwise the weights will be used. If one does that, then the two
>>> modularity values are the same.
>>>
>>> In the weighted case, the spinglass code normalizes by the number of
>>> edges and the modularity function normalizes by the sum of the
>>> weights, hence the difference.
>>>
>>> I'll modify the spinglass code, to normalize by the sum of the
>>> weights. I think this is a better approach.
>>>
>>> Actually, the spinglass code always reports the Newman-type
>>> modularity, not the generalized quantity. Maybe this should be updated
>>> as well. Together with the spinglass.community() interface, to be
>>> consistent with other functions that have a 'weights' argument.
>>>
>>> Thanks again for the report!
>>>
>>> Best Regards,
>>> Gabor
>>>
>>> On Mon, Mar 15, 2010 at 5:29 PM, Aaron Alexander-Bloch
>>> <address@hidden> wrote:
>>> > Thank you both,
>>> > I'm eager to hear what you find Gabor.
>>> > Best,
>>> > Aaron
>>> >
>>> > On Fri, Mar 5, 2010 at 11:32 PM, Gábor Csárdi <address@hidden>
>>> > wrote:
>>> >>
>>> >> Hi Aaron,
>>> >>
>>> >> hmmm, you are right, something strange is going on here, if I run the
>>> >> following:
>>> >>
>>> >> R
>>> >>
>>> >> library(igraph)
>>> >>
>>> >> largest.component <- function(x) {
>>> >>  cl <- clusters(x)
>>> >>  ss <- which(cl$membership == which.max(cl$csize)-1)-1
>>> >>  subgraph(x, ss)
>>> >> }
>>> >>
>>> >> g <- largest.component(erdos.renyi.game(100, p=5/100))
>>> >> E(g)$weight <- runif(ecount(g))
>>> >> sc <- spinglass.community(g, weights=E(g)$weight)
>>> >> sc$modularity
>>> >> modularity(g, sc$membership, weights=E(g)$weight)
>>> >>
>>> >> sc2 <- spinglass.community(g)
>>> >> sc2$modularity
>>> >> modularity(g, sc2$membership)
>>> >>
>>> >> # I get
>>> >>
>>> >> > sc$modularity
>>> >> [1] 0.2808567
>>> >> > modularity(g, sc$membership, weights=E(g)$weight)
>>> >> [1] 0.4861468
>>> >> >
>>> >> > sc2 <- spinglass.community(g)
>>> >> > sc2$modularity
>>> >> [1] 0.2737963
>>> >> > modularity(g, sc2$membership)
>>> >> [1] 0.3635749
>>> >>
>>> >> which is clearly different, both in the weighted and unweighted case.
>>> >> For spinglass.community we just use the modularity value calculated by
>>> >> the community detection code, as implemented by the original author of
>>> >> the algorithm.
>>> >>
>>> >> I will check why the two values are not the same. Thanks for your
>>> >> report!
>>> >>
>>> >> Best,
>>> >> Gabor
>>> >>
>>> >> On Tue, Mar 2, 2010 at 9:05 PM, Aaron Alexander-Bloch
>>> >> <address@hidden> wrote:
>>> >> > Hi - Thanks in advance for any help.
>>> >> >
>>> >> > I'm trying to apply spinglass.community in the R package to dense
>>> >> > weighted
>>> >> > networks and have some trouble interpreting the modularity value in
>>> >> > my
>>> >> > results. I'm assuming that $modularity is the value of the
>>> >> > Hamiltonian
>>> >> > as in
>>> >> > the Reichardt/Bornholdt paper. As I'm keeping the gamma parameter at
>>> >> > 1
>>> >> > and
>>> >> > using the 'config' model, my understanding is that the Hamiltonian
>>> >> > is
>>> >> > the
>>> >> > same as Newman's modularity, at least for binary graphs. But I'm not
>>> >> > clear
>>> >> > on how these concepts are related for weighted graphs. If I
>>> >> > separately
>>> >> > get
>>> >> > the modularity value of the partition that spinglass gives me, it is
>>> >> > different from the modularity value given by spinglass directly. So
>>> >> > my
>>> >> > question is how should the modularity value given by spinglass be
>>> >> > interpreted for weighted graphs?
>>> >> >
>>> >> > In a related question, is there any plan to implement the "weighted
>>> >> > version"
>>> >> > of this method as in Heimo (2008)
>>> >> >
>>> >> > http://iopscience.iop.org/1742-5468/2008/08/P08007/
>>> >> >
>>> >> > Thanks very much!
>>> >> > Aaron
>>> >> >
>>> >> > _______________________________________________
>>> >> > igraph-help mailing list
>>> >> > address@hidden
>>> >> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>>> >> >
>>> >> >
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> Gabor Csardi <address@hidden>     UNIL DGM
>>> >>
>>> >>
>>> >> _______________________________________________
>>> >> igraph-help mailing list
>>> >> address@hidden
>>> >> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>> >
>>> > _______________________________________________
>>> > igraph-help mailing list
>>> > address@hidden
>>> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>>> >
>>> >
>>>
>>>
>>>
>>> --
>>> Gabor Csardi <address@hidden>     UNIL DGM
>>>
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM