graph-tool February 2021

graph-tool@skewed.de

9 participants
12 discussions

How to control the orientation of the graph topology
by Xun Xiao 26 Feb '22

26 Feb '22

Hi Tiago, sometimes, when delete the graph and create a new one, then plot it, the plotted graph is shown upside down (in terms of the node text). So how could we control the orientation of the graph? Or which parameter we should use to always make node text shown in a correct orientation. Thanks a lot. -- 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.

3 5

Upside down labels
by charlie 26 Feb '22

26 Feb '22

Hi, I'm suffering from the same issue mentioned in this post: https://git.skewed.de/count0/graph-tool/issues/174 Namely, I'm trying to draw a graph that includes a lot of self-looping edges, and my labels are being printed upside down. If I remove the self-loops the labels are shown the right way up. Is there a fix for it? Thanks, Charlie -- 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.

3 3

random graph
by JM 01 Sep '21

01 Sep '21

Dear Tiago, I have a directed graph of about half a million nodes and approximately a million edges following scale free behaviour and a power law degree distribution. To test some of my hypothesis, I would like to generate random smaller graphs (about 50 up to 200 nodes) representative of the big one. When I used a sample function that samples straight away from the real distribution of the big network, I have following problems: - I generate unconnected nodes with both 0 in AND out degree. - I generate small sub parts of a few nodes that are not connected to the main graph. - If only sampling from nodes with at least 1 degree, the generated graph is coherent, but not representative anymore as I need a big portion of nodes with either only one in or one out degree. Here is the part of my script I used for that, where samples are drawn from dictionaries of the degrees: def sample_in(): a=np.random.randint(num) k_in = in_degrees[a] return k_in def sample_out(): if sample_in()==0: b=np.random.randint(num_out) k_out=out_zero_zeros.values()[b] return k_out else: b=np.random.randint(num) k_out=out_degrees[b] return k_out N=200 g=gt.random_graph(N, lambda:(sample_in(), sample_out()), model="constrained-configuration", directed=True) I also tried sampling from a list of tuples as you have mentioned before in the forum, but I didn't receive any results, as the tuples randomly drawn from my list might not be combinable. degs=[(7,1),(4,3),(5,6),(2,4),(6,8),(2,0),(3,5),(0,3),(2,7),(2,1)] g = gt.random_graph(4, lambda i: degs[i], directed=True) - Is there any option I could active that would help me in those cases I described above? - Is there a better way how to create representative small networks? Any help on that issue will be much appreciated. Best wishes, Jana -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

3 5

get_hierarchy_control_points return values
by Davide Cittaro 20 Apr '21

20 Apr '21

Hi again, I'm writing a small package that builds on graph-tool, but not on its graphics capabilities (also because I have to represent other things rather than the graph itself). Still I could use some of the functions "under the hood" for my purposes. I have a question about gt.draw.get_hierarchy_control_points(): the function returns the Bézier spline control points for edges in a given graph, but I'm having difficulties in understanding how this information is encoded. For a single edge in graph, I have dozens of values as control points (half dozens + 2), hence I suspect all splines going from node A to the root of a hierarchy and back to node B are encoded there, and control points should be taken 6 by 6 (3x2 by 3x2 coordinates?). How (x,y) for control points are encoded then: (x, x, x, y, y, y) or (x, y, x, y, x, y)? What are the 2 additiona values I have for each vector? Also, are values absolute or relative to one node in particular (A, B or root...)? Thanks d

4 10

Temporal community detection with DSBM
by ulgenklc 17 Mar '21

17 Mar '21

