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

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