__init__.py 20.5 KB
Newer Older
1
#! /usr/bin/env python
2
# -*- coding: utf-8 -*-
3
#
4
5
# graph_tool -- a general graph manipulation python module
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2006-2020 Tiago de Paula Peixoto <tiago@skewed.de>
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 <http://www.gnu.org/licenses/>.

21
"""
22
23
``graph_tool.clustering`` - Clustering coefficients
---------------------------------------------------
24
25
26

Provides algorithms for calculation of clustering coefficients,
aka. transitivity.
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
++++++++
42
43
"""

44
45
from __future__ import division, absolute_import, print_function

Tiago Peixoto's avatar
Tiago Peixoto committed
46
from .. dl_import import dl_import
47
dl_import("from . import libgraph_tool_clustering as _gt")
48

49
from .. import _degree, _prop, Graph, GraphView, VertexPropertyMap, _get_rng
50
51
from .. topology import isomorphism
from .. generation import random_rewire
52
from .. stats import vertex_hist
53

54
from collections import defaultdict
55
from numpy import *
56
from numpy import random
57
import sys
58

59
__all__ = ["local_clustering", "global_clustering", "extended_clustering",
60
           "motifs", "motif_significance"]
61

Tiago Peixoto's avatar
Tiago Peixoto committed
62

63
def local_clustering(g, weight=None, prop=None, undirected=True):
64
    r"""
Tiago Peixoto's avatar
Tiago Peixoto committed
65
    Return the local clustering coefficients for all vertices.
66
67
68

    Parameters
    ----------
69
    g : :class:`~graph_tool.Graph`
70
        Graph to be used.
71
    weight : :class:`~graph_tool.EdgePropertyMap`, optional (default: None)
72
        Edge weights. If omitted, a constant value of 1 will be used.
73
    prop : :class:`~graph_tool.VertexPropertyMap` or string, optional
74
75
        Vertex property map where results will be stored. If specified, this
        parameter will also be the return value.
76
    undirected : bool (default: True)
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
    -------
82
    prop : :class:`~graph_tool.VertexPropertyMap`
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
89
    motifs: motif counting
90
91
92

    Notes
    -----
93
94
    The local clustering coefficient [watts-collective-1998]_ :math:`c_i` is
    defined as
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\}

104
    is the set of out-neighbors of vertex :math:`i`. For undirected graphs the
105
106
107
108
109
    value of :math:`c_i` is normalized as

    .. math::
       c'_i = 2c_i.

110
111
    The implemented algorithm runs in :math:`O(|V|\left<k^2\right>)` time,
    where :math:`\left<k^2\right>` is second moment of the degree distribution.
112
113
114
115
116

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
Tiago Peixoto's avatar
Tiago Peixoto committed
117
    >>> g = gt.collection.data["karate"]
118
    >>> clust = gt.local_clustering(g)
119
    >>> print(gt.vertex_average(g, clust))
Tiago Peixoto's avatar
Tiago Peixoto committed
120
    (0.5706384782..., 0.05869813676...)
121
122
123

    References
    ----------
124
    .. [watts-collective-1998] D. J. Watts and Steven Strogatz, "Collective
Tiago Peixoto's avatar
Tiago Peixoto committed
125
       dynamics of 'small-world' networks", Nature, vol. 393, pp 440-442, 1998.
Tiago Peixoto's avatar
Tiago Peixoto committed
126
       :doi:`10.1038/30918`
127
128
    """

129
    if prop is None:
130
        prop = g.new_vertex_property("double")
131
    if g.is_directed() and undirected:
132
        g = GraphView(g, directed=False, skip_properties=True)
133
134
    _gt.local_clustering(g._Graph__graph, _prop("v", g, prop),
                         _prop("e", g, weight))
135
136
    return prop

Tiago Peixoto's avatar
Tiago Peixoto committed
137

