1

Say that I have a big network with 10^4 nodes. And then I want to analyse the neighbourhood associated with a random node, say node 10. I can see which are the nodes connected to that node by looking at the 10th row entries of the adjacency matrix, and then I can repeat this if I want to look at the neighbours of those neighbours (second shell) and so on and so forth.

Is there an efficient way to do this - or even an inefficient but better than writing the whole thing from the scratch-? The actual network that I have is a Random Regular Graph and I am interested on the tree-like local structure for large networks.

dapias
  • 2,512
  • 3
  • 15
  • 23

1 Answers1

4

If I understand your use case, there is a good way of doing this: the egonet function. You give it a graph, a starting vertex, and number of hops, and it will return an induced subgraph of the graph starting at the vertex and going out that number of hops. Here's the docstring:

  egonet(g, v, d, distmx=weights(g))

  Return the subgraph of g induced by the neighbors of v up to distance d, using weights (optionally) provided by distmx. This is equivalent to
  induced_subgraph(g, neighborhood(g, v, d, dir=dir))[1].

  Optional Arguments
  ––––––––––––––––––––

    •    dir=:out: if g is directed, this argument specifies the edge direction

  with respect to v (i.e. :in or :out).

Edited to add: if all you need are the vertex indices, then neighborhood() is what you want:

neighborhood(g, v, d, distmx=weights(g))                                                                                                            
                                                                                                                                                      
  Return a vector of each vertex in g at a geodesic distance less than or equal to d, where distances may be specified by distmx.                     
                                                                                                                                                      
  Optional Arguments                                                                                                                                  
  ––––––––––––––––––––                                                                                                                                
                                                                                                                                                      
    •    dir=:out: If g is directed, this argument specifies the edge direction                                                                       
                                                                                                                                                      
  with respect to v of the edges to be considered. Possible values: :in or :out.
sbromberger
  • 1,026
  • 6
  • 12