graph-tool August 2021

graph-tool@skewed.de

8 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

Model specification and extraction of layer-specific partitions in LayeredBlockState when overlap=True
by arttu.malkamaki＠helsinki.fi 25 Jan '22

25 Jan '22

Hello, I'm studying political coalitions over time (three time slices) and across discrete types of relationships (collaboration, ideological similarity, and discursive similarity). Since graph-tool offers (the only) principled approach that does not require arbitrary user-specified parameters (such as 'resolution' or 'coupling'), I would very much like to use it for my analysis. I'm trying to fit a SBM to a graph with edges divided into distinct layers (three time slices X three types of relationships). Each edge has a discrete weight in the range of [0, 3], with weight referring to the 'strength' of the relationship. Not all nodes participate in all layers. I'm interested in how/if the block membership varies across layers that I expect to be somewhat dependent on one another (hence I would like to avoid fitting a separate SBM to each layer). In my ideal scenario, I would be using the NestedBlockState with LayeredBlockState as base and allowing for overlaps across layers: state=NestedBlockState(g, base_type=LayeredBlockState, state_args=dict(deg_corr=True, overlap=True, layers=True, ec=g.ep.layer, recs=[g.ep.weight], rec_types=["discrete-binomial"])) dS, nmoves=0, 0 for i in range(100): ret=state.multiflip_mcmc_sweep(niter=10) dS+=ret[0] nmoves+=ret[1] print("Change in description length:", dS) print("Number of accepted vertex moves:", nmoves) mcmc_equilibrate(state, wait=1000, mcmc_args=dict(niter=10), verbose=True) bs=[] def collect_partitions(s): global bs bs.append(s.get_bs()) mcmc_equilibrate(state, force_niter=10000, mcmc_args=dict(niter=10), verbose=True, callback=collect_partitions) pm=PartitionModeState(bs, nested=True, converge=True) pv=pm.get_marginal(g) bs=pm.get_max_nested() state=state.copy(bs=bs) Two questions: Q1) This is taking very long (days) on a high performance cluster and actually I haven't seen it finishing up for once. Is my model specification correct or simply too complex? If the latter, is there a better strategy to perform my analysis? All I can think of is to revert to a non-nested model and/or reduce the number of layers and/or edges: state=LayeredBlockState(g, deg_corr=True, overlap=True, layers=True, ec=g.ep.layer, recs=[g.ep.weight], rec_types=["discrete-binomial"]) dS, nattempts, nmoves=state.multiflip_mcmc_sweep(niter=1000) print("Change in description length:", dS) print("Number of accepted vertex moves:", nmoves) mcmc_equilibrate(state, wait=1000, nbreaks=2, mcmc_args=dict(niter=10), verbose=True) bs=[] def collect_partitions(s): global bs bs.append(s.b.a.copy()) mcmc_equilibrate(state, force_niter=10000, mcmc_args=dict(niter=10), verbose=True, callback=collect_partitions) pm=PartitionModeState(bs, converge=True) pv=pm.get_marginal(g) Q2) Say that the model runs and yields a neat NestedBlockState (or LayeredBlockState) object with X overlapping blocks, 9 layers, degree-corrected, with 2 edge covariates, for graph <Graph object, undirected, with 220 vertices and 11322 edges, 2 internal vertex properties, 4 internal edge properties>. Now, in previous posts there are mentions about the number of nodes multiplying by the number of layers when 'overlap=True', but in my experiments with only two layers, this does not seem to be the case and I struggle to find a way to extract the layer-specific block and respective memberships of nodes. I've tried iteration over vertices, but what I eventually need is a 2d_array [y=all nodes in g, x=all layers in g, values=most likely block membership] in order to map how/if the block membership of each node varies across those layers in which they participate (ideally somehow denoting non-participation in the layer with NaN or some unique value). Is there some way to get there? l=state.get_levels()[0] #NestedBlockState B=l.get_nonempty_B() bv=l.get_overlap_blocks()[0] z=np.zeros((g.num_vertices(), B)) #to be filled with most likely block membership with potential overlaps across ALL layers, but I need the layer-specific information for i in range(g.num_vertices()): z[int(i), :len(z[v])]=bv[i].a+1 for v in range(g.num_vertices()*max(g.ep.layer)+1): #to see if the number of vertices multiplied by layers, which it didn't print(bv[v]) Many thanks, Arttu

2 15

Error with get_edges_prob
by Davide Cittaro 02 Sep '21

02 Sep '21

