graph-tool September 2017

graph-tool@skewed.de

10 participants
21 discussions

Help with animating a graph
by Stefan Vujovic 02 Oct '17

02 Oct '17

Hello Tiago, I am trying to make an animation using Graph tool. My data is preety simple, i have a interactions between two vertices and timestamps of those interactions, something like this: time vertex_id vertex_id 1830 356 681 1835 12 590 1835 123 456 What i am trying to do, is to show all interactions per time step, therefore i would like to animate edges, display all edges (interactions) that happen at a certain time step. What i don't get is how to loop through the list of timestamps. Should I even do it like this. I imagine looping through the list of timestamps, where every time stamp points to a list of all the edges and then I somehow (unclear how) display them. Also, what happens in the update_state function from this page https://graph-tool.skewed.de/static/doc/demos/animation/animation.html is a bit unclear to me. Could you please help me somehow? Is there any other resource/documentation I could look at, because a lot of the code from the example is like magic to me. Best regards, Stefan

3 2

all_circuits crashes on 2.22
by pampalini 27 Sep '17

27 Sep '17

Hi all, I'm running 2.22 on Ubuntu 16.04. Iterating over all_circuits() results in a segmentation fault. e.g., cycles = gt.all_circuits(G) for c in cycles: ... I also tried iterating over it by cycles.next() to see which cycle causes the crash. Turns out it crashes sporadically at different iterations. Sometimes on the first, sometimes on the seventh, etc. This happens for all combinations of python 2.7 and python 3.6 under WSL 16.04 or pure 16.04 Ubuntu. My cursory search didn't get me anywhere. Is this a bug or an error on my part? Your help is appreciated, -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 2

Public key not available
by P-M 27 Sep '17

27 Sep '17

Hello, When updating via apt-get on Ubuntu 16.04 I get an error message saying: Err:20 http://downloads.skewed.de/apt/xenial xenial Release.gpg The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 78AF38AD52B46290 Re-adding the keys as outlined in the installation instructions seems to fix the problem but I wanted to check if this was expected behaviour. Thanks for any advice in advance. Best, Philipp -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 1

Accessing the integer attribute in Vertex/Edge object directly/faster
by 肖晗 21 Sep '17

21 Sep '17

Hi, Given a `graph_tool.Edge` instance, is it possible to directly access the integer value (or its index value) of the source vertex and target vertex? My current solution is ``` s = int(e.source()) t = int(e.target()) ``` I have some function that calls the above routine many times and it is not fast enough. I am wondering if I can do it faster. Similarly, can I access the index/integer value of a Vertex object directly? -- Best Han

2 1

minimize_nested_block_model_dl speed and memory tweaks
by flxvctr 21 Sep '17

21 Sep '17

G'day! I'm struggling with a network with millions of nodes and billions of edges (follow network of Australian Twitter users), trying to apply gt.inference.minimize_nested_block_model_dl(). I'm reducing the size by analysing k-cores and increasing k step-wise to test the limits. With 19k nodes and 12m edges I'm already exceeding the 64GB RAM my machine has at the moment, so given its O(n ln^2(n)) I don't expect the whole network to fit, but I'd like to push the limit at least as far as possible. The only parameter set so far is `mcmc_equilibrate_args={'epsilon': 1e-3}`. I have four questions: 1. I've tried mcmc_args={'sequential': False, 'parallel': True}, but this did not seem to have a great impact regarding speed on my smaller k-cores, could it have on bigger ones? 2. What does the warning here (https://graph-tool.skewed.de/static/doc/inference.html#graph_tool.inference…) regarding parallel sampling mean in worst case and when is it likely that the warning actually applies? 3. I am considering either to try to fund a machine with more (expensive) RAM or to just swap memory on freely available disk space. What would you expact would be the impact on speed? Checking the behaviour of the algorithm so far I don't see it being I/O bound but rather by available memory and the sequential parts of the algo that are running on one core only. Is swapping a considerable option or should I just straight away rent a bigger machine? 4. Is there any rule of thumb for epsilon? And what is its impact if it's too large? Thanks for any help (maybe also hints how to reduce the network size while minimising the impact on the results of the nested SBM with something more sophisticated than k-cores). Cheers, Felix -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 1

