Just use the dims=... parameter of the sparseMatrix() call to specify the dimensions explicitly. T.
On Thu, Apr 7, 2016 at 1:07 PM, MikeS <[email protected]> wrote: > 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 _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
