Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/redundancy.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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)) |