[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] igraph-help Digest, Vol 117, Issue 6
|
From: |
MikeS |
|
Subject: |
Re: [igraph] igraph-help Digest, Vol 117, Issue 6 |
|
Date: |
Thu, 7 Apr 2016 18:07:04 +0700 |
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 <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 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 <address@hidden>
> To: address@hidden
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
> Message-ID:
> <address@hidden>
> 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 <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
>> *******************************************
>
>
>
> ------------------------------
>
> Message: 2
> Date: Tue, 5 Apr 2016 21:35:08 +0200
> From: Tamas Nepusz <address@hidden>
> To: Help for igraph users <address@hidden>
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
> Message-ID:
> <address@hidden>
> 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 <address@hidden>
> To: address@hidden
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
> Message-ID:
> <address@hidden>
> 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 <address@hidden>:
>> 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
>>> *******************************************
>
>
>
> ------------------------------
>
> Message: 4
> Date: Wed, 6 Apr 2016 10:08:47 +0200
> From: Tamas Nepusz <address@hidden>
> To: Help for igraph users <address@hidden>
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
> Message-ID:
> <address@hidden>
> 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 <address@hidden> 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 <address@hidden>:
>>> 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
>>>> *******************************************
>>
>> _______________________________________________
>> 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 6
> *******************************************
- Re: [igraph] igraph-help Digest, Vol 117, Issue 6,
MikeS <=