### diff env/lib/python3.9/site-packages/networkx/algorithms/bipartite/centrality.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/bipartite/centrality.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,268 @@
+import networkx as nx
+
+__all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"]
+
+
+def degree_centrality(G, nodes):
+    r"""Compute the degree centrality for nodes in a bipartite network.
+
+    The degree centrality for a node v is the fraction of nodes
+    connected to it.
+
+    Parameters
+    ----------
+    G : graph
+       A bipartite network
+
+    nodes : list or container
+      Container with all nodes in one bipartite node set.
+
+    Returns
+    -------
+    centrality : dictionary
+       Dictionary keyed by node with bipartite degree centrality as the value.
+
+    --------
+    betweenness_centrality,
+    closeness_centrality,
+    sets,
+    is_bipartite
+
+    Notes
+    -----
+    The nodes input parameter must contain all nodes in one bipartite node set,
+    but the dictionary returned contains all nodes from both bipartite node
+    sets. See :mod:bipartite documentation <networkx.algorithms.bipartite>
+    for further details on how bipartite graphs are handled in NetworkX.
+
+    For unipartite networks, the degree centrality values are
+    normalized by dividing by the maximum possible degree (which is
+    n-1 where n is the number of nodes in G).
+
+    In the bipartite case, the maximum possible degree of a node in a
+    bipartite node set is the number of nodes in the opposite node set
+    [1]_.  The degree centrality for a node v in the bipartite
+    sets U with n nodes and V with m nodes is
+
+    .. math::
+
+        d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U ,
+
+        d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V ,
+
+
+    where deg(v) is the degree of node v.
+
+    References
+    ----------
+    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
+        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
+        of Social Network Analysis. Sage Publications.
+        http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
+    """
+    top = set(nodes)
+    bottom = set(G) - top
+    s = 1.0 / len(bottom)
+    centrality = {n: d * s for n, d in G.degree(top)}
+    s = 1.0 / len(top)
+    centrality.update({n: d * s for n, d in G.degree(bottom)})
+    return centrality
+
+
+def betweenness_centrality(G, nodes):
+    r"""Compute betweenness centrality for nodes in a bipartite network.
+
+    Betweenness centrality of a node v is the sum of the
+    fraction of all-pairs shortest paths that pass through v.
+
+    Values of betweenness are normalized by the maximum possible
+    value which for bipartite graphs is limited by the relative size
+    of the two node sets [1]_.
+
+    Let n be the number of nodes in the node set U and
+    m be the number of nodes in the node set V, then
+    nodes in U are normalized by dividing by
+
+    .. math::
+
+       \frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] ,
+
+    where
+
+    .. math::
+
+        s = (n - 1) \div m , t = (n - 1) \mod m ,
+
+    and nodes in V are normalized by dividing by
+
+    .. math::
+
+        \frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] ,
+
+    where,
+
+    .. math::
+
+        p = (m - 1) \div n , r = (m - 1) \mod n .
+
+    Parameters
+    ----------
+    G : graph
+        A bipartite graph
+
+    nodes : list or container
+        Container with all nodes in one bipartite node set.
+
+    Returns
+    -------
+    betweenness : dictionary
+        Dictionary keyed by node with bipartite betweenness centrality
+        as the value.
+
+    --------
+    degree_centrality,
+    closeness_centrality,
+    sets,
+    is_bipartite
+
+    Notes
+    -----
+    The nodes input parameter must contain all nodes in one bipartite node set,
+    but the dictionary returned contains all nodes from both node sets.
+    See :mod:bipartite documentation <networkx.algorithms.bipartite>
+    for further details on how bipartite graphs are handled in NetworkX.
+
+
+    References
+    ----------
+    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
+        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
+        of Social Network Analysis. Sage Publications.
+        http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
+    """
+    top = set(nodes)
+    bottom = set(G) - top
+    n = float(len(top))
+    m = float(len(bottom))
+    s = (n - 1) // m
+    t = (n - 1) % m
+    bet_max_top = (
+        ((m ** 2) * ((s + 1) ** 2))
+        + (m * (s + 1) * (2 * t - s - 1))
+        - (t * ((2 * s) - t + 3))
+    ) / 2.0
+    p = (m - 1) // n
+    r = (m - 1) % n
+    bet_max_bot = (
+        ((n ** 2) * ((p + 1) ** 2))
+        + (n * (p + 1) * (2 * r - p - 1))
+        - (r * ((2 * p) - r + 3))
+    ) / 2.0
+    betweenness = nx.betweenness_centrality(G, normalized=False, weight=None)
+    for node in top:
+        betweenness[node] /= bet_max_top
+    for node in bottom:
+        betweenness[node] /= bet_max_bot
+    return betweenness
+
+
+def closeness_centrality(G, nodes, normalized=True):
+    r"""Compute the closeness centrality for nodes in a bipartite network.
+
+    The closeness of a node is the distance to all other nodes in the
+    graph or in the case that the graph is not connected to all other nodes
+    in the connected component containing that node.
+
+    Parameters
+    ----------
+    G : graph
+        A bipartite network
+
+    nodes : list or container
+        Container with all nodes in one bipartite node set.
+
+    normalized : bool, optional
+      If True (default) normalize by connected component size.
+
+    Returns
+    -------
+    closeness : dictionary
+        Dictionary keyed by node with bipartite closeness centrality
+        as the value.
+
+    --------
+    betweenness_centrality,
+    degree_centrality
+    sets,
+    is_bipartite
+
+    Notes
+    -----
+    The nodes input parameter must contain all nodes in one bipartite node set,
+    but the dictionary returned contains all nodes from both node sets.
+    See :mod:bipartite documentation <networkx.algorithms.bipartite>
+    for further details on how bipartite graphs are handled in NetworkX.
+
+
+    Closeness centrality is normalized by the minimum distance possible.
+    In the bipartite case the minimum distance for a node in one bipartite
+    node set is 1 from all nodes in the other node set and 2 from all
+    other nodes in its own set [1]_. Thus the closeness centrality
+    for node v  in the two bipartite sets U with
+    n nodes and V with m nodes is
+
+    .. math::
+
+        c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U,
+
+        c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V,
+
+    where d is the sum of the distances from v to all
+    other nodes.
+
+    Higher values of closeness  indicate higher centrality.
+
+    As in the unipartite case, setting normalized=True causes the
+    values to normalized further to n-1 / size(G)-1 where n is the
+    number of nodes in the connected part of graph containing the
+    node.  If the graph is not completely connected, this algorithm
+    computes the closeness centrality for each connected part
+    separately.
+
+    References
+    ----------
+    .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation
+        Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook
+        of Social Network Analysis. Sage Publications.
+        http://www.steveborgatti.com/research/publications/bhaffiliations.pdf
+    """
+    closeness = {}
+    path_length = nx.single_source_shortest_path_length
+    top = set(nodes)
+    bottom = set(G) - top
+    n = float(len(top))
+    m = float(len(bottom))
+    for node in top:
+        sp = dict(path_length(G, node))
+        totsp = sum(sp.values())
+        if totsp > 0.0 and len(G) > 1:
+            closeness[node] = (m + 2 * (n - 1)) / totsp
+            if normalized:
+                s = (len(sp) - 1.0) / (len(G) - 1)
+                closeness[node] *= s
+        else:
+            closeness[n] = 0.0
+    for node in bottom:
+        sp = dict(path_length(G, node))
+        totsp = sum(sp.values())
+        if totsp > 0.0 and len(G) > 1:
+            closeness[node] = (n + 2 * (m - 1)) / totsp
+            if normalized:
+                s = (len(sp) - 1.0) / (len(G) - 1)
+                closeness[node] *= s
+        else:
+            closeness[n] = 0.0
+    return closeness