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

Community detection questions
by lucidyan 17 Nov '16

17 Nov '16

Hi!I'm trying to perform community detection algorithm with /nested stochastic block model/ and I had some questions: Is there a way to take into account the weights of the edges? I read in *BlockState* about some /weights/, but did not understand what it is and how to use them. How to get the hierarchical results from the /nested stochastic block model/ to obtain a kind of agglomerative dendrogram? How to obtain numerical values of each vertex belonging to the clusters, after margins collectioning, like it drew in pie vertex chart in examples? How to measure quality of partitioning: is it any other metrics, than was in examples? Is it necessary that both/ Model Evidence/ was bigger and /Bethe Entropy/ was lower? What if only one metrics performs better, then other degrades? Thank you very much for your tremendous work on algorithms and only one multi-threaded library for working with graphs! I hope my questions are not too stupid and help someone else. -- 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.

2 1

find_new_level() error
by Peter Straka 17 Nov '16

17 Nov '16

Hello, I am trying to add a more detailed level at the bottom of a nested blockmodel. Given a graph g, I run c = gt.is_bipartite(g, True)[1] state = gt.minimize_nested_blockmodel_dl(g, deg_corr=True, layers=True, state_args=dict(ec=g.ep.visits, layers=False, pclabel=c), verbose=True) to find a nestedBlockState 'state'. Then I run state.duplicate_level(0) bstate = state.find_new_level(0, bisection_args={'verbose': True}) This seems to correctly invoke the bisection_minimize() method and runs for a while, then raises a ValueError: provided clabel is inconsistent with node partition. The output is below. Where exactly is the inconsistency coming from? Thank you, Peter B: 90666 <- 165691 shrinking 165691 -> 90666 B: 90666 <- 165691 B=90666 niter: 1 count: 0 breaks: 0 min_S: 4549865.6 max_S: 4549925.5 S: 4549865.6 ΔS: -59.8492 moves: 768 B: 90666 <- 165691 B=90666 niter: 2 count: 0 breaks: 0 min_S: 4549799.7 max_S: 4549925.5 S: 4549799.7 ΔS: -65.8762 moves: 720 B: 90666 <- 165691 B=90666 niter: 3 count: 0 breaks: 0 min_S: 4549799.5 max_S: 4549925.5 S: 4549799.5 ΔS: -0.251813 moves: 759 B: 90666 <- 165691 B=90666 niter: 4 count: 0 breaks: 0 min_S: 4549671.3 max_S: 4549925.5 S: 4549671.3 ΔS: -128.157 moves: 788 B: 90666 <- 165691 B=90666 niter: 5 count: 0 breaks: 0 min_S: 4549577.9 max_S: 4549925.5 S: 4549577.9 ΔS: -93.3804 moves: 797 B: 90666 <- 165691 B=90666 niter: 6 count: 0 breaks: 0 min_S: 4549495.5 max_S: 4549925.5 S: 4549495.5 ΔS: -82.3979 moves: 787 B: 90666 <- 165691 B=90666 niter: 7 count: 0 breaks: 0 min_S: 4549459.7 max_S: 4549925.5 S: 4549459.7 ΔS: -35.8572 moves: 777 ... ... ... Current bracket: (851, 90666, 165691) (2756226.276337453, 4857281.779995878, 4882260.334948147) B: 44298 <- 90666 shrinking 90666 -> 45333 Traceback (most recent call last): File "code/add_layer.py", line 9, in <module> bstate = state.find_new_level(0, bisection_args={'verbose': True}) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/nested_blockmodel.py", line 447, in find_new_level state = bisection_minimize([min_state, max_state], **bisection_args) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/bisection.py", line 157, in bisection_minimize f_mid = get_state_dl(B=mid_B, **kwargs) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/bisection.py", line 85, in get_state_dl (B, B_prev))))) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/mcmc.py", line 358, in mcmc_multilevel state = state.shrink(B=B_next, **shrink_args) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/layered_blockmodel.py", line 862, in shrink return BlockState.shrink(self, B, **kwargs) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/blockmodel.py", line 1580, in shrink state = self.copy(b=b) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/layered_blockmodel.py", line 434, in copy "rec_params", "allow_empty"])) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/layered_blockmodel.py", line 149, in __init__ "layer_entropy"])) File "/usr/lib/python2.7/dist-packages/graph_tool/inference/blockmodel.py", line 310, in __init__ raise ValueError("provided clabel is inconsistent with node partition") ValueError: provided clabel is inconsistent with node partition Dr Peter Straka Research Fellow (DECRA) School of Physical Engineering and Mathematical Sciences | UNSW Canberra Google Scholar <https://scholar.google.com.au/citations?user=o80TaWgAAAAJ> E: p.straka(a)unsw.edu.au skype: straka.ps

