Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / triads.py @ 5cef0f13

History | View | Annotate | Download (3.98 KB)

1
# triads.py - functions for analyzing triads of a graph
2
#
3
# Copyright 2015 NetworkX developers.
4
# Copyright 2011 Reya Group <http://www.reyagroup.com>
5
# Copyright 2011 Alex Levenson <alex@isnotinvain.com>
6
# Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca>
7
#
8
# This file is part of NetworkX.
9
#
10
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
11
# information.
12
"""Functions for analyzing triads of a graph."""
13
from __future__ import division
14

    
15
from networkx.utils import not_implemented_for
16

    
17
__author__ = '\n'.join(['Alex Levenson (alex@isnontinvain.com)',
18
                        'Diederik van Liere (diederik.vanliere@rotman.utoronto.ca)'])
19

    
20
__all__ = ['triadic_census']
21

    
22
#: The integer codes representing each type of triad.
23
#:
24
#: Triads that are the same up to symmetry have the same code.
25
TRICODES = (1, 2, 2, 3, 2, 4, 6, 8, 2, 6, 5, 7, 3, 8, 7, 11, 2, 6, 4, 8, 5, 9,
26
            9, 13, 6, 10, 9, 14, 7, 14, 12, 15, 2, 5, 6, 7, 6, 9, 10, 14, 4, 9,
27
            9, 12, 8, 13, 14, 15, 3, 7, 8, 11, 7, 12, 14, 15, 8, 14, 13, 15,
28
            11, 15, 15, 16)
29

    
30
#: The names of each type of triad. The order of the elements is
31
#: important: it corresponds to the tricodes given in :data:`TRICODES`.
32
TRIAD_NAMES = ('003', '012', '102', '021D', '021U', '021C', '111D', '111U',
33
               '030T', '030C', '201', '120D', '120U', '120C', '210', '300')
34

    
35

    
36
#: A dictionary mapping triad code to triad name.
37
TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)}
38

    
39

    
40
def _tricode(G, v, u, w):
41
    """Returns the integer code of the given triad.
42

43
    This is some fancy magic that comes from Batagelj and Mrvar's paper. It
44
    treats each edge joining a pair of `v`, `u`, and `w` as a bit in
45
    the binary representation of an integer.
46

47
    """
48
    combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16),
49
              (w, u, 32))
50
    return sum(x for u, v, x in combos if v in G[u])
51

    
52

    
53
@not_implemented_for('undirected')
54
def triadic_census(G):
55
    """Determines the triadic census of a directed graph.
56

57
    The triadic census is a count of how many of the 16 possible types of
58
    triads are present in a directed graph.
59

60
    Parameters
61
    ----------
62
    G : digraph
63
       A NetworkX DiGraph
64

65
    Returns
66
    -------
67
    census : dict
68
       Dictionary with triad names as keys and number of occurrences as values.
69

70
    Notes
71
    -----
72
    This algorithm has complexity $O(m)$ where $m$ is the number of edges in
73
    the graph.
74

75
    See also
76
    --------
77
    triad_graph
78

79
    References
80
    ----------
81
    .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census
82
        algorithm for large sparse networks with small maximum degree,
83
        University of Ljubljana,
84
        http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf
85

86
    """
87
    # Initialize the count for each triad to be zero.
88
    census = {name: 0 for name in TRIAD_NAMES}
89
    n = len(G)
90
    # m = dict(zip(G, range(n)))
91
    m = {v: i for i, v in enumerate(G)}
92
    for v in G:
93
        vnbrs = set(G.pred[v]) | set(G.succ[v])
94
        for u in vnbrs:
95
            if m[u] <= m[v]:
96
                continue
97
            neighbors = (vnbrs | set(G.succ[u]) | set(G.pred[u])) - {u, v}
98
            # Calculate dyadic triads instead of counting them.
99
            if v in G[u] and u in G[v]:
100
                census['102'] += n - len(neighbors) - 2
101
            else:
102
                census['012'] += n - len(neighbors) - 2
103
            # Count connected triads.
104
            for w in neighbors:
105
                if m[u] < m[w] or (m[v] < m[w] < m[u] and
106
                                   v not in G.pred[w] and
107
                                   v not in G.succ[w]):
108
                    code = _tricode(G, v, u, w)
109
                    census[TRICODE_TO_NAME[code]] += 1
110

    
111
    # null triads = total number of possible triads - all found triads
112
    #
113
    # Use integer division here, since we know this formula guarantees an
114
    # integral value.
115
    census['003'] = ((n * (n - 1) * (n - 2)) // 6) - sum(census.values())
116
    return census