File size: 3,402 Bytes
17c6d62 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | """Node redundancy for bipartite graphs."""
from itertools import combinations
import networkx as nx
from networkx import NetworkXError
__all__ = ["node_redundancy"]
@nx._dispatchable
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])
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))
|