graph-tool April 2020

graph-tool@skewed.de

21 participants
28 discussions

Re: [graph-tool] Installation has changed
by Rolf Sander 27 Apr '20

27 Apr '20

Hello Tiago, Thanks for your reply! > Are you really using a 32 bit i386 CPU in 2020? No, I have 64 bit: dpkg --print-architecture --> amd64 I think I found the solution: https://unix.stackexchange.com/questions/272908/apt-looking-for-i386-files-… Now it works fine. If other users face the same problem, maybe you could mention the following fix for /etc/apt/sources.list: deb [ arch=amd64 ] http://downloads.skewed.de/apt DISTRIBUTION main > Xenial is super old and does not compile graph-tool due to a lack of > compiler with C++17 support. It's really a pity that you face problems with the C++ compiler. I think that Ubuntu Xenial is still widely used. It is supported until April 2021: https://wiki.ubuntu.com/Releases (I would upgrade if I could but the hardware on that computer doesn't allow it) Best regards Rolf -- ----------------------------------------------------------------------- Rolf Sander phone: [+49] 6131/305-4610 Max-Planck Institute of Chemistry email: rolf.sander(a)mpic.de PO Box 3060, 55020 Mainz, Germany homepage: www.rolf-sander.net ----------------------------------------------------------------------- https://www.encyclopedia-of-geosciences.net https://www.geoscientific-model-development.net -----------------------------------------------------------------------

2 2

Analysing and visualising
by Ruffle, James 24 Apr '20

24 Apr '20

