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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Node redundancy for bipartite graphs."""
2 from itertools import combinations
3
4 from networkx import NetworkXError
5
6 __all__ = ["node_redundancy"]
7
8
9 def node_redundancy(G, nodes=None):
10 r"""Computes the node redundancy coefficients for the nodes in the bipartite
11 graph G.
12
13 The redundancy coefficient of a node v is the fraction of pairs of
14 neighbors of v that are both linked to other nodes. In a one-mode
15 projection these nodes would be linked together even if v were
16 not there.
17
18 More formally, for any vertex v, the *redundancy coefficient of v* is
19 defined by
20
21 .. math::
22
23 rc(v) = \frac{|\{\{u, w\} \subseteq N(v),
24 \: \exists v' \neq v,\: (v',u) \in E\:
25 \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}},
26
27 where N(v) is the set of neighbors of v in G.
28
29 Parameters
30 ----------
31 G : graph
32 A bipartite graph
33
34 nodes : list or iterable (optional)
35 Compute redundancy for these nodes. The default is all nodes in G.
36
37 Returns
38 -------
39 redundancy : dictionary
40 A dictionary keyed by node with the node redundancy value.
41
42 Examples
43 --------
44 Compute the redundancy coefficient of each node in a graph::
45
46 >>> from networkx.algorithms import bipartite
47 >>> G = nx.cycle_graph(4)
48 >>> rc = bipartite.node_redundancy(G)
49 >>> rc[0]
50 1.0
51
52 Compute the average redundancy for the graph::
53
54 >>> from networkx.algorithms import bipartite
55 >>> G = nx.cycle_graph(4)
56 >>> rc = bipartite.node_redundancy(G)
57 >>> sum(rc.values()) / len(G)
58 1.0
59
60 Compute the average redundancy for a set of nodes::
61
62 >>> from networkx.algorithms import bipartite
63 >>> G = nx.cycle_graph(4)
64 >>> rc = bipartite.node_redundancy(G)
65 >>> nodes = [0, 2]
66 >>> sum(rc[n] for n in nodes) / len(nodes)
67 1.0
68
69 Raises
70 ------
71 NetworkXError
72 If any of the nodes in the graph (or in nodes, if specified) has
73 (out-)degree less than two (which would result in division by zero,
74 according to the definition of the redundancy coefficient).
75
76 References
77 ----------
78 .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
79 Basic notions for the analysis of large two-mode networks.
80 Social Networks 30(1), 31--48.
81
82 """
83 if nodes is None:
84 nodes = G
85 if any(len(G[v]) < 2 for v in nodes):
86 raise NetworkXError(
87 "Cannot compute redundancy coefficient for a node"
88 " that has fewer than two neighbors."
89 )
90 # TODO This can be trivially parallelized.
91 return {v: _node_redundancy(G, v) for v in nodes}
92
93
94 def _node_redundancy(G, v):
95 """Returns the redundancy of the node v in the bipartite graph G.
96
97 If G is a graph with n nodes, the redundancy of a node is the ratio
98 of the "overlap" of v to the maximum possible overlap of v
99 according to its degree. The overlap of v is the number of pairs of
100 neighbors that have mutual neighbors themselves, other than v.
101
102 v must have at least two neighbors in G.
103
104 """
105 n = len(G[v])
106 # TODO On Python 3, we could just use G[u].keys() & G[w].keys() instead
107 # of instantiating the entire sets.
108 overlap = sum(
109 1 for (u, w) in combinations(G[v], 2) if (set(G[u]) & set(G[w])) - {v}
110 )
111 return (2 * overlap) / (n * (n - 1))