April 2014 - graph-tool - archives.skewed.de

Edge weights in assortativity
by Javier Dehesa 29 Apr '14

29 Apr '14

Hi, I'm using graph-tool to analyze a network with edge weights that represent "multiplicity" or "frequency" of the relationship. Most of the algorithms in graph-tool accept a weight in this sense (where appliable), but the assortativity (or scalar assortativity) does not. I think it's possible to use edge weights in the assortativity coefficient (correct me if I'm wrong), is there any plan to introduce this feature? I think For what I've seen, I don't think it would be hard to implement, so I can put a pull request if you find it interesting, although someone would have to review it as I don't have enough RAM in my machine to compile graph-tool. -- Javier Dehesa

2 1

Generating a "sequence" of graphs
by Jimmy Jin 29 Apr '14

29 Apr '14

Hi all, Relative graph-tool newbie here. I have a situation which I'm not sure how to approach in an efficient manner. I was hoping maybe someone could give some insight here. Basically, I want to generate an undirected Price network of N nodes, but I would like to be able to "look back" and access the subgraph when the network was only "k" nodes large. For simplicity's, say I'm adding one edge per vertex (i.e. m=1). One obvious way to do this seems to be to write a generator where, after adding the k-th vertex, you append a copy of the graph at that time onto some list. Then at the end you would have a list of length N where each element is a graph object. However... this seems kind of like overkill. I was thinking another way to do this is to generate only one graph, but give each node and edge an "age" attribute (as in the example in the tutorial). Then you could get the time-k subgraph by selecting only nodes and edges that have age less than k. Is there an obvious way to implement this in graph-tool? Specifically, for each time-k subgraph I'd want to be able to access the degree distribution at that time, and also the usual properties of the graph such as neighbors of a given node, etc. Many thanks, Jimmy

3 4

Import Error
by sandrine ollinger 28 Apr '14

28 Apr '14

Dear graph_tool users, I try to use graph_tool on my Mac OS X 10.6.8. I used Macport to install py-27-graph-tool and it seems to work perfectly. But now, when I try to import graph_tool, I have successively 2 errors: Python 2.7.6 (default, Nov 12 2013, 13:10:34) [GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin 1) >>> import graph_tool as gt Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/graph_tool/__init__.py", line 96, in <module> import scipy.stats File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/stats/__init__.py", line 324, in <module> from .stats import * File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/stats/stats.py", line 242, in <module> import scipy.special as special File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/special/__init__.py", line 531, in <module> from ._ufuncs import * File "__init__.pxd", line 155, in init scipy.special._ufuncs (scipy/special/_ufuncs.c:20976) ValueError: numpy.dtype has the wrong size, try recompiling 2) >>> import graph_tool.all as gt Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/graph_tool/__init__.py", line 96, in <module> import scipy.stats File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/stats/__init__.py", line 324, in <module> from .stats import * File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/stats/stats.py", line 242, in <module> import scipy.special as special File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/special/__init__.py", line 533, in <module> from .basic import * File "/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/scipy/special/basic.py", line 12, in <module> from ._ufuncs import ellipkm1, mathieu_a, mathieu_b, iv, jv, gamma, psi, zeta, \ ImportError: cannot import name ellipkm1 Could you help me solve this problem? Best regards, Sandrine

3 3

Computing Page Rank over the Largest Connected Component
by Panos Achlioptas 24 Apr '14

24 Apr '14

Hello to everyone, I am trying to compute the Page Rank of the nodes of the Largest CC of the ‘cond-mat-2003’ graph. It seems like I am unable to compute them over only the Largest CC. First, I extract the largest connected component: g = collection.data[cond-mat-2003] l = topology.label_largest_component(g) g = GraphView(g, vfilt=l) OR g.set_vertex_filter(l) And then calculate the PR PR = centrality.pagerank(g, damping=0.99, epsilon=1e-06) But, The length of the PR.a is equal to the number of nodes of the whole graph and even more alarming, none of its entries is equal to zero. This makes me suspect that PR is computed over the whole initial graph. Is this true? Thanks a lot, Panos

2 1

Error: Gtk, Gdk, GdkPixbuf
by EFTL 18 Apr '14

18 Apr '14

