## Mercurial > repos > shellac > sam_consensus_v3

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

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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)) |