138
139
def global_clustering(g, weight=None):
    r"""Return the global clustering coefficient.
140
141
142

    Parameters
    ----------
143
    g : :class:`~graph_tool.Graph`
144
        Graph to be used.
145
    weight : :class:`~graph_tool.EdgePropertyMap`, optional (default: None)
146
        Edge weights. If omitted, a constant value of 1 will be used.
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
157
    motifs: motif counting
158
159
160

    Notes
    -----
161
162
    The global clustering coefficient [newman-structure-2003]_ :math:`c` is
    defined as
163
164
165
166
167

    .. math::
       c = 3 \times \frac{\text{number of triangles}}
                          {\text{number of connected triples}}

168
    If weights are given, the following definition is used:
169
170

    .. math::
171
       c = \frac{\mathrm{Tr}{{\boldsymbol A}^3}}{\sum_{i\ne j}[{\boldsymbol A}^2]_{ij}},
172
173
174
175
176
177
178

    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<k^2\right>)`,
    where :math:`\left< k^2\right>` is the second moment of the degree
    distribution.
179
180
181
182
183

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
Tiago Peixoto's avatar
Tiago Peixoto committed
184
    >>> g = gt.collection.data["karate"]
185
    >>> print(gt.global_clustering(g))
Tiago Peixoto's avatar
Tiago Peixoto committed
186
    (0.2556818181..., 0.06314746595...)
187
188
189

    References
    ----------
190
    .. [newman-structure-2003] M. E. J. Newman, "The structure and function of
Tiago Peixoto's avatar
Tiago Peixoto committed
191
192
       complex networks", SIAM Review, vol. 45, pp. 167-256, 2003,
       :doi:`10.1137/S003614450342480`
193

194
195
    """

196
197
    if g.is_directed():
        g = GraphView(g, directed=False, skip_properties=True)
198
    c = _gt.global_clustering(g._Graph__graph, _prop("e", g, weight))
199
200
    return c

Tiago Peixoto's avatar
Tiago Peixoto committed
201

202
203
def extended_clustering(g, props=None, max_depth=3, undirected=False):
    r"""
Tiago Peixoto's avatar
Tiago Peixoto committed
204
    Return the extended clustering coefficients for all vertices.
205
206
207

    Parameters
    ----------
208
    g : :class:`~graph_tool.Graph`
209
        Graph to be used.
210
    props : list of :class:`~graph_tool.VertexPropertyMap` objects (optional, default: ``None``)
211
212
        list of vertex property maps where results will be stored. If specified,
        this parameter will also be the return value.
213
214
215
    max_depth : int (optional, default: ``3``)
        Maximum clustering order.
    undirected : boolean (optional, default: ``False``)
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
    -------
221
    prop : list of :class:`~graph_tool.VertexPropertyMap` objects
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
228
    motifs: motif counting
229
230
231

    Notes
    -----
232
233
    The extended clustering coefficient :math:`c^d_i` of order :math:`d` is
    defined as
234
235

    .. math::
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}},
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\}

245
    is the set of out-neighbors of :math:`i`. According to the above
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`.

249
    The implemented algorithm runs in
Tiago Peixoto's avatar
Tiago Peixoto committed
250
    :math:`O(|V|\left<k\right>^{2+\text{max-depth}})` worst time, where
251
    :math:`\left< k\right>` is the average out-degree.
252
253
254
255
256

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
Tiago Peixoto's avatar
Tiago Peixoto committed
257
    >>> g = gt.collection.data["karate"]
258
    >>> clusts = gt.extended_clustering(g, max_depth=5)
259
260
    >>> for i in range(0, 5):
    ...    print(gt.vertex_average(g, clusts[i]))
Tiago Peixoto's avatar
Tiago Peixoto committed
261
    ...
Tiago Peixoto's avatar
Tiago Peixoto committed
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...)
267
268
269

    References
    ----------
270
    .. [abdo-clustering] A. H. Abdo, A. P. S. de Moura, "Clustering as a
Tiago Peixoto's avatar
Tiago Peixoto committed
271
       measure of the local topology of networks", :arxiv:`physics/0605235`
272
273
    """