Hi all, I have a NestedBlockState with LayeredBlockState as basis, two layers. I would like to predict edges that are missing in one or the other layer (besides, is this even possible?). However, given a list of missing edges (and a list of spurious ones) I tried this a_state.get_edges_prob(missing, spurious) and get this error AttributeError Traceback (most recent call last) <ipython-input-68-b3bc5280d3da> in <module> ----> 1 a_state.get_edges_prob([missing], spurious) ~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/nested_blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args) 441 lstate._state.clear_egroups() 442 --> 443 L += lstate.get_edges_prob(missing, spurious, entropy_args=eargs) 444 if isinstance(self.levels[0], LayeredBlockState): 445 missing = [(lstate.b[u], lstate.b[v], l_) for u, v, l_ in missing] ~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/blockmodel.py in get_edges_prob(self, missing, spurious, entropy_args) 1204 pos[v] = self.b[v] 1205 -> 1206 self.remove_vertex(pos.keys()) 1207 1208 try: ~/anaconda3/envs/experimental/lib/python3.8/site-packages/graph_tool/inference/blockmodel.py in remove_vertex(self, v) 1144 twice. 1145 """ -> 1146 self._state.remove_vertex(int(v)) 1147 1148 def add_vertex(self, v, r): AttributeError: 'graph_tool::BlockState<boost::undirected_adaptor<b' object has no attribute 'remove_vertex' I'm not sure what's happening here, but as far as I know gt.BlockState (and gt.NestedBlockState and gt.LayeredBlockState) have a remove_vertex method defined, right?

2 5

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

Boost error on edge properties
by ag＠alan.gold 25 Aug '21

25 Aug '21

Hi, I'm encountering a perplexing issue that I've spent some time trying to make sense of. Apologies if this should go on the gitlab issues page, but it tells me my account has been blocked for every method I've attempted to register an account there. I get a Boost dump any time I attempt to read an edge property. I can read and write graph and vertex properties fine. I can also write to an edge property just fine. If I try to read an edge property I get an exception. I have tried many methods of installing graph_tool all with the same result. I believe I have tried all of the following: install graph_tool from the ubuntu package manager, install with conda, compile graph_tool and all dependencies from scratch on ubuntu, do a fresh install of gentoo and install using emerge. All have resulted in the same error. Am I doing something stupid here or is this broken? Below is a minimal example. > uname -srm Linux 5.10.60-gentoo-dist x86_64 Python 3.9.6 (default, Aug 24 2021, 15:56:03) [GCC 10.3.0] on linux >>> import graph_tool as gt >>> gt.__version__ '2.43 (commit 9d41331e, Wed Jul 7 15:32:52 2021 +0200)' >>> G = gt.Graph(directed=True) >>> G.gp["name"] = G.new_graph_property("string") >>> G.ep["name"] = G.new_edge_property("string") >>> G.vp["name"] = G.new_vertex_property("string") >>> >>> # name the graph >>> G.gp.name = "Test graph" >>> >>> # add the vertices >>> v = G.add_vertex(2) >>> >>> # name the vertices >>> names = ["A", "B"] >>> for (_v, name) in zip(v, names): ... G.vp.name[_v] = name ... >>> # add the edge >>> V = list(G.vertices()) >>> e = G.add_edge(V[0], V[1]) >>> >>> # name the edge >>> G.ep.name[e] = "0 -> 1" >>> >>> # print the graph name >>> print(G.gp.name) Test graph >>> >>> # print the vertex names >>> for v in G.iter_vertices(): ... print(v, G.vp.name[v]) ... 0 A 1 B >>> # print the edge names >>> for e in G.iter_edges(): ... print(e) ... print(G.ep.name[e]) ... [0, 1] Traceback (most recent call last): File "<stdin>", line 3, in <module> File "/usr/lib/python3.9/site-packages/graph_tool/__init__.py", line 887, in __getitem__ return self._PropertyMap__map[k] Boost.Python.ArgumentError: Python argument types in EdgePropertyMap<string>.__getitem__(EdgePropertyMap<string>, list) did not match C++ signature: __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::filt_graph<boost::undirected_adaptor<boost::adj_list<unsigned long> >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::adj_edge_index_property_map<unsigned long> > >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<unsigned long> > > > const>) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::filt_graph<boost::reversed_graph<boost::adj_list<unsigned long>, boost::adj_list<unsigned long> const&>, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::adj_edge_index_property_map<unsigned long> > >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<unsigned long> > > > const>) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::filt_graph<boost::adj_list<unsigned long>, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::adj_edge_index_property_map<unsigned long> > >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<unsigned long> > > > const>) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::undirected_adaptor<boost::adj_list<unsigned long> > const>) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::reversed_graph<boost::adj_list<unsigned long>, boost::adj_list<unsigned long> const&> const>) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::adj_list<unsigned long> const>) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::filt_graph<boost::undirected_adaptor<boost::adj_list<unsigned long> >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::adj_edge_index_property_map<unsigned long> > >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<unsigned long> > > > >) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::filt_graph<boost::reversed_graph<boost::adj_list<unsigned long>, boost::adj_list<unsigned long> const&>, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::adj_edge_index_property_map<unsigned long> > >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<unsigned long> > > > >) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::filt_graph<boost::adj_list<unsigned long>, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::adj_edge_index_property_map<unsigned long> > >, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::typed_identity_property_map<unsigned long> > > > >) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::undirected_adaptor<boost::adj_list<unsigned long> > >) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::reversed_graph<boost::adj_list<unsigned long>, boost::adj_list<unsigned long> const&> >) __getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::adj_edge_index_property_map<unsigned long> > > {lvalue}, graph_tool::PythonEdge<boost::adj_list<unsigned long> >)

2 2

C++ extension: retrieve the filtered graph
by oliver.baumann＠uni-bayreuth.de 24 Aug '21

24 Aug '21

Hi all, I'm currently offloading construction of the uni-modal projection of a bipartite graph from Python to C++ (NB: I am not very familiar with C++ or BGL, _yet_). Thanks to the docs on writing such extensions, I know roughly where I'm heading. This is the signature of the projection-function: template <class Graph, class ProjectedGraph> void projection(const Graph &g, ProjectedGraph &pg) Here, g is the bipartite graph, and pg is constructed in Python as: pg = Graph(GraphView(g, vfilt=lambda v: g.vp.type == 0)) I am thus passing in the graph containing only the vertices I wish to project onto, and add the edges between them in C++. In Python, pg.num_edges() correctly returns zero. In C++, it returns the same number of edges as the base-graph it was constructed from, g. How can I obtain the filtered view of pg in C++, which I expect to have no edges? Kind regards, Oliver

3 4

Writing partition labels to state object
by Lietz, Haiko 24 Aug '21

24 Aug '21

Dear all, Given a NestedBlockState object called state, I can obtain the list of nested group belongings by x = state.get_bs() I can then order the partitions by y = order_nested_partition_labels(x) Is there a way to store the ordered labels in the original NestedBlockState object? How do I have to write that? Many thanks Haiko

2 1

Assortative constraint?
by dadakinda 15 Aug '21

15 Aug '21

Hello, Is there any way to bias the nested DC-SBM model towards assortative partitions? I've tested PPBlockState, but as far as I understand it distinguishes groups only by internal vs external density via the Planted Partition model: far more restrictive than the full SBM. I'm wondering if there is a middle-ground where you have a SBM but the groups are biased (required?) to be assortative. I searched for something like this and found a couple papers: "A Regularized Stochastic Block Model for the robust community detection in complex networks" by Lu et al and "Assortative-Constrained Stochastic Block Models" by Gribel et al. Unfortunately neither uses priors to prevent overfitting, a nested formulation to address resolution limit, etc. The latter paper restricts the intra-block connection probabilities to be greater than inter-block connection probabilities. I'm not sure if there is an equivalent idea for the microcanonical model. The only idea I can think of would be to modify the likelihood in some way to make intra-block edges more likely. Any guidance is appreciated, Thank you

2 1

Creating a layered graph (aka messing with property maps)
by Davide Cittaro 15 Aug '21

15 Aug '21

Hi all, I'm trying to analyze a graph for which I have multiple layers and I'm finding difficulties in creating the graph. I have two graphs with the same vertex for which I define a edge property (the layer) like this: (g_atac, dist_atac) = gt.generate_knn(A_data, k=n_neighbors) (g_rna, dist_rna) = gt.generate_knn(R_data, k=n_neighbors) layer_atac = g_atac.new_edge_property('int') for e in g_atac.edges(): layer_atac[e] = 1 layer_rna = g_rna.new_edge_property('int') for e in g_rna.edges(): layer_rna[e] = -1 g_atac.edge_properties['layer'] = layer_atac g_rna.edge_properties['layer'] = layer_rna I then merge the graphs by graph union, first defining a node mapping: rna_mappings = g_rna.new_vertex_property("int") for x in range(g_atac.num_vertices()): rna_mappings[x] = x and then performing the actual union: gu = gt.graph_union(g_atac, g_rna, intersection=rna_mappings, internal_props=True) This indeed creates the final graph, but I noticed that instead of two layers I have three: np.unique(gu.edge_properties['layer'].a) PropertyArray([-1, 0, 1], dtype=int32) Looking back at the start graphs I have zeros in the edge_properties as well np.unique(g_rna.edge_properties['layer'].a) PropertyArray([-1, 0], dtype=int32) np.unique(g_atac.edge_properties['layer'].a) PropertyArray([0, 1], dtype=int32) and, similarly, the elements in the edge property vector are much higher than the number of edges: print((len(g_rna.ep['layer'].a), g_rna.num_edges())) (156672, 14317) which is different from what I can get from this: g_rna.get_edges([g_rna.ep['layer']]).shape (14317, 3) I'm evidently messing with (internal) properties and I'm clueless, any advice?

2 3

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool August 2021