Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Node redundancy for bipartite graphs."""
3from itertools import combinations
5import networkx as nx
6from networkx import NetworkXError
8__all__ = ["node_redundancy"]
11@nx._dispatchable
12def node_redundancy(G, nodes=None):
13 r"""Computes the node redundancy coefficients for the nodes in the bipartite
14 graph `G`.
16 The redundancy coefficient of a node `v` is the fraction of pairs of
17 neighbors of `v` that are both linked to other nodes. In a one-mode
18 projection these nodes would be linked together even if `v` were
19 not there.
21 More formally, for any vertex `v`, the *redundancy coefficient of `v`* is
22 defined by
24 .. math::
26 rc(v) = \frac{|\{\{u, w\} \subseteq N(v),
27 \: \exists v' \neq v,\: (v',u) \in E\:
28 \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}},
30 where `N(v)` is the set of neighbors of `v` in `G`.
32 Parameters
33 ----------
34 G : graph
35 A bipartite graph
37 nodes : list or iterable (optional)
38 Compute redundancy for these nodes. The default is all nodes in G.
40 Returns
41 -------
42 redundancy : dictionary
43 A dictionary keyed by node with the node redundancy value.
45 Examples
46 --------
47 Compute the redundancy coefficient of each node in a graph::
49 >>> from networkx.algorithms import bipartite
50 >>> G = nx.cycle_graph(4)
51 >>> rc = bipartite.node_redundancy(G)
52 >>> rc[0]
53 1.0
55 Compute the average redundancy for the graph::
57 >>> from networkx.algorithms import bipartite
58 >>> G = nx.cycle_graph(4)
59 >>> rc = bipartite.node_redundancy(G)
60 >>> sum(rc.values()) / len(G)
61 1.0
63 Compute the average redundancy for a set of nodes::
65 >>> from networkx.algorithms import bipartite
66 >>> G = nx.cycle_graph(4)
67 >>> rc = bipartite.node_redundancy(G)
68 >>> nodes = [0, 2]
69 >>> sum(rc[n] for n in nodes) / len(nodes)
70 1.0
72 Raises
73 ------
74 NetworkXError
75 If any of the nodes in the graph (or in `nodes`, if specified) has
76 (out-)degree less than two (which would result in division by zero,
77 according to the definition of the redundancy coefficient).
79 References
80 ----------
81 .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
82 Basic notions for the analysis of large two-mode networks.
83 Social Networks 30(1), 31--48.
85 """
86 if nodes is None:
87 nodes = G
88 if any(len(G[v]) < 2 for v in nodes):
89 raise NetworkXError(
90 "Cannot compute redundancy coefficient for a node"
91 " that has fewer than two neighbors."
92 )
93 # TODO This can be trivially parallelized.
94 return {v: _node_redundancy(G, v) for v in nodes}
97def _node_redundancy(G, v):
98 """Returns the redundancy of the node `v` in the bipartite graph `G`.
100 If `G` is a graph with `n` nodes, the redundancy of a node is the ratio
101 of the "overlap" of `v` to the maximum possible overlap of `v`
102 according to its degree. The overlap of `v` is the number of pairs of
103 neighbors that have mutual neighbors themselves, other than `v`.
105 `v` must have at least two neighbors in `G`.
107 """
108 n = len(G[v])
109 overlap = sum(
110 1 for (u, w) in combinations(G[v], 2) if (set(G[u]) & set(G[w])) - {v}
111 )
112 return (2 * overlap) / (n * (n - 1))