Most efficient way to access all nodes in a block

classic Classic list List threaded Threaded
4 messages Options
P-M
Reply | Threaded
Open this post in threaded view
|

Most efficient way to access all nodes in a block

P-M
Hello,

I have just fitted an SBM to my graph. Having run state =
gt.minimize_nested_blockmodel_dl(g, deg_corr=True) I now would like to
investigate the results a bit more closely. More specifically I am after the
best way to access all vertices assigned to a given block.

I can use get_levels() and then get_blocks() to obtain the block membership
of each vertex and from that I can use find_vertex() for a given block
number to find the list of all vertices in that block which I can then use
to loop through them. I wonder, however, if there is a more efficient way of
obtaining all vertices in a given block?

My current pseudo code looks something like the following:

state = gt.minimize_nested_blockmodel_dl(g, deg_corr=True)
#now do something for all vertices in each of the blocks
levels = state.get_levels()
graphs = state.get_bstacks() #Return the nested levels as individual graphs.
num_blocks = graphs[1].num_vertices() #find the number of blocks at level 0
blocks = levels[0].get_blocks() #Returns property map with block labels for
each vertex.
for i in range(num_blocks): #cycle through all blocks
    vs = gt.find_vertex(g,blocks,i)
    for v in vs: #cylce through all vertices in a given block
        do something

Is there some more efficient way of doing this that I am missing? I would
ideally ultimately run it after each sweep of the mcmc algorithm so would
like to minimise looping that I am doing in python if graph-tool has methods
for what I am doing which will, presumably, be faster.

Thank you for any advice in advance!

With best wishes,

Philipp



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
P-M
Reply | Threaded
Open this post in threaded view
|

Re: Most efficient way to access all nodes in a block

P-M
(I should probably add that I am only interested in relations between the
nodes in a given block with each other, so am happy to work with vertex
filters.)



--
Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Most efficient way to access all nodes in a block

Alexandre Hannud Abdo
Ni! Hi Philipp,

Yes, there are more straightforward paths to the same information:

# get some graph and model it
import graph_tool.all as gt
g = gt.collection.data["celegansneural"]
s = gt.minimize_nested_blockmodel_dl(g)

# get your groups of vertices in a dictionary
l0 = s.levels[0]
block2vertices = dict()
for i in range(l0.B):
    block2vertices[i] = gt.find_vertex(l0.g, l0.b, i)

Cheers
.~´


On Tue, Jun 19, 2018 at 7:01 PM, P-M <[hidden email]> wrote:
(I should probably add that I am only interested in relations between the
nodes in a given block with each other, so am happy to work with vertex
filters.)


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Most efficient way to access all nodes in a block

Tiago Peixoto
Administrator
Am 19.06.2018 um 21:01 schrieb Alexandre Hannud Abdo:

> Ni! Hi Philipp,
>
> Yes, there are more straightforward paths to the same information:
>
> # get some graph and model it
> import graph_tool.all as gt
> g = gt.collection.data["celegansneural"]
> s = gt.minimize_nested_blockmodel_dl(g)
>
> # get your groups of vertices in a dictionary
> l0 = s.levels[0]
> block2vertices = dict()
> for i in range(l0.B):
>     block2vertices[i] = gt.find_vertex(l0.g, l0.b, i)

Since find_vertex() is O(N), the above is O(B * N). A faster O(N) approach
is simply:

groups = defaultdict(list)
for v in g.vertices():
   groups[l0.b[v]].append(v)

Best,
Tiago
--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <tiago@skewed.de>