Re: [igraph] igraph-help Digest, Vol 117, Issue 5

[MikeS]

Tamas thanks you for the code.

I couldn't find the package sparseMatrix.
The packages 'plyr', 'Matrix' were installed and uploaded to the R
Console. Then I have tried to execute your code, but unfortunatly I
have the error. My vector memb is:
> memb
# [1] 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3
> pairs <- count(matrix(memb[get.edgelist(g)], ncol=2))
#  x.1 x.2 freq
# 1  NA  NA   42

The pairs have values 'NA' in the 1st and 2nd column.

Tamas, I have saw that you are not familiar with R.
Could someone please give idea how to fix this error?

I think that the error connects with the command: memb[get.edgelist(g)], because

> memb[get.edgelist(g)]
[1] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[26] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[51] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[76] NA NA NA NA NA NA NA NA NA

Thanks.
Mike

2016-04-05 23:00 GMT+07:00  <address@hidden>:
> Send igraph-help mailing list submissions to
>         address@hidden
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.nongnu.org/mailman/listinfo/igraph-help
> or, via email, send a message with subject or body 'help' to
>         address@hidden
>
> You can reach the person managing the list at
>         address@hidden
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of igraph-help digest..."
>
>
> Today's Topics:
>
>    1. Re: igraph-help Digest, Vol 117, Issue 3 (Tamas Nepusz)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Tue, 5 Apr 2016 12:38:50 +0200
> From: Tamas Nepusz <address@hidden>
> To: Help for igraph users <address@hidden>
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3
> Message-ID:
>         <address@hidden>
> Content-Type: text/plain; charset=UTF-8
>
> Intra-cluster and inter-cluster edge counts can be calculated much
> easier as follows (and maybe there are solutions that are even better
> - I'm not familiar with R):
>
> library(plyr)
> library(sparseMatrix)
> pairs <- count(matrix(memb[get.edgelist(g)], ncol=2))
> pairs <- sparseMatrix(i=pairs$x.1, j=pairs$x.2, x=pairs$freq)
> pairs <- pairs + t(pairs)
>
> Then the intra-cluster edge counts are given by diag(pairs)/2 (note
> the division by two) and the inter-cluster edge counts between cluster
> i and j are given by pairs[i, j]. Row and column sums belong to the
> number of edges incident on a given cluster.
>
> T.
>
>
> On Mon, Apr 4, 2016 at 2:11 PM, MikeS <address@hidden> wrote:
>> Hello,
>>
>> Tamas thanks you for reply.
>>
>> I have tried to write a script to calculate the conductance in genenal case.
>> I have used the definition of conductance from the paper
>> http://cs.stanford.edu/people/jure/pubs/comscore-icdm12.pdf
>> My code is shown below. I have the error: "in `[.data.frame`(tmp,
>> c("X1", "X2")) : undefined columns selected" on the line: "long <-
>> ....."
>> But code is working. I would like to fix this error and than to test
>> the code on some dataset.
>> Could someone please give remarks, comments to the code?
>>
>> library(igraph)
>> g <- make_graph( ~ A-B-C-D-A, E-A:B:C:D,
>>                       F-G-H-I-F, J-F:G:H:I,
>>                       K-L-M-N-K, O-K:L:M:N,
>>                       P-Q-R-S-P, T-P:Q:R:S,
>>                       B-F, E-J, C-I, L-T, O-T, M-S,
>>                       C-P, C-L, I-L, I-P)
>>
>> comm <- walktrap.community(g)
>>
>> mS <- vector() # the number of edges in S
>> cS <- vector() # the number of edges on the boundary of S
>> m <- vector()
>> ?ond <-vector()
>>
>> for (s in 0: nrow(comm$merges)) {
>>     memb <- cutat(comm, steps=s)
>>     m <- c(m, modularity (g, memb, weights=NULL))
>>     g2<-make_clusters(g, memb)
>>
>> # intra-cluster edges
>>
>> mS <- sapply(unique(membership(g2)), function(i) {
>>     vs<- which(membership(g2)==i)
>>     subg1<-induced.subgraph(g, vs)
>>       ecount(subg1)
>>       })
>>
>> # inter-cluster edges
>>
>> dcs <- data.frame(combn(unique(membership(g2)), 2))
>> cS <- sapply(dcs, function(x) {
>>   es<-E(g)[V(g)[membership(g2)==x[1]] %--% V(g)[membership(g2)==x[2]]]
>>   length(es)
>>   })
>> tmp  <- data.frame(t(dcs[1,]), t(dcs[2,]), cS)
>> long <- cbind(tmp["cS"], stack(tmp[c("X1","X2")]), row.names = NULL)
>> # Error in `[.data.frame`(tmp, c("X1", "X2")) : undefined columns selected
>>
>> cS <- with( long, tapply(cS, values, sum))
>>
>> # Conductance
>> ?ond <- c(?ond, min(cS/(2*mS + cS)))
>> }
>> par(mfrow=c(1:2))
>> plot(0:(length(m)-1), m, col="blue",xlab="Steps",ylab="Modularity")
>> plot(0:(length(?ond)-1), ?ond, col="blue",xlab="Steps",ylab="Conductance")
>>
>> 2016-04-03 23:01 GMT+07:00  <address@hidden>:
>>> Hi,
>>>
>>> There is no error in your implementation, although the way you define
>>> conductance is not exactly the way it is usually defined in the graph
>>> theory literature. (As far as I know, conductance is usually
>>> calculated for a cut of a graph, i.e. a partitioning into two disjoint
>>> sets, and the conductance of a graph is simply the minimum conductance
>>> over all possible cuts). The way you defined conductance is simply the
>>> ratio of the number of edges between clusters and the number of edges
>>> within clusters. Now, before the first merge, obviously all the edges
>>> are between clusters, so you divide a nonzero value with zero, hence
>>> you get infinity. After having performed all the merges, obviously all
>>> the edges are within clusters, so you divide zero with a nonzero
>>> value, getting zero in the end.
>>>
>>> So, there's nothing wrong with your code, but the way you defined
>>> conductance is not suitable for selecting an "optimal" number of
>>> clusters based on its extrema.
>>>
>>> T.
>>>
>>>
>>> On Sat, Apr 2, 2016 at 4:03 AM, MikeS <address@hidden> wrote:
>>>> Tamas, thanks you for reply.
>>>> My code does not have syntactical error now.
>>>> But I concerned about the result, I think I have a logical error.
>>>>
>>>> A modularity curve has the maximum value 0.4583 inside the steps'
>>>> range (on step with no.=18), but conductance curve has extremum 0 on
>>>> the right boundary.
>>>>
>>>>> max(m)
>>>> [1] 0.4583333 # index =18
>>>>> max(con)
>>>> [1] 0 # index = 20
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> ------------------------------
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> End of igraph-help Digest, Vol 117, Issue 5
> *******************************************