price.py 2.61 KB
 Tiago Peixoto committed Jul 15, 2009 1 2 3 4 ``````#! /usr/bin/env python # We probably will need some things from several places import sys, os `````` Tiago Peixoto committed Jul 13, 2010 5 6 ``````from pylab import * # for plotting from numpy.random import * # for random sampling `````` Tiago Peixoto committed Jul 15, 2009 7 8 9 10 11 12 ``````seed(42) # We need to import the graph_tool module itself from graph_tool.all import * # let's construct a Price network (the one that existed before Barabasi). It is `````` Tiago Peixoto committed May 21, 2010 13 ``````# a directed network, with preferential attachment. The algorithm below is `````` Tiago Peixoto committed Jul 15, 2009 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 ``````# very naive, and a bit slow, but quite simple. # We start with an empty, directed graph g = Graph() # We want also to keep the age information for each vertex and edge. For that # let's create some property maps v_age = g.new_vertex_property("int") e_age = g.new_edge_property("int") # The final size of the network N = 100000 # We have to start with one vertex v = g.add_vertex() v_age[v] = 0 # we will keep a list of the vertices. The number of times a vertex is in this # list will give the probability of it being selected. vlist = [v] # let's now add the new edges and vertices for i in xrange(1, N): # create our new vertex v = g.add_vertex() v_age[v] = i # we need to sample a new vertex to be the target, based on its in-degree + # 1. For that, we simply randomly sample it from vlist. i = randint(0, len(vlist)) target = vlist[i] # add edge e = g.add_edge(v, target) e_age[e] = i # put v and target in the list vlist.append(target) vlist.append(v) # now we have a graph! # let's do a random walk on the graph and print the age of the vertices we find, # just for fun. v = g.vertex(randint(0, g.num_vertices())) `````` Tiago Peixoto committed Mar 07, 2011 60 ``````while True: `````` Tiago Peixoto committed Jul 15, 2009 61 62 63 64 65 66 67 68 69 70 71 72 `````` print "vertex:", v, "in-degree:", v.in_degree(), "out-degree:",\ v.out_degree(), "age:", v_age[v] if v.out_degree() == 0: print "Nowhere else to go... We found the main hub!" break n_list = [] for w in v.out_neighbours(): n_list.append(w) v = n_list[randint(0, len(n_list))] `````` Tiago Peixoto committed May 21, 2010 73 ``````# let's save our graph for posterity. We want to save the age properties as `````` Tiago Peixoto committed Mar 07, 2011 74 ``````# well... To do this, they must become "internal" properties: `````` Tiago Peixoto committed Jul 15, 2009 75 76 77 78 79 80 `````` g.vertex_properties["age"] = v_age g.edge_properties["age"] = e_age # now we can save it g.save("price.xml.gz") `````` Tiago Peixoto committed Apr 30, 2012 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 `````` # Let's plot its in-degree distribution in_hist = vertex_hist(g, "in") y = in_hist[0] err = sqrt(in_hist[0]) err[err >= y] = y[err >= y] - 1e-2 figure(figsize=(6,4)) errorbar(in_hist[1][:-1], in_hist[0], fmt="o", yerr=err, label="in") gca().set_yscale("log") gca().set_xscale("log") gca().set_ylim(1e-1, 1e5) gca().set_xlim(0.8, 1e3) subplots_adjust(left=0.2, bottom=0.2) xlabel("\$k_{in}\$") ylabel("\$NP(k_{in})\$") tight_layout() savefig("price-deg-dist.pdf")``````