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

[address@hidden]



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

---

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