Re: [igraph] What is the fast way to find the maximum out-component in a

On Thu, Feb 27, 2014 at 2:47 AM, address@hidden <address@hidden> 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

address@hidden

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 <address@hidden> wrote:

First measure what exactly is slow with Rprof().

Gabor

On Wed, Feb 26, 2014 at 9:41 PM, address@hidden <address@hidden> 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

address@hidden

_______________________________________________
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

From:	address@hidden
Subject:	Re: [igraph] What is the fast way to find the maximum out-component in a erdos-renyi random graph
Date:	Fri, 28 Feb 2014 09:46:45 +0800