274
    if g.is_directed() and undirected:
275
        g = GraphView(g, directed=False)
Tiago Peixoto's avatar
Tiago Peixoto committed
276
    if props is None:
277
        props = []
278
        for i in range(0, max_depth):
279
            props.append(g.new_vertex_property("double"))
280
281
    _gt.extended_clustering(g._Graph__graph,
                            [_prop("v", g, p) for p in props])
282
    return props
283
284


285
def motifs(g, k, p=1.0, motif_list=None, return_maps=False):
286
    r"""
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.
290
291
292

    Parameters
    ----------
293
    g : :class:`~graph_tool.Graph`
294
295
296
        Graph to be used.
    k : int
        number of vertices of the motifs
297
    p : float or float list (optional, default: `1.0`)
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
300
        :math:`[1,\dots,k]` in the algorithm. See [wernicke-efficient-2006]_ for
301
        more details.
302
    motif_list : list of :class:`~graph_tool.Graph` objects, optional
303
        If supplied, the algorithms will only search for the motifs in this list
Tiago Peixoto's avatar
Tiago Peixoto committed
304
        (or isomorphisms).
305
    return_maps : bool (optional, default `False`)
Tiago Peixoto's avatar
Tiago Peixoto committed
306
        If ``True``, a list will be returned, which provides for each motif graph a
307
308
        list of vertex property maps which map the motif to its location in the
        main graph.
309
310
311

    Returns
    -------
312
    motifs : list of :class:`~graph_tool.Graph` objects
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
319
    vertex_maps : list of lists of :class:`~graph_tool.VertexPropertyMap` objects
320
321
        List for each motif graph containing the locations in the main
        graph. This is only returned if `return_maps == True`.
322
323
324

    See Also
    --------
325
    motif_significance: significance profile of motifs
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
333
    [wernicke-efficient-2006]_.
334
335
336
337
338

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
339
340
341
342
343
344
    .. testcode::
       :hide:

       np.random.seed(42)
       gt.seed_rng(42)

345
    >>> g = gt.random_graph(1000, lambda: (5,5))
346
    >>> motifs, counts = gt.motifs(gt.GraphView(g, directed=False), 4)
347
    >>> print(len(motifs))
Tiago Peixoto's avatar
Tiago Peixoto committed
348
    11
349
    >>> print(counts)
Tiago Peixoto's avatar
Tiago Peixoto committed
350
    [116386, 392916, 443, 507, 2574, 1124, 741, 5, 5, 8, 2]
351
352
353

    References
    ----------
354
    .. [wernicke-efficient-2006] S. Wernicke, "Efficient detection of network
355
356
       motifs", IEEE/ACM Transactions on Computational Biology and
       Bioinformatics (TCBB), Volume 3, Issue 4, Pages 347-359, 2006.
Tiago Peixoto's avatar
Tiago Peixoto committed
357
       :doi:`10.1109/TCBB.2006.51`
358
    .. [induced-subgraph-isomorphism] http://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem
359
360
361
    """

    sub_list = []
362
    directed_motifs = g.is_directed()
363

364
    if motif_list is not None:
365
366
        directed_motifs = motif_list[0].is_directed()
        for m in motif_list:
367
            if m.is_directed() != directed_motifs:
368
                raise ValueError("all motif graphs must be either directed or undirected!")
369
            if m.num_vertices() != k:
Tiago Peixoto's avatar
Tiago Peixoto committed
370
                raise ValueError("all motifs must have the same number of vertices: %d" % k)
371
372
            sub_list.append(m._Graph__graph)

373
374
375
    if directed_motifs != g.is_directed():
        raise ValueError("motifs do not have the same directionality as the graph itself!")

376
    if type(p) == float:
377
        pd = [1.0] * (k - 1)
378
379
380
381
382
        pd.append(p)
    if type(p) == list:
        pd = [float(x) for x in p]

    hist = []
