### diff env/lib/python3.9/site-packages/networkx/algorithms/bipartite/redundancy.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/redundancy.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,111 @@
+"""Node redundancy for bipartite graphs."""
+from itertools import combinations
+
+from networkx import NetworkXError
+
+__all__ = ["node_redundancy"]
+
+
+def node_redundancy(G, nodes=None):
+    r"""Computes the node redundancy coefficients for the nodes in the bipartite
+    graph G.
+
+    The redundancy coefficient of a node v is the fraction of pairs of
+    neighbors of v that are both linked to other nodes. In a one-mode
+    projection these nodes would be linked together even if v were
+    not there.
+
+    More formally, for any vertex v, the *redundancy coefficient of v* is
+    defined by
+
+    .. math::
+
+        rc(v) = \frac{|\{\{u, w\} \subseteq N(v),
+        \: \exists v' \neq  v,\: (v',u) \in E\:
+        \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}},
+
+    where N(v) is the set of neighbors of v in G.
+
+    Parameters
+    ----------
+    G : graph
+        A bipartite graph
+
+    nodes : list or iterable (optional)
+        Compute redundancy for these nodes. The default is all nodes in G.
+
+    Returns
+    -------
+    redundancy : dictionary
+        A dictionary keyed by node with the node redundancy value.
+
+    Examples
+    --------
+    Compute the redundancy coefficient of each node in a graph::
+
+        >>> from networkx.algorithms import bipartite
+        >>> G = nx.cycle_graph(4)
+        >>> rc = bipartite.node_redundancy(G)
+        >>> rc[0]
+        1.0
+
+    Compute the average redundancy for the graph::
+
+        >>> from networkx.algorithms import bipartite
+        >>> G = nx.cycle_graph(4)
+        >>> rc = bipartite.node_redundancy(G)
+        >>> sum(rc.values()) / len(G)
+        1.0
+
+    Compute the average redundancy for a set of nodes::
+
+        >>> from networkx.algorithms import bipartite
+        >>> G = nx.cycle_graph(4)
+        >>> rc = bipartite.node_redundancy(G)
+        >>> nodes = [0, 2]
+        >>> sum(rc[n] for n in nodes) / len(nodes)
+        1.0
+
+    Raises
+    ------
+    NetworkXError
+        If any of the nodes in the graph (or in nodes, if specified) has
+        (out-)degree less than two (which would result in division by zero,
+        according to the definition of the redundancy coefficient).
+
+    References
+    ----------
+    .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
+       Basic notions for the analysis of large two-mode networks.
+       Social Networks 30(1), 31--48.
+
+    """
+    if nodes is None:
+        nodes = G
+    if any(len(G[v]) < 2 for v in nodes):
+        raise NetworkXError(
+            "Cannot compute redundancy coefficient for a node"
+            " that has fewer than two neighbors."
+        )
+    # TODO This can be trivially parallelized.
+    return {v: _node_redundancy(G, v) for v in nodes}
+
+
+def _node_redundancy(G, v):
+    """Returns the redundancy of the node v in the bipartite graph G.
+
+    If G is a graph with n nodes, the redundancy of a node is the ratio
+    of the "overlap" of v to the maximum possible overlap of v
+    according to its degree. The overlap of v is the number of pairs of
+    neighbors that have mutual neighbors themselves, other than v.
+
+    v must have at least two neighbors in G.
+
+    """
+    n = len(G[v])
+    # TODO On Python 3, we could just use G[u].keys() & G[w].keys() instead
+    # of instantiating the entire sets.
+    overlap = sum(
+        1 for (u, w) in combinations(G[v], 2) if (set(G[u]) & set(G[w])) - {v}
+    )
+    return (2 * overlap) / (n * (n - 1))