Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.18 KB)

1
# -*- encoding: utf-8 -*-
2
#
3
# Copyright 2008-2019 NetworkX developers.
4
#    Aric Hagberg <hagberg@lanl.gov>
5
#    Dan Schult <dschult@colgate.edu>
6
#    Pieter Swart <swart@lanl.gov>
7
#    All rights reserved.
8
#    BSD license.
9
"""Functions for computing measures of structural holes."""
10
from __future__ import division
11

    
12
import networkx as nx
13

    
14
__all__ = ['constraint', 'local_constraint', 'effective_size']
15

    
16

    
17
def mutual_weight(G, u, v, weight=None):
18
    """Returns the sum of the weights of the edge from `u` to `v` and
19
    the edge from `v` to `u` in `G`.
20

21
    `weight` is the edge data key that represents the edge weight. If
22
    the specified key is `None` or is not in the edge data for an edge,
23
    that edge is assumed to have weight 1.
24

25
    Pre-conditions: `u` and `v` must both be in `G`.
26

27
    """
28
    try:
29
        a_uv = G[u][v].get(weight, 1)
30
    except KeyError:
31
        a_uv = 0
32
    try:
33
        a_vu = G[v][u].get(weight, 1)
34
    except KeyError:
35
        a_vu = 0
36
    return a_uv + a_vu
37

    
38

    
39
def normalized_mutual_weight(G, u, v, norm=sum, weight=None):
40
    """Returns normalized mutual weight of the edges from `u` to `v`
41
    with respect to the mutual weights of the neighbors of `u` in `G`.
42

43
    `norm` specifies how the normalization factor is computed. It must
44
    be a function that takes a single argument and returns a number.
45
    The argument will be an iterable of mutual weights
46
    of pairs ``(u, w)``, where ``w`` ranges over each (in- and
47
    out-)neighbor of ``u``. Commons values for `normalization` are
48
    ``sum`` and ``max``.
49

50
    `weight` can be ``None`` or a string, if None, all edge weights
51
    are considered equal. Otherwise holds the name of the edge
52
    attribute used as weight.
53

54
    """
55
    scale = norm(mutual_weight(G, u, w, weight)
56
                 for w in set(nx.all_neighbors(G, u)))
57
    return 0 if scale == 0 else mutual_weight(G, u, v, weight) / scale
58

    
59

    
60
def effective_size(G, nodes=None, weight=None):
61
    r"""Returns the effective size of all nodes in the graph ``G``.
62

63
    The *effective size* of a node's ego network is based on the concept
64
    of redundancy. A person's ego network has redundancy to the extent
65
    that her contacts are connected to each other as well. The
66
    nonredundant part of a person's relationships it's the effective
67
    size of her ego network [1]_.  Formally, the effective size of a
68
    node $u$, denoted $e(u)$, is defined by
69

70
    .. math::
71

72
       e(u) = \sum_{v \in N(u) \setminus \{u\}}
73
       \left(1 - \sum_{w \in N(v)} p_{uw} m_{vw}\right)
74

75
    where $N(u)$ is the set of neighbors of $u$ and $p_{uw}$ is the
76
    normalized mutual weight of the (directed or undirected) edges
77
    joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. And $m_{vw}$
78
    is the mutual weight of $v$ and $w$ divided by $v$ highest mutual
79
    weight with any of its neighbors. The *mutual weight* of $u$ and $v$
80
    is the sum of the weights of edges joining them (edge weights are
81
    assumed to be one if the graph is unweighted).
82

83
    For the case of unweighted and undirected graphs, Borgatti proposed
84
    a simplified formula to compute effective size [2]_
85

86
    .. math::
87

88
       e(u) = n - \frac{2t}{n}
89

90
    where `t` is the number of ties in the ego network (not including
91
    ties to ego) and `n` is the number of nodes (excluding ego).
92

93
    Parameters
94
    ----------
95
    G : NetworkX graph
96
        The graph containing ``v``. Directed graphs are treated like
97
        undirected graphs when computing neighbors of ``v``.
98

99
    nodes : container, optional
100
        Container of nodes in the graph ``G`` to compute the effective size.
101
        If None, the effective size of every node is computed.
102

103
    weight : None or string, optional
104
      If None, all edge weights are considered equal.
105
      Otherwise holds the name of the edge attribute used as weight.
106

107
    Returns
108
    -------
109
    dict
110
        Dictionary with nodes as keys and the constraint on the node as values.
111

112
    Notes
113
    -----
114
    Burt also defined the related concept of *efficiency* of a node's ego
115
    network, which is its effective size divided by the degree of that
116
    node [1]_. So you can easily compute efficiency:
117

118
    >>> G = nx.DiGraph()
119
    >>> G.add_edges_from([(0, 1), (0, 2), (1, 0), (2, 1)])
120
    >>> esize = nx.effective_size(G)
121
    >>> efficiency = {n: v / G.degree(n) for n, v in esize.items()}
122

123
    See also
124
    --------
125
    constraint
126

127
    References
128
    ----------
129
    .. [1] Burt, Ronald S.
130
           *Structural Holes: The Social Structure of Competition.*
131
           Cambridge: Harvard University Press, 1995.
132

133
    .. [2] Borgatti, S.
134
           "Structural Holes: Unpacking Burt's Redundancy Measures"
135
           CONNECTIONS 20(1):35-38.
136
           http://www.analytictech.com/connections/v20(1)/holes.htm
137

138
    """