383
    vertex_maps = []
384
    was_directed = g.is_directed()
385
386
    _gt.get_motifs(g._Graph__graph, k, sub_list, hist, vertex_maps,
                   return_maps,  pd, True, len(sub_list) == 0,
387
                   _get_rng())
388
389
390
391
392
393

    # assemble graphs
    temp = []
    for m in sub_list:
        mg = Graph()
        mg._Graph__graph = m
394
        mg.reindex_edges()
395
396
397
        temp.append(mg)
    sub_list = temp

398
399
400
401
    if return_maps:
        list_hist = list(zip(sub_list, hist, vertex_maps))
    else:
        list_hist = list(zip(sub_list, hist))
402
    # sort according to in-degree sequence
403
    list_hist.sort(key=lambda x: sorted([v.in_degree() for v in x[0].vertices()]))
404
405

    # sort according to out-degree sequence
406
    list_hist.sort(key=lambda x: sorted([v.out_degree() for v in x[0].vertices()]))
407
408

    # sort according to ascending number of edges
409
    list_hist.sort(key=lambda x: x[0].num_edges())
410
411
412
413

    sub_list = [x[0] for x in list_hist]
    hist = [x[1] for x in list_hist]

414
    if return_maps:
415
        vertex_maps = [x[2] for x in list_hist]
416
417
        for i, vlist in enumerate(vertex_maps):
            sub = sub_list[i]
418
            vertex_maps[i] = [VertexPropertyMap(vm, sub) for vm in vlist]
419
        return sub_list, hist, vertex_maps
420
    return sub_list, hist
421

Tiago Peixoto's avatar
Tiago Peixoto committed
422

423
424
425
def _graph_sig(g):
    """return the graph signature, i.e., the in and out degree distribution as
    concatenated as a tuple."""
426
    bins = list(range(0, g.num_vertices() + 1))
427
    in_dist = vertex_hist(g, "in", bins=bins if g.is_directed() else [0, 1],
428
                          float_count=False)
Tiago Peixoto's avatar
Tiago Peixoto committed
429
430
    out_dist = vertex_hist(g, "out", bins=bins, float_count=False)
    sig = tuple([(in_dist[1][i], in_dist[0][i]) for \
431
                 i in range(len(in_dist[0]))] +
Tiago Peixoto's avatar
Tiago Peixoto committed
432
                [(out_dist[1][i], out_dist[0][i]) for\
433
                 i in range(len(out_dist[0]))])
434
435
    return sig

Tiago Peixoto's avatar
Tiago Peixoto committed
436

437
def motif_significance(g, k, n_shuffles=100, p=1.0, motif_list=None,
438
                       threshold=0, self_loops=False, parallel_edges=False,
439
                       full_output=False, shuffle_model="configuration"):
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
    ----------
447
    g : :class:`~graph_tool.Graph`
448
449
        Graph to be used.
    k : int
Tiago Peixoto's avatar
Tiago Peixoto committed
450
        Number of vertices of the motifs
451
    n_shuffles : int (optional, default: 100)
Tiago Peixoto's avatar
Tiago Peixoto committed
452
        Number of shuffled networks to consider for the z-score
453
    p : float or float list (optional, default: 1.0)
Tiago Peixoto's avatar
Tiago Peixoto committed
454
        Uniform fraction of the motifs to be sampled. If a float list is
455
        provided, it will be used as the fraction at each depth
456
        :math:`[1,\dots,k]` in the algorithm. See [wernicke-efficient-2006]_ for
457
        more details.
458
    motif_list : list of :class:`~graph_tool.Graph` objects (optional, default: None)
459
        If supplied, the algorithms will only search for the motifs in this list
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)
464
        Whether or not the shuffled graphs are allowed to contain self-loops
465
    parallel_edges : bool (optional, default: False)
466
467
        Whether or not the shuffled graphs are allowed to contain parallel
        edges.
468
    full_output : bool (optional, default: False)
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.
473
    shuffle_model : string (optional, default: "configuration")
