Tamas, thanks you for reply. I spent some hours in testing the code. It's work in most cases. I have found one exception. If the vector memb is: > memb [1] 1 1 2 3 4 5 1 4 1 1 4 1 1 1 1 1 1 1 1 1 it's means that the cluster # 5 includes the node only and does not have edges inside. Then > pairs <- count(matrix(memb[get.edgelist(g, names=FALSE)], ncol=2)) x.1 x.2 freq 1 1 1 39 2 1 2 1 3 1 3 2 4 1 4 6 5 2 1 2 6 2 4 2 7 3 1 2 8 3 4 2 9 4 1 7 10 4 2 1 11 4 4 4 12 5 1 2 13 5 2 1 14 5 4 1 And the 'x.1=1 x.2=5 freq=0' is ommited. As a result we will have 5 x 4 sparse Matrix and the command > pairs <- pairs + t(pairs) gives to Error: Matrices must have same dimensions in .Arith.Csparse(e1, e2, .Generic, class. = "dgCMatrix")
MikeS 2016-04-06 23:00 GMT+07:00 <[email protected]>: > Send igraph-help mailing list submissions to > [email protected] > > 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 > [email protected] > > You can reach the person managing the list at > [email protected] > > 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 5 (MikeS) > 2. Re: igraph-help Digest, Vol 117, Issue 5 (Tamas Nepusz) > 3. Re: igraph-help Digest, Vol 117, Issue 5 (MikeS) > 4. Re: igraph-help Digest, Vol 117, Issue 5 (Tamas Nepusz) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Wed, 6 Apr 2016 00:39:25 +0700 > From: MikeS <[email protected]> > To: [email protected] > Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5 > Message-ID: > <ca+ozr4skaw217-rcpbdtyuvdtwbxanx9nhglpqrqg62iadt...@mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > 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 <[email protected]>: >> Send igraph-help mailing list submissions to >> [email protected] >> >> 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 >> [email protected] >> >> You can reach the person managing the list at >> [email protected] >> >> 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 <[email protected]> >> To: Help for igraph users <[email protected]> >> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3 >> Message-ID: >> <cabsfaermgk2z9o6gq2uublag5nmhi7zf_v5uub59jwa-p1y...@mail.gmail.com> >> 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 <[email protected]> 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 <[email protected]>: >>>> 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 <[email protected]> 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 >>> [email protected] >>> https://lists.nongnu.org/mailman/listinfo/igraph-help >> >> >> >> ------------------------------ >> >> _______________________________________________ >> igraph-help mailing list >> [email protected] >> https://lists.nongnu.org/mailman/listinfo/igraph-help >> >> >> End of igraph-help Digest, Vol 117, Issue 5 >> ******************************************* > > > > ------------------------------ > > Message: 2 > Date: Tue, 5 Apr 2016 21:35:08 +0200 > From: Tamas Nepusz <[email protected]> > To: Help for igraph users <[email protected]> > Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5 > Message-ID: > <cabsfaer+oo5gqomu--5h2y-1cajgv0+odq4e2g_qvqojuf7...@mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > >> I couldn't find the package sparseMatrix. > Ah, sorry, I meant the Matrix package of course. > >>> 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. > What does get.edgelist(g) return? Does it return the proper edge list > of the graph? > > T. > > > > ------------------------------ > > Message: 3 > Date: Wed, 6 Apr 2016 08:53:57 +0700 > From: MikeS <[email protected]> > To: [email protected] > Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5 > Message-ID: > <ca+ozr4v3jp46w_bghsor-s_lqnnmfulqgqc6v3zmk4c-cfo...@mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > Tamas, thanks you for reply. > >>What does get.edgelist(g) return? Does it return the proper edge list >>of the graph? > > Yes, get.edgelist(g) returns the proper edge list of the igraph g. > > 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) >>g > IGRAPH UN-- 20 42 -- > + attr: name (v/c) > + edges (vertex names): > [1] A--B A--D A--E B--C B--E B--F C--D C--E C--I C--L C--P D--E E--J F--G > F--I > [16] F--J G--H G--J H--I H--J I--J I--L I--P K--L K--N K--O L--M L--O L--T > M--N > [31] M--O M--S N--O O--T P--Q P--S P--T Q--R Q--T R--S R--T S--T > >> get.edgelist(g) > [,1] [,2] > [1,] "A" "B" > [2,] "A" "D" > [3,] "A" "E" > [4,] "B" "C" > [5,] "B" "E" > [6,] "B" "F" > [7,] "C" "D" > [8,] "C" "E" > [9,] "C" "I" > [10,] "C" "L" > [11,] "C" "P" > [12,] "D" "E" > [13,] "E" "J" > [14,] "F" "G" > [15,] "F" "I" > [16,] "F" "J" > [17,] "G" "H" > [18,] "G" "J" > [19,] "H" "I" > [20,] "H" "J" > [21,] "I" "J" > [22,] "I" "L" > [23,] "I" "P" > [24,] "K" "L" > [25,] "K" "N" > [26,] "K" "O" > [27,] "L" "M" > [28,] "L" "O" > [29,] "L" "T" > [30,] "M" "N" > [31,] "M" "O" > [32,] "M" "S" > [33,] "N" "O" > [34,] "O" "T" > [35,] "P" "Q" > [36,] "P" "S" > [37,] "P" "T" > [38,] "Q" "R" > [39,] "Q" "T" > [40,] "R" "S" > [41,] "R" "T" > [42,] "S" "T" > > Mike > > 2016-04-06 0:39 GMT+07:00 MikeS <[email protected]>: >> 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 <[email protected]>: >>> Send igraph-help mailing list submissions to >>> [email protected] >>> >>> 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 >>> [email protected] >>> >>> You can reach the person managing the list at >>> [email protected] >>> >>> 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 <[email protected]> >>> To: Help for igraph users <[email protected]> >>> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3 >>> Message-ID: >>> <cabsfaermgk2z9o6gq2uublag5nmhi7zf_v5uub59jwa-p1y...@mail.gmail.com> >>> 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 <[email protected]> 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 <[email protected]>: >>>>> 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 <[email protected]> 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 >>>> [email protected] >>>> https://lists.nongnu.org/mailman/listinfo/igraph-help >>> >>> >>> >>> ------------------------------ >>> >>> _______________________________________________ >>> igraph-help mailing list >>> [email protected] >>> https://lists.nongnu.org/mailman/listinfo/igraph-help >>> >>> >>> End of igraph-help Digest, Vol 117, Issue 5 >>> ******************************************* > > > > ------------------------------ > > Message: 4 > Date: Wed, 6 Apr 2016 10:08:47 +0200 > From: Tamas Nepusz <[email protected]> > To: Help for igraph users <[email protected]> > Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5 > Message-ID: > <CABsfaERNnhkVDF0TaAu5678=aWbzL-Cm=dh2rbezhee4hr+...@mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > Ah, get.edgelist() returns the vertex names by default if the vertices > have names; you need to use get.edgelist(g, names=FALSE). Then it > should work. > T. > > > On Wed, Apr 6, 2016 at 3:53 AM, MikeS <[email protected]> wrote: >> Tamas, thanks you for reply. >> >>>What does get.edgelist(g) return? Does it return the proper edge list >>>of the graph? >> >> Yes, get.edgelist(g) returns the proper edge list of the igraph g. >> >> 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) >>>g >> IGRAPH UN-- 20 42 -- >> + attr: name (v/c) >> + edges (vertex names): >> [1] A--B A--D A--E B--C B--E B--F C--D C--E C--I C--L C--P D--E E--J F--G >> F--I >> [16] F--J G--H G--J H--I H--J I--J I--L I--P K--L K--N K--O L--M L--O L--T >> M--N >> [31] M--O M--S N--O O--T P--Q P--S P--T Q--R Q--T R--S R--T S--T >> >>> get.edgelist(g) >> [,1] [,2] >> [1,] "A" "B" >> [2,] "A" "D" >> [3,] "A" "E" >> [4,] "B" "C" >> [5,] "B" "E" >> [6,] "B" "F" >> [7,] "C" "D" >> [8,] "C" "E" >> [9,] "C" "I" >> [10,] "C" "L" >> [11,] "C" "P" >> [12,] "D" "E" >> [13,] "E" "J" >> [14,] "F" "G" >> [15,] "F" "I" >> [16,] "F" "J" >> [17,] "G" "H" >> [18,] "G" "J" >> [19,] "H" "I" >> [20,] "H" "J" >> [21,] "I" "J" >> [22,] "I" "L" >> [23,] "I" "P" >> [24,] "K" "L" >> [25,] "K" "N" >> [26,] "K" "O" >> [27,] "L" "M" >> [28,] "L" "O" >> [29,] "L" "T" >> [30,] "M" "N" >> [31,] "M" "O" >> [32,] "M" "S" >> [33,] "N" "O" >> [34,] "O" "T" >> [35,] "P" "Q" >> [36,] "P" "S" >> [37,] "P" "T" >> [38,] "Q" "R" >> [39,] "Q" "T" >> [40,] "R" "S" >> [41,] "R" "T" >> [42,] "S" "T" >> >> Mike >> >> 2016-04-06 0:39 GMT+07:00 MikeS <[email protected]>: >>> 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 <[email protected]>: >>>> Send igraph-help mailing list submissions to >>>> [email protected] >>>> >>>> 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 >>>> [email protected] >>>> >>>> You can reach the person managing the list at >>>> [email protected] >>>> >>>> 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 <[email protected]> >>>> To: Help for igraph users <[email protected]> >>>> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3 >>>> Message-ID: >>>> >>>> <cabsfaermgk2z9o6gq2uublag5nmhi7zf_v5uub59jwa-p1y...@mail.gmail.com> >>>> 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 <[email protected]> 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 <[email protected]>: >>>>>> 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 <[email protected]> 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 >>>>> [email protected] >>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help >>>> >>>> >>>> >>>> ------------------------------ >>>> >>>> _______________________________________________ >>>> igraph-help mailing list >>>> [email protected] >>>> https://lists.nongnu.org/mailman/listinfo/igraph-help >>>> >>>> >>>> End of igraph-help Digest, Vol 117, Issue 5 >>>> ******************************************* >> >> _______________________________________________ >> igraph-help mailing list >> [email protected] >> https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > ------------------------------ > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > End of igraph-help Digest, Vol 117, Issue 6 > ******************************************* _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
