I've used the brew to install the igraph according to your instruction, but i do not know how to start to use it because it isn't an app, is it? Could you please help me how to use it ?

------=_Part_50921_1814895559.1459562481693-- From MAILER-DAEMON Sat Apr 02 05:14:36 2016 Received: from list by lists.gnu.org with archive (Exim 4.71) id 1amHdc-0001pP-99 for mharc-igraph-help@gnu.org; Sat, 02 Apr 2016 05:14:36 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:60974) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from

It is a C library, which means that you have to write your=
own C programs to make use of it.=C2=A0 Here's the tutorial to get sta=
rted:

On 2 April 2016 at 04=
:01, =E7=8E=8B=E9=92=A7 <wangjun200805@163.com> wrote:

I've used the brew to install the i= graph according to your instruction, but i do not know how to start to use = it because it isn't an app, is it? Could you please help me how to use = it ?=C2=A0

___= ____________________________________________

igraph-help mailing list

igraph-help@nongnu.org

https://lists.nongnu.org/mailman/listinfo/igrap= h-help

--047d7bb046c05787b2052f7cec9d-- From MAILER-DAEMON Sat Apr 02 10:04:26 2016 Received: from list by lists.gnu.org with archive (Exim 4.71) id 1amMA6-0002Yc-4b for mharc-igraph-help@gnu.org; Sat, 02 Apr 2016 10:04:26 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:58930) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from

Hello there,

