August 2014 - graph-tool - archives.skewed.de

Interpreting min_dl (min value of nats per edge) for blockmodel on multigraphs
by ayates 16 Aug '14

16 Aug '14

How would one best interpret the min_dl value returned by minimize_nested_blockmodel_dl and minimize_blockmodel_dl when a multigraph (weighted) graph is processed? The min_dl for a multigraph can be much lower for the same graph without multiplicities. What is a reasonable way to explain, using the min_dl values, that a multigraph version of graph produces a "better" (or not) description of the same graph without multiplicities? -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

2 1

Using an edge_property on GraphView
by ayates 16 Aug '14

16 Aug '14

Is it correct to use an edge property map of a graph with a graph view based on that graph? Specifically, I have an edge property of edge weights. I then filter the graph to the largest connected component, and then I want to run nested blockmodel on that largest connected component with the corresponding edge weights. The exact code I want to use is below. Is this correct, or do I need to also filter weight_prop so that it only has information about edges not filtered in the GraphView GL? Thank you so much! EDGES, WEIGHT_V = get_edge_set(ADJ, WEIGHTS, N, K) G = gt.Graph() G.add_vertex(N) G.add_edge_list(EDGES) G.set_directed(False) largest = graph_tool.topology.label_largest_component(G) GL = gt.GraphView(G, vfilt=largest) weight_prop = G.new_edge_property("int16_t") weight_prop.a = WEIGHT_V NBM = graph_tool.community.minimize_nested_blockmodel_dl(GL, verbose=True, epsilon=E, eweight=weight_prop) -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

2 1

PropertyMap._get_data
by Dominik 15 Aug '14

15 Aug '14

Hi, I have a code that accesses pmap.a for a PropertyMap pmap attached to vertex-filtered GraphView quite frequently. The function PropertyMap._get_data calls the GraphView constructor every time, simply to construct a non-filtered graph view from which it obtains e.g. the number of vertices for vertex properties. Quite some time is spent in this constructor cumulatively, since it is called millions of times from _get_data in my case. It seems to me that there could be a simpler solution if the API is extended a bit. See in graph.cc Actually, all we might want to do, is to use SoftNumVertices despite working on a vertex-filtered graph, right? So, we don't need to construct a non-filtered graph. Is that correct? It could be kind of a "GetUnfilteredNumberOfVertices". BR, Dominik -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

2 1

Speeding up minimize_nested_blockmodel_dl on large networks?
by ayates 14 Aug '14

14 Aug '14

Hi, I am having some trouble reproducing the performance of minimize_nested_blockmodel_dl on large networks as in the publication "Hierarchical block structures and high-resolution model selection in large networks"? Namely, for large graphs, even with verbose=True, no output is generated, but the CPU usage stays at 100% for hours to days. My network contains 1.5 million nodes and a sorted adjacency list per node such that I can choose the top K edges per node as a parameter. I have tried sampling down to 200,000 nodes and K=5, but minimize_nested_blockmodel_dl does not seem to be proceeding with computation. CPU is being used at 100% while running , and there is plenty of free memory. Are there options that I can use in minimize_nested_blockmodel_dl to improve performance? Other than sampling and limiting K, are there other strategies that I can try? I compiled using the parallel computing option and am using AWS EC2 instances. The largest network that I have been able to get a result for within 24 compute hours on C3 sized EC2 instances has been 100,000 nodes, K=5. (undirected, average degree about 8) -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

2 2

Energy minimization problem
by Quentin Oliveau 11 Aug '14

11 Aug '14

Dear all, I recently discoverd the graph-tool library so first of all congratulation for this development and the nice documentation. As a non "graph" guy I'm currently facing some trouble trying to adapt an energy minimization problem using the boykov_kolmogorov_max_flow function. The goal is to reproduced the work of this paper <https://www.cis.uab.edu/kddm/seminar_home/Lin_Sept25_tree-camera-ready.pdf> (page 3) which uses the max flow function on an 8 connected image where each pixels are discribed by a discrete value (0 or 1) and a probability. I'm still wondering what's the best way to create an 8-connected graph from an array and how to deal with the dual description of the pixels. I some of you have some tips to share, i would gladely listen to them. Thanks in advance,

2 1

simulated annealing energy function
by de 11 Aug '14

11 Aug '14

Hi, Tiago, first of all, let me express my appreciation to your great work - and that you share it with others! it somewhat related to issues #62 <https://git.skewed.de/count0/graph-tool/issues/62> and #29 <https://git.skewed.de/count0/graph-tool/issues/29> - which are about giving more algorithms for community detection - which i think is very important. However, I would like to use simulated annealing(SA) algo - with a different quality(modularity) function, than of Newman. you indeed gave some "freedom", letting the user to define gamma.However if I want to use another function for some reason with SA , there is apparently no way to do it. Looking at the code(graph_community.hh ), I saw that the SA mechanism is not separated from the energy function itself ( that Newman with gamma=1, you give here <https://graph-tool.skewed.de/static/doc/community.html#graph_tool.community…> ). I see no reason for this , as SA algo could be used with many energy functions. I hope in the future you can fix it, and even maybe somehow give the user an API to set the energy function(?) from the python code. Thanks. -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

