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

[Aaron Alexander-Bloch]

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(). 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.

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