CODEWITHSUNDEEP
rigraphbreadth-first-searchgraph-traversal
EUps
EUps

Reputation: 41

Using bfs (igraph, R) to sample from my large graph

I have a large graph and would like to "chunk it up" using a breadth-first search approach. That is, I will randomly pick a starting vertex, and then perform a BFS until I am left with a graph with (for example) 100 vertices. This is a process I plan to repeat a number of times, so that eventually, I have a number of different sub-graphs of my large graph. At the moment, here is how I am coding this up in R (this is just an example, my graph is not a ring). 

y <- make_ring(1000)
bfsy <- bfs(y, root=1, "all", order=TRUE)
suby <- bfsy$order[1:100]
newgraph = induced.subgraph(y, suby)

Obviously, this is not efficient, since I perform the whole BFS and I only need 100 vertices. Any hints on how to code this better? And, any hints on how I might randomize this process even more by randomizing queue order at each new stage (this is my next problem to tackle, ha)? Referrals to textbooks/papers area always appreciated.

Upvotes: 1

Views: 1288

Answers (2)

Saeid
Saeid

Reputation: 4265

I am not familiar with R, but I think you can do this easily by using your own graph traversal method. Simply modify BFS or DFS to follow your requirements:

VERTICES = 100
RANDOM_CHANCE = 0.5

Breadth-First-Search(Graph, root):

     create empty queue Q      

     Q.enqueue(root)
     visited.put(root)     
     create empty list Edges        

     # this will stop the BFS after reaching to a certain amount of nodes
     while Q is not empty AND visited.size() <‌ VERTICES:        
         current = Q.dequeue()

         for each node n that is adjacent to current:
             if n in visited:
                 continue
             # This will randomly choose the edges
             if random() < RANDOM_CHANCE:
                 continue
             Q.enqueue(n)
             visited.put(n)
             Edges.put( current->n )

In the end your sub-graph is consist of the nodes visited and edges in Edges. You can tweak the value of VERTICES and RANDOM_CHANCE to get different kinds of graphs. Also you can put the restriction on the number of edges too.

You can apply a similar method on DFS. DFS will give you graphs that have more depths.

Upvotes: 0

Sandipan Dey
Sandipan Dey

Reputation: 23109

You can try to use the callback function parameter as follows, also you can use the extra parameter:

y <- make_ring(1000)
f <- function(graph, data, extra) {
 data['rank'] == 100
}
bfsy  <- bfs(y, root=1, "all", order=TRUE, callback = f)

bfsy$order # only the first 100 values are not NAs
+ 1000/1000 vertices:
   [1]    1    2 1000    3  999    4  998    5  997    6  996    7  995    8  994    9  993   10  992   11  991   12  990   13  989   14  988
  [28]   15  987   16  986   17  985   18  984   19  983   20  982   21  981   22  980   23  979   24  978   25  977   26  976   27  975   28
  [55]  974   29  973   30  972   31  971   32  970   33  969   34  968   35  967   36  966   37  965   38  964   39  963   40  962   41  961
  [82]   42  960   43  959   44  958   45  957   46  956   47  955   48  954   49  953   50  952   51  951   NA   NA   NA   NA   NA   NA   NA
 [109]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [136]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [163]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [190]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [217]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [244]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA

suby <- bfsy$order[1:100]
newgraph = induced.subgraph(y, suby)

Upvotes: 1

Related Questions