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

[Tamas Nepusz]

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
>
> I am looking for a test dataset in order to check results.
>
> 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)
> gnc <- walktrap.community(g)
> m <- vector()
> con <- vector()
> for (s in 0: nrow(gnc$merges)) {
>
> memb <- cutat(gnc, steps=s)
> m <- c(m, modularity (g, memb, weights=NULL))
>
> g2<-make_clusters(g, memb)
>
>   intra<-0
>   extra<-0
>     for(i in 1:length(E(g)))
>         {
>          ifelse(crossing(g2, g)[i]==FALSE, intra<-intra+1, extra<-extra+1)
>     }
> con <-c(con, extra/intra)
>
>  }
> windows()
> par(mfrow=c(1:2))
> plot(0:(length(m)-1), m, col="blue",xlab="Steps",ylab="Modularity")
> plot(0:(length(con)-1), con, col="blue",xlab="Steps",ylab="Conductance")
>
> Could someone please give me an idea where is error in my code?
>
> 2016-04-01 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: Community detection based on conductance (MikeS)
>>    2. Re: Community detection based on conductance (Tamas Nepusz)
>>
>>
>> ----------------------------------------------------------------------
>>
>> Message: 1
>> Date: Fri, 1 Apr 2016 08:50:31 +0700
>> From: MikeS <address@hidden>
>> To: address@hidden
>> Subject: Re: [igraph] Community detection based on conductance
>> Message-ID:
>>         <address@hidden>
>> Content-Type: text/plain; charset=UTF-8
>>
>> Hello,
>>
>> I would like to compare two partitioning network metric -- modularity
>> and conductance -- step by step. Example code is shown below. Maximum
>> modularity equal to
>>
>>> max(m)
>> [1] 0.4583333
>>
>> 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)
>> gnc <- walktrap.community(g)
>>
>> m <- vector()
>> con <- vector()
>> for (s in 0: nrow(gnc$merges)) {
>>     memb <- cutat(gnc, steps=s)
>>     m <- c(m, modularity (g, memb, weights=NULL))
>>             intra<-0 # edge connects two nodes inside community
>>            extra<-0 # edge connects two different communities
>>         for(i in 1:length(E(g))) {
>> #       ifelse(crossing(comm, g)[i]==FALSE, intra<- intra+1, extra<- extra+1)
>>         }
>> #   con <-c(con, intra/extra)
>> }
>>
>> Could someone please give me an idea how to convert the vector 'memb'
>> into community object 'comm'? Unfortunately, I don?t know how to pass
>> the first argument to the crossing('comm', g).
>>
>>
>>
>> ------------------------------
>>
>> Message: 2
>> Date: Fri, 1 Apr 2016 09:13:48 +0200
>> From: Tamas Nepusz <address@hidden>
>> To: Help for igraph users <address@hidden>
>> Subject: Re: [igraph] Community detection based on conductance
>> Message-ID:
>>         <address@hidden>
>> Content-Type: text/plain; charset=UTF-8
>>
>> Hi,
>>
>>> Could someone please give me an idea how to convert the vector 'memb'
>> into community object 'comm'?
>>
>> make_clusters(graph, membership) seems to do the trick.
>>
>> T.
>>
>>
>> On Fri, Apr 1, 2016 at 3:50 AM, MikeS <address@hidden> wrote:
>>> Hello,
>>>
>>> I would like to compare two partitioning network metric -- modularity
>>> and conductance -- step by step. Example code is shown below. Maximum
>>> modularity equal to
>>>
>>>> max(m)
>>> [1] 0.4583333
>>>
>>> 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)
>>> gnc <- walktrap.community(g)
>>>
>>> m <- vector()
>>> con <- vector()
>>> for (s in 0: nrow(gnc$merges)) {
>>>     memb <- cutat(gnc, steps=s)
>>>     m <- c(m, modularity (g, memb, weights=NULL))
>>>             intra<-0 # edge connects two nodes inside community
>>>            extra<-0 # edge connects two different communities
>>>         for(i in 1:length(E(g))) {
>>> #       ifelse(crossing(comm, g)[i]==FALSE, intra<- intra+1, extra<- 
>>> extra+1)
>>>         }
>>> #   con <-c(con, intra/extra)
>>> }
>>>
>>> Could someone please give me an idea how to convert the vector 'memb'
>>> into community object 'comm'? Unfortunately, I don?t know how to pass
>>> the first argument to the crossing('comm', g).
>>>
>>> _______________________________________________
>>> 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 1
>> *******************************************
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help