This is more of like an implementation question. I'm PhD student in math and I've been trying out different dynamic community detection(DCD) algorithms to compare their performance. I was stuck on graph-tool's implementation for a few months because the documentation for the layered networks was really short and I noticed this mailing list just now. I have multiple questions: first, am I initiating the network correctly below? My network is a list of weighted adjacency matrices corresponding to each snapshots. g = Graph() e_weight = g.new_ep("double") e_layer = g.new_ep("int") g.add_edge_list(edge_list, hashed = True, eprops=[e_weight, e_layer]) ## edge_list has (v1,v2,w,t) format g.edge_properties["edge_weight"] = e_weight ## weights of the intralayer edges g.edge_properties["edge_layer"] = e_layer ## since this is a multilayer network, each edge has to come with a layer information that it belongs to(a layer is a snapshot of the temporal network and has nothing to do with nested model which I will use the word 'level' for) Then, when I run the optimizer with the below code, I feel like I'm doing something wrong. I want to use 'independent layers' model since this is a temporal network and edge weights within each layer are varying between [0,1]. for deg_corr in [True, False]: state = minimize_nested_blockmodel_dl(g, layers = True, deg_corr = deg_corr, state_args=dict(ec = g.ep.edge_layer, layers = True, recs=[g.ep.edge_weight], rec_types=["real-exponential"])) S1 = state.entropy() # we will pad the hierarchy with another four empty levels, to # give it room to potentially increase state = state.copy(bs=state.get_bs() + [np.zeros(1)] * 4, sampling = True) for i in range(100): # this should be sufficiently large state.multiflip_mcmc_sweep(beta=np.inf, niter=10) S2 = state.entropy() print(S1,S2, S2-S1) I have a serious problem with getting the node labels. The code below only returns the node membership information for N nodes(size of the aggregated network). But since this is an evolving network, nodes are expected to change communities over time, so below code should return NxT(number of nodes times number of layers) many community labels? levels = state.get_levels() for s in levels: print(s) This returns the network partition at different levels of the nested SBM but only for N many nodes. What am I missing? -- Sent from: https://nabble.skewed.de/

2 4

minimize_blockmodel_dl taking a long time to run
by sam 01 Mar '21

01 Mar '21

hi, i'm running minimize_blockmodel_dl on a somewhat large network (230K vertices, ~1M edges) and it's taking a very long time. hours so far. as i understand it should run in O(N*ln^2N), and it shouldn't depend on properties of the network in the past it's never taken this long on my machine for networks of similar size anything i might be able to change to speed things up? thx! -- Sent from: https://nabble.skewed.de/

2 1

dfs/bfs seem to have overhead depending on total graph size
by My-Tien Nguyen 01 Mar '21

01 Mar '21

Hi all, I’ve got a very large undirected graph (407 mil vertices, 522 mil edges, 2 vertex properties) that consists of multiple connected components (ccs). I noticed that when I call e.g. dfs_iterator or dfs_search on a source vertex, it takes around 1 – 2 seconds to return. The upper bound is depending on the component’s size, but the lower bound seems to be the same for all components. I have created a test graph with only a subset of the ccs of the large graph. Iterating the same cc in the test graph takes only a couple of milliseconds instead of ≥ 1 s. This tells me, that the dfs/bfs iterators have some kind of overhead depending on the complete graph size. I wrote a DFSVisitor that collects some timings during iteration to better see which steps consume time. Here are the results (rounded for readability): In [30]: test_dfs(graph, graph.vertex(0)) # first time the function is entered visitor.start_vertex_t 2.3e-05 s visitor.first_discover_vertex_t 0.18 s visitor.first_examine_edge_t 0.18 s visitor.first_tree_edge_t 0.63 s visitor.first_finish_vertex_t 0.63 s # average time between last 2 calls of the function visitor.discover_vertex_t 0.002 s visitor.examine_edge_t 0.001 s visitor.tree_edge_t 0.001 s visitor.finish_vertex_t 0.001 s # last time finished() is called visitor.finished 1.3 s # number of times the functions were called visitor.discovered_vertices 565 visitor.examined_edges 1978 visitor.tree_edges 564 visitor.finished_vertices 565 took 1.38 s As you can see, start_vertex is called immediately, but then it takes a very long time until the other Visitor functions are called for the first time after which the calls are faster again, but still quite slow. On the test graph I think I can see the same trend with smaller numbers because the graph is smaller: In [30]: test_dfs(test_graph, test_graph.vertex(0)) # first time the function is entered visitor.start_vertex_t 2e-05 s visitor.first_discover_vertex_t 0.0007 s visitor.first_examine_edge_t 0.0007 s visitor.first_tree_edge_t 0.0016s visitor.first_finish_vertex_t 0.0015 s # average time between last 2 calls of the function visitor.discover_vertex_t 1.6e-05 s visitor.examine_edge_t 3.7e-06 s visitor.tree_edge_t 1.4e-05 s visitor.finish_vertex_t 1.4e-05 s # last time finished() is called visitor.finished 0.01 s # number of times the functions were called visitor.discovered_vertices 565 visitor.examined_edges 1978 visitor.tree_edges 564 visitor.finished_vertices 565 took 0.01 s If I iterate the same cc in the large graph in python, it takes me only a couple of milliseconds: def dfs(graph, vertex_idx): t = time.time() todo = {vertex_idx} visited = set() while len(todo) > 0: next_vertex = todo.pop() visited.add(next_vertex) todo |= set(graph.iter_all_neighbors(graph.vertex(next_vertex))) - visited print(f'dfs took {time.time() - t} s') return visited In [38]: d = dfs(graph, 0) dfs took 0.01653146743774414 s Because of graph_tool’s slowness for small ccs I ended up writing a heuristic that always attempts a naive python dfs first, but aborts if 1 second is exceeded and only then does the graph_tool dfs. Anyone know what’s going on here? Best My-Tien