Hi, this is the first time I'm dabbling into graph-tool as I had always been using networkx. Anyway, I managed to successfully install the package via MacPorts. When I run: import graph_tool -- everything seems to be running okay. However, when I run: from graph_tool.all import * I am getting the following: ERROR:root:Could not find any typelib for Gtk ERROR:root:Could not find any typelib for Gdk ERROR:root:Could not find any typelib for GdkPixbuf Has anyone encountered this before? Were you able to resolve it? Thank you. E

5 14

How can I generate an Erdos-Renyi network which follows Possion distribution with random_graph function?
by Liu 17 Apr '14

17 Apr '14

Dear Tiago, I am trying to generate an Erdos-Renyi network like this: import graph_tool.all as gt import numpy.random as np g = gt.random_graph(1000, deg_sampler=np.poisson(4), directed=False) but it doesn't work out. Is anything I misunderstood in the documentation? I am new in this field. Thanks for your help! Best, Liu

2 1

Building graph from adjacency matrix
by Pietro Battiston 05 Apr '14

05 Apr '14

Hello, I tried graph-tool after some experience with networkx, in search for better efficiency (attracted by [1]) ... but unfortunately, it seems like it all depends on how data is stored! The (several) networks I play with are dense weighted networks of 1435 nodes. They are defined in terms of their adjacency matrices, which are pandas dataframes stored in a HDF5 store. In order to get the relative network with networkx, I would do dg = nx.from_numpy_matrix(hstore['my_df'].as_matrix(), create_using=nx.DiGraph()) which took around 18 seconds. In graph-tool, the best alternative I found, based on [2] and [3], is: # Since the bottleneck is given by the calls to g.add_edge(), # numba actually slows down things a bit. #from numba import autojit # #@autojit def graph_from_adj_matrix(m): g = Graph() n = m.shape[0] edges = list(g.add_vertex(n=n)) c = Counter(every=10, until=n) for i in xrange(n): for j in xrange(n): if m[i,j]: g.add_edge(edges[i], edges[j]) c.count() return g g = graph_from_adj_matrix(hstore['my_df'].as_matrix()) ... which takes around 200 seconds (and is still not even weighted!). Is there anything trivial (or simply new) I'm missing (apart from the possibility, mentioned in [3], of writing my code in C++)? [1] : http://graph-tool.skewed.de/performance [2] : http://lists.skewed.de/pipermail/graph-tool/2011-September/000438.html [3] : http://graph-tool.skewed.de/trac/ticket/106 Thanks, Pietro

3 8

minimize nested blockmodel dl performance
by Jose Magaña 04 Apr '14

04 Apr '14

Hello, I am a new user of the library so forgive if my questions are very basic. I am using the minimize_nested_blockmodel_dl in order to create a hierarchical cluster for a graph. The graph is created from a matrix distance of the nodes in the graph. There are 180 nodes. I have tried with different transformations of the distances to weights, basically w=1-d and w=1/d, previously normalizing to fit in range 0-1. Only with the second one I have been able to obtain a non-trivial partition and the partition obtained is quite bad (low NMI and high NVI ... ). Using other methods, much simpler, I have found much better partition (agglomerative clustering for example) so I know the data allows for a better partition to be obtained. The method is non-parametric, once the weights are provided, except for the number of sweeps, epsilons,... How can I know if I need to increase the number of sweeps or if I have reached the limit of the algorithm? So far, I have run upto 10K sweeps but there is no much difference in the execution time nor the result. What other parameters can be adjusted and under what criteria? How must the data be normalized to obtain optimal results(increase algorithm chances of finding a better partition series)? Thanks in advance Jose

2 1

strongly connected components
by Marcelo Maia 03 Apr '14

03 Apr '14

Hello, Here is my digraph in .dot format: digraph G { 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0->3 ; 0->2 ; 1->4 ; 1->8 ; 2->5 ; 3->7 ; 3->8 ; 4->8 ; 5->6 ; 6->2 ; 7->9 ; 8->0 ; 9->7 ; } to load it, just do: from graph_tool import load_graph g = load_graph('filename', fmt='dot') So, How can i get a list of all strongly connected components<http://en.wikipedia.org/wiki/Strongly_connected_component> of a digraph? I tried *label_components, *but i didnt understand how it works... Thanks!

2 1