139
    def redundancy(G, u, v, weight=None):
140
        nmw = normalized_mutual_weight
141
        r = sum(nmw(G, u, w, weight=weight) * nmw(G, v, w, norm=max, weight=weight)
142
                for w in set(nx.all_neighbors(G, u)))
143
        return 1 - r
144
    effective_size = {}
145
    if nodes is None:
146
        nodes = G
147
    # Use Borgatti's simplified formula for unweighted and undirected graphs
148
    if not G.is_directed() and weight is None:
149
        for v in nodes:
150
            # Effective size is not defined for isolated nodes
151
            if len(G[v]) == 0:
152
                effective_size[v] = float('nan')
153
                continue
154
            E = nx.ego_graph(G, v, center=False, undirected=True)
155
            effective_size[v] = len(E) - (2 * E.size()) / len(E)
156
    else:
157
        for v in nodes:
158
            # Effective size is not defined for isolated nodes
159
            if len(G[v]) == 0:
160
                effective_size[v] = float('nan')
161
                continue
162
            effective_size[v] = sum(redundancy(G, v, u, weight)
163
                                    for u in set(nx.all_neighbors(G, v)))
164
    return effective_size
165

    
166

    
167
def constraint(G, nodes=None, weight=None):
168
    r"""Returns the constraint on all nodes in the graph ``G``.
169

170
    The *constraint* is a measure of the extent to which a node *v* is
171
    invested in those nodes that are themselves invested in the
172
    neighbors of *v*. Formally, the *constraint on v*, denoted `c(v)`,
173
    is defined by
174

175
    .. math::
176

177
       c(v) = \sum_{w \in N(v) \setminus \{v\}} \ell(v, w)
178

179
    where `N(v)` is the subset of the neighbors of `v` that are either
180
    predecessors or successors of `v` and `\ell(v, w)` is the local
181
    constraint on `v` with respect to `w` [1]_. For the definition of local
182
    constraint, see :func:`local_constraint`.
183

184
    Parameters
185
    ----------
186
    G : NetworkX graph
187
        The graph containing ``v``. This can be either directed or undirected.
188

189
    nodes : container, optional
190
        Container of nodes in the graph ``G`` to compute the constraint. If
191
        None, the constraint of every node is computed.
192

193
    weight : None or string, optional
194
      If None, all edge weights are considered equal.
195
      Otherwise holds the name of the edge attribute used as weight.
196

197
    Returns
198
    -------
199
    dict
200
        Dictionary with nodes as keys and the constraint on the node as values.
201

202
    See also
203
    --------
204
    local_constraint
205

206
    References
207
    ----------
208
    .. [1] Burt, Ronald S.
209
           "Structural holes and good ideas".
210
           American Journal of Sociology (110): 349–399.
211

212
    """
213
    if nodes is None:
214
        nodes = G
215
    constraint = {}
216
    for v in nodes:
217
        # Constraint is not defined for isolated nodes
218
        if len(G[v]) == 0:
219
            constraint[v] = float('nan')
220
            continue
221
        constraint[v] = sum(local_constraint(G, v, n, weight)
222
                            for n in set(nx.all_neighbors(G, v)))
223
    return constraint
224

    
225

    
226
def local_constraint(G, u, v, weight=None):
227
    r"""Returns the local constraint on the node ``u`` with respect to
228
    the node ``v`` in the graph ``G``.
229

230
    Formally, the *local constraint on u with respect to v*, denoted
231
    $\ell(v)$, is defined by
232

233
    .. math::
234

235
       \ell(u, v) = \left(p_{uv} + \sum_{w \in N(v)} p_{uw} p{wv}\right)^2,
236

237
    where $N(v)$ is the set of neighbors of $v$ and $p_{uv}$ is the
238
    normalized mutual weight of the (directed or undirected) edges
239
    joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. The *mutual
240
    weight* of $u$ and $v$ is the sum of the weights of edges joining
241
    them (edge weights are assumed to be one if the graph is
242
    unweighted).
243

244
    Parameters
245
    ----------
246
    G : NetworkX graph
247
        The graph containing ``u`` and ``v``. This can be either
248
        directed or undirected.
249

250
    u : node
251
        A node in the graph ``G``.
252

253
    v : node
254
        A node in the graph ``G``.
255

256
    weight : None or string, optional
257
      If None, all edge weights are considered equal.
258
      Otherwise holds the name of the edge attribute used as weight.
259

260
    Returns
261
    -------
262
    float
263
        The constraint of the node ``v`` in the graph ``G``.
264

265
    See also
266
    --------
267
    constraint
268

269
    References
270
    ----------
271
    .. [1] Burt, Ronald S.
272
           "Structural holes and good ideas".
273
           American Journal of Sociology (110): 349–399.
274

275
    """
276
    nmw = normalized_mutual_weight
277
    direct = nmw(G, u, v, weight=weight)
278
    indirect = sum(nmw(G, u, w, weight=weight) * nmw(G, w, v, weight=weight)
279
                   for w in set(nx.all_neighbors(G, u)))
280
    return (direct + indirect) ** 2