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.
> 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
