1"""Functions for computing measures of structural holes."""
2
3import networkx as nx
4
5__all__ = ["constraint", "local_constraint", "effective_size"]
6
7
8def mutual_weight(G, u, v, weight=None):
9    """Returns the sum of the weights of the edge from `u` to `v` and
10    the edge from `v` to `u` in `G`.
11
12    `weight` is the edge data key that represents the edge weight. If
13    the specified key is `None` or is not in the edge data for an edge,
14    that edge is assumed to have weight 1.
15
16    Pre-conditions: `u` and `v` must both be in `G`.
17
18    """
19    try:
20        a_uv = G[u][v].get(weight, 1)
21    except KeyError:
22        a_uv = 0
23    try:
24        a_vu = G[v][u].get(weight, 1)
25    except KeyError:
26        a_vu = 0
27    return a_uv + a_vu
28
29
30def normalized_mutual_weight(G, u, v, norm=sum, weight=None):
31    """Returns normalized mutual weight of the edges from `u` to `v`
32    with respect to the mutual weights of the neighbors of `u` in `G`.
33
34    `norm` specifies how the normalization factor is computed. It must
35    be a function that takes a single argument and returns a number.
36    The argument will be an iterable of mutual weights
37    of pairs ``(u, w)``, where ``w`` ranges over each (in- and
38    out-)neighbor of ``u``. Commons values for `normalization` are
39    ``sum`` and ``max``.
40
41    `weight` can be ``None`` or a string, if None, all edge weights
42    are considered equal. Otherwise holds the name of the edge
43    attribute used as weight.
44
45    """
46    scale = norm(mutual_weight(G, u, w, weight) for w in set(nx.all_neighbors(G, u)))
47    return 0 if scale == 0 else mutual_weight(G, u, v, weight) / scale
48
49
50def effective_size(G, nodes=None, weight=None):
51    r"""Returns the effective size of all nodes in the graph ``G``.
52
53    The *effective size* of a node's ego network is based on the concept
54    of redundancy. A person's ego network has redundancy to the extent
55    that her contacts are connected to each other as well. The
56    nonredundant part of a person's relationships it's the effective
57    size of her ego network [1]_.  Formally, the effective size of a
58    node $u$, denoted $e(u)$, is defined by
59
60    .. math::
61
62       e(u) = \sum_{v \in N(u) \setminus \{u\}}
63       \left(1 - \sum_{w \in N(v)} p_{uw} m_{vw}\right)
64
65    where $N(u)$ is the set of neighbors of $u$ and $p_{uw}$ is the
66    normalized mutual weight of the (directed or undirected) edges
67    joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. And $m_{vw}$
68    is the mutual weight of $v$ and $w$ divided by $v$ highest mutual
69    weight with any of its neighbors. The *mutual weight* of $u$ and $v$
70    is the sum of the weights of edges joining them (edge weights are
71    assumed to be one if the graph is unweighted).
72
73    For the case of unweighted and undirected graphs, Borgatti proposed
74    a simplified formula to compute effective size [2]_
75
76    .. math::
77
78       e(u) = n - \frac{2t}{n}
79
80    where `t` is the number of ties in the ego network (not including
81    ties to ego) and `n` is the number of nodes (excluding ego).
82
83    Parameters
84    ----------
85    G : NetworkX graph
86        The graph containing ``v``. Directed graphs are treated like
87        undirected graphs when computing neighbors of ``v``.
88
89    nodes : container, optional
90        Container of nodes in the graph ``G`` to compute the effective size.
91        If None, the effective size of every node is computed.
92
93    weight : None or string, optional
94      If None, all edge weights are considered equal.
95      Otherwise holds the name of the edge attribute used as weight.
96
97    Returns
98    -------
99    dict
100        Dictionary with nodes as keys and the effective size of the node as values.
101
102    Notes
103    -----
104    Burt also defined the related concept of *efficiency* of a node's ego
105    network, which is its effective size divided by the degree of that
106    node [1]_. So you can easily compute efficiency:
107
108    >>> G = nx.DiGraph()
109    >>> G.add_edges_from([(0, 1), (0, 2), (1, 0), (2, 1)])
110    >>> esize = nx.effective_size(G)
111    >>> efficiency = {n: v / G.degree(n) for n, v in esize.items()}
112
113    See also
114    --------
115    constraint
116
117    References
118    ----------
119    .. [1] Burt, Ronald S.
120           *Structural Holes: The Social Structure of Competition.*
121           Cambridge: Harvard University Press, 1995.
122
123    .. [2] Borgatti, S.
124           "Structural Holes: Unpacking Burt's Redundancy Measures"
125           CONNECTIONS 20(1):35-38.
126           http://www.analytictech.com/connections/v20(1)/holes.htm
127
128    """
129
130    def redundancy(G, u, v, weight=None):
131        nmw = normalized_mutual_weight
132        r = sum(
133            nmw(G, u, w, weight=weight) * nmw(G, v, w, norm=max, weight=weight)
134            for w in set(nx.all_neighbors(G, u))
135        )
136        return 1 - r
137
138    effective_size = {}
139    if nodes is None:
140        nodes = G
141    # Use Borgatti's simplified formula for unweighted and undirected graphs
142    if not G.is_directed() and weight is None:
143        for v in nodes:
144            # Effective size is not defined for isolated nodes
145            if len(G[v]) == 0:
146                effective_size[v] = float("nan")
147                continue
148            E = nx.ego_graph(G, v, center=False, undirected=True)
149            effective_size[v] = len(E) - (2 * E.size()) / len(E)
150    else:
151        for v in nodes:
152            # Effective size is not defined for isolated nodes
153            if len(G[v]) == 0:
154                effective_size[v] = float("nan")
155                continue
156            effective_size[v] = sum(
157                redundancy(G, v, u, weight) for u in set(nx.all_neighbors(G, v))
158            )
159    return effective_size
160
161
162def constraint(G, nodes=None, weight=None):
163    r"""Returns the constraint on all nodes in the graph ``G``.
164
165    The *constraint* is a measure of the extent to which a node *v* is
166    invested in those nodes that are themselves invested in the
167    neighbors of *v*. Formally, the *constraint on v*, denoted `c(v)`,
168    is defined by
169
170    .. math::
171
172       c(v) = \sum_{w \in N(v) \setminus \{v\}} \ell(v, w)
173
174    where `N(v)` is the subset of the neighbors of `v` that are either
175    predecessors or successors of `v` and `\ell(v, w)` is the local
176    constraint on `v` with respect to `w` [1]_. For the definition of local
177    constraint, see :func:`local_constraint`.
178
179    Parameters
180    ----------
181    G : NetworkX graph
182        The graph containing ``v``. This can be either directed or undirected.
183
184    nodes : container, optional
185        Container of nodes in the graph ``G`` to compute the constraint. If
186        None, the constraint of every node is computed.
187
188    weight : None or string, optional
189      If None, all edge weights are considered equal.
190      Otherwise holds the name of the edge attribute used as weight.
191
192    Returns
193    -------
194    dict
195        Dictionary with nodes as keys and the constraint on the node as values.
196
197    See also
198    --------
199    local_constraint
200
201    References
202    ----------
203    .. [1] Burt, Ronald S.
204           "Structural holes and good ideas".
205           American Journal of Sociology (110): 349–399.
206
207    """
208    if nodes is None:
209        nodes = G
210    constraint = {}
211    for v in nodes:
212        # Constraint is not defined for isolated nodes
213        if len(G[v]) == 0:
214            constraint[v] = float("nan")
215            continue
216        constraint[v] = sum(
217            local_constraint(G, v, n, weight) for n in set(nx.all_neighbors(G, v))
218        )
219    return constraint
220
221
222def local_constraint(G, u, v, weight=None):
223    r"""Returns the local constraint on the node ``u`` with respect to
224    the node ``v`` in the graph ``G``.
225
226    Formally, the *local constraint on u with respect to v*, denoted
227    $\ell(v)$, is defined by
228
229    .. math::
230
231       \ell(u, v) = \left(p_{uv} + \sum_{w \in N(v)} p_{uw} p{wv}\right)^2,
232
233    where $N(v)$ is the set of neighbors of $v$ and $p_{uv}$ is the
234    normalized mutual weight of the (directed or undirected) edges
235    joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. The *mutual
236    weight* of $u$ and $v$ is the sum of the weights of edges joining
237    them (edge weights are assumed to be one if the graph is
238    unweighted).
239
240    Parameters
241    ----------
242    G : NetworkX graph
243        The graph containing ``u`` and ``v``. This can be either
244        directed or undirected.
245
246    u : node
247        A node in the graph ``G``.
248
249    v : node
250        A node in the graph ``G``.
251
252    weight : None or string, optional
253      If None, all edge weights are considered equal.
254      Otherwise holds the name of the edge attribute used as weight.
255
256    Returns
257    -------
258    float
259        The constraint of the node ``v`` in the graph ``G``.
260
261    See also
262    --------
263    constraint
264
265    References
266    ----------
267    .. [1] Burt, Ronald S.
268           "Structural holes and good ideas".
269           American Journal of Sociology (110): 349–399.
270
271    """
272    nmw = normalized_mutual_weight
273    direct = nmw(G, u, v, weight=weight)
274    indirect = sum(
275        nmw(G, u, w, weight=weight) * nmw(G, w, v, weight=weight)
276        for w in set(nx.all_neighbors(G, u))
277    )
278    return (direct + indirect) ** 2
279