<= /div>
--001a114386ace83b48052f80f882--
From MAILER-DAEMON Sat Apr 02 18:32:49 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1amU65-00073K-8f
for mharc-igraph-help@gnu.org; Sat, 02 Apr 2016 18:32:49 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:45876)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1amU61-00072i-RH
for igraph-help@nongnu.org; Sat, 02 Apr 2016 18:32:47 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1amU60-0001Kx-18
for igraph-help@nongnu.org; Sat, 02 Apr 2016 18:32:45 -0400
Received: from mail-lf0-x22d.google.com ([2a00:1450:4010:c07::22d]:34736)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1amU5z-0001Kh-KW
for igraph-help@nongnu.org; Sat, 02 Apr 2016 18:32:43 -0400
Received: by mail-lf0-x22d.google.com with SMTP id c62so118820958lfc.1
for ; Sat, 02 Apr 2016 15:32:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to; bh=s305sgwunBcjzYxE+nLA6fecPjsIkKT+ZG4+BK+q24w=;
b=nz6Lw+q+NImsKQccVz/BPbvnS7lkd0ItI1SfP7fjGESt86AceelWNJLd/qwFqy3Gmd
xiJpNvVUqRuZQYvMGqGBg1abiNZgtNXdn8XKm0Xx+isETgw5K/d0nQgluDElO2nrt4BB
WTD+clNaGlenMfK3dPyz1WQ+U5SaZgYdRlVjFzpedYneNjJ6q49gjLGN8p3BIJ8Wz1NJ
MrdAEoJuH1FPllFoDKVlnE2wx5KNI6gSO038AvzFB/ek8V2G1MnZnmwmyBkCTDerjAV4
JqKampq9ojpeywAny1Ch5Uc2brPeof75I65TizOV/PbR+ZgfG5fKSCchjTi3FPbs6hT6
rXew==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to;
bh=s305sgwunBcjzYxE+nLA6fecPjsIkKT+ZG4+BK+q24w=;
b=CBcU2qE2FeEIgCYC0w8DzqsG1tssLlEL9irkPFtN91LFJbE/vkFUbA0KCha7+959jT
yjFszD6nCfvIVkyixApsBvG6FXLHasO8Jf9E8APe6rLYf2/4NGqflPr3urdObHDDrYKE
O7YkGN+W/AcodaNI2EH6tJUiu8LpuTcSIzrux8uqK81YshLC35hOgWLJP/FfV+Xy8eM4
9cfOEenALy7qrU0n5t4UCE5r1OfxpTz63t6nrD9oF/sAR0AvRM4qeucjQz3/al60WDjg
lH2UVAtmBvW7waQKt+k8I4i60JFrSP5LXEepESKOD2RlMg2aKiC8yCh8+6VtLGUsDemq
9n5A==
X-Gm-Message-State: AD7BkJLl6Qs4j8TixXMS6zc0UXQQo3FvvfqE2M4kTmwodTvVvSjpTHYS21HLxX/qNzorORZGeNlBvxBtZdZ9nw==
MIME-Version: 1.0
X-Received: by 10.25.25.84 with SMTP id 81mr4740434lfz.71.1459636362392; Sat,
02 Apr 2016 15:32:42 -0700 (PDT)
Sender: ntamas@gmail.com
Received: by 10.25.15.42 with HTTP; Sat, 2 Apr 2016 15:32:42 -0700 (PDT)
In-Reply-To:
References:
Date: Sun, 3 Apr 2016 00:32:42 +0200
X-Google-Sender-Auth: _isXXmCq064Td86X02oJ1-XZxPc
Message-ID:
From: Tamas Nepusz
To: Help for igraph users
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2a00:1450:4010:c07::22d
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 1
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Sat, 02 Apr 2016 22:32:47 -0000
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 <4botru@gmail.com> 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 :
>> Send igraph-help mailing list submissions to
>> igraph-help@nongnu.org
>>
>> 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
>> igraph-help-request@nongnu.org
>>
>> You can reach the person managing the list at
>> igraph-help-owner@nongnu.org
>>
>> 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 <4botru@gmail.com>
>> To: igraph-help@nongnu.org
>> Subject: Re: [igraph] Community detection based on conductance
>> Message-ID:
>>
>> 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
>> To: Help for igraph users
>> Subject: Re: [igraph] Community detection based on conductance
>> Message-ID:
>>
>> 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 <4botru@gmail.com> 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
>>> igraph-help@nongnu.org
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>> ------------------------------
>>
>> _______________________________________________
>> igraph-help mailing list
>> igraph-help@nongnu.org
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>> End of igraph-help Digest, Vol 117, Issue 1
>> *******************************************
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Sat Apr 02 19:16:06 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1amUly-000420-P1
for mharc-igraph-help@gnu.org; Sat, 02 Apr 2016 19:16:06 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:50984)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1amUlw-000415-Nj
for igraph-help@nongnu.org; Sat, 02 Apr 2016 19:16:05 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1amUlv-00017C-RS
for igraph-help@nongnu.org; Sat, 02 Apr 2016 19:16:04 -0400
Received: from mail-lb0-x22b.google.com ([2a00:1450:4010:c04::22b]:36726)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1amUlv-000178-Jh
for igraph-help@nongnu.org; Sat, 02 Apr 2016 19:16:03 -0400
Received: by mail-lb0-x22b.google.com with SMTP id qe11so109366783lbc.3
for ; Sat, 02 Apr 2016 16:16:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to; bh=ykb29b9HDKdFbC0kxCLveoXxkhWeorKRni092BJVNIs=;
b=akGstq2+hWlf4kt8qWFACQokoOqLNvMcI1JvoNFBMqy9kRt9TH+1q+EKi6yKmmL9AA
HUaJZGAEJgXFAMJ2hibyMoP2xeq8FiyCzvlJPvlzr0LyIleuH0PPuoOtoPtnmqRQlwZN
rVVyPGIIu2hAvdDCzfGrEWcDx7yDZNb7c3zGFofXBk83hVmI3BfSxDAZBUoMeocakq89
2n2OIxLa9+clZojf1mBt4ygBZEO3DNnBEYenNHjbju4RE94lfrlXF+/0EVYFSiPk6nt0
4TfHXxxzGQNZp5TwonnAJDRgnkJvZj7CL/3DKr+fhpd2ttJNTv3ABCn42JPdzOWZKMK7
nkGQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to;
bh=ykb29b9HDKdFbC0kxCLveoXxkhWeorKRni092BJVNIs=;
b=LeIVFlUlxLio47w7ozzno29FgHtVBZ+wVWzkdRB+I3uoRNiVnFJUXoGkdsZ79KTSEt
emG4Ol/rxxx4C3O2EavzP6jBCZurM4JP+jG64feb/1OE4m3M9pg847bVcdm345otQQ+j
mErKeTn7fEGTjNJDPIxdZHaYCAkUVdxqEgUsQEuEnPN4xsQTCDa7Cmsi4fHj+jHUtTst
zG+RifS5JnyOBZTuv88qLSKrxjBsoaJYd13nMJs+uIRqeRpWTQIZPs+AmENoZtqT/yhN
8i+fPcHICk2uYDWJ/e0DgB0dABaxOSBsffNt8ocVyRcjdV59lSa4zv/INxKr/3Dbfd1v
IdgQ==
X-Gm-Message-State: AD7BkJI4MLuMnuvxu5Uz+4NTAcr/233GrSePCYYbIsAKpr/TkBmcDT50ib4mDd/lnoHyA6bp6AMwME8s9HoGTA==
MIME-Version: 1.0
X-Received: by 10.112.151.207 with SMTP id us15mr140701lbb.28.1459638962810;
Sat, 02 Apr 2016 16:16:02 -0700 (PDT)
Sender: ntamas@gmail.com
Received: by 10.25.15.42 with HTTP; Sat, 2 Apr 2016 16:16:02 -0700 (PDT)
In-Reply-To:
References:
Date: Sun, 3 Apr 2016 01:16:02 +0200
X-Google-Sender-Auth: opp_6ie_-pv_I6h0FUNBSIrzy68
Message-ID:
From: Tamas Nepusz
To: Help for igraph users
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2a00:1450:4010:c04::22b
Subject: Re: [igraph] Speed up calculation of pairwise shortest distances
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Sat, 02 Apr 2016 23:16:05 -0000
Hi,
> My implementation:
> for each of the 100 million pairs:
> call get_shortest_paths()
> take the min between 120 and the length of the list of edges in the
> shortest path
Why not like this:
for each of the vertices that occur as sources in the pairs:
call shortest_paths([vertex], [all the vertices that occur as
targets for the source vertex])
then take the min
shortest_paths() will return the lengths of the paths only, not the
actual paths. (I know, this function has quite a misleading name).
Also, running the calculation grouped by source vertices lets igraph
perform less work if one of the paths found (or some part of it) turns
out to be a prefix for some other path originating from the same
source but ending at a different target.
> I'm clearly wasting efforts because:
> - get_shortest_paths() returns the actual path between the two nodes, but
> I'm only interested in the distance (I need something like
> "get_shortest_distance")
Most of the computational effort is spent on finding that path, saving
it usually does not represent a large overhead (compared to what it
took to find that path in such a large graph).
> - get_shortest_paths() processes until it reaches destination node, but
> since we have an upper bound, I'd suffice to use a "cutoff" value for the
> distance calculation
Unfortunately this is not implemented in igraph yet for shortest path
calculations.
T.
From MAILER-DAEMON Mon Apr 04 08:11:53 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1an3MH-0004tZ-Cs
for mharc-igraph-help@gnu.org; Mon, 04 Apr 2016 08:11:53 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:39869)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1an3MD-0004ot-Qc
for igraph-help@nongnu.org; Mon, 04 Apr 2016 08:11:51 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1an3MC-0005aP-HU
for igraph-help@nongnu.org; Mon, 04 Apr 2016 08:11:49 -0400
Received: from mail-vk0-x22b.google.com ([2607:f8b0:400c:c05::22b]:34992)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1an3MC-0005aH-Cf
for igraph-help@nongnu.org; Mon, 04 Apr 2016 08:11:48 -0400
Received: by mail-vk0-x22b.google.com with SMTP id e6so176608172vkh.2
for ; Mon, 04 Apr 2016 05:11:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:content-transfer-encoding;
bh=MBsp3GZ99HBgFOjrIxZ/aCE3W046s5o1YLgixVJbJsY=;
b=gFF6dHeiu4JuoDWeUx2LBl19Q7L8xdQVOdJfjT9SXElZFJEScxxtKp/8WSeOaglAMK
R/NzEy5Ql4Yzx1rsfxhghF4dp+WaBYPE+ywDhH7Xs71oRnrFsgwaOU6t2tgMzx95MCbJ
WWSs2c/FTYGSRG0aqf7ImhGYzVOevrAyapJJnaSQ1W5eCuVoDo3J/KhzecnRA88L4Ck2
hbUE/WR9IUq/e/JsaOu4u89EkiLmKFzuSuLfM5G3U8/tNQgPNcpeLsBuf1kyKaHXnt1O
2Xl9+333miY5hehB9KTexAhaE5kBQiwpwu+a3b8jAcJqFtTJ5Db4UtAyff1NQIu+/sVo
Sw3w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:to:content-transfer-encoding;
bh=MBsp3GZ99HBgFOjrIxZ/aCE3W046s5o1YLgixVJbJsY=;
b=Mfqwg/qxzytdtZinMIj3wbL1YCadvIyYLC0CV8Bl210lyY1JShVacijRQu727rwD2h
0/YGw7UDwZ8l1lYXqqXc2LWL2nG27eTICT6rnsrsbjP71Zw8GAJTZPgqzzOctDfyt3NS
+qZwTDTTeqSV0E/MahVkSgIjQ9KQ5XuXQoKS7/ftLjg5pLlB5U7Z56KoGVNN3Hz4g08M
SlpgG32OCCsE60pQjVaDrGIeaYgPb/GwmcXgrM8gNdf4Jp43imns7cvD1I2AgMAi2GE4
tU9vJ9sCVjuZ++Evp4BR3ja4ESE1e3m5MFD7L3CdaKTC7oRTdiXv5CHCdA1e3q6OP/dZ
ozbQ==
X-Gm-Message-State: AD7BkJKd91n20hQ6TFANN3DXtsrR3p+GqS98q+LhDRFi9jIRcPkD8/n/HuUit4GlQy9beiS/Hro6p9Xzv2C5Yg==
MIME-Version: 1.0
X-Received: by 10.176.6.232 with SMTP id g95mr1739506uag.115.1459771907351;
Mon, 04 Apr 2016 05:11:47 -0700 (PDT)
Received: by 10.176.1.135 with HTTP; Mon, 4 Apr 2016 05:11:47 -0700 (PDT)
In-Reply-To:
References:
Date: Mon, 4 Apr 2016 19:11:47 +0700
Message-ID:
From: MikeS <4botru@gmail.com>
To: igraph-help@nongnu.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2607:f8b0:400c:c05::22b
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 04 Apr 2016 12:11:51 -0000
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()
=D1=81ond <-vector()
for (s in 0: nrow(comm$merges)) {
memb <- cutat(comm, steps=3Ds)
m <- c(m, modularity (g, memb, weights=3DNULL))
g2<-make_clusters(g, memb)
# intra-cluster edges
mS <- sapply(unique(membership(g2)), function(i) {
vs<- which(membership(g2)=3D=3Di)
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)=3D=3Dx[1]] %--% V(g)[membership(g2)=3D=3Dx[2=
]]]
length(es)
})
tmp <- data.frame(t(dcs[1,]), t(dcs[2,]), cS)
long <- cbind(tmp["cS"], stack(tmp[c("X1","X2")]), row.names =3D NULL)
# Error in `[.data.frame`(tmp, c("X1", "X2")) : undefined columns selected
cS <- with( long, tapply(cS, values, sum))
# Conductance
=D1=81ond <- c(=D1=81ond, min(cS/(2*mS + cS)))
}
par(mfrow=3Dc(1:2))
plot(0:(length(m)-1), m, col=3D"blue",xlab=3D"Steps",ylab=3D"Modularity")
plot(0:(length(=D1=81ond)-1), =D1=81ond, col=3D"blue",xlab=3D"Steps",ylab=
=3D"Conductance")
2016-04-03 23:01 GMT+07:00 :
> 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 <4botru@gmail.com> 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.=3D18), but conductance curve has extremum 0 on
>> the right boundary.
>>
>>> max(m)
>> [1] 0.4583333 # index =3D18
>>> max(con)
>> [1] 0 # index =3D 20
From MAILER-DAEMON Tue Apr 05 06:38:56 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1anONs-0006sj-Pr
for mharc-igraph-help@gnu.org; Tue, 05 Apr 2016 06:38:56 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:49068)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1anONp-0006nv-PK
for igraph-help@nongnu.org; Tue, 05 Apr 2016 06:38:55 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1anONo-0007Q4-Ct
for igraph-help@nongnu.org; Tue, 05 Apr 2016 06:38:53 -0400
Received: from mail-lf0-x22d.google.com ([2a00:1450:4010:c07::22d]:36428)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1anONn-0007Px-W1
for igraph-help@nongnu.org; Tue, 05 Apr 2016 06:38:52 -0400
Received: by mail-lf0-x22d.google.com with SMTP id g184so7289946lfb.3
for ; Tue, 05 Apr 2016 03:38:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to:content-transfer-encoding;
bh=e4vsZmIrK3Y77J/7vZGuP3N0xq9dRtwWyBLlM7RL4Lw=;
b=Uz/qbLNbzsXE9D+Irbz5LlZEj0YsMaNn9UjvMIRAgbwcTwdK+cEet38eB7b7zJve3/
r6QI5Ss5ARuxYfQwWiOJ49xXzpHY94ds3C2mXYDBSfEyKPqnKJxk6RxqUT+hcbf8sRoE
dhpSZdfWOTpjQWvIV4GUUrjJ/qzF4OJTXKClJhG0q2wagBLd6DaBTYbs9zuuS2e5gOpJ
QoxEJ4RL4UskNxZxc75tsHQPp3ZCUXoSsJit1zmJZuaHAURRkL8V6rmm4Kw4Xn1t5PvS
ObEJQ5asuyBIgamEQAs8bfce425SkFEfUny0KDqQAecwZriIww+6PxHfG+2rONHps5bs
jBmg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to:content-transfer-encoding;
bh=e4vsZmIrK3Y77J/7vZGuP3N0xq9dRtwWyBLlM7RL4Lw=;
b=G2nhm/C9UvbIHF+8HzSrWLs8xCJRKGbLT1fU5iY+MwiskR9KcRPXmm8Wzth25Xukip
P/bR/gmqQmwC4/hdgKP7/a9Z33b8mnT9sSbY0A3vBnhMnP8/b5mZlr6m+270Y4lB0Zba
sqhN/yffbF1wxBq7yfFtHVei4Qb+6Rg40o2WOtxr5byZ97QQkmRvur87Cwe6cnqKlqeS
nnwVJEKCSCICsP6On+y6XReg83z4FHYlET1b4Z1d22H1VSmiit8OydGYWzCfaX6JETFS
n3PXionnWIirbgvZW6HvBolwJfZNA3+U8NT+MeAIlc2Z2MOvQbt/npmEwZhwycCj9Uu9
sjCw==
X-Gm-Message-State: AD7BkJL38ksHNQTvQFtFIVWEWukEWLbOD8Qhwm0clpf+oOrH7JzMBPfQHT/aeOesOET1YTf7MNyR3BBYM/PAsA==
MIME-Version: 1.0
X-Received: by 10.25.25.84 with SMTP id 81mr10727247lfz.71.1459852730769; Tue,
05 Apr 2016 03:38:50 -0700 (PDT)
Sender: ntamas@gmail.com
Received: by 10.25.15.42 with HTTP; Tue, 5 Apr 2016 03:38:50 -0700 (PDT)
In-Reply-To:
References:
Date: Tue, 5 Apr 2016 12:38:50 +0200
X-Google-Sender-Auth: epZSXIqnFGzv7bOIWGyguEGo68w
Message-ID:
From: Tamas Nepusz
To: Help for igraph users
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2a00:1450:4010:c07::22d
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2016 10:38:55 -0000
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=3D2))
pairs <- sparseMatrix(i=3Dpairs$x.1, j=3Dpairs$x.2, x=3Dpairs$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 <4botru@gmail.com> wrote:
> Hello,
>
> Tamas thanks you for reply.
>
> I have tried to write a script to calculate the conductance in genenal ca=
se.
> 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()
> =D1=81ond <-vector()
>
> for (s in 0: nrow(comm$merges)) {
> memb <- cutat(comm, steps=3Ds)
> m <- c(m, modularity (g, memb, weights=3DNULL))
> g2<-make_clusters(g, memb)
>
> # intra-cluster edges
>
> mS <- sapply(unique(membership(g2)), function(i) {
> vs<- which(membership(g2)=3D=3Di)
> 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)=3D=3Dx[1]] %--% V(g)[membership(g2)=3D=3Dx=
[2]]]
> length(es)
> })
> tmp <- data.frame(t(dcs[1,]), t(dcs[2,]), cS)
> long <- cbind(tmp["cS"], stack(tmp[c("X1","X2")]), row.names =3D NULL)
> # Error in `[.data.frame`(tmp, c("X1", "X2")) : undefined columns selecte=
d
>
> cS <- with( long, tapply(cS, values, sum))
>
> # Conductance
> =D1=81ond <- c(=D1=81ond, min(cS/(2*mS + cS)))
> }
> par(mfrow=3Dc(1:2))
> plot(0:(length(m)-1), m, col=3D"blue",xlab=3D"Steps",ylab=3D"Modularity")
> plot(0:(length(=D1=81ond)-1), =D1=81ond, col=3D"blue",xlab=3D"Steps",ylab=
=3D"Conductance")
>
> 2016-04-03 23:01 GMT+07:00 :
>> 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 <4botru@gmail.com> 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.=3D18), but conductance curve has extremum 0 on
>>> the right boundary.
>>>
>>>> max(m)
>>> [1] 0.4583333 # index =3D18
>>>> max(con)
>>> [1] 0 # index =3D 20
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Tue Apr 05 13:39:34 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1anUww-0000ZJ-Ax
for mharc-igraph-help@gnu.org; Tue, 05 Apr 2016 13:39:34 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:34217)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1anUwq-0000Ye-Dy
for igraph-help@nongnu.org; Tue, 05 Apr 2016 13:39:33 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1anUwo-0000Bk-KZ
for igraph-help@nongnu.org; Tue, 05 Apr 2016 13:39:28 -0400
Received: from mail-vk0-x22a.google.com ([2607:f8b0:400c:c05::22a]:34593)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1anUwo-0000Bd-Ey
for igraph-help@nongnu.org; Tue, 05 Apr 2016 13:39:26 -0400
Received: by mail-vk0-x22a.google.com with SMTP id e185so27268185vkb.1
for ; Tue, 05 Apr 2016 10:39:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to;
bh=5pjrylsKZtJWq1Kx1ljxYWTp1QZA5SCgFbkUvpeV1/U=;
b=HU8ZvaYv5JXMd91hdFx/V7pmCUAjmH9wMTvpEwles3E2axVBKLDO/HAHfhY1++xmlw
eY8qdpeDTG1jK3rPajcnBRwv7uADizhmr4uGzlBpvCg8mvTh+LHen1bepkYk+B+M2atF
P/noeBVFIskZpkir4vptKUDHRW15JZxSO9kXHa9ZZIwmOoFB7eOFxxwf7VUnJPSt8PPv
GSucsYGmcAEFxDE9jcLG+x93uMbvj56TLQQooQ7s9gvcjfShvNCC9houtVYScULv6Ivt
pheFmBX/AFvrtxQKsyY3gsYrMqdFMBalHM11kiZbP2hdDMRwBauLdNjXsj7Q1pphjctp
m2Ew==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:to;
bh=5pjrylsKZtJWq1Kx1ljxYWTp1QZA5SCgFbkUvpeV1/U=;
b=e49HSfNInBds3hpglQvMQD2Eq2eWd6iizDWv498h3mvIOH6DLdsYZx76Kery3CpsxE
5aQgpFzHzFhDq2oAyjr9gLJQ6Fu/WeEB0wbC08RE+mTqj/hmHO1Dw38vSK1n6bZxuoXr
6h7+SoPn1ETEcqnDYSWcgvGvwD4VMfZRloYi+gjLuGY//uXW2wjKsBQVRzAjmk2KEdHx
hGuoBAgUwjhEsPpMrByw6vCL1Dod7dhy6zfX1E/kBhwuaFODC4MPMbMFkQDKkmdPvzyN
BSge46vrSgiv5TObVsdPVGJKDmap0/F7aFmvG4Ay7MRTRQDJmPCFYwgydOV1m6T5pSqf
Z08w==
X-Gm-Message-State: AD7BkJIP41Zp4MapJyC67mGwnzQRoe6TYH1JB4Rv/vb0dX9bRIlRjHyhKL016bIxwjBXa2IbZUED5X+fVzCTpg==
MIME-Version: 1.0
X-Received: by 10.176.0.110 with SMTP id 101mr10196466uai.15.1459877965657;
Tue, 05 Apr 2016 10:39:25 -0700 (PDT)
Received: by 10.176.1.135 with HTTP; Tue, 5 Apr 2016 10:39:25 -0700 (PDT)
In-Reply-To:
References:
Date: Wed, 6 Apr 2016 00:39:25 +0700
Message-ID:
From: MikeS <4botru@gmail.com>
To: igraph-help@nongnu.org
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2607:f8b0:400c:c05::22a
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2016 17:39:33 -0000
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 :
> Send igraph-help mailing list submissions to
> igraph-help@nongnu.org
>
> 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
> igraph-help-request@nongnu.org
>
> You can reach the person managing the list at
> igraph-help-owner@nongnu.org
>
> 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
> To: Help for igraph users
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3
> Message-ID:
>
> 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 <4botru@gmail.com> 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 :
>>> 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 <4botru@gmail.com> 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
>> igraph-help@nongnu.org
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> ------------------------------
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> End of igraph-help Digest, Vol 117, Issue 5
> *******************************************
From MAILER-DAEMON Tue Apr 05 15:35:13 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1anWkr-0001M9-Ns
for mharc-igraph-help@gnu.org; Tue, 05 Apr 2016 15:35:13 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:58358)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1anWkp-0001Kt-2a
for igraph-help@nongnu.org; Tue, 05 Apr 2016 15:35:11 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1anWko-0002zv-CS
for igraph-help@nongnu.org; Tue, 05 Apr 2016 15:35:11 -0400
Received: from mail-lb0-x235.google.com ([2a00:1450:4010:c04::235]:36196)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1anWko-0002zr-4Z
for igraph-help@nongnu.org; Tue, 05 Apr 2016 15:35:10 -0400
Received: by mail-lb0-x235.google.com with SMTP id qe11so16081847lbc.3
for ; Tue, 05 Apr 2016 12:35:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to; bh=h3YWGS1Nxm2tZr+yhXc73HU+Kno+ufvyNiFOFZLjGTU=;
b=me+xutp9q97+lHflpRKBNgZuwaR/WURrR6uVQjQokjjTz1e4zItMZN6M7XwcbitQ/q
2V4V4pH+yK5dJMlE3yNG4OOaoSSWMh0Q6nUE6YqYNNEZCf3N9OqfSmDo7pFi+ofmaxm6
21SqNm/g5K4Q0oRYtCWDdoEVLcz+y0t6+YRa5Uvsl9e00s/PAppMQVJaSV18tIpSr165
e2voLg0fqdfj3QKA6g9wBA5mpAE/qfcXdPzIAgA7ha9/MEVJo/yIRKwEr6xUDPHaJbuq
WbcaEVPpev/XTL+QtUOUaDMfzzqkw7/U3nonHQWTkWOQYqFo9HLOUpRhiL4x00SVnnvS
b69g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to;
bh=h3YWGS1Nxm2tZr+yhXc73HU+Kno+ufvyNiFOFZLjGTU=;
b=QpL8OUzcchrpo81HtoWJQIWSCLhseVhGvGdV3jCc9PVIwbsMUS61cIsxwN8YO4qKAL
3IR2JmR9t3wIdnYCSNT4nGgitx3zJN1vTHdgpLT4x38FochWudgbms8QuNkxOUUSnSpu
iISPua/NcKc9rSeG6aFSRKwHAIvlhnX1FcqHdtoE7S7RDt3HpUP9nUSFJqpoM+Fvg+e7
j4l4OXPNtbuIXNXWVORqDAmmCppY5GrQiHxDJZwzx7Qw3It727ChRqxaDY8vML0kYnyo
uK3wOjxCREm22EE7WVsHdARDQxANmux2IRzsKj+iqMi2W8OYV3tPXjcmmtyXFHdWW79k
lLUQ==
X-Gm-Message-State: AD7BkJI3zUr0841DcDffmYIKKCJKmAbyW6DKqX9aQwMcu7toBPa8BOjTO7CB72oshskjvlV+2WTX24VBAvILZQ==
MIME-Version: 1.0
X-Received: by 10.112.84.105 with SMTP id x9mr8814633lby.23.1459884909016;
Tue, 05 Apr 2016 12:35:09 -0700 (PDT)
Sender: ntamas@gmail.com
Received: by 10.25.15.42 with HTTP; Tue, 5 Apr 2016 12:35:08 -0700 (PDT)
In-Reply-To:
References:
Date: Tue, 5 Apr 2016 21:35:08 +0200
X-Google-Sender-Auth: 61FBuRWVmkNmxMO2i3dfd_CCtnU
Message-ID:
From: Tamas Nepusz
To: Help for igraph users
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2a00:1450:4010:c04::235
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2016 19:35:11 -0000
> 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.
From MAILER-DAEMON Tue Apr 05 21:54:04 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1ancfU-0004mr-7Z
for mharc-igraph-help@gnu.org; Tue, 05 Apr 2016 21:54:04 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:58954)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1ancfQ-0004mb-9S
for igraph-help@nongnu.org; Tue, 05 Apr 2016 21:54:01 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1ancfO-0002zv-BV
for igraph-help@nongnu.org; Tue, 05 Apr 2016 21:54:00 -0400
Received: from mail-vk0-x22b.google.com ([2607:f8b0:400c:c05::22b]:35742)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1ancfO-0002zh-50
for igraph-help@nongnu.org; Tue, 05 Apr 2016 21:53:58 -0400
Received: by mail-vk0-x22b.google.com with SMTP id e6so40843921vkh.2
for ; Tue, 05 Apr 2016 18:53:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to;
bh=d16mBWGaJejEkzv/LVQfpU1zpLgCY6GiFw5DCehY5AE=;
b=LnPVLSFQGdvvEBBBovyeIaUFm8O05G8WyYJ+ebsrBBquC8bVx90lG84x66KekIq0fH
BvUctTZDVxHjQ0J20+BLZ1E7FmqA5+qxmU4HMRi20jy92zR4PCDFm8FDyQyvN3AYvfoX
CuYF26plAommfWPqAs/rVHUilRrZO3BmmWkUhM9SeiIrcHVRuuH/x6DdLpqiKksYQNrL
73Jv+k7tqrJXo6HdOkr6CD+pIoeL1XUVKEMLGA3IxGT6Woo1m7CUY9aXZU3PFEJwA/2O
1Fo9Axdiz5CIQQUC+ZX/2FRi2HCEDes5YhCJTBMx17tVhpcB02TQMMzHLgn8KVcb84hA
qE1w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:to;
bh=d16mBWGaJejEkzv/LVQfpU1zpLgCY6GiFw5DCehY5AE=;
b=iUVvMzyi7TNWO0x+uyQfcfgGirUd8zXrzz2id4C1ZbVCQZQeCA5KThFb+HD6rxhgiG
64l0vrL1ryfaFeaxVWyUb3PfM7c0V6KYjZ3mih/bLyeUK9SiFlBVOaWspnb2aL4eNTch
e96/eC8fCOI+MmNteYL4ZFiw2D2uSuJt7XeS0g/xEBlpNZKKg2Yy7obQMCvj+k6Si3/b
vZDRULlLslB9c+SxGAxG4Z1WXyEmtAQCIt9IeU2xdcMLrk9Q9NoecDS6dpo+7Kc/jO8O
8dE9bk4ARHNlw6zvJzxmRNOr5TlhYOb0xCecIaeA6PlLOXSercv+5hXW03pVtBl3KqDz
Zlgg==
X-Gm-Message-State: AD7BkJLXeMFT7oK9w6JgNjz5C2q2T5CsRAzzumSCmQUi6Pbt/10RVTSGKlYtPpvELJTKT97PBDC6MKg6gDFrKA==
MIME-Version: 1.0
X-Received: by 10.31.135.200 with SMTP id j191mr7623407vkd.91.1459907637550;
Tue, 05 Apr 2016 18:53:57 -0700 (PDT)
Received: by 10.176.1.135 with HTTP; Tue, 5 Apr 2016 18:53:57 -0700 (PDT)
In-Reply-To:
References:
Date: Wed, 6 Apr 2016 08:53:57 +0700
Message-ID:
From: MikeS <4botru@gmail.com>
To: igraph-help@nongnu.org
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2607:f8b0:400c:c05::22b
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 06 Apr 2016 01:54:02 -0000
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 <4botru@gmail.com>:
> 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 :
>> Send igraph-help mailing list submissions to
>> igraph-help@nongnu.org
>>
>> 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
>> igraph-help-request@nongnu.org
>>
>> You can reach the person managing the list at
>> igraph-help-owner@nongnu.org
>>
>> 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
>> To: Help for igraph users
>> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3
>> Message-ID:
>>
>> 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 <4botru@gmail.com> 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 :
>>>> 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 <4botru@gmail.com> 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
>>> igraph-help@nongnu.org
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>> ------------------------------
>>
>> _______________________________________________
>> igraph-help mailing list
>> igraph-help@nongnu.org
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>> End of igraph-help Digest, Vol 117, Issue 5
>> *******************************************
From MAILER-DAEMON Wed Apr 06 04:08:53 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1aniWD-000875-NF
for mharc-igraph-help@gnu.org; Wed, 06 Apr 2016 04:08:53 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:35517)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1aniWA-00086q-8a
for igraph-help@nongnu.org; Wed, 06 Apr 2016 04:08:52 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1aniW8-00084f-FO
for igraph-help@nongnu.org; Wed, 06 Apr 2016 04:08:50 -0400
Received: from mail-lb0-x22d.google.com ([2a00:1450:4010:c04::22d]:36436)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1aniW8-00084T-22
for igraph-help@nongnu.org; Wed, 06 Apr 2016 04:08:48 -0400
Received: by mail-lb0-x22d.google.com with SMTP id qe11so24718930lbc.3
for ; Wed, 06 Apr 2016 01:08:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:sender:in-reply-to:references:date:message-id:subject
:from:to; bh=hkpHYz72/OWUSj/gLg5pP7w9BITJ0wx0sYtTNkJakXg=;
b=zhTmh2e1pmCf4/0wp5uKbM+jrwolQFjLRsiJgmvrBcgfF9T0FU/Wq4sVZnC0qWaL7U
hvonS0hG1/0osg7niKcNWP2HgDuMoseCxC5FFj9D2I9WyOEtBuS1tlC1R0CIJ+kN9pOU
Gm3A7LPcgJ7mgeLpg2g6vQWHvjughH19E6MrZhjVFO2tLB/KSvBJJDYzISVTF4GuYNmw
gE4EIPTTeKecMNi76+L9I24EtwpEf1ip2QULPriTMWzzH4h+WSoQBnuTI+e5gJIKC3yu
4Lq9bIfbu0ZflwpCKslM+1o4ncZVgXTdUtmBAcviLemDIQVAex6qNIonf7wGPj8s+3x0
G8+g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:date
:message-id:subject:from:to;
bh=hkpHYz72/OWUSj/gLg5pP7w9BITJ0wx0sYtTNkJakXg=;
b=Nyz8UAt7F/Pwc/9yh0tmUGpktTotAO8otG2Zw7RYLK8NjaEJDvjzj4gTaCmJ24lcjH
wn6EnCNbPj57QQ3okwhNmmRTejI8VPrV5PRJlN9n1/cEPcW9NBE/ZoLbJEyiB9lahzg9
XQGQpFNYAJMeoOBoISbRVPXP6hBEWqDAxfOwQZZUjTya8SFAod2NVdys6IvdrVj0d09C
8DEXWSMu0qIRXd/2SWQhRLzqb6cMocPx/sZslEbb94lzP6LEyXHlZMdjTmVQGmjJxK+4
DQOh/rdPpLUdv4R4Ksvuto2uyV3DAKU9b4C/Au/fPSkO09I+0eDHLn4zsQ9bAz77ktUv
7KsA==
X-Gm-Message-State: AD7BkJIVWSQ3ldnNM6qIyiH3WHu8Gwe6NRWczIBQHkeWXCRY5xlVEg7wgLK9mH/yRbpzLW2J3nM9289khmzt0A==
MIME-Version: 1.0
X-Received: by 10.112.151.207 with SMTP id us15mr6285620lbb.28.1459930127225;
Wed, 06 Apr 2016 01:08:47 -0700 (PDT)
Sender: ntamas@gmail.com
Received: by 10.25.15.42 with HTTP; Wed, 6 Apr 2016 01:08:47 -0700 (PDT)
In-Reply-To:
References:
Date: Wed, 6 Apr 2016 10:08:47 +0200
X-Google-Sender-Auth: UoRFAYnznHOLhTpucUX9MRAs9Oo
Message-ID:
From: Tamas Nepusz
To: Help for igraph users
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2a00:1450:4010:c04::22d
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 06 Apr 2016 08:08:52 -0000
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 <4botru@gmail.com> 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 <4botru@gmail.com>:
>> 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 :
>>> Send igraph-help mailing list submissions to
>>> igraph-help@nongnu.org
>>>
>>> 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
>>> igraph-help-request@nongnu.org
>>>
>>> You can reach the person managing the list at
>>> igraph-help-owner@nongnu.org
>>>
>>> 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
>>> To: Help for igraph users
>>> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 3
>>> Message-ID:
>>>
>>> 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 <4botru@gmail.com> 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 :
>>>>> 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 <4botru@gmail.com> 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
>>>> igraph-help@nongnu.org
>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>>
>>>
>>> ------------------------------
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> igraph-help@nongnu.org
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>>
>>> End of igraph-help Digest, Vol 117, Issue 5
>>> *******************************************
>
> _______________________________________________
> igraph-help mailing list
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
From MAILER-DAEMON Thu Apr 07 07:07:15 2016
Received: from list by lists.gnu.org with archive (Exim 4.71)
id 1ao7mN-0001lG-BF
for mharc-igraph-help@gnu.org; Thu, 07 Apr 2016 07:07:15 -0400
Received: from eggs.gnu.org ([2001:4830:134:3::10]:38738)
by lists.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1ao7mI-0001cz-6E
for igraph-help@nongnu.org; Thu, 07 Apr 2016 07:07:14 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1ao7mE-0008ON-7v
for igraph-help@nongnu.org; Thu, 07 Apr 2016 07:07:10 -0400
Received: from mail-vk0-x234.google.com ([2607:f8b0:400c:c05::234]:33624)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from <4botru@gmail.com>) id 1ao7mD-0008OF-R4
for igraph-help@nongnu.org; Thu, 07 Apr 2016 07:07:06 -0400
Received: by mail-vk0-x234.google.com with SMTP id k1so94142529vkb.0
for ; Thu, 07 Apr 2016 04:07:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to;
bh=k5I4L1/lQnQM12u/mc+5BgiuFgMq9sBbEdYmpl4jv2E=;
b=xmXi1tHzNBJQDv3aBWZOBaQCoXoQhi2d1hP5HjmGLws8H/mpcQO7qDX3vTmmaW1sSi
es8pSkU0DfI2idXzK5khK8T70Dk2dWn4ATP54/952UovbJnT8IVwxEGZt3rCkcdmBcpI
DuVLzzN0FVRRAmECZj3bS/oUooL4sRg/Q/wf0tpzHWZybx05ZhRagrbtgSa+rOtjq+Wa
2WK2qdS8LvIFfyKsgtOvracbFl0e1xDhtgh0VR2qKh6cn3M7YK043JoTAZZTpBVePm6h
NjAtaxPTWWtUZjwZUrwEKZMUUE/dC8M+V4cb6kQXgEKseSBfiFu9ISUnuwU+HMNb8TBA
4X+g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:to;
bh=k5I4L1/lQnQM12u/mc+5BgiuFgMq9sBbEdYmpl4jv2E=;
b=XRK9N/jcJKdUtTiYBpymhCLD0INus5oT7+oMC/v0fjag6ayROxR7qlrki92jRgLbH2
w5hP9YA6hDn9WyyKQNrB9HXzjMukRwvfUi6wIvVkvVs1x+CxW85Hh2DIK6U3RcREE5S3
Loh4GTxWqo+LanbO+s6B0exO//hppQPCAr9B1fj8N1CdAkyCAzKzMPPWy+uY+4spEsD4
hlJ0pB9NJFJbX/KhFcRn/1m2wPGTFleIDu1warfYpKzcgzQqcEB7wNb8DA0arEuFLUTv
TfI3WAXwT3lYdQz74ElC9j4c28RYoALyBpr2l7zufGpmKddJc7TX6PbThgUEHrRsu6Fk
dukA==
X-Gm-Message-State: AD7BkJKL7i9eGP0ZOcfvw4f8VE5iycLHwFimy0bn1LNCl1M4Ismchpgsf3ycQQnrdvspm0lmwjRWls4eXrcTZQ==
MIME-Version: 1.0
X-Received: by 10.176.2.49 with SMTP id 46mr1115561uas.39.1460027224446; Thu,
07 Apr 2016 04:07:04 -0700 (PDT)
Received: by 10.176.1.135 with HTTP; Thu, 7 Apr 2016 04:07:04 -0700 (PDT)
In-Reply-To:
References:
Date: Thu, 7 Apr 2016 18:07:04 +0700
Message-ID:
From: MikeS <4botru@gmail.com>
To: igraph-help@nongnu.org
Content-Type: text/plain; charset=UTF-8
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2607:f8b0:400c:c05::234
Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 6
X-BeenThere: igraph-help@nongnu.org
X-Mailman-Version: 2.1.14
Precedence: list
Reply-To: Help for igraph users
List-Id: Help for igraph users
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Thu, 07 Apr 2016 11:07:14 -0000
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 :
> Send igraph-help mailing list submissions to
> igraph-help@nongnu.org
>
> 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
> igraph-help-request@nongnu.org
>
> You can reach the person managing the list at
> igraph-help-owner@nongnu.org
>
> 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 <4botru@gmail.com>
> To: igraph-help@nongnu.org
> Subject: Re: [igraph] igraph-help Digest, Vol 117, Issue 5
> Message-ID:
>
> 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