Dear Graph-Tool Community, I am interested in analysing the hierarchical partitions generated by the nested blockmodel. Specifically, after I have generated a nested SBM; I would then like to post-process this and calculate measures such as eigenvector centrality for a given hierarchical node; save this as a property, and then in visualisation apply either a size or colormap constraint to said node weighted by its centrality. Using the collection data; g = gt.collection.data["celegansneural”] state = gt.minimize_nested_blockmodel_dl(g) I can then ascertain what my levels are with; l1state = state.levels[1].g l2state = state.levels[2].g etc. I can then calculate eigenvector centrality of a given hierarchical partition as follows; ee1, x1 = gt.eigenvector(l1state) ee2, x2 = gt.eigenvector(l2state) 1) This presumably then needs to be saved as a hvprops(?!). But, I am unclear how to do this, not least in a way that I know for sure that the correct hierarchical vertices within l1state and l2state are aligning to the generated centrality measures of x1 and x2, respectively. 2) Furthermore, if/when that is achieved, how can I call upon this in drawing, for example to size the level 1 hierarchical vertices according to centrality, or level 2 vertices by another measure, etc.? Hugely grateful for any solutions! James

5 7

graph_union issue
by BleakHeart 23 Apr '20

23 Apr '20

Hello, I am trying to do the union of 3 different geometric_graph. This is what I wrote: from graph_tool.all import * from gi.repository import Gtk, Gdk import numpy as np # M networks with N total vertices N = 1500 M = 3 G = Graph(directed=False) for i in range(M): points = np.column_stack([np.random.random(N//M) * 100, i * 100 / M + np.random.random(N//M) * 100 / M]) G = graph_union(G, geometric_graph(points, 0.3)) pos = sfdp_layout(G) totdeg = G.degree_property_map("total") win = GraphWindow(G, pos, geometry=(1000, 1000), vertex_size=totdeg) win.connect("delete_event", Gtk.main_quit) win.show_all() Gtk.main() When I try to run this, I get the following error: in graph_union intersection = g2.new_vertex_property("int64_t", -1) AttributeError: 'tuple' object has no attribute 'new_vertex_property' Actually I have no idea how to solve this error, I used the grap_union function before in the same way but the graphs type were: Graph(directed=False) and random_graph(). Does anyone run this error? -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 2

Fast way to draw moving graphs in video
by Lex Fridman 21 Apr '20

21 Apr '20

Hi all, I'm currently drawing a graph snapshot to an image file, then loading it back in and writing that image to a video with OpenCV. This I/O process is a big bottleneck. Does anyone know a faster way to do this? Are there ways in graph-tool to speed this up or skip the I/O alltogether? - Lex

2 1

Latent Poisson questions
by Deklan Webster 21 Apr '20

21 Apr '20

Saw you mentioning the latent Poisson model on Twitter. I skimmed through what I could understand of the paper. Can it apply to directed graphs? I saw in the paper you were 'erasing' the multiedges back into a simple graph. Can you erase into a simple directed graph? Is it correct to say that this approach supplants degree-correction? And, for DC vs non-DC you had a section in the docs about selecting which one fits your network best given the entropy. Is there something analogous here? Or, do I just try it out and see the results? In the paper you mentioned this can be applied to community detection. As a user, is this as simple as instantiating LatentMultigraphBlockState and then everything else is pretty much the same: equilibrate with the new multiflip, etc? On Twitter you mentioned the latent Poisson approach in relation to link prediction. Over on the other thread you just recommended I use `MeasuredBlockState.get_edge_prob`. What's the difference with `LatentMultigraphBlockStat.get_edge_prob`? Will the latter give better results? I see they're both subclasses of `UncertainBaseState`. Thanks for your help as always

2 20

Re: [graph-tool] efficient random sampling of paths between two nodes
by Franco Peschiera 20 Apr '20

20 Apr '20

Hello Tiago, Thanks again for the quick answers and feedback. In fact, the more I think about how to take the most advantage of the graph, the more I think that in my case what I would really like is to control the way the paths are being sampled. So, the process would become a biased sampling where I’m the one giving the bias in the form of the probability of choosing each edge when traversing from the origin to the destination. This probability would depend on information of the node and additional information that will depend on each iteration of my algorithm. It could also be an edge property, I guess. One caveat is that DFS will not be possible since I want to make each sampling independent from the previous one and so getting several paths would be less efficient. Although I’d assume that this is not too much of a problem given that I’d need a smaller sample if I know it’s probably going to be a better one. I was thinking on doing something on the lines of the following (I’ve only tested it with a small graph): def sample_path_from_nodes(node1, node2, all_weights, cutoff): # all_weights is a dictionary on the graph edges current = node1 path = [] visited = set() while True: if current == node2: # we finished! return path + [current] visited.add(current) # maybe we should add (current, len(path)) neighbors = set(current.out_neighbors()) - visited if len(path) >= cutoff or not len(neighbors): # this path does not reach node2 # we backtrack # and we will never visit this node again current = path.pop() continue if not len(path) and not len(neighbors): # there is no path to node2 # this should not be possible return None # we haven't reached node2 # but there is still hope path.append(current) weights = [all_weights.get((current, n), 1) for n in neighbors] _sum = sum(weights) weights = [w/_sum for w in weights] current = np.random.choice(a=list(neighbors), p=weights) I fear this will not be as efficient as just getting a lot of paths via all_paths. Do you think this makes sense for sampling with preferences on edges? And if so, do you think it will perform a lot better if I did it as a graph-tool C++ extension? I guess I can always test the python version and see how it goes… thanks! Franco > Date: Wed, 15 Apr 2020 10:59:51 +0200 > From: Tiago de Paula Peixoto <tiago(a)skewed.de> > To: graph-tool(a)skewed.de > Subject: Re: [graph-tool] efficient random sampling of paths between > two nodes > Message-ID: <8ab80efc-e70b-58c8-b33f-54075880bfff(a)skewed.de> > Content-Type: text/plain; charset="utf-8" > > Am 15.04.20 um 10:42 schrieb Franco Peschiera: > > I now would like to test giving edges a weight in order for that > > |cutoff| argument to use it. I know the |shortest_distance| function > > accepts weights of edges in order to do Dijkstra. Could the same be done > > with |all_paths| such that the search is stopped if an accumulated > > weighted-distance is reached? > > I'm afraid not. > > > Is there any (alternative) way of > > controlling which paths I get from the |all_paths| besides that |cutoff| > > argument? > > There is no other argument to the function, which is deterministic. > > You could randomize the order of the edges in the graph (by removing and > adding them again in a random order), which will change which paths are > shown first, but would not give you a proper unbiased sampling. > > > Or whatever specialized logic regarding path sampling / > > filtering I would have to implemented myself (just like the examples you > > shared)? Would this be something you would consider adding to graph-tool? > > I think adding an algorithm to perform uniform sampling of paths in DAGs > would be useful, but I can't promise I will find the time anytime soon > to implement one. > > Best, > Tiago > > -- > Tiago de Paula Peixoto <tiago(a)skewed.de> > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > graph-tool mailing list > graph-tool(a)skewed.de > https://lists.skewed.de/mailman/listinfo/graph-tool > > > ------------------------------ > > End of graph-tool Digest, Vol 147, Issue 24 > ******************************************* >

2 1

Removing thrown (C++) exceptions
by Jeff Trull 20 Apr '20

20 Apr '20

C++ exceptions are zero cost only when *not* thrown; keeping them out of critical paths can make a significant difference in performance. Throwing exceptions is currently a routine part of the process of identifying concrete types for dispatching. When runtime is dominated by code strictly inside C++ this is not an issue, but for algorithms that must repeatedly cross the C++/Python boundary it can become a real performance problem. In particular, the search algorithms and their Visitors do this; I have found that using a non-throwing approach makes a dramatic speed improvement - over 2X for a maze router benchmark based on an implicit A* search. I'm offering this patch <https://git.skewed.de/count0/graph-tool/-/merge_requests/24> as an implementation; I think it may be worth investigating if similar optimizations are available elsewhere in the code. Best, Jeff

2 1

Clustering coefficient with parallel edges
by Tanguy Fardet 16 Apr '20

16 Apr '20

Hi Tiago, I was recently comparing the behavior of the clustering coefficient in different graph libraries and I was surprised by the results given by graph-tool with parallel edges: import graph_tool as gt from graph_tool.clustering import local_clustering from graph_tool.stats import remove_parallel_edges num_nodes = 5 edge_list = [(0, 3), (3, 0), (1, 0), (0, 1), (1, 2), (2, 1), (2, 4), (4, 2), (4, 1), (1, 4), (4, 3), (3, 4)] g = gt.Graph() g.add_vertex(num_nodes) g.add_edge_list(edge_list) print(local_clustering(g, undirected=False).a) print(local_clustering(g, undirected=True).a) g.set_directed(False) remove_parallel_edges(g) print(local_clustering(g, undirected=True).a) Gives: [0. 0.33333333 1. 0. 0.33333333] [0. 0.26666667 0.66666667 0. 0.26666667] [0. 0.33333333 1. 0. 0.33333333] And I must say I was expecting the same result for all three ^^ The graph: From what I understand, then, it seems that, when using undirected=True, graph-tool considers reciprocal edges as two different ones and considers the possible triangles between parallel edges as distinct. Is this desired behavior, and if so, why? I know it stems from the mathematical formula, but I think this one was derived from simple graphs and I'm not sure I see the physical meaning of the "extension" to parallel edges, besides the fact that it would perhaps give the same result as weighting the edges by their number. If this is indeed desired, is there a quick way to do the equivalent of setting the graph to undirected and removing the parallel edges in "view-mode" (i.e. making the removal temporary, like a filter)? Thanks in advance for your help and for your work on graph-tool. Best, Tanguy

3 9

efficient random sampling of paths between two nodes
by Franco Peschiera 15 Apr '20

15 Apr '20

Hello again Tiago, First of all thanks for the resources and help. As you may expect, I somewhat lack a specialized background in graph theory and so I sometimes miss the correct terminology. As a reminder, this is a DAG. I haven’t, yet, implemented the random unbiased generator version of all_paths you kindly shared in those links, although I have it listed as a possible future step. As a temporary workaround, I’ve been doing the following each time I want to randomly sample paths between two nodes: 1. I calculate the min and max length of paths between the two nodes (the min using topology.shortest_distance, a good aproximation of the max is trivial). 2. I sample a number between those min and max`. 3. I execute topology.all_paths with that number as cutoff argument to obtain the paths generator. 4. I then execute some sampling from that generator, with an iteration limit. This is, of course, just a very crude and biased way of sampling, but at least it returns a different set of paths at each time it is executed. Until now, I’ve been assuming each edge has a weight of 1. I now would like to test giving edges a weight in order for that cutoff argument to use it. I know the shortest_distance function accepts weights of edges in order to do Dijkstra. Could the same be done with all_paths such that the search is stopped if an accumulated weighted-distance is reached? Is there any (alternative) way of controlling which paths I get from the all_paths besides that cutoff argument? Or whatever specialized logic regarding path sampling / filtering I would have to implemented myself (just like the examples you shared)? Would this be something you would consider adding to graph-tool? For example, I’ve been even wondering if I could just create a temporal view from the graph, by a randomly filtering edges or nodes before samplinh the paths, so as to, again, reduce the graph I will be sampling at each iteration. as always thanks for your time and help! Franco Peschiera Message: 2 > Date: Mon, 23 Mar 2020 21:37:52 +0000 > From: Tiago de Paula Peixoto <tiago(a)skewed.de> > To: Main discussion list for the graph-tool project > <graph-tool(a)skewed.de> > Subject: Re: [graph-tool] efficient random sampling of paths between > two nodes > Message-ID: <e7b73784-607d-6644-f613-46af6d9bc1d1(a)skewed.de> > Content-Type: text/plain; charset=utf-8 > > Am 23.03.20 um 22:14 schrieb Franco Peschiera: > > Hello Tiago, > > > > First of all, thanks for your time. > > > > I see what you mean by having a biased logic that would prefer shorter > > paths to longer ones, I had not thought about that. > > > > Regarding the self-reference part, I think it would not be a problem > > because of the structure of my particular (directed) graph. In fact, > > each node represents an assignment *at some given time period* and the > > outward neighbors of a node represent assignments *in the future*. In > > this way, a path can never visit a previously visited node since there > > are no possible cycles. In fact I can easily calculate the shortest and > > longest possible path between two nodes (shortest: using graphql's > > `shortest_distance` method, longest= number of periods in between the > > two nodes). > > Well, for DAG (directed acyclic graphs) the situation is quite > different, you should have said so in the beginning. > > > So the paths I want to create (or sample) are just the different ways > > one can go from a node N1 (in period P1) to node N2 (in period P2 > P1).? > > I think that in my graph I could just sample neighbors with a weight > > that depends on how far they are (in number of periods) from the node: > > the farthest neighbor will have the least probability of being chosen. > > This way, I'd compensate the fact that shorter paths take less hops. > > > > What do you think? > > Why do I get the impression I'm using google more than you to answer > your question? > > Here is an approach using rejection sampling: > > > https://math.stackexchange.com/questions/2673132/a-procedure-for-sampling-p… > > Another approach is to count the number of paths that go through each > node (this is feasible for DAGs) and use this to sample directly, see: > > > https://pdfs.semanticscholar.org/0d74/e82c41124f83c842d5432abcb914ed1f410f.… > > Best, > Tiago > > > -- > Tiago de Paula Peixoto <tiago(a)skewed.de> >

2 1

Re: [graph-tool] graph-tool Digest, Vol 147, Issue 15
by Edwin Lock 10 Apr '20

10 Apr '20

Hi Tiago, Thanks again for your helpful reply. I have now changed my approach to modifying the beta parameter instead, as you suggested in your previous reply. However, I’m still running into unexpected behaviour. I would expect that I can change the beta parameters after the model is instantiated, to modify the progress of infection between iterations of the model; at least that is what I thought the constant_beta flag is for. However, it seems that the model ignores any changes that I make to the beta map after instantiating. What am I doing or understanding wrong? Here’s my minimum working example (adapted to the new approach), where I set beta to 0 for all edges but new infections still happen. # SETUP from graph_tool.generation import price_network from graph_tool.dynamics import SIRSState g = price_network(20, directed=False) # Initialise beta map with transmission probability 1 for all edges beta_map = g.new_edge_property('float', 1) model = SIRSState(g, beta=beta_map, r=0, constant_beta=False) # ensure no spontaneous infections state = model.get_state() # TEST print("before quarantining:\n", state.a) # Set transmission probability to 0 for all edges beta_map.a = 0 # Run model one time step model.iterate_sync() # New nodes in the filtered graph are infected print("filtered state after quarantining:\n", state.a) Essentially, I am looking for some way to isolate vertices and ensure they cannot infect others. On a related note, I am running into issues implementing the following subroutine efficiently: for a list of vertices (as a numpy integer array), determine the indices of all edges in the graph incident to at least one of the vertices in the list. Here the index is w.r.t. edge property maps. Is there an efficient way using a graph-tool function that I’m missing? Many thanks for all your help. Best, Edwin > On 10 Apr 2020, at 18:01, graph-tool-request(a)skewed.de wrote: > > > Message: 1 > Date: Fri, 10 Apr 2020 12:04:34 +0200 > From: Tiago de Paula Peixoto <tiago(a)skewed.de> > To: graph-tool(a)skewed.de > Subject: Re: [graph-tool] Extending SIR epidemic model with a > quarantined/immunised state > Message-ID: <0caae619-b590-ed5f-0434-de264972d2e6(a)skewed.de> > Content-Type: text/plain; charset="utf-8" > > Am 10.04.20 um 09:54 schrieb Edwin Lock: >> Thanks for getting back to me so quickly! >> >> I have a ?quarantined? vertex property map that maintains who is quarantined and have set a vertex filter on the graph to filter out quarantined people. Quarantined people are not supposed to be able to infect others. >> >> Here is a minimum working example where I quarantine all infected people from the graph but new people are infected in the next time step. >> >> # SETUP >> from graph_tool.generation import price_network >> from graph_tool.dynamics import SIRSState >> g = price_network(20) >> model = SIRSState(g, r=0) # make sure there are no spontaneous infections >> state = model.get_state() >> # Keep track of who is quarantined >> quarantined = g.new_vertex_property('bool', False) >> # Filter out quarantined nodes from graph >> g.set_vertex_filter(quarantined, inverted=True) > > I imagined you were maybe doing it like this... Indeed, the SIRSState > keeps track of the original unfiltered graph. > > What you need to do is to set the filter before you create the > SIRSState, and it should work as you are expecting. > >> Another question: I want to stop quarantined people from infecting others, but I do want them to recover with the same probability as non-quarantined people. In this case it makes sense to use an edge filter to remove all edges adjacent to a quarantined person >> instead of filtering the person?s vertex itself, right? > > Yes, this would be the correct approach. It would also be equivalent to > modifying the beta parameter as I described previously. > > Best, > Tiago

2 1

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool April 2020