Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/bipartite/redundancy.py: 47%

1"""Node redundancy for bipartite graphs.""" 

2from itertools import combinations 

3 

4import networkx as nx 

5from networkx import NetworkXError 

6 

7__all__ = ["node_redundancy"] 

8 

9 

10@nx._dispatch 

11def node_redundancy(G, nodes=None): 

12 r"""Computes the node redundancy coefficients for the nodes in the bipartite 

13 graph `G`. 

14 

15 The redundancy coefficient of a node `v` is the fraction of pairs of 

16 neighbors of `v` that are both linked to other nodes. In a one-mode 

17 projection these nodes would be linked together even if `v` were 

18 not there. 

19 

20 More formally, for any vertex `v`, the *redundancy coefficient of `v`* is 

21 defined by 

22 

23 .. math:: 

24 

25 rc(v) = \frac{|\{\{u, w\} \subseteq N(v), 

26 \: \exists v' \neq v,\: (v',u) \in E\: 

27 \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}}, 

28 

29 where `N(v)` is the set of neighbors of `v` in `G`. 

30 

31 Parameters 

32 ---------- 

33 G : graph 

34 A bipartite graph 

35 

36 nodes : list or iterable (optional) 

37 Compute redundancy for these nodes. The default is all nodes in G. 

38 

39 Returns 

40 ------- 

41 redundancy : dictionary 

42 A dictionary keyed by node with the node redundancy value. 

43 

44 Examples 

45 -------- 

46 Compute the redundancy coefficient of each node in a graph:: 

47 

48 >>> from networkx.algorithms import bipartite 

49 >>> G = nx.cycle_graph(4) 

50 >>> rc = bipartite.node_redundancy(G) 

51 >>> rc[0] 

52 1.0 

53 

54 Compute the average redundancy for the graph:: 

55 

56 >>> from networkx.algorithms import bipartite 

57 >>> G = nx.cycle_graph(4) 

58 >>> rc = bipartite.node_redundancy(G) 

59 >>> sum(rc.values()) / len(G) 

60 1.0 

61 

62 Compute the average redundancy for a set of nodes:: 

63 

64 >>> from networkx.algorithms import bipartite 

65 >>> G = nx.cycle_graph(4) 

66 >>> rc = bipartite.node_redundancy(G) 

67 >>> nodes = [0, 2] 

68 >>> sum(rc[n] for n in nodes) / len(nodes) 

69 1.0 

70 

71 Raises 

72 ------ 

73 NetworkXError 

74 If any of the nodes in the graph (or in `nodes`, if specified) has 

75 (out-)degree less than two (which would result in division by zero, 

76 according to the definition of the redundancy coefficient). 

77 

78 References 

79 ---------- 

80 .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008). 

81 Basic notions for the analysis of large two-mode networks. 

82 Social Networks 30(1), 31--48. 

83 

84 """ 

85 if nodes is None: 

86 nodes = G 

87 if any(len(G[v]) < 2 for v in nodes): 

88 raise NetworkXError( 

89 "Cannot compute redundancy coefficient for a node" 

90 " that has fewer than two neighbors." 

91 ) 

92 # TODO This can be trivially parallelized. 

93 return {v: _node_redundancy(G, v) for v in nodes} 

94 

95 

96def _node_redundancy(G, v): 

97 """Returns the redundancy of the node `v` in the bipartite graph `G`. 

98 

99 If `G` is a graph with `n` nodes, the redundancy of a node is the ratio 

100 of the "overlap" of `v` to the maximum possible overlap of `v` 

101 according to its degree. The overlap of `v` is the number of pairs of 

102 neighbors that have mutual neighbors themselves, other than `v`. 

103 

104 `v` must have at least two neighbors in `G`. 

105 

106 """ 

107 n = len(G[v]) 

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