__init__.py 17.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#! /usr/bin/env python
# graph_tool.py -- a general graph manipulation python module
#
# Copyright (C) 2007 Tiago de Paula Peixoto <tiago@forked.de>
#
# 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/>.

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

Provides algorithms for calculation of clustering coefficients,
aka. transitivity.
"""

Tiago Peixoto's avatar
Tiago Peixoto committed
27
from .. dl_import import dl_import
28
dl_import("import libgraph_tool_clustering as _gt")
29

30
31
from .. core import _degree, _prop, Graph
from .. misc import isomorphism
32
from numpy import *
33
import sys
34

35
__all__ = ["local_clustering", "global_clustering", "extended_clustering",
36
           "motifs", "motif_significance"]
37

38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def local_clustering(g, prop=None, undirected=False):
    r"""
    Return vertex property containing local clustering coefficients for all
    vertices.

    Parameters
    ----------
    g : Graph
        Graph to be used.
    prop : PropertyMap or string, optional
        Vertex property map where results will be stored. If specified, this
        parameter will also be the return value.
    undirected : bool, optional
        Calculate the *undirected* clustering coefficient, if graph is directed
        (this option has no effect if the graph is undirected).

    Returns
    -------
    prop : PropertyMap
        Vertex property containing the clustering coefficients.

    See Also
    --------
    global_clustering: global clustering coefficient
    extended_clustering: extended (generalized) clustering coefficient
63
    motifs: motif counting
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

    Notes
    -----
    The local clustering coefficient [1]_ :math:`c_i` is defined as

    .. 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\}

    is the set of out-neighbours of vertex :math:`i`. For undirected graphs the
    value of :math:`c_i` is normalized as

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

    The implemented algorithm runs in :math:`O(|V|\left< k\right>^3)` time,
    where :math:`\left< k\right>` is the average out-degree.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> g = gt.random_graph(1000, lambda: (5,5), seed=42)
    >>> clust = gt.local_clustering(g)
    >>> print gt.vertex_average(g, clust)
    (0.0045633333333333333, 0.00041406305209606802)

    References
    ----------
    .. [1] D. J. Watts and Steven Strogatz, "Collective dynamics of
       'small-world' networks", Nature, vol. 393, pp 440-442, 1998.
       doi:10.1038/30918
    """

102
103
    if prop == None:
        prop = g.new_vertex_property("double")
104
105
106
107
    was_directed = g.directed()
    if g.directed() and undirected:
        g.set_directed(False)
    try:
108
       _gt.extended_clustering(g._Graph__graph,
109
110
111
112
                                [_prop("v", g, prop)])
    finally:
        if was_directed and undirected:
            g.set_directed(True)
113
114
115
    return prop

def global_clustering(g):
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
    r"""
    Return global clustering coefficients for graphs.

    Parameters
    ----------
    g : Graph
        Graph to be used.

    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
133
    motifs: motif counting
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

    Notes
    -----
    The global clustering coefficient [1]_ :math:`c` is defined as

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

    The implemented algorithm runs in :math:`O(|V|\left< k\right>^3)` time,
    where :math:`\left< k\right>` is the average (total) degree.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> g = gt.random_graph(1000, lambda: (5,5), seed=42)
    >>> print gt.global_clustering(g)
    (0.0086380072318200073, 0.00044516087903790925)

    References
    ----------
    .. [1] M. E. J. Newman, "The structure and function of complex networks",
       SIAM Review, vol. 45, pp. 167-256, 2003
    """

160
    c =_gt.global_clustering(g._Graph__graph)
161
162
    return c

163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
def extended_clustering(g, props=None, max_depth=3, undirected=False):
    r"""
    Return a list of vertex properties containing the extended clustering
    coefficients for all vertices.

    Parameters
    ----------
    g : Graph
        Graph to be used.
    props : list of PropertyMap objects, optional
        list of vertex property maps where results will be stored. If specified,
        this parameter will also be the return value.
    max_depth : int, optional
        Maximum clustering order (default: 3).
    undirected : bool, optional
        Calculate the *undirected* clustering coefficients, if graph is directed
        (this option has no effect if the graph is undirected).

    Returns
    -------
    prop : list of PropertyMap objects
        List of vertex properties containing the clustering coefficients.

    See Also
    --------
    local_clustering: local clustering coefficient
    global_clustering: global clustering coefficient
