__init__.py 20.5 KB
 Tiago Peixoto committed Jul 15, 2008 1 #! /usr/bin/env python  Tiago Peixoto committed Mar 07, 2010 2 # -*- coding: utf-8 -*-  Tiago Peixoto committed Jul 15, 2008 3 #  Tiago Peixoto committed Mar 07, 2010 4 5 # graph_tool -- a general graph manipulation python module #  Tiago Peixoto committed Feb 14, 2018 6 # Copyright (C) 2006-2018 Tiago de Paula Peixoto  Tiago Peixoto committed Jul 15, 2008 7 8 9 10 11 12 13 14 15 16 17 18 19 20 # # 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 .  Tiago Peixoto committed Jan 11, 2009 21 """  Tiago Peixoto committed Jan 18, 2009 22 23 graph_tool.clustering - Clustering coefficients ---------------------------------------------------  Tiago Peixoto committed Jan 11, 2009 24 25 26  Provides algorithms for calculation of clustering coefficients, aka. transitivity.  Tiago Peixoto committed Oct 05, 2009 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41  Summary +++++++ .. autosummary:: :nosignatures: local_clustering global_clustering extended_clustering motifs motif_significance Contents ++++++++  Tiago Peixoto committed Jan 11, 2009 42 43 """  Tiago Peixoto committed Jun 03, 2012 44 45 from __future__ import division, absolute_import, print_function  Tiago Peixoto committed Oct 26, 2008 46 from .. dl_import import dl_import  Tiago Peixoto committed Jun 03, 2012 47 dl_import("from . import libgraph_tool_clustering as _gt")  Tiago Peixoto committed Jul 15, 2008 48   Tiago Peixoto committed Jun 12, 2013 49 from .. import _degree, _prop, Graph, GraphView, PropertyMap, _get_rng  Tiago Peixoto committed Sep 03, 2009 50 51 from .. topology import isomorphism from .. generation import random_rewire  Tiago Peixoto committed Sep 12, 2009 52 from .. stats import vertex_hist  Tiago Peixoto committed Jun 03, 2012 53   Tiago Peixoto committed Sep 12, 2009 54 from collections import defaultdict  Tiago Peixoto committed Jul 15, 2008 55 from numpy import *  Tiago Peixoto committed Oct 05, 2009 56 from numpy import random  Tiago Peixoto committed Mar 09, 2009 57 import sys  Tiago Peixoto committed Jul 15, 2008 58   Tiago Peixoto committed Mar 09, 2009 59 __all__ = ["local_clustering", "global_clustering", "extended_clustering",  Tiago Peixoto committed Apr 24, 2009 60  "motifs", "motif_significance"]  Tiago Peixoto committed Jul 15, 2008 61   Tiago Peixoto committed May 03, 2010 62   Tiago Peixoto committed Apr 07, 2019 63 def local_clustering(g, weight=None, prop=None, undirected=True):  Tiago Peixoto committed Jan 11, 2009 64  r"""  Tiago Peixoto committed Dec 14, 2009 65  Return the local clustering coefficients for all vertices.  Tiago Peixoto committed Jan 11, 2009 66 67 68  Parameters ----------  Tiago Peixoto committed Oct 05, 2009 69  g : :class:~graph_tool.Graph  Tiago Peixoto committed Jan 11, 2009 70  Graph to be used.  Tiago Peixoto committed May 26, 2019 71  weight : :class:~graph_tool.EdgePropertyMap, optional (default: None)  Tiago Peixoto committed Apr 07, 2019 72  Edge weights. If omitted, a constant value of 1 will be used.  Tiago Peixoto committed May 26, 2019 73  prop : :class:~graph_tool.VertexPropertyMap or string, optional  Tiago Peixoto committed Jan 11, 2009 74 75  Vertex property map where results will be stored. If specified, this parameter will also be the return value.  Tiago Peixoto committed Mar 07, 2011 76  undirected : bool (default: True)  Tiago Peixoto committed Jan 11, 2009 77 78 79 80 81  Calculate the *undirected* clustering coefficient, if graph is directed (this option has no effect if the graph is undirected). Returns -------  Tiago Peixoto committed May 26, 2019 82  prop : :class:~graph_tool.VertexPropertyMap  Tiago Peixoto committed Jan 11, 2009 83 84 85 86 87 88  Vertex property containing the clustering coefficients. See Also -------- global_clustering: global clustering coefficient extended_clustering: extended (generalized) clustering coefficient  Tiago Peixoto committed Mar 09, 2009 89  motifs: motif counting  Tiago Peixoto committed Jan 11, 2009 90 91 92  Notes -----  Tiago Peixoto committed Oct 05, 2009 93 94  The local clustering coefficient [watts-collective-1998]_ :math:c_i is defined as  Tiago Peixoto committed Jan 11, 2009 95 96 97 98 99 100 101 102 103  .. math:: c_i = \frac{|\{e_{jk}\}|}{k_i(k_i-1)} :\, v_j,v_k \in N_i,\, e_{jk} \in E where :math:k_i is the out-degree of vertex :math:i, and .. math:: N_i = \{v_j : e_{ij} \in E\}  Tiago Peixoto committed Sep 26, 2017 104  is the set of out-neighbors of vertex :math:i. For undirected graphs the  Tiago Peixoto committed Jan 11, 2009 105 106 107 108 109  value of :math:c_i is normalized as .. math:: c'_i = 2c_i.  Tiago Peixoto committed Apr 07, 2019 110 111  The implemented algorithm runs in :math:O(|V|\left) time, where :math:\left is second moment of the degree distribution.  Tiago Peixoto committed Jan 11, 2009 112 113 114 115 116  If enabled during compilation, this algorithm runs in parallel. Examples --------  Tiago Peixoto committed Nov 29, 2018 117  >>> g = gt.collection.data["karate"]  Tiago Peixoto committed Jan 11, 2009 118  >>> clust = gt.local_clustering(g)  Tiago Peixoto committed Jun 03, 2012 119  >>> print(gt.vertex_average(g, clust))  Tiago Peixoto committed Nov 29, 2018 120  (0.5706384782..., 0.05869813676...)  Tiago Peixoto committed Jan 11, 2009 121 122 123  References ----------  Tiago Peixoto committed Oct 05, 2009 124  .. [watts-collective-1998] D. J. Watts and Steven Strogatz, "Collective  Tiago Peixoto committed Dec 14, 2009 125  dynamics of 'small-world' networks", Nature, vol. 393, pp 440-442, 1998.  Tiago Peixoto committed Dec 21, 2010 126  :doi:10.1038/30918  Tiago Peixoto committed Jan 11, 2009 127 128  """  Tiago Peixoto committed Oct 19, 2016 129  if prop is None:  Tiago Peixoto committed Jul 15, 2008 130  prop = g.new_vertex_property("double")  Tiago Peixoto committed Apr 25, 2009 131  if g.is_directed() and undirected:  Tiago Peixoto committed Oct 19, 2016 132  g = GraphView(g, directed=False, skip_properties=True)  Tiago Peixoto committed Apr 07, 2019 133 134  _gt.local_clustering(g._Graph__graph, _prop("v", g, prop), _prop("e", g, weight))  Tiago Peixoto committed Jul 15, 2008 135 136  return prop  Tiago Peixoto committed May 03, 2010 137   Tiago Peixoto committed Apr 07, 2019 138 139 def global_clustering(g, weight=None): r"""Return the global clustering coefficient.  Tiago Peixoto committed Jan 11, 2009 140 141 142  Parameters ----------  Tiago Peixoto committed Oct 05, 2009 143  g : :class:~graph_tool.Graph  Tiago Peixoto committed Jan 11, 2009 144  Graph to be used.  Tiago Peixoto committed May 26, 2019 145  weight : :class:~graph_tool.EdgePropertyMap, optional (default: None)  Tiago Peixoto committed Apr 07, 2019 146  Edge weights. If omitted, a constant value of 1 will be used.  Tiago Peixoto committed Jan 11, 2009 147 148 149 150 151 152 153 154 155 156  Returns ------- c : tuple of floats Global clustering coefficient and standard deviation (jacknife method) See Also -------- local_clustering: local clustering coefficient extended_clustering: extended (generalized) clustering coefficient  Tiago Peixoto committed Mar 09, 2009 157  motifs: motif counting  Tiago Peixoto committed Jan 11, 2009 158 159 160  Notes -----  Tiago Peixoto committed Oct 05, 2009 161 162  The global clustering coefficient [newman-structure-2003]_ :math:c is defined as  Tiago Peixoto committed Jan 11, 2009 163 164 165 166 167  .. math:: c = 3 \times \frac{\text{number of triangles}} {\text{number of connected triples}}  Tiago Peixoto committed Apr 07, 2019 168 169 170 171 172 173 174 175 176 177 178  If weights are given, the following definition is used .. math:: c = \frac{\operatorname{Tr}{{\boldsymbol A}^3}}{\sum_{i\ne j}[{\boldsymbol A}^2]_{ij}}, where :math:\boldsymbol A is the weighted adjacency matrix, and it is assumed that the weights are normalized, i.e. :math:A_{ij} \le 1. The implemented algorithm runs in time :math:O(|V|\left), where :math:\left< k^2\right> is the second moment of the degree distribution.  Tiago Peixoto committed Jan 11, 2009 179 180 181 182 183  If enabled during compilation, this algorithm runs in parallel. Examples --------  Tiago Peixoto committed Nov 29, 2018 184  >>> g = gt.collection.data["karate"]  Tiago Peixoto committed Jun 03, 2012 185  >>> print(gt.global_clustering(g))  Tiago Peixoto committed Nov 29, 2018 186  (0.2556818181..., 0.06314746595...)  Tiago Peixoto committed Jan 11, 2009 187 188 189  References ----------  Tiago Peixoto committed Oct 05, 2009 190  .. [newman-structure-2003] M. E. J. Newman, "The structure and function of  Tiago Peixoto committed Dec 21, 2010 191 192  complex networks", SIAM Review, vol. 45, pp. 167-256, 2003, :doi:10.1137/S003614450342480  Tiago Peixoto committed Apr 07, 2019 193   Tiago Peixoto committed Jan 11, 2009 194 195  """  Tiago Peixoto committed Oct 19, 2016 196 197  if g.is_directed(): g = GraphView(g, directed=False, skip_properties=True)  Tiago Peixoto committed Apr 07, 2019 198  c = _gt.global_clustering(g._Graph__graph, _prop("e", g, weight))  Tiago Peixoto committed Jul 15, 2008 199 200  return c  Tiago Peixoto committed May 03, 2010 201   Tiago Peixoto committed Jan 11, 2009 202 203 def extended_clustering(g, props=None, max_depth=3, undirected=False): r"""  Tiago Peixoto committed Dec 14, 2009 204  Return the extended clustering coefficients for all vertices.  Tiago Peixoto committed Jan 11, 2009 205 206 207  Parameters ----------  Tiago Peixoto committed Oct 05, 2009 208  g : :class:~graph_tool.Graph  Tiago Peixoto committed Jan 11, 2009 209  Graph to be used.  Tiago Peixoto committed May 26, 2019 210  props : list of :class:~graph_tool.VertexPropertyMap objects (optional, default: None)  Tiago Peixoto committed Jan 11, 2009 211 212  list of vertex property maps where results will be stored. If specified, this parameter will also be the return value.  Tiago Peixoto committed May 26, 2019 213 214 215  max_depth : int (optional, default: 3) Maximum clustering order. undirected : boolean (optional, default: False)  Tiago Peixoto committed Jan 11, 2009 216 217 218 219 220  Calculate the *undirected* clustering coefficients, if graph is directed (this option has no effect if the graph is undirected). Returns -------  Tiago Peixoto committed May 26, 2019 221  prop : list of :class:~graph_tool.VertexPropertyMap objects  Tiago Peixoto committed Jan 11, 2009 222 223 224 225 226 227  List of vertex properties containing the clustering coefficients. See Also -------- local_clustering: local clustering coefficient global_clustering: global clustering coefficient  Tiago Peixoto committed Mar 09, 2009 228  motifs: motif counting  Tiago Peixoto committed Jan 11, 2009 229 230 231  Notes -----  Tiago Peixoto committed Oct 05, 2009 232 233  The extended clustering coefficient :math:c^d_i of order :math:d is defined as  Tiago Peixoto committed Jan 11, 2009 234 235  .. math::  Tiago Peixoto committed Jul 15, 2009 236 237  c^d_i = \frac{\left|\right\{ \{u,v\}; u,v \in N_i | d_{G(V\setminus \{i\})}(u,v) = d \left\}\right|}{{\left|N_i\right| \choose 2}},  Tiago Peixoto committed Jan 11, 2009 238 239 240 241 242 243 244  where :math:d_G(u,v) is the shortest distance from vertex :math:u to :math:v in graph :math:G, and .. math:: N_i = \{v_j : e_{ij} \in E\}  Tiago Peixoto committed Sep 26, 2017 245  is the set of out-neighbors of :math:i. According to the above  Tiago Peixoto committed Jan 11, 2009 246 247 248  definition, we have that the traditional local clustering coefficient is recovered for :math:d=1, i.e., :math:c^1_i = c_i.  Tiago Peixoto committed Oct 05, 2009 249  The implemented algorithm runs in  Tiago Peixoto committed Dec 14, 2009 250  :math:O(|V|\left^{2+\text{max-depth}}) worst time, where  Tiago Peixoto committed Oct 05, 2009 251  :math:\left< k\right> is the average out-degree.  Tiago Peixoto committed Jan 11, 2009 252 253 254 255 256  If enabled during compilation, this algorithm runs in parallel. Examples --------  Tiago Peixoto committed Nov 29, 2018 257  >>> g = gt.collection.data["karate"]  Tiago Peixoto committed Jan 11, 2009 258  >>> clusts = gt.extended_clustering(g, max_depth=5)  Tiago Peixoto committed Jun 03, 2012 259 260  >>> for i in range(0, 5): ... print(gt.vertex_average(g, clusts[i]))  Tiago Peixoto committed Nov 03, 2012 261  ...  Tiago Peixoto committed Nov 29, 2018 262 263 264 265 266  (0.5706384782076..., 0.05869813676256...) (0.3260389360735..., 0.04810773205917...) (0.0530678759917..., 0.01513061504691...) (0.0061658977316..., 0.00310690511463...) (0.0002162629757..., 0.00021305890271...)  Tiago Peixoto committed Jan 11, 2009 267 268 269  References ----------  Tiago Peixoto committed Oct 05, 2009 270  .. [abdo-clustering] A. H. Abdo, A. P. S. de Moura, "Clustering as a  Tiago Peixoto committed Dec 21, 2010 271  measure of the local topology of networks", :arxiv:physics/0605235  Tiago Peixoto committed Jan 11, 2009 272 273  """  Tiago Peixoto committed Apr 25, 2009 274  if g.is_directed() and undirected:  Tiago Peixoto committed Mar 07, 2011 275  g = GraphView(g, directed=False)  Tiago Peixoto committed Oct 20, 2016 276  if props is None:  Tiago Peixoto committed Jul 15, 2008 277  props = []  Tiago Peixoto committed Jun 03, 2012 278  for i in range(0, max_depth):  Tiago Peixoto committed Jul 15, 2008 279  props.append(g.new_vertex_property("double"))  Tiago Peixoto committed Mar 07, 2011 280 281  _gt.extended_clustering(g._Graph__graph, [_prop("v", g, p) for p in props])  Tiago Peixoto committed Jul 15, 2008 282  return props  Tiago Peixoto committed Mar 09, 2009 283 284   Tiago Peixoto committed Jun 12, 2013 285 def motifs(g, k, p=1.0, motif_list=None, return_maps=False):  Tiago Peixoto committed Mar 09, 2009 286  r"""  Tiago Peixoto committed May 29, 2014 287 288 289  Count the occurrence of k-size node-induced subgraphs (motifs). A tuple with two lists is returned: the list of motifs found, and the list with their respective counts.  Tiago Peixoto committed Mar 09, 2009 290 291 292  Parameters ----------  Tiago Peixoto committed Oct 05, 2009 293  g : :class:~graph_tool.Graph  Tiago Peixoto committed Mar 09, 2009 294 295 296  Graph to be used. k : int number of vertices of the motifs  Tiago Peixoto committed Jun 12, 2013 297  p : float or float list (optional, default: 1.0)  Tiago Peixoto committed Mar 09, 2009 298 299  uniform fraction of the motifs to be sampled. If a float list is provided, it will be used as the fraction at each depth  Tiago Peixoto committed Oct 05, 2009 300  :math:[1,\dots,k] in the algorithm. See [wernicke-efficient-2006]_ for  Tiago Peixoto committed Mar 09, 2009 301  more details.  Tiago Peixoto committed Oct 05, 2009 302  motif_list : list of :class:~graph_tool.Graph objects, optional  Tiago Peixoto committed Mar 09, 2009 303  If supplied, the algorithms will only search for the motifs in this list  Tiago Peixoto committed Dec 14, 2009 304  (or isomorphisms).  Tiago Peixoto committed Jun 12, 2013 305  return_maps : bool (optional, default False)  Tiago Peixoto committed Jun 22, 2013 306  If True, a list will be returned, which provides for each motif graph a  Tiago Peixoto committed Jun 12, 2013 307 308  list of vertex property maps which map the motif to its location in the main graph.  Tiago Peixoto committed Mar 09, 2009 309 310 311  Returns -------  Tiago Peixoto committed Oct 05, 2009 312  motifs : list of :class:~graph_tool.Graph objects  Tiago Peixoto committed Mar 09, 2009 313 314 315 316 317 318  List of motifs of size k found in the Graph. Graphs are grouped according to their isomorphism class, and only one of each class appears in this list. The list is sorted according to in-degree sequence, out-degree-sequence, and number of edges (in this order). counts : list of ints The number of times the respective motif in the motifs list was counted  Tiago Peixoto committed May 26, 2019 319  vertex_maps : list of lists of :class:~graph_tool.VertexPropertyMap objects  Tiago Peixoto committed Jun 12, 2013 320 321  List for each motif graph containing the locations in the main graph. This is only returned if return_maps == True.  Tiago Peixoto committed Mar 09, 2009 322 323 324  See Also --------  Tiago Peixoto committed Apr 24, 2009 325  motif_significance: significance profile of motifs  Tiago Peixoto committed Mar 09, 2009 326 327 328 329 330 331 332  local_clustering: local clustering coefficient global_clustering: global clustering coefficient extended_clustering: extended (generalized) clustering coefficient Notes ----- This functions implements the ESU and RAND-ESU algorithms described in  Tiago Peixoto committed Oct 05, 2009 333  [wernicke-efficient-2006]_.  Tiago Peixoto committed Mar 09, 2009 334 335 336 337 338  If enabled during compilation, this algorithm runs in parallel. Examples --------  Tiago Peixoto committed Dec 26, 2012 339 340 341 342 343 344  .. testcode:: :hide: np.random.seed(42) gt.seed_rng(42)  Tiago Peixoto committed Oct 05, 2009 345  >>> g = gt.random_graph(1000, lambda: (5,5))  Tiago Peixoto committed Mar 07, 2011 346  >>> motifs, counts = gt.motifs(gt.GraphView(g, directed=False), 4)  Tiago Peixoto committed Jun 03, 2012 347  >>> print(len(motifs))  Tiago Peixoto committed Nov 29, 2018 348  11  Tiago Peixoto committed Jun 03, 2012 349  >>> print(counts)  Tiago Peixoto committed Nov 29, 2018 350  [116386, 392916, 443, 507, 2574, 1124, 741, 5, 5, 8, 2]  Tiago Peixoto committed Mar 09, 2009 351 352 353  References ----------  Tiago Peixoto committed Oct 05, 2009 354  .. [wernicke-efficient-2006] S. Wernicke, "Efficient detection of network  Tiago Peixoto committed Mar 09, 2009 355 356  motifs", IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 3, Issue 4, Pages 347-359, 2006.  Tiago Peixoto committed Dec 21, 2010 357  :doi:10.1109/TCBB.2006.51  Tiago Peixoto committed May 29, 2014 358  .. [induced-subgraph-isomorphism] http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem  Tiago Peixoto committed Mar 09, 2009 359 360 361  """ sub_list = []  Tiago Peixoto committed Mar 07, 2011 362  directed_motifs = g.is_directed()  Tiago Peixoto committed Mar 09, 2009 363   Tiago Peixoto committed Mar 07, 2011 364  if motif_list is not None:  Tiago Peixoto committed Apr 24, 2009 365 366  directed_motifs = motif_list[0].is_directed() for m in motif_list:  Tiago Peixoto committed Mar 09, 2009 367  if m.is_directed() != directed_motifs:  Tiago Peixoto committed Mar 07, 2011 368  raise ValueError("all motif graphs must be either directed or undirected!")  Tiago Peixoto committed Mar 09, 2009 369  if m.num_vertices() != k:  Tiago Peixoto committed Mar 11, 2018 370  raise ValueError("all motifs must have the same number of vertices: %d" % k)  Tiago Peixoto committed Mar 09, 2009 371 372  sub_list.append(m._Graph__graph)  Tiago Peixoto committed Mar 07, 2011 373 374 375  if directed_motifs != g.is_directed(): raise ValueError("motifs do not have the same directionality as the graph itself!")  Tiago Peixoto committed Mar 09, 2009 376  if type(p) == float:  Tiago Peixoto committed Mar 07, 2011 377  pd = [1.0] * (k - 1)  Tiago Peixoto committed Mar 09, 2009 378 379 380 381 382  pd.append(p) if type(p) == list: pd = [float(x) for x in p] hist = []  Tiago Peixoto committed Jun 12, 2013 383  vertex_maps = []  Tiago Peixoto committed Mar 09, 2009 384  was_directed = g.is_directed()  Tiago Peixoto committed Jun 12, 2013 385 386  _gt.get_motifs(g._Graph__graph, k, sub_list, hist, vertex_maps, return_maps, pd, True, len(sub_list) == 0,  Tiago Peixoto committed Dec 26, 2012 387  _get_rng())  Tiago Peixoto committed Mar 09, 2009 388 389 390 391 392 393  # assemble graphs temp = [] for m in sub_list: mg = Graph() mg._Graph__graph = m  Tiago Peixoto committed Mar 07, 2011 394  mg.reindex_edges()  Tiago Peixoto committed Mar 09, 2009 395 396 397  temp.append(mg) sub_list = temp  Tiago Peixoto committed Jul 14, 2014 398 399 400 401  if return_maps: list_hist = list(zip(sub_list, hist, vertex_maps)) else: list_hist = list(zip(sub_list, hist))  Tiago Peixoto committed Mar 09, 2009 402  # sort according to in-degree sequence  Tiago Peixoto committed Dec 26, 2012 403  list_hist.sort(key=lambda x: sorted([v.in_degree() for v in x[0].vertices()]))  Tiago Peixoto committed Mar 09, 2009 404 405  # sort according to out-degree sequence  Tiago Peixoto committed Dec 26, 2012 406  list_hist.sort(key=lambda x: sorted([v.out_degree() for v in x[0].vertices()]))  Tiago Peixoto committed Mar 09, 2009 407 408  # sort according to ascending number of edges  Tiago Peixoto committed Dec 26, 2012 409  list_hist.sort(key=lambda x: x[0].num_edges())  Tiago Peixoto committed Mar 09, 2009 410 411 412 413  sub_list = [x[0] for x in list_hist] hist = [x[1] for x in list_hist]  Tiago Peixoto committed Jun 12, 2013 414  if return_maps:  Tiago Peixoto committed Jul 14, 2014 415  vertex_maps = [x[2] for x in list_hist]  Tiago Peixoto committed Jun 12, 2013 416 417 418 419  for i, vlist in enumerate(vertex_maps): sub = sub_list[i] vertex_maps[i] = [PropertyMap(vm, sub, "v") for vm in vlist] return sub_list, hist, vertex_maps  Tiago Peixoto committed Mar 09, 2009 420  return sub_list, hist  Tiago Peixoto committed Apr 24, 2009 421   Tiago Peixoto committed May 03, 2010 422   Tiago Peixoto committed Sep 12, 2009 423 424 425 def _graph_sig(g): """return the graph signature, i.e., the in and out degree distribution as concatenated as a tuple."""  Tiago Peixoto committed Jun 03, 2012 426  bins = list(range(0, g.num_vertices() + 1))  Tiago Peixoto committed Mar 11, 2018 427  in_dist = vertex_hist(g, "in", bins=bins if g.is_directed() else [0, 1],  Tiago Peixoto committed Sep 12, 2009 428  float_count=False)  Tiago Peixoto committed May 03, 2010 429 430  out_dist = vertex_hist(g, "out", bins=bins, float_count=False) sig = tuple([(in_dist[1][i], in_dist[0][i]) for \  Tiago Peixoto committed Jun 03, 2012 431  i in range(len(in_dist[0]))] +  Tiago Peixoto committed May 03, 2010 432  [(out_dist[1][i], out_dist[0][i]) for\  Tiago Peixoto committed Jun 03, 2012 433  i in range(len(out_dist[0]))])  Tiago Peixoto committed Sep 12, 2009 434 435  return sig  Tiago Peixoto committed May 03, 2010 436   Tiago Peixoto committed Sep 05, 2009 437 def motif_significance(g, k, n_shuffles=100, p=1.0, motif_list=None,  Tiago Peixoto committed Mar 07, 2011 438  threshold=0, self_loops=False, parallel_edges=False,  Tiago Peixoto committed Jan 01, 2017 439  full_output=False, shuffle_model="configuration"):  Tiago Peixoto committed Apr 24, 2009 440 441 442 443 444 445 446  r""" Obtain the motif significance profile, for subgraphs with k vertices. A tuple with two lists is returned: the list of motifs found, and their respective z-scores. Parameters ----------  Tiago Peixoto committed Oct 05, 2009 447  g : :class:~graph_tool.Graph  Tiago Peixoto committed Apr 24, 2009 448 449  Graph to be used. k : int  Tiago Peixoto committed Mar 07, 2011 450  Number of vertices of the motifs  Tiago Peixoto committed Sep 12, 2009 451  n_shuffles : int (optional, default: 100)  Tiago Peixoto committed Mar 07, 2011 452  Number of shuffled networks to consider for the z-score  Tiago Peixoto committed Sep 12, 2009 453  p : float or float list (optional, default: 1.0)  Tiago Peixoto committed Mar 07, 2011 454  Uniform fraction of the motifs to be sampled. If a float list is  Tiago Peixoto committed Apr 24, 2009 455  provided, it will be used as the fraction at each depth  Tiago Peixoto committed Oct 05, 2009 456  :math:[1,\dots,k] in the algorithm. See [wernicke-efficient-2006]_ for  Tiago Peixoto committed Apr 24, 2009 457  more details.  Tiago Peixoto committed Oct 05, 2009 458  motif_list : list of :class:~graph_tool.Graph objects (optional, default: None)  Tiago Peixoto committed Apr 24, 2009 459  If supplied, the algorithms will only search for the motifs in this list  Tiago Peixoto committed Sep 12, 2009 460 461 462 463  (isomorphisms) threshold : int (optional, default: 0) If a given motif count is below this level, it is not considered. self_loops : bool (optional, default: False)  Tiago Peixoto committed Apr 24, 2009 464  Whether or not the shuffled graphs are allowed to contain self-loops  Tiago Peixoto committed Sep 12, 2009 465  parallel_edges : bool (optional, default: False)  Tiago Peixoto committed Apr 24, 2009 466 467  Whether or not the shuffled graphs are allowed to contain parallel edges.  Tiago Peixoto committed Sep 12, 2009 468  full_output : bool (optional, default: False)  Tiago Peixoto committed Apr 24, 2009 469 470 471 472  If set to True, three additional lists are returned: the count of each motif, the average count of each motif in the shuffled networks, and the standard deviation of the average count of each motif in the shuffled networks.  Tiago Peixoto committed Jan 01, 2017 473  shuffle_model : string (optional, default: "configuration")  Tiago Peixoto committed Apr 25, 2013 474 475  Shuffle model to use. See :func:~graph_tool.generation.random_rewire for details.  Tiago Peixoto committed Apr 24, 2009 476 477 478  Returns -------  Tiago Peixoto committed Oct 05, 2009 479  motifs : list of :class:~graph_tool.Graph objects  Tiago Peixoto committed Apr 24, 2009 480 481 482 483 484 485  List of motifs of size k found in the Graph. Graphs are grouped according to their isomorphism class, and only one of each class appears in this list. The list is sorted according to in-degree sequence, out-degree-sequence, and number of edges (in this order). z-scores : list of floats The z-score of the respective motives. See below for the definition of  Tiago Peixoto committed Dec 14, 2009 486  the z-score.  Tiago Peixoto committed Apr 24, 2009 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502  See Also -------- motifs: motif counting or sampling local_clustering: local clustering coefficient global_clustering: global clustering coefficient extended_clustering: extended (generalized) clustering coefficient Notes ----- The z-score :math:z_i of motif i is defined as .. math:: z_i = \frac{N_i - \left} {\sqrt{\left<(N^s_i)^2\right> - \left^2}},  Tiago Peixoto committed Jul 15, 2009 503  where :math:N_i is the number of times motif i found, and :math:N^s_i  Tiago Peixoto committed Apr 24, 2009 504  is the count of the same motif but on a shuffled network. It measures how  Tiago Peixoto committed Mar 07, 2010 505  many standard deviations is each motif count, in respect to an ensemble of  Tiago Peixoto committed Apr 24, 2009 506 507 508 509 510 511 512 513  randomly shuffled graphs with the same degree sequence. The z-scores values are not normalized. If enabled during compilation, this algorithm runs in parallel. Examples --------  Tiago Peixoto committed Sep 12, 2009 514  >>> from numpy import random  Tiago Peixoto committed Oct 05, 2009 515 516  >>> random.seed(10) >>> g = gt.random_graph(100, lambda: (3,3))  Tiago Peixoto committed Apr 24, 2009 517  >>> motifs, zscores = gt.motif_significance(g, 3)  Tiago Peixoto committed Jun 03, 2012 518  >>> print(len(motifs))  Tiago Peixoto committed Nov 29, 2018 519  12  Tiago Peixoto committed Jun 03, 2012 520  >>> print(zscores)  Tiago Peixoto committed Nov 29, 2018 521  [2.59252643351441, 2.5966529814390387, 2.3459237708258587, -1.0829180621127024, -1.3368754665984663, -2.33027728409781, -3.055817397993647, -0.1, -0.15, -0.19, -0.4, -0.01]  Tiago Peixoto committed Jun 26, 2018 522 523 524 525 526 527 528  References ---------- .. [wernicke-efficient-2006] S. Wernicke, "Efficient detection of network motifs", IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 3, Issue 4, Pages 347-359, 2006. :doi:10.1109/TCBB.2006.51  Tiago Peixoto committed Apr 24, 2009 529 530  """  Tiago Peixoto committed Mar 07, 2011 531  s_ms, counts = motifs(g, k, p, motif_list)  Tiago Peixoto committed Sep 12, 2009 532  if threshold > 0:  Tiago Peixoto committed Jun 03, 2012 533  s_ms, counts = list(zip(*[x for x in zip(s_ms, counts) if x[1] > threshold]))  Tiago Peixoto committed Sep 12, 2009 534 535  s_ms = list(s_ms) counts = list(counts)  Tiago Peixoto committed May 03, 2010 536 537  s_counts = [0] * len(s_ms) s_dev = [0] * len(s_ms)  Tiago Peixoto committed Apr 24, 2009 538   Tiago Peixoto committed Sep 12, 2009 539 540  # group subgraphs by number of edges m_e = defaultdict(lambda: [])  Tiago Peixoto committed Jun 03, 2012 541  for i in range(len(s_ms)):  Tiago Peixoto committed Sep 12, 2009 542 543  m_e[_graph_sig(s_ms[i])].append(i)  Tiago Peixoto committed Apr 24, 2009 544 545  # get samples sg = g.copy()  Tiago Peixoto committed Jun 03, 2012 546  for i in range(0, n_shuffles):  Tiago Peixoto committed Apr 25, 2013 547  random_rewire(sg, model=shuffle_model, self_loops=self_loops,  Tiago Peixoto committed May 11, 2009 548  parallel_edges=parallel_edges)  Tiago Peixoto committed Mar 07, 2011 549  m_temp, count_temp = motifs(sg, k, p, motif_list)  Tiago Peixoto committed Sep 12, 2009 550  if threshold > 0:  Tiago Peixoto committed Jun 03, 2012 551 552 553  m_temp, count_temp = list(zip(*[x for x in zip(m_temp, count_temp) \ if x[1] > threshold])) for j in range(0, len(m_temp)):  Tiago Peixoto committed Apr 24, 2009 554  found = False  Tiago Peixoto committed Sep 12, 2009 555  for l in m_e[_graph_sig(m_temp[j])]:  Tiago Peixoto committed Apr 24, 2009 556 557 558  if isomorphism(s_ms[l], m_temp[j]): found = True s_counts[l] += count_temp[j]  Tiago Peixoto committed May 03, 2010 559  s_dev[l] += count_temp[j] ** 2  Tiago Peixoto committed Apr 24, 2009 560 561 562  if not found: s_ms.append(m_temp[j]) s_counts.append(count_temp[j])  Tiago Peixoto committed May 03, 2010 563  s_dev.append(count_temp[j] ** 2)  Tiago Peixoto committed Apr 24, 2009 564  counts.append(0)  Tiago Peixoto committed May 03, 2010 565  m_e[_graph_sig(m_temp[j])].append(len(s_ms) - 1)  Tiago Peixoto committed Apr 24, 2009 566   Tiago Peixoto committed May 03, 2010 567 568  s_counts = [x / float(n_shuffles) for x in s_counts] s_dev = [max(sqrt(x[0] / float(n_shuffles) - x[1] ** 2), 1) \  Tiago Peixoto committed Jun 03, 2012 569  for x in zip(s_dev, s_counts)]  Tiago Peixoto committed Apr 24, 2009 570   Tiago Peixoto committed Jun 03, 2012 571  list_hist = list(zip(s_ms, s_counts, s_dev))  Tiago Peixoto committed Apr 24, 2009 572  # sort according to in-degree sequence  Tiago Peixoto committed Dec 26, 2012 573  list_hist.sort(key = lambda x: sorted([v.in_degree() for v in x[0].vertices()])),  Tiago Peixoto committed Apr 24, 2009 574 575  # sort according to out-degree sequence  Tiago Peixoto committed Dec 26, 2012 576  list_hist.sort(key = lambda x: sorted([v.out_degree() for v in x[0].vertices()]))  Tiago Peixoto committed Apr 24, 2009 577 578  # sort according to ascending number of edges  Tiago Peixoto committed Dec 26, 2012 579  list_hist.sort(key = lambda x: x[0].num_edges())  Tiago Peixoto committed Apr 24, 2009 580   Tiago Peixoto committed Jun 03, 2012 581  s_ms, s_counts, s_dev = list(zip(*list_hist))  Tiago Peixoto committed Apr 24, 2009 582   Tiago Peixoto committed Jun 03, 2012 583  zscore = [(x[0] - x[1]) / x[2] for x in zip(counts, s_counts, s_dev)]  Tiago Peixoto committed Apr 24, 2009 584 585 586 587 588  if full_output: return s_ms, zscore, counts, s_counts, s_dev else: return s_ms, zscore