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

[Tamas Nepusz]

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