November 2018 - graph-tool - archives.skewed.de

Understanding the entropy of edge counts at each hSBM layer
by Tzu-Chi Yen 16 Nov '18

16 Nov '18

Dear Tiago, I am trying to understand each value of NestedBlockState.level_entropy that contributes to the entropy of a hierarchical SBM (hSBM). In particular, I am focusing on the “prior for the edge counts“. In PRE 95, 012317 (2017), we have used the multigraph entropy for _all levels_ of the hSBM because of the dominance of parallel edges at higher levels. Nevertheless, for each level (l=k; 1 <= k < L), we assume its connectivity pattern is generated by some NDC-SBM at a higher level (l=k+1), rendering the sum of the entropy terms of all levels smaller than that of a flat prior, avoiding under-fitting. There will be 2 questions along with the thread. To see what arguments BlockState.entropy() uses, I added, >> print("eargs.###: {}".format(eargs.###)) before the return line of the entropy() function in the graph_tool/inference/blockmodel.py file, where ### can be _degree_dl_, _edges_dl_, and _multigraph_, etc. Taking the “lesmis” dataset as an example, if we run minimize_nested_blockmodel_dl() on it, we (may) obtain two levels, i.e. [(77, 6), (6, 1)]. Now using this commands, >> nested_state.level_entropy(0) which outputs: eargs.dense: False eargs.edges_dl: False eargs.multigraph: True Out[•]: 630.133156768878 And, with this command, >> nested_state.level_entropy(1) It outputs: eargs.dense: True eargs.edges_dl: True eargs.multigraph: True Out[•]: 71.0082133080805 Which constitute the two levels of entropies that sum up to nested_state.entropy(). Here is my 1st question: 🧐 Why is `edges_dl` excluded except the highest level? I expected `edges_dl` at the lowest to be something nonzero, but _less_ than `69.21645383885243`, i.e. the exact negative logarithm of Eq. (40) of the PRE paper, using B=6 and e=254 (the number of edges of the “lesmis” dataset). Am I thinking it the right way? 🧐 <— this is the 2nd question. Sincerely thanks, Tzu-Chi -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 5

Condensation Graph Original Edges and Vertices
by Dominguez Morán, Juan Manuel 16 Nov '18

16 Nov '18

Hi everyone! condensation_graph() returns (among other things) the inter-community edges with their respective counts yet not which were the specific edges that connected the communities in the original graph. Is there an out-of-the-box way of obtaining this information? Same goes for vertices. Greatly appreciate the help, Juan

2 1

Kernel died problem while calculating edge probability
by ashutosh 15 Nov '18

15 Nov '18

Sir, I am trying to follow the example on "edge prediction as binary classification". Here is my code: *import graph_tool as gt import pandas as pd* # create a graph object in data frame format *ndf = pd.DataFrame({'Node1':['a','b','c','d','e'],'Node2':['c','e','b','a','d'],'Weight':[0.2,0.8,0.4,0.5,0.7], 'RandProp1':[1,2,3,1,2]}) ng = gt.Graph() nprop = ng.new_edge_property("float") ng.edge_properties['Weight'] = nprop* # important to map the properties to the graph *LayerProp = ng.new_edge_property('float') ng.edge_properties['LayerProp'] = LayerProp* *nvp = ng.add_edge_list(ndf.values.tolist(),hashed=True,string_vals=True,eprops=[nprop,LayerProp])* # minimizing the graph and inferring partitions *stateA = gt.inference.minimize_nested_blockmodel_dl(ng,layers=True, state_args=dict(ec=LayerProp,layers=True), deg_corr=True,verbose=True)* *L = 10 bs = stateA.get_bs() bs += [np.zeros(1)]*(L-len(bs)) stateB = stateA.copy(bs=bs, sampling=True) probs=([]) def collect_edge_probs(s): p = s.get_edges_prob([missing_edges[0]],entropy_args=dict(partition_dl=False)) probs[0].append(p); missing_edges = [(1,2,1)] *# for layered network you need to specify layer number *gt.inference.mcmc_equilibrate(stateB,force_niter=1000,mcmc_args=dict(niter=10), callback=collect_edge_probs,verbose=True)* When I run this code, it gives me kernel died error. Please help. I have another query that; how can we get the layer associated with the node? In the above code when I try the command *for i in nvp: print(i)* I get the output as : *a,c,b,e,d* and when I type the command *LayerProp.a* I get the output: *PropertyArray([ 1., 2., 3., 1., 2.])* How do I understand that because the order of addition of nodes depends on the order they come along with add_edge_list command, while the LayerProp is added in the order as mentioned in the property map. -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

1 1

Parallelized Boykov Kolmogorov Max Flow
by Craig Stutts ARA/SED 14 Nov '18

14 Nov '18

Are there plans to parallelize graph_tool.flow.boykov_kolmogorov_max_flow? I have an implementation that mimics MATLAB's maxflow function with default parameters, but it is considerably slower. Looking at task manager, it appears to be single threaded even though OpenMP is enabled and the number of threads is set correctly. Thanks, Craig

2 1

make[3]: *** [graph_triangulation.lo] Error 1
by Zahra Sheikhbahaee 08 Nov '18

08 Nov '18

*Hi Tiago,* *I tried to install graph-tool on macOS again and non of port install py-graph-tool or brew install graph-tool works on my laptop and I get **this error:* Segmentation fault: 11 *Then I tried to download the source and I ran:* ./configure CPPFLAGS="-I/usr/local/Cellar/py2cairo/1.17.1/include/" --with-cgal=/usr/local/Cellar/cgal/ *and then* make install *and I got this error message:* */usr/local/include/CGAL/internal/Triangulation_ds_circulators_3.h:181:1:* *note: *candidate: '*template<class Tds_> bool CGAL::internal::operator==(typename Tds_::Cell_handle, CGAL::internal::Triangulation_ds_cell_circulator_3<Tds_>)*' *operator*==(typename Tds_::Cell_handle ch, Triangulation_ds_cell_circulator_3<Tds_> cc) *^~~~~~~~* */usr/local/include/CGAL/internal/Triangulation_ds_circulators_3.h:181:1:* *note: * template argument deduction/substitution failed: In file included from */opt/local/include/gcc8/c++/memory:76*, from */usr/local/include/boost/config/no_tr1/memory.hpp:21* , from */usr/local/include/boost/get_pointer.hpp:14*, from */usr/local/include/boost/python/object/pointer_holder.hpp:11*, from */usr/local/include/boost/python/to_python_indirect.hpp:10*, from */usr/local/include/boost/python/converter/arg_to_python.hpp:10*, from */usr/local/include/boost/python/call.hpp:15*, from */usr/local/include/boost/python/object_core.hpp:14*, from */usr/local/include/boost/python/object.hpp:9*, from *../../../src/graph/graph.hh:23*, from *graph_triangulation.cc:23*: */opt/local/include/gcc8/c++/bits/stl_function.h:356:20:* *note: * '*CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<CGAL::Triangulation_data_structure_3<CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> >, CGAL::Delaunay_triangulation_cell_base_3<CGAL::Epick, CGAL::Triangulation_cell_base_3<CGAL::Epick, CGAL::Triangulation_ds_cell_base_3<void> > >, CGAL::Sequential_tag> > >*' is not derived from ' *CGAL::internal::Triangulation_ds_cell_circulator_3<Tds_>*' { return *__x == __y*; } *~~~~^~~~~~* make[3]: *** [graph_triangulation.lo] Error 1 make[2]: *** [install-recursive] Error 1 make[1]: *** [install-recursive] Error 1 make: *** [install-recursive] Error 1 It is really annoying because non of these approaches work. I also would like to install new version of graph tool on python 2.7 and it fails. any suggestion? Thanks in advance. Best, Zahra

3 3

Enforcing node separation in network partition
by ashutosh 05 Nov '18

05 Nov '18

Sir, Is there any way to enforce two nodes to be present in different network partitions rather than allowing the SBM algorithm itself to figure partitions for every node ? A little different question to the above would be, is it possible to allow partitions around specific nodes only in graph tool ? For the first one, there is an option to define the initial state in SBM algorithm, but I think that requires to define for every node. Also after the algorithm runs the network will eventually converge towards best partition which may or may not respect the condition of keeping two nodes separate. For the second, I feel it becomes like a k-means clustering. -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

2 1