474
475
        Shuffle model to use. See :func:`~graph_tool.generation.random_rewire`
        for details.
476
477
478

    Returns
    -------
479
    motifs : list of :class:`~graph_tool.Graph` objects
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's avatar
Tiago Peixoto committed
486
        the z-score.
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<N^s_i\right>}
         {\sqrt{\left<(N^s_i)^2\right> - \left<N^s_i\right>^2}},

503
    where :math:`N_i` is the number of times motif i found, and :math:`N^s_i`
504
    is the count of the same motif but on a shuffled network. It measures how
Tiago Peixoto's avatar
Tiago Peixoto committed
505
    many standard deviations is each motif count, in respect to an ensemble of
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
    --------
514
    >>> from numpy import random
515
516
    >>> random.seed(10)
    >>> g = gt.random_graph(100, lambda: (3,3))
517
    >>> motifs, zscores = gt.motif_significance(g, 3)
518
    >>> print(len(motifs))
Tiago Peixoto's avatar
Tiago Peixoto committed
519
    12
520
    >>> print(zscores)
Tiago Peixoto's avatar
Tiago Peixoto committed
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]
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`
529
530
    """

531
    s_ms, counts = motifs(g, k, p, motif_list)
532
    if threshold > 0:
533
        s_ms, counts = list(zip(*[x for x in zip(s_ms, counts) if x[1] > threshold]))
534
535
        s_ms = list(s_ms)
        counts = list(counts)
Tiago Peixoto's avatar
Tiago Peixoto committed
536
537
    s_counts = [0] * len(s_ms)
    s_dev = [0] * len(s_ms)
538

539
540
    # group subgraphs by number of edges
    m_e = defaultdict(lambda: [])
541
    for i in range(len(s_ms)):
542
543
        m_e[_graph_sig(s_ms[i])].append(i)

544
545
    # get samples
    sg = g.copy()
546
    for i in range(0, n_shuffles):
547
        random_rewire(sg, model=shuffle_model, self_loops=self_loops,
548
                      parallel_edges=parallel_edges)
549
        m_temp, count_temp = motifs(sg, k, p, motif_list)
550
        if threshold > 0:
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)):
554
            found = False
555
            for l in m_e[_graph_sig(m_temp[j])]:
556
557
558
                if isomorphism(s_ms[l], m_temp[j]):
                    found = True
                    s_counts[l] += count_temp[j]
Tiago Peixoto's avatar
Tiago Peixoto committed
559
                    s_dev[l] += count_temp[j] ** 2
560
561
562
            if not found:
                s_ms.append(m_temp[j])
                s_counts.append(count_temp[j])
Tiago Peixoto's avatar
Tiago Peixoto committed
563
                s_dev.append(count_temp[j] ** 2)
564
                counts.append(0)
Tiago Peixoto's avatar
Tiago Peixoto committed
565
                m_e[_graph_sig(m_temp[j])].append(len(s_ms) - 1)
566

Tiago Peixoto's avatar
Tiago Peixoto committed
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) \
569
              for x in zip(s_dev, s_counts)]
570

571
    list_hist = list(zip(s_ms, s_counts, s_dev))
572
    # sort according to in-degree sequence
573
    list_hist.sort(key = lambda x: sorted([v.in_degree() for v in x[0].vertices()])),
574
575

    # sort according to out-degree sequence
576
    list_hist.sort(key = lambda x: sorted([v.out_degree() for v in x[0].vertices()]))
577
578

    # sort according to ascending number of edges
579
    list_hist.sort(key = lambda x: x[0].num_edges())
580

581
    s_ms, s_counts, s_dev = list(zip(*list_hist))
582

583
    zscore = [(x[0] - x[1]) / x[2] for x in zip(counts, s_counts, s_dev)]
584
585
586
587
588

    if full_output:
        return s_ms, zscore, counts, s_counts, s_dev
    else:
        return s_ms, zscore