#! /usr/bin/env python # graph_tool.py -- a general graph manipulation python module # # Copyright (C) 2007 Tiago de Paula Peixoto # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program. If not, see . """ graph_tool.generation - Random graph generation --------------------------------------------------- Summary +++++++ .. autosummary:: :nosignatures: random_graph random_rewire predecessor_tree line_graph graph_union Contents ++++++++ """ from .. dl_import import dl_import dl_import("import libgraph_tool_generation") from .. core import Graph, _check_prop_scalar, _prop import sys, numpy, numpy.random __all__ = ["random_graph", "random_rewire", "predecessor_tree", "line_graph", "graph_union"] def _corr_wrap(i, j, corr): return corr(i[1], j[1]) def random_graph(N, deg_sampler, deg_corr=None, directed=True, parallel=False, self_loops=False, verbose=False): r""" Generate a random graph, with a given degree distribution and correlation. Parameters ---------- N : int Number of vertices in the graph. deg_sampler : function A degree sampler function which is called without arguments, and returns a tuple of ints representing the in and out-degree of a given vertex (or a single int for undirected graphs, representing the out-degree). This function is called once per vertex, but may be called more times, if the degree sequence cannot be used to build a graph. deg_corr : function (optional, default: None) A function which give the degree correlation of the graph. It should be callable with two parameters: the in,out-degree pair of the source vertex an edge, and the in,out-degree pair of the target of the same edge (for undirected graphs, both parameters are single values). The function should return a number proportional to the probability of such an edge existing in the generated graph. directed : bool (optional, default: True) Whether the generated graph should be directed. parallel : bool (optional, default: False) If True, parallel edges are allowed. self_loops : bool (optional, default: False) If True, self-loops are allowed. Returns ------- random_graph : :class:~graph_tool.Graph The generated graph. See Also -------- random_rewire: in place graph shuffling Notes ----- The algorithm maintains a list of all available source and target degree pairs, such that the deg_corr function is called only once with the same parameters. The uncorrelated case, the complexity is :math:O(V+E). For the correlated case the worst-case complexity is :math:O(V^2), but the typical case has complexity :math:O(V + E\log N_k + N_k^2), where :math:N_k < V is the number of different degrees sampled (or in,out-degree pairs). Examples -------- >>> from numpy.random import randint, random, seed, poisson >>> from pylab import * >>> seed(42) This is a degree sampler which uses rejection sampling to sample from the distribution :math:P(k)\propto 1/k, up to a maximum. >>> def sample_k(max): ... accept = False ... while not accept: ... k = randint(1,max+1) ... accept = random() < 1.0/k ... return k ... The following generates a random undirected graph with degree distribution :math:P(k)\propto 1/k (with k_max=40) and an *assortative* degree correlation of the form: .. math:: P(i,k) \propto \frac{1}{1+|i-k|} >>> g = gt.random_graph(1000, lambda: sample_k(40), ... lambda i,k: 1.0/(1+abs(i-k)), directed=False) >>> gt.scalar_assortativity(g, "out") (0.60296352140954257, 0.011780362691333932) The following samples an in,out-degree pair from the joint distribution: .. math:: p(j,k) = \frac{1}{2}\frac{e^{-m_1}m_1^j}{j!}\frac{e^{-m_1}m_1^k}{k!} + \frac{1}{2}\frac{e^{-m_2}m_2^j}{j!}\frac{e^{-m_2}m_2^k}{k!} with :math:m_1 = 4 and :math:m_2 = 20. >>> def deg_sample(): ... if random() > 0.5: ... return poisson(4), poisson(4) ... else: ... return poisson(20), poisson(20) ... The following generates a random directed graph with this distribution, and plots the combined degree correlation. >>> g = gt.random_graph(20000, deg_sample) >>> >>> hist = gt.combined_corr_hist(g, "in", "out") >>> imshow(hist[0], interpolation="nearest") <...> >>> colorbar() <...> >>> xlabel("in-degree") <...> >>> ylabel("out-degree") <...> >>> savefig("combined-deg-hist.png") .. figure:: combined-deg-hist.png :align: center Combined degree histogram. A correlated directed graph can be build as follows. Consider the following degree correlation: .. math:: P(j',k'|j,k)=\frac{e^{-k}k^{j'}}{j'!} \frac{e^{-(20-j)}(20-j)^{k'}}{k'!} i.e., the in->out correlation is "disassortative", the out->in correlation is "assortative", and everything else is uncorrelated. We will use a flat degree distribution in the range [1,20). >>> p = scipy.stats.poisson >>> g = gt.random_graph(20000, lambda: (sample_k(19), sample_k(19)), ... lambda a,b: (p.pmf(a[0],b[1])* ... p.pmf(a[1],20-b[0]))) Lets plot the average degree correlations to check. >>> clf() >>> corr = gt.avg_neighbour_corr(g, "in", "in") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{in}\right>$ vs in") (...) >>> corr = gt.avg_neighbour_corr(g, "in", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{out}\right>$ vs in") (...) >>> corr = gt.avg_neighbour_corr(g, "out", "in") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{in}\right>$ vs out") (...) >>> corr = gt.avg_neighbour_corr(g, "out", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{out}\right>$ vs out") (...) >>> legend(loc="best") <...> >>> xlabel("source degree") <...> >>> ylabel("average target degree") <...> >>> savefig("deg-corr-dir.png") .. figure:: deg-corr-dir.png :align: center Average nearest neighbour correlations. """ seed = numpy.random.randint(0, sys.maxint) g = Graph() if deg_corr == None: uncorrelated = True else: uncorrelated = False if not directed and deg_corr != None: corr = lambda i,j: _corr_wrap(i, j, deg_corr) else: corr = deg_corr libgraph_tool_generation.gen_random_graph(g._Graph__graph, N, deg_sampler, corr, uncorrelated, not parallel, not self_loops, not directed, seed, verbose) g.set_directed(directed) return g def random_rewire(g, strat= "uncorrelated", parallel_edges = False, self_loops = False): r""" Shuffle the graph in-place. The degrees (either in or out) of each vertex are always the same, but otherwise the edges are randomly placed. If strat == "correlated", the degree correlations are also maintained: The new source and target of each edge both have the same in and out-degree. Parameters ---------- g : :class:~graph_tool.Graph Graph to be shuffled. The graph will be modified. strat : string (optional, default: "uncorrelated") If strat == "uncorrelated" only the degrees of the vertices will be maintained, nothing else. If strat == "correlated", additionally the new source and target of each edge both have the same in and out-degree. parallel : bool (optional, default: False) If True, parallel edges are allowed. self_loops : bool (optional, default: False) If True, self-loops are allowed. See Also -------- random_graph: random graph generation Notes ----- Each edge gets swapped at least once, so the overall complexity is :math:O(E). Examples -------- Some small graphs for visualization. >>> from numpy.random import zipf, seed >>> from pylab import * >>> seed(42) >>> g = gt.random_graph(1000, lambda: sample_k(10), ... lambda i,j: exp(abs(i-j)), directed=False) >>> gt.graph_draw(g, layout="arf", output="rewire_orig.png", size=(6,6)) <...> >>> gt.random_rewire(g, "correlated") >>> gt.graph_draw(g, layout="arf", output="rewire_corr.png", size=(6,6)) <...> >>> gt.random_rewire(g) >>> gt.graph_draw(g, layout="arf", output="rewire_uncorr.png", size=(6,6)) <...> Some ridiculograms _ : .. image:: rewire_orig.png .. image:: rewire_corr.png .. image:: rewire_uncorr.png *Left:* Original graph; *Middle:* Shuffled graph, with degree correlations; *Right:* Shuffled graph, without degree correlations. We can try some larger graphs to get better statistics. >>> clf() >>> g = gt.random_graph(20000, lambda: sample_k(20), ... lambda i,j: exp(abs(i-j)), directed=False) >>> corr = gt.avg_neighbour_corr(g, "out", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", label="original") (...) >>> gt.random_rewire(g, "correlated") >>> corr = gt.avg_neighbour_corr(g, "out", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", label="correlated") (...) >>> gt.random_rewire(g) >>> corr = gt.avg_neighbour_corr(g, "out", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", label="uncorrelated") (...) >>> xlabel("$k$") <...> >>> ylabel(r"$\left$") <...> >>> legend(loc="best") <...> >>> savefig("shuffled-stats.png") .. figure:: shuffled-stats.png :align: center Average degree correlations for the different shuffled and non-shuffled graphs. The shuffled graph with correlations displays exactly the same correlation as the original graph. Now let's do it for a directed graph. See :func:~graph_tool.generation.random_graph for more details. >>> p = scipy.stats.poisson >>> g = gt.random_graph(20000, lambda: (sample_k(19), sample_k(19)), ... lambda a,b: (p.pmf(a[0],b[1])* ... p.pmf(a[1],20-b[0]))) >>> clf() >>> corr = gt.avg_neighbour_corr(g, "in", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{o}\right>$ vs i") (...) >>> corr = gt.avg_neighbour_corr(g, "out", "in") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{i}\right>$ vs o") (...) >>> gt.random_rewire(g, "correlated") >>> corr = gt.avg_neighbour_corr(g, "in", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{o}\right>$ vs i, corr.") (...) >>> corr = gt.avg_neighbour_corr(g, "out", "in") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{i}\right>$ vs o, corr.") (...) >>> gt.random_rewire(g, "uncorrelated") >>> corr = gt.avg_neighbour_corr(g, "in", "out") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{o}\right>$ vs i, uncorr.") (...) >>> corr = gt.avg_neighbour_corr(g, "out", "in") >>> errorbar(corr[2], corr[0], yerr=corr[1], fmt="o-", ... label=r"$\left<\text{i}\right>$ vs o, uncorr.") (...) >>> legend(loc="best") <...> >>> xlabel("source degree") <...> >>> ylabel("average target degree") <...> >>> savefig("shuffled-deg-corr-dir.png") .. figure:: shuffled-deg-corr-dir.png :align: center Average degree correlations for the different shuffled and non-shuffled directed graphs. The shuffled graph with correlations displays exactly the same correlation as the original graph. """ seed = numpy.random.randint(0, sys.maxint) g.stash_filter(reversed=True) libgraph_tool_generation.random_rewire(g._Graph__graph, strat, self_loops, parallel_edges, seed) g.pop_filter(reversed=True) def predecessor_tree(g, pred_map): """Return a graph from a list of predecessors given by the 'pred_map' vertex property.""" _check_prop_scalar(pred_map, "pred_map") pg = Graph() libgraph_tool_generation.predecessor_graph(g._Graph__graph, pg._Graph__graph, _prop("v", g, pred_map)) return pg def line_graph(g): """Return the line graph of the given graph g. Notes ----- Given an undirected graph G, its line graph L(G) is a graph such that * each vertex of L(G) represents an edge of G; and * two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint ("are adjacent") in G. For a directed graph, the second criterion becomes: * Two vertices representing directed edges from u to v and from w to x in G are connected by an edge from uv to wx in the line digraph when v = w. References ---------- .. [line-wiki] http://en.wikipedia.org/wiki/Line_graph """ lg = Graph(directed=g.is_directed()) vertex_map = lg.new_vertex_property("int64_t") libgraph_tool_generation.line_graph(g._Graph__graph, lg._Graph__graph, _prop("v", lg, vertex_map)) return lg, vertex_map def graph_union(g1, g2, props=[], include=False): """Return the union of graphs g1 and g2, composed of all edges and vertices of g1 and g2, without overlap. Parameters ---------- g1 : :class:~graph_tool.Graph First graph in the union. g2 : :class:~graph_tool.Graph Second graph in the union. props : list of tuples of :class:~graph_tool.PropertyMap (optional, default: []) Each element in this list must be a tuple of two PropertyMap objects. The first element must be a property of g1, and the second of g2. The values of the property maps are propagated into the union graph, and returned. include : bool (optional, default: False) If true, graph g2 is inserted into g1 which is modified. If false, a new graph is created, and both graphs remain unmodified. Returns ------- ug : :class:~graph_tool.Graph The union graph props : list of :class:~graph_tool.PropertyMap objects List of propagated properties. This is only returned if props is not empty. """ if not include: g1 = Graph(g1) g1.stash_filter(directed=True) g1.set_directed(True) g2.stash_filter(directed=True) g2.set_directed(True) n_props = [] try: vmap, emap = libgraph_tool_generation.graph_union(g1._Graph__graph, g2._Graph__graph) for p in props: p1, p2 = p if not include: p1 = g1.copy_property(p1) if p2.value_type() != p1.value_type(): p2 = g2.copy_property(p2, value_type=p1.value_type()) if p1.key_type() == 'v': libgraph_tool_generation.\ vertex_property_union(g1._Graph__graph, g2._Graph__graph, vmap, emap, _prop(p1.key_type(), g1, p1), _prop(p2.key_type(), g2, p2)) else: libgraph_tool_generation.\ edge_property_union(g1._Graph__graph, g2._Graph__graph, vmap, emap, _prop(p1.key_type(), g1, p1), _prop(p2.key_type(), g2, p2)) n_props.append(p1) finally: g1.pop_filter(directed=True) g2.pop_filter(directed=True) if len(n_props) > 0: return g1, n_props else: return g1