2 1

Tune the size of detected communities?
by Peter Straka 17 Nov '16

17 Nov '16

Hello, I have a large bipartite network with ~10^4 vertices of type I and ~10^6 vertices of type II. I fitted a nested blockmodel, hoping to identify communities of type I. Unfortunately, the detected communities (at the lowest level in the hierarchy) have a median size that is about twice as big as the empirical evidence suggests; (kind of reminding me of the resolution limit problem). Is there a way to tune the sizes of the communities at the lowest level? I'm thinking - could forcing an extra hierarchy level help, or - adding in another (non-nested) simple block model at the lowest level? - Is it possible to reduce the penalty on the description length? Any ideas would be greatly appreciated... many thanks in advance! Peter Dr Peter Straka Research Fellow (DECRA) School of Physical Engineering and Mathematical Sciences | UNSW Canberra Google Scholar <https://scholar.google.com.au/citations?user=o80TaWgAAAAJ> E: p.straka(a)unsw.edu.au skype: straka.ps

2 1

Multiprocessing.Process bug
by François Kawala 15 Nov '16

15 Nov '16

Hello, I observe a quite strange bug that involves python's multiprocessing library. I try to use (read only) one graph instance with several *Multithreading.Process*. The graph is unserialized in the parent process. Each child receives a reference to the graph. Then each child does simple repetitive calls to *graph_tool.topology.shortest_distance*. Everything great each child process works as fast as it can. However when the main process executes the *hash_graphs* function presented below, each child process hangs infinitely. The *hash_graphs* is executed prior to the children start. def hash_graphs(*args): """ Provides an edge based graph digest that can be used to invalidate old cache. :type args: tuple of :class:`graph_tool.GraphView` :param args: the graphs to be hashed. :rtype: str :return: a hash digest of the input graph. """ graph_hash = hashlib.md5() for graph in args: graph_hash.update(gt.edge_endpoint_property(graph, graph.vp['id'], "source").a.tobytes()) graph_hash.update(gt.edge_endpoint_property(graph, graph.vp['id'], "target").a.tobytes()) return graph_hash.hexdigest() I package a MWE, it is available here : https://drive.google.com/file/d/0B5GhhBKHOKOxVnpfYTBwNDZxODA/view?usp=shari…. To run it simply do : tar xzf mwe.tar.gz # run the buggy version python3 -m mwe DO_HASH # run as expected python3 -m mwe The buggy output looks like : <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-2, started)> does shortest_distance from 266188 to 207342 <MyProcess(MyProcess-3, started)> does shortest_distance from 514127 to 290838 <MyProcess(MyProcess-4, started)> does shortest_distance from 439705 to 87897 <MyProcess(MyProcess-5, started)> does shortest_distance from 223098 to 440593 <MyProcess(MyProcess-6, started)> does shortest_distance from 279880 to 368550 <MyProcess(MyProcess-7, started)> does shortest_distance from 108357 to 199593 <MyProcess(MyProcess-8, started)> does shortest_distance from 273888 to 275937 The expected output looks like : <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-2, started)> does shortest_distance from 266188 to 207342 <MyProcess(MyProcess-3, started)> does shortest_distance from 514127 to 290838 <MyProcess(MyProcess-5, started)> does shortest_distance from 223098 to 440593 <MyProcess(MyProcess-6, started)> does shortest_distance from 279880 to 368550 <MyProcess(MyProcess-1, started)> done. <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-2, started)> done. <MyProcess(MyProcess-2, started)> does shortest_distance from 266188 to 207342 <MyProcess(MyProcess-4, started)> does shortest_distance from 439705 to 87897 <MyProcess(MyProcess-7, started)> does shortest_distance from 108357 to 199593 <MyProcess(MyProcess-3, started)> done. <MyProcess(MyProcess-1, started)> done. <MyProcess(MyProcess-3, started)> does shortest_distance from 514127 to 290838 <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-8, started)> does shortest_distance from 273888 to 275937 <MyProcess(MyProcess-2, started)> done. <MyProcess(MyProcess-2, started)> does shortest_distance from 266188 to 207342 <MyProcess(MyProcess-3, started)> done. <MyProcess(MyProcess-3, started)> does shortest_distance from 514127 to 290838 <MyProcess(MyProcess-1, started)> done. <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-6, started)> done. <MyProcess(MyProcess-6, started)> does shortest_distance from 279880 to 368550 <MyProcess(MyProcess-4, started)> done. <MyProcess(MyProcess-4, started)> does shortest_distance from 439705 to 87897 <MyProcess(MyProcess-8, started)> done. <MyProcess(MyProcess-8, started)> does shortest_distance from 273888 to 275937 <MyProcess(MyProcess-1, started)> done. <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-2, started)> done. <MyProcess(MyProcess-2, started)> does shortest_distance from 266188 to 207342 <MyProcess(MyProcess-3, started)> done. <MyProcess(MyProcess-3, started)> does shortest_distance from 514127 to 290838 <MyProcess(MyProcess-5, started)> done. <MyProcess(MyProcess-5, started)> does shortest_distance from 223098 to 440593 <MyProcess(MyProcess-1, started)> done. <MyProcess(MyProcess-1, started)> does shortest_distance from 452946 to 391015 <MyProcess(MyProcess-8, started)> done. <MyProcess(MyProcess-8, started)> does shortest_distance from 273888 to 275937 <MyProcess(MyProcess-7, started)> done. <MyProcess(MyProcess-7, started)> does shortest_distance from 108357 to 199593 <MyProcess(MyProcess-3, started)> done. <MyProcess(MyProcess-3, started)> does shortest_distance from 514127 to 290838 ... How could I explain this behavior ? Bests, François.