190
    motifs: motif counting
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

    Notes
    -----
    The definition of the extended clustering coefficient :math:`c^d_i` of order
    :math:`d` is defined as

    .. math::
       c^d_i = \frac{\left|\right\{ \{u,v\}; u,v \in N_i | d_{G(V\diagdown
       \{i\})}(u,v) = d \left\}\right|}{\binom{\left|N_i\right|}{2}},

    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\}

    is the set of out-neighbours of :math:`i`. According to the above
    definition, we have that the traditional local clustering coefficient is
    recovered for :math:`d=1`, i.e., :math:`c^1_i = c_i`.

    The implemented algorithm runs in :math:`O(|V|\left<
    k\right>^{2+\text{max_depth}})` worst time, where :math:`\left< k\right>` is
    the average out-degree.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> g = gt.random_graph(1000, lambda: (5,5), seed=42)
    >>> clusts = gt.extended_clustering(g, max_depth=5)
    >>> for i in xrange(0, 5):
    ...    print gt.vertex_average(g, clusts[i])
    ...
    (0.0045633333333333333, 0.00041406305209606802)
    (0.027705, 0.0010493633929938454)
    (0.11730666666666667, 0.00201118990760307)
    (0.41394666666666663, 0.0030157036105470745)
    (0.41717499999999996, 0.0030272310298907366)

    References
    ----------
    .. [1] A. H. Abdo, A. P. S. de Moura, "Clustering as a measure of the local
       topology of networks", arXiv:physics/0605235v4
    """

    was_directed = g.directed()
    if g.directed() and undirected:
        g.set_directed(False)
239
240
241
242
    if props == None:
        props = []
        for i in xrange(0, max_depth):
            props.append(g.new_vertex_property("double"))
243
    try:
244
245
       _gt.extended_clustering(g._Graph__graph,
                               [_prop("v", g, p) for p in props])
246
247
248
    finally:
        if was_directed and undirected:
            g.set_directed(True)
249
    return props
250
251


252
def motifs(g, k, p=1.0, motif_list=None, undirected=None, seed=0):
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
    r"""
    Count the occurrence of k-size subgraphs (motifs). A tuple with two lists is
    returned: the list of motifs found, and the list with their respective
    counts.

    Parameters
    ----------
    g : Graph
        Graph to be used.
    k : int
        number of vertices of the motifs
    p : float or float list, optional (default: 1.0)
        uniform fraction of the motifs to be sampled. If a float list is
        provided, it will be used as the fraction at each depth
        :math:`[1,\dots,k]` in the algorithm. See [wernicke_efficient_2006]_ for
        more details.
269
    motif_list : list of Graph objects, optional
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
        If supplied, the algorithms will only search for the motifs in this list
        (or isomorphisms thereof)
    undirected : bool, optional
        Treat the graph as *undirected*, if graph is directed
        (this option has no effect if the graph is undirected).
    seed : int, optional (default: 0)
        Seed for the random number generator. It the value is 0, a random seed
        is used.

    Returns
    -------
    motifs : list of Graph objects
        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

    See Also
    --------
291
    motif_significance: significance profile of motifs
292
293
294
295
296
297
298
299
300
301
302
303
304
305
    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
    [wernicke_efficient_2006]_.

    If enabled during compilation, this algorithm runs in parallel.

    Examples
    --------
    >>> g = gt.random_graph(1000, lambda: (5,5), seed=42)
306
    >>> motifs, counts = gt.motifs(g, 4, undirected=True))
307
    >>> print len(motifs)
308
    11
309
    >>> print counts
310
    [115708, 390659, 612, 696, 2872, 1556, 811, 4, 8, 6, 1]
