Yes, it is because that i used an old version of igraph.
Thank you so much for help me to fix the question and I will remember to
present reproducible code next time.
best for you
xueming
[email protected]
From: Gábor Csárdi
Date: 2014-02-27 22:04
To: Help for igraph users
Subject: Re: [igraph] What is the fast way to find the maximum out-component in
a erdos-renyi random graph
On Thu, Feb 27, 2014 at 2:47 AM, [email protected] <[email protected]>
wrote:
Hi
Thank you
It is really fast, but the elements of scc_bfs$order are all NaN.
I set root to other array which with more than one element, the result of
graph.bfs()$order is NaN.
You are probably using an old version of igraph that had a bug in graph.bfs()
and considered only the first vertex in 'root'. Please install the latest
version.
Btw. if you want your example to be reproducible, please include 1) your igraph
version, and 2) set the random seed if you are using random graphs. Thanks.
Gabor
> library(igraph)
> ER2 <- erdos.renyi.game(100, 200, "gnm", directed=TRUE)
> graph.bfs(ER2, root=2, neimode="out",unreachable=FALSE)$order
[1] 2 14 59 64 4 23 82 77 85 93 9 58 25 54 32 33 76 62
65 74 98 100 41 29 60
[26] 18 56 80 1 5 86 95 15 89 43 44 52 34 81 84 53 6 91
99 49 63 66 72 10 45
[51] 22 57 21 27 70 97 30 75 40 92 96 11 71 73 87 39 79 94
51 61 37 48 47 68 13
[76] 35 46 16 83 31 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
NaN NaN NaN NaN NaN NaN NaN
> graph.bfs(ER2, root=c(1, 2), neimode="out",unreachable=FALSE)$order
[1] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
NaN NaN NaN NaN NaN NaN NaN
[26] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
NaN NaN NaN NaN NaN NaN NaN
[51] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
NaN NaN NaN NaN NaN NaN NaN
[76] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
NaN NaN NaN NaN NaN NaN NaN
Am I making some other mistakes?
BTW: Usually, a out-component is defined as the out-component of a strongly
connected component. The giant strongly connected component and the giant
out-component appear at the same time (Ref: Marian Bouguna et al, Ceneralized
percolation in random directed networks, Physic Review E 72, 016106, 2005).
best
Xueming
[email protected]
From: Gábor Csárdi
Date: 2014-02-27 11:47
To: Help for igraph users
Subject: Re: [igraph] What is the fast way to find the maximum out-component in
a erdos-renyi random graph
Btw. if the maximum out-component is defined as the out-component of the
largest strongly connected component (what if there is no largest, btw?), then
all you need to do is to do a BFS from the vertices of the largest strongly
connected component:
library(igraph)
ER2 <- erdos.renyi.game(100000, 200000, "gnm", directed=TRUE)
scc <- clusters(ER2, mode="strong")
largest_scc_v <- which(scc$membership == which.max(scc$csize))
scc_bfs <- graph.bfs(ER2, root=largest_scc_v, neimode="out",
unreachable=FALSE)
reachable <- na.omit(scc_bfs$order)
out_comp <- setdiff(reachable, largest_scc_v)
This whole thing takes less than a second on my laptop.
Gabor
On Wed, Feb 26, 2014 at 9:59 PM, Gábor Csárdi <[email protected]> wrote:
First measure what exactly is slow with Rprof().
Gabor
On Wed, Feb 26, 2014 at 9:41 PM, [email protected] <[email protected]>
wrote:
Hi!
Iam trying to find the maximum out-component in a erdos-renyi random graph.
Using the array GSCCnod to record the vertices in the maximum strongly
connected component,
Goutnod to record that if a vertice is in the maximum out-component:
Goutnod[i]==-1 means that vertice i is not in the maximum out-component
and Goutnod[i]==1 means that vertice i is in the maximum out-component.
But the graph contains too many vertices. It takes too much time to compute
Goutnod. How can I make it faster.
Here is the source code:
ER2 <- erdos.renyi.game(100000, 200000, "gnm", TRUE)
SGer2_CluMem=clusters(ER2, "strong")$membership
SGer2_CluSiz=clusters(ER2, "strong")$csize
SGer2_CluNum=clusters(ER2, "strong")$no
Nummax <-0
for (i in 1:SGer2_CluNum)
{
if (SGer2_CluSiz[i] > Nummax)
{
Nummax <- SGer2_CluSiz[i]
Maxmem <- i
}
}
GSCCnod <- rep(0, Nummax)
j <- 1
for (i in 1:100000)
{
if (SGer2_CluMem[i] == Maxmem)
{
GSCCnod[j] <- i
j <- j + 1
}
}
Goutnod <- rep(-1,100000)
for (i in 1:Nummax)
{
gout <- subcomponent(ER2, GSCCnod[i], "out")
len <- length(gout)
for (k in 1: len)
Goutnod[gout[k]] <- 1
}
Thank you
Best
Xueming
[email protected]
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