2 1

Performance search vs shortest_path
by Alessandro Tonin 09 Feb '21

09 Feb '21

First of all, thanks a lot for this amazing library. I have a question about the performance of shortest_path vs dijkstra_search with a custom Visitor. I implemented a very basic example <https://nabble.skewed.de/file/t496286/basic_example.py> with a Visitor with just the method Using a graph of approx. 60k edges and 60k vertices, the performance of dijkstra_search are 30 times slower than the default method shortest_path. Is this difference normal, or I am doing some error in the code? Thanks, Alessandro -- Sent from: https://nabble.skewed.de/

2 3

graph-tool memory usage
by nikhrao 09 Feb '21

09 Feb '21

Hi all, I'm a current R-igraph user trying to understand the feasibility of switching to graph-tool. I have some memory constraints on the server I'm using and I'm trying to understand how graph-tool operates. The performance comparison documentation says the following: "Graph-tool's performance comes at the cost of increased time and memory required during compilation. This is mostly due to the in-place graph filtering functionality..". Since filtering seems to me to be a chiefly visualization-related task, does graph-tool typically require large amounts of RAM due to filtering only for visualization, but not for other tasks? Or is it the case that filtering is continually occurring under the hood and hence graph-tool uses large amounts of memory in general? Thanks! -- Sent from: https://nabble.skewed.de/

2 5

confused with minimize_nested_blockmodel_dl
by stephan 03 Feb '21

03 Feb '21

I'm learning to use minimize_nested_blockmodel_dl. I tried a 4 vertex graph that should result in two groups at the first level, but only one group is found. The code is below. I'm using v 2.35. Thanks, Stephan g = Graph() v0 = g.add_vertex() v1 = g.add_vertex() v2 = g.add_vertex() v3 = g.add_vertex() e01 = g.add_edge(v0, v1) e10 = g.add_edge(v1, v0) e23 = g.add_edge(v2, v3) e32 = g.add_edge(v3, v2) e03 = g.add_edge(v0, v3) edge_weights = g.new_edge_property('int') edge_weights[e01] = 5 edge_weights[e10] = 5 edge_weights[e23] = 5 edge_weights[e32] = 5 edge_weights[e03] = 1 state = minimize_nested_blockmodel_dl(g, overlap=False, state_args=dict(recs=[edge_weights], rec_types=['discrete-geometric']) ) print('Should be 2, but is ',state.levels[0].B) -- Sent from: https://nabble.skewed.de/

2 1

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool February 2021