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

1"""Functions for computing clustering of pairs 

2 

3""" 

4 

5import itertools 

6 

7import networkx as nx 

8 

9__all__ = [ 

10 "clustering", 

11 "average_clustering", 

12 "latapy_clustering", 

13 "robins_alexander_clustering", 

14] 

15 

16 

17def cc_dot(nu, nv): 

18 return len(nu & nv) / len(nu | nv) 

19 

20 

21def cc_max(nu, nv): 

22 return len(nu & nv) / max(len(nu), len(nv)) 

23 

24 

25def cc_min(nu, nv): 

26 return len(nu & nv) / min(len(nu), len(nv)) 

27 

28 

29modes = {"dot": cc_dot, "min": cc_min, "max": cc_max} 

30 

31 

32@nx._dispatch 

33def latapy_clustering(G, nodes=None, mode="dot"): 

34 r"""Compute a bipartite clustering coefficient for nodes. 

35 

36 The bipartite clustering coefficient is a measure of local density 

37 of connections defined as [1]_: 

38 

39 .. math:: 

40 

41 c_u = \frac{\sum_{v \in N(N(u))} c_{uv} }{|N(N(u))|} 

42 

43 where `N(N(u))` are the second order neighbors of `u` in `G` excluding `u`, 

44 and `c_{uv}` is the pairwise clustering coefficient between nodes 

45 `u` and `v`. 

46 

47 The mode selects the function for `c_{uv}` which can be: 

48 

49 `dot`: 

50 

51 .. math:: 

52 

53 c_{uv}=\frac{|N(u)\cap N(v)|}{|N(u) \cup N(v)|} 

54 

55 `min`: 

56 

57 .. math:: 

58 

59 c_{uv}=\frac{|N(u)\cap N(v)|}{min(|N(u)|,|N(v)|)} 

60 

61 `max`: 

62 

63 .. math:: 

64 

65 c_{uv}=\frac{|N(u)\cap N(v)|}{max(|N(u)|,|N(v)|)} 

66 

67 

68 Parameters 

69 ---------- 

70 G : graph 

71 A bipartite graph 

72 

73 nodes : list or iterable (optional) 

74 Compute bipartite clustering for these nodes. The default 

75 is all nodes in G. 

76 

77 mode : string 

78 The pairwise bipartite clustering method to be used in the computation. 

79 It must be "dot", "max", or "min". 

80 

81 Returns 

82 ------- 

83 clustering : dictionary 

84 A dictionary keyed by node with the clustering coefficient value. 

85 

86 

87 Examples 

88 -------- 

89 >>> from networkx.algorithms import bipartite 

90 >>> G = nx.path_graph(4) # path graphs are bipartite 

91 >>> c = bipartite.clustering(G) 

92 >>> c[0] 

93 0.5 

94 >>> c = bipartite.clustering(G, mode="min") 

95 >>> c[0] 

96 1.0 

97 

98 See Also 

99 -------- 

100 robins_alexander_clustering 

101 average_clustering 

102 networkx.algorithms.cluster.square_clustering 

103 

104 References 

105 ---------- 

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

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

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

109 """ 

110 if not nx.algorithms.bipartite.is_bipartite(G): 

111 raise nx.NetworkXError("Graph is not bipartite") 

112 

113 try: 

114 cc_func = modes[mode] 

115 except KeyError as err: 

116 raise nx.NetworkXError( 

117 "Mode for bipartite clustering must be: dot, min or max" 

118 ) from err 

119 

120 if nodes is None: 

121 nodes = G 

122 ccs = {} 

123 for v in nodes: 

124 cc = 0.0 

125 nbrs2 = {u for nbr in G[v] for u in G[nbr]} - {v} 

126 for u in nbrs2: 

127 cc += cc_func(set(G[u]), set(G[v])) 

128 if cc > 0.0: # len(nbrs2)>0 

129 cc /= len(nbrs2) 

130 ccs[v] = cc 

131 return ccs 

132 

133 

134clustering = latapy_clustering 

135 

136 

137@nx._dispatch(name="bipartite_average_clustering") 

138def average_clustering(G, nodes=None, mode="dot"): 