2 6

Images in vertices
by Nils Hachmeister 15 Nov '16

15 Nov '16

Hello, I'm using graph_tool in a scenario, in which the meaning of a vertex cannot be easily be explained by a label or a text. To get a meaningful graph I would need to display a image inside the vertices. Has anyone an idea, how could this be achieved? Thanks Soraltan

3 3

Simplification of graphs
by Giovanni Colavizza 07 Nov '16

07 Nov '16

Hello, I am new to the tool, which looks amazing so far! I have a question: all graphs are created as multigraphs. I would like to load graphs with signed edges, and be able to remove some of them for different tests. Yet, after removal, I’d like to simplify the graph and collapse all multiple edges between the same two nodes into a unique edge, summing up all the weights of these different edges into a unique weight. How would you suggest doing it? Besides externally from graph_tool, that is. Thanks! Giovanni

2 1

Vertex Position for plotting NestedBlockState
by philipplorenz 04 Nov '16

04 Nov '16

Is there a possibility to get the nodes Positions from a NestedBlockState Object? -- 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.

2 4

random_graph stochastic block model produces unreasonably interconnected blocks
by G. B. 04 Nov '16

04 Nov '16

I'm currently building two-type random graphs of 100 vertices using the traditional_blockmodel feature of the random_graph/random_rewire functions. The degree_sampler I'm using is just lambda: poisson(5), which means that my graphs have about 250 edges. My blocks contain 15 vertices and 85 vertices respectively. When I tune the correlation function in the following way: def corr(a,b): if a==b: return 20 else: return 1 I would expect, based on the documentation, that the following is approximately true: 250 edges = (15*85)*(1*p_baseline) + (15 choose 2)*(20*p_baseline)+(85 choose 2)*(20*p_baseline). Solving this equation gives an approximate value of p_baseline = .0033, given the degree_sampler I started with. If p_baseline = .0033, then p_acrossblocks = .0033*1 = .0033 as well. Since there are 85*15=1275 possible edges across the two blocks, I would expect an average of .0033*1275=4.2 edges across the blocks in the entire network. Despite this, I am continually seeing the minority block being, on average, highly centralized in the overall network, with many more edges reaching from it to the other block than would be predicted. What has gone wrong here? Have I misunderstood the vertex_corr feature? Any help would be greatly appreciated. -- 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.

2 5