311
312
313
314
315
316
317
318
319
320
321
322
323
324

    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.
    """

    if seed == 0:
        seed = random.randint(0, sys.maxint)

    sub_list = []
    directed_motifs = g.is_directed() if undirected == None else not undirected

325
326
327
    if motif_list != None:
        directed_motifs = motif_list[0].is_directed()
        for m in motif_list:
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
            if m.is_directed() != directed_motifs:
                raise ValueError("all motif graphs must be either directed or undirected")
            if m.num_vertices() != k:
                raise ValueError("all motifs must have the same number of vertices: " + k)
            sub_list.append(m._Graph__graph)

    if type(p) == float:
        pd = [1.0]*(k-1)
        pd.append(p)
    if type(p) == list:
        pd = [float(x) for x in p]

    hist = []
    was_directed = g.is_directed()
    if g.is_directed() and not directed_motifs:
        g.set_directed(False)
    try:
       _gt.get_motifs(g._Graph__graph, k, sub_list, hist, pd,
                      True, len(sub_list) == 0,
                      seed)
    finally:
        if was_directed and not directed_motifs:
            g.set_directed(True)

    # assemble graphs
    temp = []
    for m in sub_list:
        mg = Graph()
        mg._Graph__graph = m
        temp.append(mg)
    sub_list = temp

    list_hist = zip(sub_list, hist)
    # sort according to in-degree sequence
    list_hist.sort(lambda x,y: cmp(sorted([v.in_degree() for v in x[0].vertices()]),
                                   sorted([v.in_degree() for v in y[0].vertices()])))

    # sort according to out-degree sequence
    list_hist.sort(lambda x,y: cmp(sorted([v.out_degree() for v in x[0].vertices()]),
                                   sorted([v.out_degree() for v in y[0].vertices()])))

    # sort according to ascending number of edges
    list_hist.sort(lambda x,y: cmp(x[0].num_edges(), y[0].num_edges()))

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

    return sub_list, hist
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510

def motif_significance(g, k, n_shuffles=10, p=1.0, motif_list=None,
                       undirected=None, self_loops=False, parallel_edges=False,
                       full_output=False, seed=0):
    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
    ----------
    g : Graph
        Graph to be used.
    k : int
        number of vertices of the motifs
    n_shuffles : int, optional (default: 10)
        number of shuffled networks to consider for the z-score
    p : float or float list, optional (default: 1.0)
        uniform fraction of the motifs to be sampled. If a float list is
        provided, it will be used as the fraction at each depth
        :math:`[1,\dots,k]` in the algorithm. See [wernicke_efficient_2006]_ for
        more details.
    motif_list : list of Graph objects, optional
        If supplied, the algorithms will only search for the motifs in this list
        (or isomorphisms thereof)
    undirected : bool, optional
        Treat the graph as *undirected*, if graph is directed
        (this option has no effect if the graph is undirected).
    self_loops : bool, optional (default: False)
        Whether or not the shuffled graphs are allowed to contain self-loops
    parallel_edges : bool, optional (default: False)
        Whether or not the shuffled graphs are allowed to contain parallel
        edges.
    full_output : bool, optional (default: False)
        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.
    seed : int, optional (default: 0)
        Seed for the random number generator. It the value is 0, a random seed
        is used.

    Returns
    -------
    motifs : list of Graph objects
        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
        a z-score.

    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}},

    where :math:`N_i` is the number of times motif $i$ found, and :math:`N^s_i`
    is the count of the same motif but on a shuffled network. It measures how
    many standard deviations is each motif count, in respect to a ensemble of
    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
    --------
    >>> g = gt.random_graph(1000, lambda: (5,5), seed=42)
    >>> motifs, zscores = gt.motif_significance(g, 3)
    >>> print len(motifs)
    11
    >>> print zscores
    [0.23425857453240315, 0.23849227914686885, 0.46705666396159251, 0.26171196129510765, -0.28131244310816039, -0.29007872608538582, -0.56694670951384085, -0.5, -0.33333333333333337, -0.46852128566581813, -0.5]
    """
    from itertools import izip
    from .. misc import random_rewire, isomorphism

    s_ms, counts = motifs(g, k, p, motif_list, undirected, seed)
    s_counts = [0]*len(s_ms)
    s_dev = [0]*len(s_ms)

    # get samples
    sg = g.copy()
    for i in xrange(0, n_shuffles):
        random_rewire(sg, self_loops=self_loops, parallel_edges=parallel_edges)
        m_temp, count_temp = motifs(sg, k, p, motif_list, undirected, seed)
        for j in xrange(0, len(m_temp)):
            found = False
            for l in xrange(0, len(s_ms)):
                if isomorphism(s_ms[l], m_temp[j]):
                    found = True
                    s_counts[l] += count_temp[j]
                    s_dev[l] += count_temp[j]**2
            if not found:
                s_ms.append(m_temp[j])
                s_counts.append(count_temp[j])
                s_dev.append(count_temp[j]**2)
                counts.append(0)

    s_counts = [ x/float(n_shuffles) for x in s_counts ]
    s_dev = [ sqrt(x[0]/float(n_shuffles) - x[1]**2) \
              for x in izip(s_dev,s_counts) ]

    list_hist = zip(s_ms, s_counts, s_dev)
    # sort according to in-degree sequence
    list_hist.sort(lambda x,y: cmp(sorted([v.in_degree() for v in x[0].vertices()]),
                                   sorted([v.in_degree() for v in y[0].vertices()])))

    # sort according to out-degree sequence
    list_hist.sort(lambda x,y: cmp(sorted([v.out_degree() for v in x[0].vertices()]),
                                   sorted([v.out_degree() for v in y[0].vertices()])))

    # sort according to ascending number of edges
    list_hist.sort(lambda x,y: cmp(x[0].num_edges(), y[0].num_edges()))

    s_ms, s_counts, s_dev = zip(*list_hist)

    zscore = [(x[0] - x[1])/x[2] for x in izip(counts, s_counts, s_dev)]

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