|
From: | Gábor Csárdi |
Subject: | Re: [igraph] What is the fast way to find the maximum out-component in a erdos-renyi random graph |
Date: | Thu, 27 Feb 2014 09:04:13 -0500 |
HiThank youIt 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 NaNAm 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).bestXueming
From: Gábor CsárdiDate: 2014-02-27 11:47Subject: Re: [igraph] What is the fast way to find the maximum out-component in a erdos-renyi random graphBtw. 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 <address@hidden> wrote:
First measure what exactly is slow with Rprof().Gabor
_______________________________________________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-componentand 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")$membershipSGer2_CluSiz=clusters(ER2, "strong")$csizeSGer2_CluNum=clusters(ER2, "strong")$noNummax <-0for (i in 1:SGer2_CluNum){if (SGer2_CluSiz[i] > Nummax){Nummax <- SGer2_CluSiz[i]Maxmem <- i}}GSCCnod <- rep(0, Nummax)j <- 1for (i in 1:100000){if (SGer2_CluMem[i] == Maxmem){GSCCnod[j] <- ij <- 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 youBestXueming
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
[Prev in Thread] | Current Thread | [Next in Thread] |