Integrating edmond's algorithm in boost graph with graph_tool
by 肖晗 20 Sep '17

20 Sep '17

Hi, I am trying to integrate a boost graph implementation <https://github.com/atofigh/edmonds-alg> of Tarjan's optimal branching algorithm with graph_tool The code is in pure C++ and I want to wrap it using boost python. The ultimate goal is I can pass in a `graph_tool.Graph` instance to the wrapped function directly. For example: ``` from graph_tool.generation import complete_graph from pyedmond import optimal_branching # suppose I made it already, pyedmond is the name of the module after wrapping g = complete_graph(1000, directed=True) optimal_branching(g) # it runs and give the correct result. ``` ----------------- My attempt (with code example <https://github.com/xiaohan2012/pyedmond>): instead of using `graph_tool.Graph`, I created another graph type using boost graph (in C++), say the name is `MyGraph`. Then I pass the edges and weights in `graph_tool.Graph` (in Python) to `MyGraph` (in C++) via boost python so that a new MyGraph is created. Last I pass in the MyGraph instance to the optimal branching function in C++. I do this "graph copying" because `graph_tool.Graph` does not match the signature of the optimal branching function, which requires: ``` boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> ``` ---------------- My question is: Can I circumvent the graph copying procedure? -- Best Han

2 2

Re: [graph-tool] Infinite looping in hierarchy_minimize
by Valery Topinsky 20 Sep '17

20 Sep '17

Hello Tiago. There is the example code which cause the same infinite looping: > *import numpy as np* > *from graph_tool.all import ** > *gg = collection.data['football']* > *dummy_type = np.array(map(lambda x: int('state' in x.lower()), > gg.vp.label.get_2d_array([0])[0]))* > *dummy_weights = gg.new_edge_property('double')* > *dummy_weights.a = edge_endpoint_property(gg, gg.vp.value, "source").a - > edge_endpoint_property(gg, gg.vp.value, "target").a* > *test = minimize_nested_blockmodel_dl(gg, deg_corr=False, b_min = > dummy_type, B_max = 50, B_min=5,* > * state_args=dict(clabel = > dummy_type, * > * recs = > [dummy_weights],* > * rec_types = > ['real-normal']* > * ), ** > verbose=True)* My investigation showed that the issue occurs only if I have simultaneously two things: *clabel constraint* and *real-normal covariates* for edges. If I remove one of them - everything is fine, If I change the covariates type from normal to any other -- again, no looping. This specific *clabel* forces for bisection search degenerated bounds (min_state = max_state), and normal covariates some how affects on entropy calculus. As I understand, the problem is in potentially wrong entropy calculation here: https://git.skewed.de/count0/graph-tool/blob/master/src/graph_tool/inferenc… As we saw from outputs, code is trying to replace (N=2, B=1) with (N=2, B=2) and is getting lower entropy. Here https://git.skewed.de/count0/graph-tool/blob/master/src/graph_tool/inferenc… I found that only in case of normal covariates you have subtraction for entropy, hence potentially smaller entropy for more sophisticated model. Hope, it helps. Thank you, Valeriy.

2 1

Fastest way to get a random neighbor
by balazshoranyi01 15 Sep '17

15 Sep '17

Hi There, I was wondering what your thoughts were on the fastest way to get a random neighbor of a vertex? Right now I am doing something like: / outid = G.get_out_neighbours(v) outid = random.choice(outid)/ I'm trying to implement a type of random walk and have the above code wrapped in a for loop ~ 100000 iterations. Is there a better way to implement this? Thanks! -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 1

Question about output of `get_edges_prob` for spurious edges
by Philipp-Maximilian Jacob 12 Sep '17

12 Sep '17