139 r"""Compute the average bipartite clustering coefficient. 

140 

141 A clustering coefficient for the whole graph is the average, 

142 

143 .. math:: 

144 

145 C = \frac{1}{n}\sum_{v \in G} c_v, 

146 

147 where `n` is the number of nodes in `G`. 

148 

149 Similar measures for the two bipartite sets can be defined [1]_ 

150 

151 .. math:: 

152 

153 C_X = \frac{1}{|X|}\sum_{v \in X} c_v, 

154 

155 where `X` is a bipartite set of `G`. 

156 

157 Parameters 

158 ---------- 

159 G : graph 

160 a bipartite graph 

161 

162 nodes : list or iterable, optional 

163 A container of nodes to use in computing the average. 

164 The nodes should be either the entire graph (the default) or one of the 

165 bipartite sets. 

166 

167 mode : string 

168 The pairwise bipartite clustering method. 

169 It must be "dot", "max", or "min" 

170 

171 Returns 

172 ------- 

173 clustering : float 

174 The average bipartite clustering for the given set of nodes or the 

175 entire graph if no nodes are specified. 

176 

177 Examples 

178 -------- 

179 >>> from networkx.algorithms import bipartite 

180 >>> G = nx.star_graph(3) # star graphs are bipartite 

181 >>> bipartite.average_clustering(G) 

182 0.75 

183 >>> X, Y = bipartite.sets(G) 

184 >>> bipartite.average_clustering(G, X) 

185 0.0 

186 >>> bipartite.average_clustering(G, Y) 

187 1.0 

188 

189 See Also 

190 -------- 

191 clustering 

192 

193 Notes 

194 ----- 

195 The container of nodes passed to this function must contain all of the nodes 

196 in one of the bipartite sets ("top" or "bottom") in order to compute 

197 the correct average bipartite clustering coefficients. 

198 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` 

199 for further details on how bipartite graphs are handled in NetworkX. 

200 

201 

202 References 

203 ---------- 

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

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

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

207 """ 

208 if nodes is None: 

209 nodes = G 

210 ccs = latapy_clustering(G, nodes=nodes, mode=mode) 

211 return sum(ccs[v] for v in nodes) / len(nodes) 

212 

213 

214@nx._dispatch 

215def robins_alexander_clustering(G): 

216 r"""Compute the bipartite clustering of G. 

217 

218 Robins and Alexander [1]_ defined bipartite clustering coefficient as 

219 four times the number of four cycles `C_4` divided by the number of 

220 three paths `L_3` in a bipartite graph: 

221 

222 .. math:: 

223 

224 CC_4 = \frac{4 * C_4}{L_3} 

225 

226 Parameters 

227 ---------- 

228 G : graph 

229 a bipartite graph 

230 

231 Returns 

232 ------- 

233 clustering : float 

234 The Robins and Alexander bipartite clustering for the input graph. 

235 

236 Examples 

237 -------- 

238 >>> from networkx.algorithms import bipartite 

239 >>> G = nx.davis_southern_women_graph() 

240 >>> print(round(bipartite.robins_alexander_clustering(G), 3)) 

241 0.468 

242 

243 See Also 

244 -------- 

245 latapy_clustering 

246 networkx.algorithms.cluster.square_clustering 

247 

248 References 

249 ---------- 

250 .. [1] Robins, G. and M. Alexander (2004). Small worlds among interlocking 

251 directors: Network structure and distance in bipartite graphs. 

252 Computational & Mathematical Organization Theory 10(1), 69–94. 

253 

254 """ 

255 if G.order() < 4 or G.size() < 3: 

256 return 0 

257 L_3 = _threepaths(G) 

258 if L_3 == 0: 

259 return 0 

260 C_4 = _four_cycles(G) 

261 return (4.0 * C_4) / L_3 

262 

263 

264def _four_cycles(G): 

265 cycles = 0 

266 for v in G: 

267 for u, w in itertools.combinations(G[v], 2): 

268 cycles += len((set(G[u]) & set(G[w])) - {v}) 

269 return cycles / 4 

270 

271 

272def _threepaths(G): 

273 paths = 0 

274 for v in G: 

275 for u in G[v]: 

276 for w in set(G[u]) - {v}: 

277 paths += len(set(G[w]) - {v, u}) 

278 # Divide by two because we count each three path twice 

279 # one for each possible starting point 

280 return paths / 2