2 1

simulated annealing energy function
by de 10 Aug '14

10 Aug '14

it somewhat related to issues #62 <https://git.skewed.de/count0/graph-tool/issues/62> and #29 <https://git.skewed.de/count0/graph-tool/issues/29> - which are about giving more algorithms for community detection - which i think is very important. However, I would like to use simulated annealing(SA) algo - with a different quality(modularity) function, than of Newman. you indeed gave some "freedom", letting the user to define gamma.However if I want to use another function for some reason with SA , there is apparently no way to do it. Looking at the code(graph_community.hh ), I saw that the SA mechanism is not separated from the energy function itself ( that Newman with gamma=1, you give here <https://graph-tool.skewed.de/static/doc/community.html#graph_tool.community…> ). I see no reason for this , as SA algo could be used with many energy functions. I hope in the future you can fix it, and even maybe somehow give the user an API to set the energy function(?) from the python code. Thanks. -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

1 0

Fastest way to iterate through edges
by ... 08 Aug '14

08 Aug '14

Hi all, I haven't been on the list very long but I see this question keeps coming up. I just thought I put some numbers out so people know. Graph tool is super fast at doing the c++ stuff it does, and super convenient for picking through the data on a python level also, but it doesn't make python fast. So, here are some examples of working with a mask in Python. Notice that numpy is not fast just because it is numpy. I chose an Nx3 array because numpy masking is extra slow with shapes other than Nx1. ================ import numpy as np a_generator = ((x,x+2,x*x) for x in range(1000)) a_list =[(x,x+2,x*x) for x in range(1000)] a_array = np.array(a_list) mask = np.ones((len(a_array)),dtype=np.bool) mask[::3] = False def tupled(): for x,b in zip(a_generator,mask): if b: c,d,e =x def looped(): for x,b in zip(a_list,mask): if b: c,d,e =x def masked(): for x in a_array[mask]: c,d,e = x #IPython magic function: timeit %timeit tupled() 1000000 loops, best of 3: 510 ns per loop %timeit looped() 10000 loops, best of 3: 76.6 µs per loop %timeit masked() 1000 loops, best of 3: 445 µs per loop ================ Notice the nano seconds vs micro seconds. The generator is the clear winner. Now, here are some graph tool specific examples. I left out the mask, but clearly you can create and manipulate a mask as you see fit. ================= >>>graph <Graph object, directed, reversed, with 32183 vertices and 199381 edges at 0x7f62842ee9d0> >>>def graph_loop0(): for i in range(10): #Only 10 times because this is soooo slooow for e in graph.edges(): v1,v2 = e.source(),e.target() >>>def graph_loop1(): edges = [[e.source(),e.target()] for e in graph.edges()] for i in range(1000): for e in edges: v1,v2 = e[0],e[1] >>>def graph_loop2(): edges = [[e.source(),e.target()] for e in graph.edges()] gen = (e for e in edges) for x in range(1000): for e in gen: v1,v2 = e[0],e[1] >>>from time import time >>>a=time(); graph_loop0(); print time()-a 23.1095559597 >>>a=time(); graph_loop1(); print time()-a 15.721350193 >>>a=time(); graph_loop2(); print time()-a 2.80044198036 ======================= The loop1 and loop2 are doing 100x more, so the generator is 1000x faster. If you're just looping through once, it makes sense to use the convenience graph_tool provides. But if you are implementing a graph algorithm, just grab what you need from the graph_tool graph into a list or whatever python object makes sense for what you're doing. -Elliot

2 2

Accessing vertex/edge indices
by Helen Lampesis 05 Aug '14

05 Aug '14

Hello graphGang! I have some relative simple (but also quiet practical) questions for you. 1. How can you access the indices of the nodes of an arbitrary graph? - You can not assume that they are equal to the "range(graph.num_vertices())”. For instance, imagine that we are dealing with a filtered version of some graph. - Is there another way than invoking the iterator graph.vertices() ? The application I have at hand is to sample pairs of nodes of a graph and apply a function like the shortest distance between them (and I would like to do that fast). 2. I think that when it comes to sampling/accessing of the indices of edges there is not a better way than invoking the iterator graph.edges() and work with its output. Correct? Thanks a lot, H.

3 3

Python 3.4.0 import error
by marklasta 01 Aug '14

01 Aug '14

Hi there, I'm from my Linux Box, currently running Xubuntu 14.04 64 with Python 3.4.0 and facing the following trouble: at from graph_tool.all import * I get this: ** (.:2907): WARNING **: Couldn't connect to accessibility bus: Failed to connect to socket /tmp/dbus-7yP0jhxsND: Connection refused I really do not know how to solve it ! Any suggestions ? -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

2 1