I've been using igraph=
(with python) some months now in my research.

First of all, than=
k you very much for this great piece of software.

=
So, right to the point: I have a performance issue and need advise on usage=
of the library.

I'll detail the scenario below.

Graph properties:

undirected, unweighted

n=
umber of vertices: ~1.7 million

number of edges: ~125 million=

Operation being performed:

Given two sa=
mples of vertices, compute the distance between each pair (the distance is =
upper bounded to a fixed value, say 120).

size of sample 1 is ~10=
0 k

size of sample 2 is ~1 k

My implemen=
tation:

for each of the 100 million pairs:

=C2=A0 =C2=
=A0 =C2=A0 call get_shortest_paths()

=C2=A0 =C2=A0 =C2=A0 take th=
e min between 120 and the length of the list of edges in the shortest path<=
/div>

The issue:

each call to get_shortest_pat=
hs() takes from ~5s to ~30s

I'm=
clearly wasting efforts because:

- get_shortest_paths() returns =
the actual path between the two nodes, but I'm only interested in the d=
istance (I need something like "get_shortest_distance")

-=C2=A0get_shortest_paths()=C2=A0processes until it reaches destination no=
de, but since we have an upper bound, I'd suffice to use a "cutoff=
" value=C2=A0for the distance calculation

So, I'd like to know if (and how) is it possible to perform=
better.

Felipe

<= /div>