1import networkx as nx
2
3__all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"]
4
5
6def degree_centrality(G, nodes):
7    r"""Compute the degree centrality for nodes in a bipartite network.
8
9    The degree centrality for a node `v` is the fraction of nodes
10    connected to it.
11
12    Parameters
13    ----------
14    G : graph
15       A bipartite network
16
17    nodes : list or container
18      Container with all nodes in one bipartite node set.
19
20    Returns
21    -------
22    centrality : dictionary
23       Dictionary keyed by node with bipartite degree centrality as the value.
24
25    See Also
26    --------
27    betweenness_centrality
28    closeness_centrality
29    :func:`~networkx.algorithms.bipartite.basic.sets`
30    :func:`~networkx.algorithms.bipartite.basic.is_bipartite`
31
32    Notes
33    -----
34    The nodes input parameter must contain all nodes in one bipartite node set,
35    but the dictionary returned contains all nodes from both bipartite node
36    sets. See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
37    for further details on how bipartite graphs are handled in NetworkX.
38
39    For unipartite networks, the degree centrality values are
40    normalized by dividing by the maximum possible degree (which is
41    `n-1` where `n` is the number of nodes in G).
42
43    In the bipartite case, the maximum possible degree of a node in a
44    bipartite node set is the number of nodes in the opposite node set
45    [1]_.  The degree centrality for a node `v` in the bipartite
46    sets `U` with `n` nodes and `V` with `m` nodes is
47
48    .. math::
49
50        d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U ,
51
52        d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V ,
53
54
55    where `deg(v)` is the degree of node `v`.
56
57    References
58    ----------
59    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
60        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
61        of Social Network Analysis. Sage Publications.
62        https://dx.doi.org/10.4135/9781446294413.n28
63    """
64    top = set(nodes)
65    bottom = set(G) - top
66    s = 1.0 / len(bottom)
67    centrality = {n: d * s for n, d in G.degree(top)}
68    s = 1.0 / len(top)
69    centrality.update({n: d * s for n, d in G.degree(bottom)})
70    return centrality
71
72
73def betweenness_centrality(G, nodes):
74    r"""Compute betweenness centrality for nodes in a bipartite network.
75
76    Betweenness centrality of a node `v` is the sum of the
77    fraction of all-pairs shortest paths that pass through `v`.
78
79    Values of betweenness are normalized by the maximum possible
80    value which for bipartite graphs is limited by the relative size
81    of the two node sets [1]_.
82
83    Let `n` be the number of nodes in the node set `U` and
84    `m` be the number of nodes in the node set `V`, then
85    nodes in `U` are normalized by dividing by
86
87    .. math::
88
89       \frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] ,
90
91    where
92
93    .. math::
94
95        s = (n - 1) \div m , t = (n - 1) \mod m ,
96
97    and nodes in `V` are normalized by dividing by
98
99    .. math::
100
101        \frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] ,
102
103    where,
104
105    .. math::
106
107        p = (m - 1) \div n , r = (m - 1) \mod n .
108
109    Parameters
110    ----------
111    G : graph
112        A bipartite graph
113
114    nodes : list or container
115        Container with all nodes in one bipartite node set.
116
117    Returns
118    -------
119    betweenness : dictionary
120        Dictionary keyed by node with bipartite betweenness centrality
121        as the value.
122
123    See Also
124    --------
125    degree_centrality
126    closeness_centrality
127    :func:`~networkx.algorithms.bipartite.basic.sets`
128    :func:`~networkx.algorithms.bipartite.basic.is_bipartite`
129
130    Notes
131    -----
132    The nodes input parameter must contain all nodes in one bipartite node set,
133    but the dictionary returned contains all nodes from both node sets.
134    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
135    for further details on how bipartite graphs are handled in NetworkX.
136
137
138    References
139    ----------
140    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
141        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
142        of Social Network Analysis. Sage Publications.
143        https://dx.doi.org/10.4135/9781446294413.n28
144    """
145    top = set(nodes)
146    bottom = set(G) - top
147    n = float(len(top))
148    m = float(len(bottom))
149    s = (n - 1) // m
150    t = (n - 1) % m
151    bet_max_top = (
152        ((m ** 2) * ((s + 1) ** 2))
153        + (m * (s + 1) * (2 * t - s - 1))
154        - (t * ((2 * s) - t + 3))
155    ) / 2.0
156    p = (m - 1) // n
157    r = (m - 1) % n
158    bet_max_bot = (
159        ((n ** 2) * ((p + 1) ** 2))
160        + (n * (p + 1) * (2 * r - p - 1))
161        - (r * ((2 * p) - r + 3))
162    ) / 2.0
163    betweenness = nx.betweenness_centrality(G, normalized=False, weight=None)
164    for node in top:
165        betweenness[node] /= bet_max_top
166    for node in bottom:
167        betweenness[node] /= bet_max_bot
168    return betweenness
169
170
171def closeness_centrality(G, nodes, normalized=True):
172    r"""Compute the closeness centrality for nodes in a bipartite network.
173
174    The closeness of a node is the distance to all other nodes in the
175    graph or in the case that the graph is not connected to all other nodes
176    in the connected component containing that node.
177
178    Parameters
179    ----------
180    G : graph
181        A bipartite network
182
183    nodes : list or container
184        Container with all nodes in one bipartite node set.
185
186    normalized : bool, optional
187      If True (default) normalize by connected component size.
188
189    Returns
190    -------
191    closeness : dictionary
192        Dictionary keyed by node with bipartite closeness centrality
193        as the value.
194
195    See Also
196    --------
197    betweenness_centrality
198    degree_centrality
199    :func:`~networkx.algorithms.bipartite.basic.sets`
200    :func:`~networkx.algorithms.bipartite.basic.is_bipartite`
201
202    Notes
203    -----
204    The nodes input parameter must contain all nodes in one bipartite node set,
205    but the dictionary returned contains all nodes from both node sets.
206    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
207    for further details on how bipartite graphs are handled in NetworkX.
208
209
210    Closeness centrality is normalized by the minimum distance possible.
211    In the bipartite case the minimum distance for a node in one bipartite
212    node set is 1 from all nodes in the other node set and 2 from all
213    other nodes in its own set [1]_. Thus the closeness centrality
214    for node `v`  in the two bipartite sets `U` with
215    `n` nodes and `V` with `m` nodes is
216
217    .. math::
218
219        c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U,
220
221        c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V,
222
223    where `d` is the sum of the distances from `v` to all
224    other nodes.
225
226    Higher values of closeness  indicate higher centrality.
227
228    As in the unipartite case, setting normalized=True causes the
229    values to normalized further to n-1 / size(G)-1 where n is the
230    number of nodes in the connected part of graph containing the
231    node.  If the graph is not completely connected, this algorithm
232    computes the closeness centrality for each connected part
233    separately.
234
235    References
236    ----------
237    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
238        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
239        of Social Network Analysis. Sage Publications.
240        https://dx.doi.org/10.4135/9781446294413.n28
241    """
242    closeness = {}
243    path_length = nx.single_source_shortest_path_length
244    top = set(nodes)
245    bottom = set(G) - top
246    n = float(len(top))
247    m = float(len(bottom))
248    for node in top:
249        sp = dict(path_length(G, node))
250        totsp = sum(sp.values())
251        if totsp > 0.0 and len(G) > 1:
252            closeness[node] = (m + 2 * (n - 1)) / totsp
253            if normalized:
254                s = (len(sp) - 1.0) / (len(G) - 1)
255                closeness[node] *= s
256        else:
257            closeness[n] = 0.0
258    for node in bottom:
259        sp = dict(path_length(G, node))
260        totsp = sum(sp.values())
261        if totsp > 0.0 and len(G) > 1:
262            closeness[node] = (n + 2 * (m - 1)) / totsp
263            if normalized:
264                s = (len(sp) - 1.0) / (len(G) - 1)
265                closeness[node] *= s
266        else:
267            closeness[n] = 0.0
268    return closeness
269