__init__.py 76 KB
 Tiago Peixoto committed Apr 10, 2008 1 #! /usr/bin/env python  Tiago Peixoto committed Mar 07, 2010 2 # -*- coding: utf-8 -*-  Tiago Peixoto committed Apr 10, 2008 3 #  Tiago Peixoto committed Mar 07, 2010 4 5 # graph_tool -- a general graph manipulation python module #  Tiago Peixoto committed Jan 01, 2017 6 # Copyright (C) 2006-2017 Tiago de Paula Peixoto  Tiago Peixoto committed Apr 10, 2008 7 8 9 10 11 12 13 14 15 16 17 18 # # 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  Tiago Peixoto committed Jan 06, 2013 19 # along with this program. If not, see .s  Tiago Peixoto committed Apr 10, 2008 20   Tiago Peixoto committed Jul 15, 2009 21 """  Tiago Peixoto committed Oct 05, 2009 22 graph_tool.generation - Random graph generation  Tiago Peixoto committed Jul 15, 2009 23 ---------------------------------------------------  Tiago Peixoto committed Oct 05, 2009 24 25 26 27 28 29 30 31 32  Summary +++++++ .. autosummary:: :nosignatures: random_graph random_rewire  Tiago Peixoto committed Dec 04, 2016 33  generate_sbm  Tiago Peixoto committed Oct 05, 2009 34 35 36  predecessor_tree line_graph graph_union  Tiago Peixoto committed Dec 06, 2009 37  triangulation  Tiago Peixoto committed Oct 04, 2010 38 39  lattice geometric_graph  Tiago Peixoto committed Nov 13, 2010 40  price_network  Tiago Peixoto committed Apr 13, 2013 41  complete_graph  Tiago Peixoto committed Apr 14, 2013 42  circular_graph  Tiago Peixoto committed Apr 02, 2016 43  condensation_graph  Tiago Peixoto committed Oct 05, 2009 44 45 46  Contents ++++++++  Tiago Peixoto committed Jul 15, 2009 47 48 """  Tiago Peixoto committed Jun 03, 2012 49 from __future__ import division, absolute_import, print_function  Tiago Peixoto committed Sep 25, 2015 50 51 52 import sys if sys.version_info < (3,): range = xrange  Tiago Peixoto committed Jun 03, 2012 53   Tiago Peixoto committed Oct 26, 2008 54 from .. dl_import import dl_import  Tiago Peixoto committed Jun 03, 2012 55 dl_import("from . import libgraph_tool_generation")  Tiago Peixoto committed Apr 10, 2008 56   Tiago Peixoto committed Sep 25, 2015 57 58 from .. import Graph, GraphView, _check_prop_scalar, _prop, _limit_args, \ _gt_type, _get_rng, _c_str, libcore  Tiago Peixoto committed Feb 20, 2010 59 from .. stats import label_parallel_edges, label_self_loops  Tiago Peixoto committed Aug 27, 2011 60 61 import inspect import types  Tiago Peixoto committed Sep 25, 2015 62 63 import numpy import numpy.random  Tiago Peixoto committed Apr 10, 2008 64   Tiago Peixoto committed Dec 04, 2016 65 66 67 68 __all__ = ["random_graph", "random_rewire", "generate_sbm", "predecessor_tree", "line_graph", "graph_union", "triangulation", "lattice", "geometric_graph", "price_network", "complete_graph", "circular_graph", "condensation_graph"]  Tiago Peixoto committed Apr 10, 2008 69   Tiago Peixoto committed May 03, 2010 70   Tiago Peixoto committed Apr 25, 2013 71 72 def random_graph(N, deg_sampler, directed=True, parallel_edges=False, self_loops=False, block_membership=None,  Tiago Peixoto committed Nov 18, 2011 73  block_type="int", degree_block=False,  Tiago Peixoto committed May 01, 2013 74  random=True, verbose=False, **kwargs):  Tiago Peixoto committed Aug 02, 2009 75  r"""  Tiago Peixoto committed Apr 25, 2013 76 77 78 79 80 81 82  Generate a random graph, with a given degree distribution and (optionally) vertex-vertex correlation. The graph will be randomized via the :func:~graph_tool.generation.random_rewire function, and any remaining parameters will be passed to that function. Please read its documentation for all the options regarding the different statistical models which can be chosen.  Tiago Peixoto committed Aug 02, 2009 83 84 85 86 87 88 89 90 91 92 93  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.  Tiago Peixoto committed Aug 27, 2011 94   Tiago Peixoto committed Nov 18, 2011 95  Optionally, you can also pass a function which receives one or two  Tiago Peixoto committed Oct 20, 2016 96  arguments. If block_membership is None, the single argument passed  Tiago Peixoto committed May 01, 2013 97  will be the index of the vertex which will receive the degree. If  Tiago Peixoto committed Oct 20, 2016 98  block_membership is not None, the first value passed will be the vertex  Tiago Peixoto committed Nov 18, 2011 99  index, and the second will be the block value of the vertex.  Tiago Peixoto committed Aug 27, 2011 100  directed : bool (optional, default: True)  Tiago Peixoto committed Aug 02, 2009 101  Whether the generated graph should be directed.  Tiago Peixoto committed Aug 27, 2011 102 103 104 105  parallel_edges : bool (optional, default: False) If True, parallel edges are allowed. self_loops : bool (optional, default: False) If True, self-loops are allowed.  Tiago Peixoto committed Apr 25, 2013 106  block_membership : list or :class:~numpy.ndarray or function (optional, default: None)  Tiago Peixoto committed Apr 25, 2013 107  If supplied, the graph will be sampled from a stochastic blockmodel  Tiago Peixoto committed May 01, 2013 108 109 110  ensemble, and this parameter specifies the block membership of the vertices, which will be passed to the :func:~graph_tool.generation.random_rewire function.  Tiago Peixoto committed Apr 25, 2013 111 112 113 114  If the value is a list or a :class:~numpy.ndarray, it must have len(block_membership) == N, and the values will define to which block each vertex belongs.  Tiago Peixoto committed Aug 27, 2011 115 116 117 118  If this value is a function, it will be used to sample the block types. It must be callable either with no arguments or with a single argument which will be the vertex index. In either case it must return  Tiago Peixoto committed Nov 18, 2011 119  a type compatible with the block_type parameter.  120 121 122 123  See the documentation for the vertex_corr parameter of the :func:~graph_tool.generation.random_rewire function which specifies the correlation matrix.  Tiago Peixoto committed Nov 18, 2011 124  block_type : string (optional, default: "int")  Tiago Peixoto committed Oct 20, 2016 125  Value type of block labels. Valid only if block_membership is not None.  Tiago Peixoto committed Nov 18, 2011 126 127 128 129 130  degree_block : bool (optional, default: False) If True, the degree of each vertex will be appended to block labels when constructing the blockmodel, such that the resulting block type will be a pair :math:(r, k), where :math:r is the original block label.  Tiago Peixoto committed Aug 27, 2011 131 132 133 134 135  random : bool (optional, default: True) If True, the returned graph is randomized. Otherwise a deterministic placement of the edges will be used. verbose : bool (optional, default: False) If True, verbose information is displayed.  Tiago Peixoto committed Aug 02, 2009 136 137 138  Returns -------  Tiago Peixoto committed Oct 05, 2009 139  random_graph : :class:~graph_tool.Graph  Tiago Peixoto committed Aug 02, 2009 140  The generated graph.  Tiago Peixoto committed Aug 27, 2011 141 142  blocks : :class:~graph_tool.PropertyMap A vertex property map with the block values. This is only returned if  Tiago Peixoto committed Oct 20, 2016 143  block_membership is not None.  Tiago Peixoto committed Aug 02, 2009 144 145 146  See Also --------  Tiago Peixoto committed Apr 25, 2013 147  random_rewire: in-place graph shuffling  Tiago Peixoto committed Aug 02, 2009 148 149 150  Notes -----  Tiago Peixoto committed Feb 20, 2010 151 152 153  The algorithm makes sure the degree sequence is graphical (i.e. realizable) and keeps re-sampling the degrees if is not. With a valid degree sequence, the edges are placed deterministically, and later the graph is shuffled with  Tiago Peixoto committed Apr 25, 2013 154 155  the :func:~graph_tool.generation.random_rewire function, with all remaining parameters passed to it.  Tiago Peixoto committed Feb 20, 2010 156   Tiago Peixoto committed Aug 24, 2011 157  The complexity is :math:O(V + E) if parallel edges are allowed, and  Tiago Peixoto committed May 01, 2013 158  :math:O(V + E \times\text{n-iter}) if parallel edges are not allowed.  Tiago Peixoto committed Aug 24, 2011 159 160 161 162 163 164  .. note :: If parallel_edges == False this algorithm only guarantees that the returned graph will be a random sample from the desired ensemble if  Tiago Peixoto committed Apr 25, 2013 165  n_iter is sufficiently large. The algorithm implements an  Tiago Peixoto committed Aug 24, 2011 166 167 168 169  efficient Markov chain based on edge swaps, with a mixing time which depends on the degree distribution and correlations desired. If degree correlations are provided, the mixing time tends to be larger.  Tiago Peixoto committed Aug 02, 2009 170 171  Examples --------  Tiago Peixoto committed Dec 26, 2012 172 173 174 175  .. testcode:: :hide:  Tiago Peixoto committed Sep 21, 2015 176  import numpy.random  Tiago Peixoto committed Dec 26, 2012 177  from pylab import *  Tiago Peixoto committed Sep 21, 2015 178  np.random.seed(43)  Tiago Peixoto committed Dec 26, 2012 179  gt.seed_rng(42)  Tiago Peixoto committed Aug 02, 2009 180 181 182 183 184 185 186  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:  Tiago Peixoto committed Sep 21, 2015 187 188  ... k = np.random.randint(1,max+1) ... accept = np.random.random() < 1.0/k  Tiago Peixoto committed Aug 02, 2009 189 190 191 192 193 194 195 196 197 198 199  ... 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|}  Tiago Peixoto committed Dec 04, 2016 200 201  >>> g = gt.random_graph(1000, lambda: sample_k(40), model="probabilistic-configuration", ... edge_probs=lambda i, k: 1.0 / (1 + abs(i - k)), directed=False,  Tiago Peixoto committed Apr 25, 2013 202  ... n_iter=100)  Tiago Peixoto committed Aug 02, 2009 203 204 205 206 207 208 209 210 211 212 213 214  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:  Tiago Peixoto committed Sep 21, 2015 215  ... return np.random.poisson(4), np.random.poisson(4)  Tiago Peixoto committed Aug 02, 2009 216  ... else:  Tiago Peixoto committed Sep 21, 2015 217  ... return np.random.poisson(20), np.random.poisson(20)  Tiago Peixoto committed Dec 26, 2012 218  ...  Tiago Peixoto committed Aug 02, 2009 219 220 221 222 223 224 225  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")  Tiago Peixoto committed Apr 30, 2012 226  >>>  Tiago Peixoto committed Sep 09, 2014 227 228  >>> figure() <...>  Tiago Peixoto committed Oct 31, 2012 229  >>> imshow(hist[0].T, interpolation="nearest", origin="lower")  Tiago Peixoto committed Aug 02, 2009 230 231 232  <...> >>> colorbar() <...>  Tiago Peixoto committed Oct 05, 2009 233  >>> xlabel("in-degree")  Tiago Peixoto committed Aug 02, 2009 234  <...>  Tiago Peixoto committed Oct 05, 2009 235  >>> ylabel("out-degree")  Tiago Peixoto committed Aug 02, 2009 236  <...>  Tiago Peixoto committed Sep 09, 2014 237  >>> tight_layout()  Tiago Peixoto committed Sep 24, 2017 238  >>> savefig("combined-deg-hist.svg")  Tiago Peixoto committed Aug 02, 2009 239   Tiago Peixoto committed Dec 26, 2012 240 241 242  .. testcode:: :hide:  Tiago Peixoto committed Sep 24, 2017 243  savefig("combined-deg-hist.pdf")  Tiago Peixoto committed Dec 26, 2012 244   Tiago Peixoto committed Sep 02, 2011 245  .. figure:: combined-deg-hist.*  Tiago Peixoto committed Aug 02, 2009 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263  :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)),  Tiago Peixoto committed Dec 04, 2016 264 265 266  ... model="probabilistic-configuration", ... edge_probs=lambda a,b: (p.pmf(a[0], b[1]) * ... p.pmf(a[1], 20 - b[0])),  Tiago Peixoto committed Apr 25, 2013 267  ... n_iter=100)  Tiago Peixoto committed Aug 02, 2009 268 269 270  Lets plot the average degree correlations to check.  Tiago Peixoto committed Sep 24, 2017 271  >>> figure(figsize=(6,3))  Tiago Peixoto committed Dec 06, 2009 272  <...>  Tiago Peixoto committed Sep 26, 2017 273  >>> corr = gt.avg_neighbor_corr(g, "in", "in")  Tiago Peixoto committed Jul 13, 2010 274  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 275  ... label=r"$\left<\text{in}\right>$ vs in")  Tiago Peixoto committed Apr 30, 2012 276  <...>  Tiago Peixoto committed Sep 26, 2017 277  >>> corr = gt.avg_neighbor_corr(g, "in", "out")  Tiago Peixoto committed Jul 13, 2010 278  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 279  ... label=r"$\left<\text{out}\right>$ vs in")  Tiago Peixoto committed Apr 30, 2012 280  <...>  Tiago Peixoto committed Sep 26, 2017 281  >>> corr = gt.avg_neighbor_corr(g, "out", "in")  Tiago Peixoto committed Jul 13, 2010 282  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 283  ... label=r"$\left<\text{in}\right>$ vs out")  Tiago Peixoto committed Apr 30, 2012 284  <...>  Tiago Peixoto committed Sep 26, 2017 285  >>> corr = gt.avg_neighbor_corr(g, "out", "out")  Tiago Peixoto committed Jul 13, 2010 286  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 287  ... label=r"$\left<\text{out}\right>$ vs out")  Tiago Peixoto committed Aug 02, 2009 288  <...>  Tiago Peixoto committed Sep 24, 2017 289  >>> legend(loc='center left', bbox_to_anchor=(1, 0.5))  Tiago Peixoto committed Apr 30, 2012 290 291  <...> >>> xlabel("Source degree")  Tiago Peixoto committed Aug 02, 2009 292  <...>  Tiago Peixoto committed Apr 30, 2012 293  >>> ylabel("Average target degree")  Tiago Peixoto committed Aug 02, 2009 294  <...>  Tiago Peixoto committed Sep 09, 2014 295  >>> tight_layout()  Tiago Peixoto committed Sep 24, 2017 296 297 298  >>> box = gca().get_position() >>> gca().set_position([box.x0, box.y0, box.width * 0.7, box.height]) >>> savefig("deg-corr-dir.svg")  Tiago Peixoto committed Aug 02, 2009 299   Tiago Peixoto committed Dec 26, 2012 300 301 302  .. testcode:: :hide:  Tiago Peixoto committed Sep 24, 2017 303  savefig("deg-corr-dir.pdf")  Tiago Peixoto committed Dec 26, 2012 304   Tiago Peixoto committed Sep 02, 2011 305  .. figure:: deg-corr-dir.*  Tiago Peixoto committed Aug 02, 2009 306 307  :align: center  Tiago Peixoto committed Sep 26, 2017 308  Average nearest neighbor correlations.  Tiago Peixoto committed Aug 27, 2011 309 310   Tiago Peixoto committed Apr 25, 2013 311  **Stochastic blockmodels**  Tiago Peixoto committed Aug 27, 2011 312 313   Tiago Peixoto committed Nov 18, 2011 314 315 316  The following example shows how a stochastic blockmodel [holland-stochastic-1983]_ [karrer-stochastic-2011]_ can be generated. We will consider a system of 10 blocks, which form communities. The connection  Tiago Peixoto committed Aug 27, 2011 317 318  probability will be given by  Tiago Peixoto committed Dec 04, 2016 319  >>> def prob(a, b):  Tiago Peixoto committed Aug 27, 2011 320 321 322 323 324 325 326  ... if a == b: ... return 0.999 ... else: ... return 0.001 The blockmodel can be generated as follows.  Tiago Peixoto committed Sep 02, 2013 327  >>> g, bm = gt.random_graph(2000, lambda: poisson(10), directed=False,  Tiago Peixoto committed Dec 04, 2016 328  ... model="blockmodel",  Tiago Peixoto committed Apr 25, 2013 329  ... block_membership=lambda: randint(10),  Tiago Peixoto committed Dec 04, 2016 330  ... edge_probs=prob)  Tiago Peixoto committed May 02, 2013 331  >>> gt.graph_draw(g, vertex_fill_color=bm, edge_color="black", output="blockmodel.pdf")  Tiago Peixoto committed Aug 27, 2011 332 333  <...>  Tiago Peixoto committed Dec 26, 2012 334 335 336  .. testcode:: :hide:  Tiago Peixoto committed May 02, 2013 337  gt.graph_draw(g, vertex_fill_color=bm, edge_color="black", output="blockmodel.png")  Tiago Peixoto committed Dec 26, 2012 338   Tiago Peixoto committed Sep 02, 2011 339  .. figure:: blockmodel.*  Tiago Peixoto committed Aug 27, 2011 340 341 342 343 344 345 346 347 348 349  :align: center Simple blockmodel with 10 blocks. References ---------- .. [metropolis-equations-1953] Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. "Equations of State Calculations by Fast Computing Machines". Journal of Chemical Physics 21  Tiago Peixoto committed Dec 26, 2012 350  (6): 1087-1092 (1953). :doi:10.1063/1.1699114  Tiago Peixoto committed Aug 27, 2011 351  .. [hastings-monte-carlo-1970] Hastings, W.K. "Monte Carlo Sampling Methods  Tiago Peixoto committed Dec 26, 2012 352  Using Markov Chains and Their Applications". Biometrika 57 (1): 97-109 (1970).  Tiago Peixoto committed Aug 27, 2011 353  :doi:10.1093/biomet/57.1.97  Tiago Peixoto committed Nov 18, 2011 354 355 356 357 358 359  .. [holland-stochastic-1983] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt, "Stochastic blockmodels: First steps," Social Networks 5, no. 2: 109-13 (1983) :doi:10.1016/0378-8733(83)90021-7 .. [karrer-stochastic-2011] Brian Karrer and M. E. J. Newman, "Stochastic blockmodels and community structure in networks," Physical Review E 83, no. 1: 016107 (2011) :doi:10.1103/PhysRevE.83.016107 :arxiv:1008.3926  Tiago Peixoto committed Aug 02, 2009 360  """  Tiago Peixoto committed Aug 24, 2011 361   Tiago Peixoto committed Apr 10, 2008 362  g = Graph()  Tiago Peixoto committed Aug 27, 2011 363   Tiago Peixoto committed Apr 25, 2013 364 365  if (type(block_membership) is types.FunctionType or type(block_membership) is types.LambdaType):  Tiago Peixoto committed Nov 18, 2011 366 367  btype = block_type bm = []  Tiago Peixoto committed Apr 25, 2013 368  if len(inspect.getargspec(block_membership)[0]) == 0:  Tiago Peixoto committed Jun 03, 2012 369  for i in range(N):  Tiago Peixoto committed Apr 25, 2013 370  bm.append(block_membership())  Tiago Peixoto committed Aug 27, 2011 371  else:  Tiago Peixoto committed Jun 03, 2012 372  for i in range(N):  Tiago Peixoto committed Apr 25, 2013 373 374 375 376  bm.append(block_membership(i)) block_membership = bm elif block_membership is not None: btype = _gt_type(block_membership[0])  Tiago Peixoto committed Aug 27, 2011 377 378  if len(inspect.getargspec(deg_sampler)[0]) > 0:  Tiago Peixoto committed Apr 25, 2013 379 380  if block_membership is not None: sampler = lambda i: deg_sampler(i, block_membership[i])  Tiago Peixoto committed Aug 27, 2011 381  else:  Tiago Peixoto committed Oct 12, 2011 382  sampler = deg_sampler  Tiago Peixoto committed Aug 27, 2011 383 384 385  else: sampler = lambda i: deg_sampler()  Tiago Peixoto committed Sep 22, 2016 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402  if not directed: def sampler_wrap(*args): k = sampler(*args) try: return int(k) except: raise ValueError("degree value not understood: " + str(k)) else: def sampler_wrap(*args): k = sampler(*args) try: return int(k[0]), int(k[1]) except: raise ValueError("(in,out)-degree value pair not understood: " + str(k)) libgraph_tool_generation.gen_graph(g._Graph__graph, N, sampler_wrap,  Tiago Peixoto committed Apr 25, 2013 403  not parallel_edges,  Tiago Peixoto committed Aug 24, 2011 404  not self_loops, not directed,  Tiago Peixoto committed Dec 26, 2012 405  _get_rng(), verbose, True)  Tiago Peixoto committed Aug 27, 2011 406 407  g.set_directed(directed)  Tiago Peixoto committed Nov 18, 2011 408 409 410 411 412 413 414 415 416 417 418 419  if degree_block: if btype in ["object", "string"] or "vector" in btype: btype = "object" elif btype in ["int", "int32_t", "bool"]: btype = "vector" elif btype in ["long", "int64_t"]: btype = "vector" elif btype in ["double"]: btype = "vector" elif btype in ["long double"]: btype = "vector"  Tiago Peixoto committed Apr 25, 2013 420  if block_membership is not None:  Tiago Peixoto committed Aug 27, 2011 421 422 423  bm = g.new_vertex_property(btype) if btype in ["object", "string"] or "vector" in btype: for v in g.vertices():  Tiago Peixoto committed Nov 18, 2011 424  if not degree_block:  Tiago Peixoto committed Apr 25, 2013 425  bm[v] = block_membership[int(v)]  Tiago Peixoto committed Nov 18, 2011 426 427  else: if g.is_directed():  Tiago Peixoto committed Apr 25, 2013 428  bm[v] = (block_membership[int(v)], v.in_degree(),  Tiago Peixoto committed Nov 18, 2011 429 430  v.out_degree()) else:  Tiago Peixoto committed Apr 25, 2013 431  bm[v] = (block_membership[int(v)], v.out_degree())  Tiago Peixoto committed Aug 27, 2011 432 433  else: try:  Tiago Peixoto committed Apr 25, 2013 434  bm.a = block_membership  Tiago Peixoto committed Aug 27, 2011 435 436 437  except ValueError: bm = g.new_vertex_property("object") for v in g.vertices():  Tiago Peixoto committed Apr 25, 2013 438  bm[v] = block_membership[int(v)]  Tiago Peixoto committed Aug 27, 2011 439 440  else: bm = None  Tiago Peixoto committed Aug 24, 2011 441   Tiago Peixoto committed Feb 20, 2010 442  if random:  Tiago Peixoto committed Dec 24, 2013 443  g.set_fast_edge_removal(True)  Tiago Peixoto committed Apr 25, 2013 444 445 446  random_rewire(g, parallel_edges=parallel_edges, self_loops=self_loops, verbose=verbose, block_membership=bm, **kwargs)  Tiago Peixoto committed Dec 24, 2013 447  g.set_fast_edge_removal(False)  Tiago Peixoto committed Aug 24, 2011 448   Tiago Peixoto committed Aug 27, 2011 449 450 451 452  if bm is None: return g else: return g, bm  Tiago Peixoto committed Aug 04, 2009 453   Tiago Peixoto committed May 03, 2010 454   Tiago Peixoto committed Dec 04, 2016 455 456 @_limit_args({"model": ["erdos", "configuration", "constrained-configuration", "probabilistic-configuration", "blockmodel-degree",  457  "blockmodel", "blockmodel-micro"]})  Tiago Peixoto committed Dec 04, 2016 458 def random_rewire(g, model="configuration", n_iter=1, edge_sweep=True,  459  parallel_edges=False, self_loops=False, configuration=True,  Tiago Peixoto committed Oct 02, 2017 460 461  edge_probs=None, block_membership=None, cache_probs=True, persist=False, pin=None, ret_fail=False, verbose=False):  Tiago Peixoto committed Dec 04, 2016 462  r"""Shuffle the graph in-place, following a variety of possible statistical  Tiago Peixoto committed Apr 25, 2013 463 464  models, chosen via the parameter model.  Tiago Peixoto committed Aug 07, 2009 465 466 467  Parameters ----------  Tiago Peixoto committed Oct 05, 2009 468  g : :class:~graph_tool.Graph  Tiago Peixoto committed Aug 07, 2009 469  Graph to be shuffled. The graph will be modified.  Tiago Peixoto committed Dec 04, 2016 470  model : string (optional, default: "configuration")  Tiago Peixoto committed Apr 25, 2013 471 472  The following statistical models can be chosen, which determine how the edges are rewired.  Tiago Peixoto committed May 01, 2013 473   Tiago Peixoto committed Apr 25, 2013 474 475  erdos The edges will be rewired entirely randomly, and the resulting graph  Tiago Peixoto committed Dec 04, 2016 476 477  will correspond to the :math:G(N,E) Erdős–Rényi model. configuration  Tiago Peixoto committed Apr 25, 2013 478 479  The edges will be rewired randomly, but the degree sequence of the graph will remain unmodified.  Tiago Peixoto committed Dec 04, 2016 480  constrained-configuration  Tiago Peixoto committed Apr 25, 2013 481  The edges will be rewired randomly, but both the degree sequence of  482 483 484  the graph and the *vertex-vertex (in,out)-degree correlations* will remain exactly preserved. If the block_membership parameter is passed, the block variables at the endpoints of the edges will be  Tiago Peixoto committed Dec 04, 2016 485 486 487 488 489 490 491 492 493 494  preserved, instead of the degree-degree correlation. probabilistic-configuration This is similar to constrained-configuration, but the vertex-vertex correlations are not preserved, but are instead sampled from an arbitrary degree-based probabilistic model specified via the edge_probs parameter. The degree-sequence is preserved. blockmodel-degree This is just like probabilistic-configuration, but the values passed to the edge_probs function will correspond to the block membership values specified by the block_membership parameter.  Tiago Peixoto committed Apr 25, 2013 495  blockmodel  Tiago Peixoto committed Dec 04, 2016 496 497  This is just like blockmodel-degree, but the degree sequence *is not* preserved during rewiring.  498 499 500  blockmodel-micro This is like blockmodel, but the exact number of edges between groups is preserved as well.  Tiago Peixoto committed Aug 24, 2011 501 502 503 504 505 506 507 508 509  n_iter : int (optional, default: 1) Number of iterations. If edge_sweep == True, each iteration corresponds to an entire "sweep" over all edges. Otherwise this corresponds to the total number of edges which are randomly chosen for a swap attempt (which may repeat). edge_sweep : bool (optional, default: True) If True, each iteration will perform an entire "sweep" over the edges, where each edge is visited once in random order, and a edge swap is attempted.  Tiago Peixoto committed Feb 04, 2014 510  parallel_edges : bool (optional, default: False)  Tiago Peixoto committed Aug 24, 2011 511 512 513  If True, parallel edges are allowed. self_loops : bool (optional, default: False) If True, self-loops are allowed.  514 515 516 517 518 519  configuration : bool (optional, default: True) If True, graphs are sampled from the corresponding maximum-entropy ensemble of configurations (i.e. distinguishable half-edge pairings), otherwise they are sampled from the maximum-entropy ensemble of graphs (i.e. indistinguishable half-edge pairings). The distinction is only relevant if parallel edges are allowed.  Tiago Peixoto committed Dec 04, 2016 520 521 522  edge_probs : function or sequence of triples (optional, default: None) A function which determines the edge probabilities in the graph. In general it should have the following signature:  523 524 525  .. code::  Tiago Peixoto committed Dec 04, 2016 526  def prob(r, s):  527 528 529  ... return p  Tiago Peixoto committed Dec 04, 2016 530  where the return value should be a non-negative scalar.  Tiago Peixoto committed Apr 25, 2013 531   Tiago Peixoto committed Dec 04, 2016 532 533 534 535  Alternatively, this parameter can be a list of triples of the form (r, s, p), with the same meaning as the r, s and p values above. If a given (r, s) combination is not present in this list, the corresponding value of p is assumed to be zero. If the same  536  (r, s) combination appears more than once, their p values will  Tiago Peixoto committed Dec 04, 2016 537 538 539 540 541 542 543 544 545 546 547 548 549 550  be summed together. This is useful when the correlation matrix is sparse, i.e. most entries are zero. If model == probabilistic-configuration the parameters r and s correspond respectively to the (in, out)-degree pair of the source vertex of an edge, and the (in,out)-degree pair of the target of the same edge (for undirected graphs, both parameters are scalars instead). The value of p should be a number proportional to the probability of such an edge existing in the generated graph. If model == blockmodel-degree or model == blockmodel, the r and s values passed to the function will be the block values of the respective vertices, as specified via the block_membership parameter. The value of p should be a number proportional to the  551  probability of such an edge existing in the generated graph.  Tiago Peixoto committed Apr 25, 2013 552 553 554 555  block_membership : :class:~graph_tool.PropertyMap (optional, default: None) If supplied, the graph will be rewired to conform to a blockmodel ensemble. The value must be a vertex property map which defines the block of each vertex.  Tiago Peixoto committed Apr 30, 2012 556  cache_probs : bool (optional, default: True)  Tiago Peixoto committed Dec 04, 2016 557  If True, the probabilities returned by the edge_probs parameter  Tiago Peixoto committed Apr 30, 2012 558 559 560 561  will be cached internally. This is crucial for good performance, since in this case the supplied python function is called only a few times, and not at every attempted edge rewire move. However, in the case were the different parameter combinations to the probability function is very  Tiago Peixoto committed Apr 25, 2013 562 563 564 565 566 567 568 569  large, the memory and time requirements to keep the cache may not be worthwhile. persist : bool (optional, default: False) If True, an edge swap which is rejected will be attempted again until it succeeds. This may improve the quality of the shuffling for some probabilistic models, and should be sufficiently fast for sparse graphs, but otherwise it may result in many repeated attempts for certain corner-cases in which edges are difficult to swap.  Tiago Peixoto committed Mar 14, 2014 570 571 572 573  pin : :class:~graph_tool.PropertyMap (optional, default: None) Edge property map which, if provided, specifies which edges are allowed to be rewired. Edges for which the property value is 1 (or True) will be left unmodified in the graph.  Tiago Peixoto committed Aug 24, 2011 574 575 576 577 578 579  verbose : bool (optional, default: False) If True, verbose information is displayed. Returns -------  Tiago Peixoto committed Apr 25, 2013 580 581 582  rejection_count : int Number of rejected edge moves (due to parallel edges or self-loops, or the probabilistic model used).  Tiago Peixoto committed Aug 07, 2009 583 584 585 586 587 588 589  See Also -------- random_graph: random graph generation Notes -----  Tiago Peixoto committed Feb 20, 2010 590  This algorithm iterates through all the edges in the network and tries to  Tiago Peixoto committed Apr 25, 2013 591 592  swap its target or source with the target or source of another edge. The selected canditate swaps are chosen according to the model parameter.  Tiago Peixoto committed Feb 20, 2010 593 594  .. note::  Tiago Peixoto committed Aug 07, 2009 595   Tiago Peixoto committed Aug 24, 2011 596 597 598 599 600 601 602 603  If parallel_edges = False, parallel edges are not placed during rewiring. In this case, the returned graph will be a uncorrelated sample from the desired ensemble only if n_iter is sufficiently large. The algorithm implements an efficient Markov chain based on edge swaps, with a mixing time which depends on the degree distribution and correlations desired. If degree probabilistic correlations are provided, the mixing time tends to be larger.  Tiago Peixoto committed Jan 01, 2017 604 605 606 607 608 609 610  If model is either "probabilistic-configuration", "blockmodel" or "blockmodel-degree", the Markov chain still needs to be mixed, even if parallel edges and self-loops are allowed. In this case the Markov chain is implemented using the Metropolis-Hastings [metropolis-equations-1953]_ [hastings-monte-carlo-1970]_ acceptance/rejection algorithm. It will eventually converge to the desired probabilities for sufficiently large values of n_iter.  Tiago Peixoto committed Aug 24, 2011 611   Tiago Peixoto committed Feb 20, 2010 612   Tiago Peixoto committed Aug 24, 2011 613  Each edge is tentatively swapped once per iteration, so the overall  Tiago Peixoto committed Sep 02, 2011 614 615  complexity is :math:O(V + E \times \text{n-iter}). If edge_sweep == False, the complexity becomes :math:O(V + E + \text{n-iter}).  Tiago Peixoto committed Aug 24, 2011 616   Tiago Peixoto committed Aug 07, 2009 617 618 619 620 621  Examples -------- Some small graphs for visualization.  Tiago Peixoto committed Dec 26, 2012 622 623 624 625 626 627 628 629  .. testcode:: :hide: from numpy.random import random, seed from pylab import * seed(43) gt.seed_rng(42)  Tiago Peixoto committed Sep 21, 2015 630  >>> g, pos = gt.triangulation(np.random.random((1000,2)))  Tiago Peixoto committed Apr 30, 2012 631  >>> pos = gt.arf_layout(g)  Tiago Peixoto committed Dec 26, 2012 632  >>> gt.graph_draw(g, pos=pos, output="rewire_orig.pdf", output_size=(300, 300))  Tiago Peixoto committed Sep 03, 2009 633  <...>  Tiago Peixoto committed Dec 26, 2012 634 635 636 637 638 639  .. testcode:: :hide: gt.graph_draw(g, pos=pos, output="rewire_orig.png", output_size=(300, 300))  Tiago Peixoto committed Dec 04, 2016 640  >>> ret = gt.random_rewire(g, "constrained-configuration")  Tiago Peixoto committed Apr 30, 2012 641  >>> pos = gt.arf_layout(g)  Tiago Peixoto committed Dec 26, 2012 642  >>> gt.graph_draw(g, pos=pos, output="rewire_corr.pdf", output_size=(300, 300))  Tiago Peixoto committed Sep 03, 2009 643  <...>  Tiago Peixoto committed Dec 26, 2012 644 645 646 647 648 649  .. testcode:: :hide: gt.graph_draw(g, pos=pos, output="rewire_corr.png", output_size=(300, 300))  Tiago Peixoto committed Sep 21, 2015 650  >>> ret = gt.random_rewire(g)  Tiago Peixoto committed Apr 30, 2012 651  >>> pos = gt.arf_layout(g)  Tiago Peixoto committed Dec 26, 2012 652  >>> gt.graph_draw(g, pos=pos, output="rewire_uncorr.pdf", output_size=(300, 300))  Tiago Peixoto committed Sep 03, 2009 653  <...>  Tiago Peixoto committed Dec 26, 2012 654 655 656 657 658 659  .. testcode:: :hide: gt.graph_draw(g, pos=pos, output="rewire_uncorr.png", output_size=(300, 300))  Tiago Peixoto committed Sep 21, 2015 660  >>> ret = gt.random_rewire(g, "erdos")  Tiago Peixoto committed Apr 30, 2012 661  >>> pos = gt.arf_layout(g)  Tiago Peixoto committed Dec 26, 2012 662  >>> gt.graph_draw(g, pos=pos, output="rewire_erdos.pdf", output_size=(300, 300))  Tiago Peixoto committed Dec 21, 2009 663  <...>  Tiago Peixoto committed Aug 07, 2009 664   Tiago Peixoto committed Dec 26, 2012 665 666 667 668 669  .. testcode:: :hide: gt.graph_draw(g, pos=pos, output="rewire_erdos.png", output_size=(300, 300))  Tiago Peixoto committed Oct 05, 2009 670  Some ridiculograms _ :  Tiago Peixoto committed Aug 07, 2009 671   Tiago Peixoto committed Sep 02, 2011 672 673 674 675  .. image:: rewire_orig.* .. image:: rewire_corr.* .. image:: rewire_uncorr.* .. image:: rewire_erdos.*  Tiago Peixoto committed Aug 07, 2009 676   Tiago Peixoto committed Apr 30, 2012 677 678  **From left to right**: Original graph; Shuffled graph, with degree correlations; Shuffled graph, without degree correlations; Shuffled graph, with random degrees.  Tiago Peixoto committed Aug 07, 2009 679   Tiago Peixoto committed Apr 30, 2012 680  We can try with larger graphs to get better statistics, as follows.  Tiago Peixoto committed Aug 07, 2009 681   Tiago Peixoto committed Sep 24, 2017 682  >>> figure(figsize=(6,3))  Tiago Peixoto committed Dec 06, 2009 683  <...>  Tiago Peixoto committed Dec 04, 2016 684 685  >>> g = gt.random_graph(30000, lambda: sample_k(20), model="probabilistic-configuration", ... edge_probs=lambda i, j: exp(abs(i-j)), directed=False,  Tiago Peixoto committed Apr 25, 2013 686  ... n_iter=100)  Tiago Peixoto committed Sep 26, 2017 687  >>> corr = gt.avg_neighbor_corr(g, "out", "out")  Tiago Peixoto committed Apr 30, 2012 688 689  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-", label="Original") <...>  Tiago Peixoto committed Dec 04, 2016 690  >>> ret = gt.random_rewire(g, "constrained-configuration")  Tiago Peixoto committed Sep 26, 2017 691  >>> corr = gt.avg_neighbor_corr(g, "out", "out")  Tiago Peixoto committed Apr 30, 2012 692 693  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="*", label="Correlated") <...>  Tiago Peixoto committed Sep 21, 2015 694  >>> ret = gt.random_rewire(g)  Tiago Peixoto committed Sep 26, 2017 695  >>> corr = gt.avg_neighbor_corr(g, "out", "out")  Tiago Peixoto committed Apr 30, 2012 696 697  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-", label="Uncorrelated") <...>  Tiago Peixoto committed Sep 21, 2015 698  >>> ret = gt.random_rewire(g, "erdos")  Tiago Peixoto committed Sep 26, 2017 699  >>> corr = gt.avg_neighbor_corr(g, "out", "out")  Tiago Peixoto committed Apr 30, 2012 700 701  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-", label=r"Erd\H{o}s") <...>  Tiago Peixoto committed Aug 07, 2009 702 703 704 705  >>> xlabel("$k$") <...> >>> ylabel(r"$\left$") <...>  Tiago Peixoto committed Sep 24, 2017 706  >>> legend(loc='center left', bbox_to_anchor=(1, 0.5))  Tiago Peixoto committed Aug 07, 2009 707  <...>  Tiago Peixoto committed Sep 25, 2017 708  >>> tight_layout()  Tiago Peixoto committed Sep 24, 2017 709 710 711  >>> box = gca().get_position() >>> gca().set_position([box.x0, box.y0, box.width * 0.7, box.height]) >>> savefig("shuffled-stats.svg")  Tiago Peixoto committed Aug 07, 2009 712   Tiago Peixoto committed Dec 26, 2012 713 714 715  .. testcode:: :hide:  Tiago Peixoto committed Sep 24, 2017 716  savefig("shuffled-stats.pdf")  Tiago Peixoto committed Dec 26, 2012 717 718   Tiago Peixoto committed Sep 02, 2011 719  .. figure:: shuffled-stats.*  Tiago Peixoto committed Aug 07, 2009 720 721 722 723 724 725 726 727 728 729 730  :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)),  Tiago Peixoto committed Dec 04, 2016 731 732  ... model="probabilistic-configuration", ... edge_probs=lambda a, b: (p.pmf(a[0], b[1]) * p.pmf(a[1], 20 - b[0])),  Tiago Peixoto committed Apr 25, 2013 733  ... n_iter=100)  Tiago Peixoto committed Sep 24, 2017 734  >>> figure(figsize=(6,3))  Tiago Peixoto committed Dec 06, 2009 735  <...>  Tiago Peixoto committed Sep 26, 2017 736  >>> corr = gt.avg_neighbor_corr(g, "in", "out")  Tiago Peixoto committed Jul 13, 2010 737  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 738  ... label=r"$\left<\text{o}\right>$ vs i")  Tiago Peixoto committed Apr 30, 2012 739  <...>  Tiago Peixoto committed Sep 26, 2017 740  >>> corr = gt.avg_neighbor_corr(g, "out", "in")  Tiago Peixoto committed Jul 13, 2010 741  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 742  ... label=r"$\left<\text{i}\right>$ vs o")  Tiago Peixoto committed Apr 30, 2012 743  <...>  Tiago Peixoto committed Dec 04, 2016 744  >>> ret = gt.random_rewire(g, "constrained-configuration")  Tiago Peixoto committed Sep 26, 2017 745  >>> corr = gt.avg_neighbor_corr(g, "in", "out")  Tiago Peixoto committed Jul 13, 2010 746  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 747  ... label=r"$\left<\text{o}\right>$ vs i, corr.")  Tiago Peixoto committed Apr 30, 2012 748  <...>  Tiago Peixoto committed Sep 26, 2017 749  >>> corr = gt.avg_neighbor_corr(g, "out", "in")  Tiago Peixoto committed Jul 13, 2010 750  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 751  ... label=r"$\left<\text{i}\right>$ vs o, corr.")  Tiago Peixoto committed Apr 30, 2012 752  <...>  Tiago Peixoto committed Dec 04, 2016 753  >>> ret = gt.random_rewire(g, "configuration")  Tiago Peixoto committed Sep 26, 2017 754  >>> corr = gt.avg_neighbor_corr(g, "in", "out")  Tiago Peixoto committed Jul 13, 2010 755  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 756  ... label=r"$\left<\text{o}\right>$ vs i, uncorr.")  Tiago Peixoto committed Apr 30, 2012 757  <...>  Tiago Peixoto committed Sep 26, 2017 758  >>> corr = gt.avg_neighbor_corr(g, "out", "in")  Tiago Peixoto committed Jul 13, 2010 759  >>> errorbar(corr[2][:-1], corr[0], yerr=corr[1], fmt="o-",  Tiago Peixoto committed Oct 05, 2009 760  ... label=r"$\left<\text{i}\right>$ vs o, uncorr.")  Tiago Peixoto committed Aug 07, 2009 761  <...>  Tiago Peixoto committed Sep 24, 2017 762  >>> legend(loc='center left', bbox_to_anchor=(1, 0.5))  Tiago Peixoto committed Apr 30, 2012 763 764  <...> >>> xlabel("Source degree")  Tiago Peixoto committed Aug 07, 2009 765  <...>  Tiago Peixoto committed Apr 30, 2012 766  >>> ylabel("Average target degree")  Tiago Peixoto committed Aug 07, 2009 767  <...>  Tiago Peixoto committed Sep 09, 2014 768  >>> tight_layout()  Tiago Peixoto committed Sep 24, 2017 769  >>> box = gca().get_position()  Tiago Peixoto committed Sep 25, 2017 770  >>> gca().set_position([box.x0, box.y0, box.width * 0.55, box.height])  Tiago Peixoto committed Sep 24, 2017 771  >>> savefig("shuffled-deg-corr-dir.svg")  Tiago Peixoto committed Aug 07, 2009 772   Tiago Peixoto committed Dec 26, 2012 773 774 775  .. testcode:: :hide:  Tiago Peixoto committed Sep 24, 2017 776  savefig("shuffled-deg-corr-dir.pdf")  Tiago Peixoto committed Dec 26, 2012 777   Tiago Peixoto committed Sep 02, 2011 778  .. figure:: shuffled-deg-corr-dir.*  Tiago Peixoto committed Aug 07, 2009 779 780 781 782 783 784  :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.  Tiago Peixoto committed Aug 27, 2011 785 786 787 788 789  References ---------- .. [metropolis-equations-1953] Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. "Equations of State Calculations by Fast Computing Machines". Journal of Chemical Physics 21  Tiago Peixoto committed Dec 26, 2012 790  (6): 1087-1092 (1953). :doi:10.1063/1.1699114  Tiago Peixoto committed Aug 27, 2011 791  .. [hastings-monte-carlo-1970] Hastings, W.K. "Monte Carlo Sampling Methods  Tiago Peixoto committed Dec 26, 2012 792  Using Markov Chains and Their Applications". Biometrika 57 (1): 97-109 (1970).  Tiago Peixoto committed Aug 27, 2011 793  :doi:10.1093/biomet/57.1.97  Tiago Peixoto committed Nov 18, 2011 794 795 796 797 798 799  .. [holland-stochastic-1983] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt, "Stochastic blockmodels: First steps," Social Networks 5, no. 2: 109-13 (1983) :doi:10.1016/0378-8733(83)90021-7 .. [karrer-stochastic-2011] Brian Karrer and M. E. J. Newman, "Stochastic blockmodels and community structure in networks," Physical Review E 83, no. 1: 016107 (2011) :doi:10.1103/PhysRevE.83.016107 :arxiv:1008.3926  Tiago Peixoto committed Aug 27, 2011 800 801  """  Tiago Peixoto committed Feb 20, 2010 802   Tiago Peixoto committed Dec 04, 2016 803 804  if (edge_probs is not None and not g.is_directed()) and "blockmodel" not in model: corr = lambda i, j: edge_probs(i[1], j[1])  Tiago Peixoto committed Feb 20, 2010 805  else:  Tiago Peixoto committed Dec 04, 2016 806  corr = edge_probs  Tiago Peixoto committed Feb 20, 2010 807   Tiago Peixoto committed Dec 04, 2016 808 809  if model not in ["probabilistic-configuration", "blockmodel", "blockmodel-degree"]:  Tiago Peixoto committed Aug 24, 2011 810  g = GraphView(g, reversed=False)  Tiago Peixoto committed Feb 23, 2017 811 812  elif edge_probs is None: raise ValueError("A function must be supplied as the 'edge_probs' parameter")  Tiago Peixoto committed Apr 25, 2013 813   Tiago Peixoto committed Dec 04, 2016 814  traditional = True  815  micro = False  Tiago Peixoto committed Dec 04, 2016 816  if model == "blockmodel-degree":  Tiago Peixoto committed Apr 25, 2013 817  model = "blockmodel"  Tiago Peixoto committed Dec 04, 2016 818  traditional = False  819 820 821  if model == "blockmodel-micro": model = "blockmodel" micro = True  822   Tiago Peixoto committed Mar 14, 2014 823 824 825 826 827 828  if pin is None: pin = g.new_edge_property("bool") if pin.value_type() != "bool": pin = pin.copy(value_type="bool")  829 830 831  fast = g.get_fast_edge_removal() if not fast: g.set_fast_edge_removal(True)  Tiago Peixoto committed Sep 25, 2015 832 833  pcount = libgraph_tool_generation.random_rewire(g._Graph__graph, _c_str(model),  Tiago Peixoto committed Aug 24, 2011 834 835  n_iter, not edge_sweep, self_loops, parallel_edges,  Tiago Peixoto committed Oct 02, 2017 836  configuration,  837  traditional, micro, persist, corr,  Tiago Peixoto committed Mar 14, 2014 838 839  _prop("e", g, pin), _prop("v", g, block_membership),  Tiago Peixoto committed Apr 30, 2012 840  cache_probs,  Tiago Peixoto committed Dec 26, 2012 841  _get_rng(), verbose)  842 843  if not fast: g.set_fast_edge_removal(False)  Tiago Peixoto committed Apr 25, 2013 844  return pcount  Tiago Peixoto committed Aug 17, 2009 845   Tiago Peixoto committed Sep 28, 2017 846 847 848 849 def generate_sbm(b, probs, out_degs=None, in_degs=None, directed=False, micro_ers=False, micro_degs=False): r"""Generate a random graph by sampling from the Poisson or microcanonical stochastic block model.  Tiago Peixoto committed Dec 04, 2016 850 851 852 853 854 855 856 857  Parameters ---------- b : iterable or :class:numpy.ndarray Group membership for each node. probs : two-dimensional :class:numpy.ndarray or :class:scipy.sparse.spmatrix Matrix with edge propensities between groups. The value probs[r,s] corresponds to the average number of edges between groups r and  Tiago Peixoto committed Dec 22, 2016 858 859  s (or twice the average number if r == s and the graph is undirected).  Tiago Peixoto committed Dec 04, 2016 860  out_degs : iterable or :class:numpy.ndarray (optional, default: None)  Tiago Peixoto committed Dec 22, 2016 861 862 863  Out-degree propensity for each node. If not provided, a constant value will be used. Note that the values will be normalized inside each group, if they are not already so.  Tiago Peixoto committed Dec 04, 2016 864  in_degs : iterable or :class:numpy.ndarray (optional, default: None)  Tiago Peixoto committed Dec 22, 2016 865 866 867  In-degree propensity for each node. If not provided, a constant value will be used. Note that the values will be normalized inside each group, if they are not already so.  Tiago Peixoto committed Dec 04, 2016 868 869  directed : bool (optional, default: False) Whether the graph is directed.  Tiago Peixoto committed Sep 28, 2017 870 871 872 873 874 875 876 877 878 879 880  micro_ers : bool (optional, default: False) If true, the microcanonical version of the model will be evoked, where the numbers of edges between groups will be given exactly by the parameter probs, and this will not fluctuate between samples. micro_degs : bool (optional, default: False) If true, the microcanonical version of the degree-corrected model will be evoked, where the degrees of nodes will be given exactly by the parameters out_degs and in_degs, and they will not fluctuate between samples. (If micro_degs == True it implies micro_ers == True.)  Tiago Peixoto committed Dec 04, 2016 881 882 883 884 885 886 887 888 889 890 891 892 893  Returns ------- g : :class:~graph_tool.Graph The generated graph. See Also -------- random_graph: random graph generation Notes -----  Tiago Peixoto committed Oct 09, 2017 894 895 896 897 898  The algorithm generates multigraphs with self-loops, according to the Poisson degree-corrected stochastic block model (SBM), which includes the traditional SBM as a special case. The multigraphs are generated with probability  Tiago Peixoto committed Dec 04, 2016 899 900 901  .. math::  Tiago Peixoto committed Sep 28, 2017 902  P({\boldsymbol A}|{\boldsymbol \theta},{\boldsymbol \lambda},{\boldsymbol b})  Tiago Peixoto committed Dec 04, 2016 903  = \prod_{i_ model is used instead, where both the number of edges between groups as well as the degrees of the nodes are preserved exactly, instead of only on expectation. In this case, the parameters are interpreted as :math:{\boldsymbol\lambda}\equiv{\boldsymbol e} and :math:{\boldsymbol\theta}\equiv{\boldsymbol k}, where :math:e_{rs} is the number of edges between groups :math:r and :math:s (or twice that if :math:r=s in the undirected case), and :math:k_i is the degree of node  Tiago Peixoto committed Oct 09, 2017 953 954  :math:i. This model is a generalization of the configuration model, where multigraphs are sampled with probability  Tiago Peixoto committed Sep 28, 2017 955 956 957 958 959 960 961 962 963 964 965 966 967  .. math:: P({\boldsymbol A}|{\boldsymbol k},{\boldsymbol e},{\boldsymbol b}) = \frac{\prod_{r>> g = gt.collection.data["polblogs"] >>> g = gt.GraphView(g, vfilt=gt.label_largest_component(g)) >>> g = gt.Graph(g, prune=True) >>> state = gt.minimize_blockmodel_dl(g)  Tiago Peixoto committed Jan 01, 2017 996  >>> u = gt.generate_sbm(state.b.a, gt.adjacency(state.get_bg(),  Tiago Peixoto committed Sep 28, 2017 997  ... state.get_ers()).T,  Tiago Peixoto committed Dec 04, 2016 998 999 1000  ... g.degree_property_map("out").a, ... g.degree_property_map("in").a, directed=True) >>> gt.graph_draw(g, g.vp.pos, output="polblogs-sbm.png") `