Dear Tiago, I am trying to understand the output of get_edges_prob when using it for spurious edges. What value is the routine returning? Am I getting the "likelihood" of the edge being spurious or the "likelihood" of it "actually" existing? Say, if I have two edges I am assuming to be spurious, "a" and "b", and edge "a" scores a higher likelihood ratio value than edge "b" (having used `s.get_edges_prob([],[a], entropy_args=dict(partition_dl=False))` and `s.get_edges_prob([],[b], entropy_args=dict(partition_dl=False))`). Is "a" more likely to be a spurious edge than "b" or is it the other way round (i.e. "a" being more likely to indeed exist than "b")? Best, Philipp

3 4

Infinite looping in hierarchy_minimize
by Valery Topinsky 07 Sep '17

07 Sep '17

Hello. I'm trying to test the latest version of graph_tool (0.23dev) and building the nested sbm with edge weights. I'm launching the following command: minimize_nested_blockmodel_dl( graph, deg_corr=False, b_min = graph.vp.ikind, B_max = 150, B_min = 5, mcmc_equilibrate_args = dict(wait = 100, nbreaks=2, max_niter=100000), mcmc_args = dict(niter=10), state_args = dict( clabel = graph.vp.ikind, recs = [ln2rev], rec_types = ['real-normal'] ), verbose=True, ) And can see that there is infinite looping: ... level 386 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 387 l=387 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=387 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=387 Bisect at B = 2 with S = 34.5778592783179 l=387 Best result: B = 2, S = 34.5778592783179 level 387 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 388 l=388 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=388 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=388 Bisect at B = 2 with S = 34.5778592783179 l=388 Best result: B = 2, S = 34.5778592783179 level 388 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 389 l=389 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=389 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=389 Bisect at B = 2 with S = 34.5778592783179 l=389 Best result: B = 2, S = 34.5778592783179 level 389 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 390 l=390 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=390 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=390 Bisect at B = 2 with S = 34.5778592783179 l=390 Best result: B = 2, S = 34.5778592783179 level 390 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 391 l=391 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=391 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=391 Bisect at B = 2 with S = 34.5778592783179 l=391 Best result: B = 2, S = 34.5778592783179 level 391 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 392 l=392 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=392 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=392 Bisect at B = 2 with S = 34.5778592783179 l=392 Best result: B = 2, S = 34.5778592783179 level 392 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 393 l=393 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=393 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=393 Bisect at B = 2 with S = 34.5778592783179 l=393 Best result: B = 2, S = 34.5778592783179 level 393 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 394 l=394 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=394 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=394 Bisect at B = 2 with S = 34.5778592783179 l=394 Best result: B = 2, S = 34.5778592783179 level 394 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 395 l=395 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=395 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=395 Bisect at B = 2 with S = 34.5778592783179 l=395 Best result: B = 2, S = 34.5778592783179 level 395 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 396 l=396 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=396 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=396 Bisect at B = 2 with S = 34.5778592783179 l=396 Best result: B = 2, S = 34.5778592783179 level 396 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 397 l=397 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=397 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=397 Bisect at B = 2 with S = 34.5778592783179 l=397 Best result: B = 2, S = 34.5778592783179 level 397 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 398 l=398 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=398 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=398 Bisect at B = 2 with S = 34.5778592783179 l=398 Best result: B = 2, S = 34.5778592783179 level 398 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 399 l=399 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=399 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=399 Bisect at B = 2 with S = 34.5778592783179 l=399 Best result: B = 2, S = 34.5778592783179 level 399 : replaced (2, 1) -> (2, 2) , dS: -15.0337981072 400 l=400 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=400 Current bracket: (2, 2, 2) (34.577859278317902, 34.577859278317902, 34.577859278317902) l=400 Bisect at B = 2 with S = 34.5778592783179 l=400 Best result: B = 2, S = 34.5778592783179 What is wrong with the launch of minimization ? Thank you Valeriy

2 1

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool September 2017