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

1"""One-mode (unipartite) projections of bipartite graphs."""

2import networkx as nx

3from networkx.exception import NetworkXAlgorithmError

4from networkx.utils import not_implemented_for

6__all__ = [

7 "projected_graph",

8 "weighted_projected_graph",

9 "collaboration_weighted_projected_graph",

10 "overlap_weighted_projected_graph",

11 "generic_weighted_projected_graph",

12]

15@nx._dispatch(graphs="B", preserve_node_attrs=True, preserve_graph_attrs=True)

16def projected_graph(B, nodes, multigraph=False):

17 r"""Returns the projection of B onto one of its node sets.

19 Returns the graph G that is the projection of the bipartite graph B

20 onto the specified nodes. They retain their attributes and are connected

21 in G if they have a common neighbor in B.

23 Parameters

24 ----------

25 B : NetworkX graph

26 The input graph should be bipartite.

28 nodes : list or iterable

29 Nodes to project onto (the "bottom" nodes).

31 multigraph: bool (default=False)

32 If True return a multigraph where the multiple edges represent multiple

33 shared neighbors. They edge key in the multigraph is assigned to the

34 label of the neighbor.

36 Returns

37 -------

38 Graph : NetworkX graph or multigraph

39 A graph that is the projection onto the given nodes.

41 Examples

42 --------

43 >>> from networkx.algorithms import bipartite

44 >>> B = nx.path_graph(4)

45 >>> G = bipartite.projected_graph(B, [1, 3])

46 >>> list(G)

47 [1, 3]

48 >>> list(G.edges())

49 [(1, 3)]

51 If nodes `a`, and `b` are connected through both nodes 1 and 2 then

52 building a multigraph results in two edges in the projection onto

53 [`a`, `b`]:

55 >>> B = nx.Graph()

56 >>> B.add_edges_from([("a", 1), ("b", 1), ("a", 2), ("b", 2)])

57 >>> G = bipartite.projected_graph(B, ["a", "b"], multigraph=True)

58 >>> print([sorted((u, v)) for u, v in G.edges()])

59 [['a', 'b'], ['a', 'b']]

61 Notes

62 -----

63 No attempt is made to verify that the input graph B is bipartite.

64 Returns a simple graph that is the projection of the bipartite graph B

65 onto the set of nodes given in list nodes. If multigraph=True then

66 a multigraph is returned with an edge for every shared neighbor.

68 Directed graphs are allowed as input. The output will also then

69 be a directed graph with edges if there is a directed path between

70 the nodes.

72 The graph and node properties are (shallow) copied to the projected graph.

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

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

77 See Also

78 --------

79 is_bipartite,

80 is_bipartite_node_set,

81 sets,

82 weighted_projected_graph,

83 collaboration_weighted_projected_graph,

84 overlap_weighted_projected_graph,

85 generic_weighted_projected_graph

86 """

87 if B.is_multigraph():

88 raise nx.NetworkXError("not defined for multigraphs")

89 if B.is_directed():

90 directed = True

91 if multigraph:

92 G = nx.MultiDiGraph()

93 else:

94 G = nx.DiGraph()

95 else:

96 directed = False

97 if multigraph:

98 G = nx.MultiGraph()

99 else:

100 G = nx.Graph()

101 G.graph.update(B.graph)

102 G.add_nodes_from((n, B.nodes[n]) for n in nodes)

103 for u in nodes:

104 nbrs2 = {v for nbr in B[u] for v in B[nbr] if v != u}

105 if multigraph:

106 for n in nbrs2:

107 if directed:

108 links = set(B[u]) & set(B.pred[n])

109 else:

110 links = set(B[u]) & set(B[n])

111 for l in links:

112 if not G.has_edge(u, n, l):

113 G.add_edge(u, n, key=l)

114 else:

115 G.add_edges_from((u, n) for n in nbrs2)

116 return G

117

118

119@not_implemented_for("multigraph")

120@nx._dispatch(graphs="B")

121def weighted_projected_graph(B, nodes, ratio=False):

122 r"""Returns a weighted projection of B onto one of its node sets.

123

124 The weighted projected graph is the projection of the bipartite

125 network B onto the specified nodes with weights representing the

126 number of shared neighbors or the ratio between actual shared

127 neighbors and possible shared neighbors if ``ratio is True`` [1]_.

128 The nodes retain their attributes and are connected in the resulting

129 graph if they have an edge to a common node in the original graph.

130

131 Parameters

132 ----------

133 B : NetworkX graph

134 The input graph should be bipartite.

135

136 nodes : list or iterable

137 Distinct nodes to project onto (the "bottom" nodes).

138

139 ratio: Bool (default=False)

140 If True, edge weight is the ratio between actual shared neighbors

141 and maximum possible shared neighbors (i.e., the size of the other

142 node set). If False, edges weight is the number of shared neighbors.

143

144 Returns

145 -------

146 Graph : NetworkX graph

147 A graph that is the projection onto the given nodes.

148

149 Examples

150 --------

151 >>> from networkx.algorithms import bipartite

152 >>> B = nx.path_graph(4)

153 >>> G = bipartite.weighted_projected_graph(B, [1, 3])

154 >>> list(G)

155 [1, 3]

156 >>> list(G.edges(data=True))

157 [(1, 3, {'weight': 1})]

158 >>> G = bipartite.weighted_projected_graph(B, [1, 3], ratio=True)

159 >>> list(G.edges(data=True))

160 [(1, 3, {'weight': 0.5})]

161

162 Notes

163 -----

164 No attempt is made to verify that the input graph B is bipartite, or that

165 the input nodes are distinct. However, if the length of the input nodes is

166 greater than or equal to the nodes in the graph B, an exception is raised.

167 If the nodes are not distinct but don't raise this error, the output weights

168 will be incorrect.

169 The graph and node properties are (shallow) copied to the projected graph.

170

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

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

173

174 See Also

175 --------

176 is_bipartite,

177 is_bipartite_node_set,

178 sets,

179 collaboration_weighted_projected_graph,

180 overlap_weighted_projected_graph,

181 generic_weighted_projected_graph

182 projected_graph

183

184 References

185 ----------

186 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation

187 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook

188 of Social Network Analysis. Sage Publications.

189 """

190 if B.is_directed():

191 pred = B.pred

192 G = nx.DiGraph()

193 else:

194 pred = B.adj

195 G = nx.Graph()

196 G.graph.update(B.graph)

197 G.add_nodes_from((n, B.nodes[n]) for n in nodes)

198 n_top = len(B) - len(nodes)

199

200 if n_top < 1:

201 raise NetworkXAlgorithmError(

202 f"the size of the nodes to project onto ({len(nodes)}) is >= the graph size ({len(B)}).\n"

203 "They are either not a valid bipartite partition or contain duplicates"

204 )

205

206 for u in nodes:

207 unbrs = set(B[u])

208 nbrs2 = {n for nbr in unbrs for n in B[nbr]} - {u}

209 for v in nbrs2:

210 vnbrs = set(pred[v])

211 common = unbrs & vnbrs

212 if not ratio:

213 weight = len(common)

214 else:

215 weight = len(common) / n_top

216 G.add_edge(u, v, weight=weight)

217 return G

218

219

220@not_implemented_for("multigraph")

221@nx._dispatch(graphs="B")

222def collaboration_weighted_projected_graph(B, nodes):

223 r"""Newman's weighted projection of B onto one of its node sets.

224

225 The collaboration weighted projection is the projection of the

226 bipartite network B onto the specified nodes with weights assigned

227 using Newman's collaboration model [1]_:

228

229 .. math::

230

231 w_{u, v} = \sum_k \frac{\delta_{u}^{k} \delta_{v}^{k}}{d_k - 1}

232

233 where `u` and `v` are nodes from the bottom bipartite node set,

234 and `k` is a node of the top node set.

235 The value `d_k` is the degree of node `k` in the bipartite

236 network and `\delta_{u}^{k}` is 1 if node `u` is

237 linked to node `k` in the original bipartite graph or 0 otherwise.

238

239 The nodes retain their attributes and are connected in the resulting

240 graph if have an edge to a common node in the original bipartite

241 graph.

242

243 Parameters

244 ----------

245 B : NetworkX graph

246 The input graph should be bipartite.

247

248 nodes : list or iterable

249 Nodes to project onto (the "bottom" nodes).

250

251 Returns

252 -------

253 Graph : NetworkX graph

254 A graph that is the projection onto the given nodes.

255

256 Examples

257 --------

258 >>> from networkx.algorithms import bipartite

259 >>> B = nx.path_graph(5)

260 >>> B.add_edge(1, 5)

261 >>> G = bipartite.collaboration_weighted_projected_graph(B, [0, 2, 4, 5])

262 >>> list(G)

263 [0, 2, 4, 5]

264 >>> for edge in sorted(G.edges(data=True)):

265 ... print(edge)

266 ...

267 (0, 2, {'weight': 0.5})

268 (0, 5, {'weight': 0.5})

269 (2, 4, {'weight': 1.0})

270 (2, 5, {'weight': 0.5})

271

272 Notes

273 -----

274 No attempt is made to verify that the input graph B is bipartite.

275 The graph and node properties are (shallow) copied to the projected graph.

276

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

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

279

280 See Also

281 --------

282 is_bipartite,

283 is_bipartite_node_set,

284 sets,

285 weighted_projected_graph,

286 overlap_weighted_projected_graph,

287 generic_weighted_projected_graph,

288 projected_graph

289

290 References

291 ----------

292 .. [1] Scientific collaboration networks: II.

293 Shortest paths, weighted networks, and centrality,

294 M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).

295 """

296 if B.is_directed():

297 pred = B.pred

298 G = nx.DiGraph()

299 else:

300 pred = B.adj

301 G = nx.Graph()

302 G.graph.update(B.graph)

303 G.add_nodes_from((n, B.nodes[n]) for n in nodes)

304 for u in nodes:

305 unbrs = set(B[u])

306 nbrs2 = {n for nbr in unbrs for n in B[nbr] if n != u}

307 for v in nbrs2:

308 vnbrs = set(pred[v])

309 common_degree = (len(B[n]) for n in unbrs & vnbrs)

310 weight = sum(1.0 / (deg - 1) for deg in common_degree if deg > 1)

311 G.add_edge(u, v, weight=weight)

312 return G

313

314

315@not_implemented_for("multigraph")

316@nx._dispatch(graphs="B")

317def overlap_weighted_projected_graph(B, nodes, jaccard=True):

318 r"""Overlap weighted projection of B onto one of its node sets.

319

320 The overlap weighted projection is the projection of the bipartite

321 network B onto the specified nodes with weights representing

322 the Jaccard index between the neighborhoods of the two nodes in the

323 original bipartite network [1]_:

324

325 .. math::

326

327 w_{v, u} = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}

328

329 or if the parameter 'jaccard' is False, the fraction of common

330 neighbors by minimum of both nodes degree in the original

331 bipartite graph [1]_:

332

333 .. math::

334

335 w_{v, u} = \frac{|N(u) \cap N(v)|}{min(|N(u)|, |N(v)|)}

336

337 The nodes retain their attributes and are connected in the resulting

338 graph if have an edge to a common node in the original bipartite graph.

339

340 Parameters

341 ----------

342 B : NetworkX graph

343 The input graph should be bipartite.

344

345 nodes : list or iterable

346 Nodes to project onto (the "bottom" nodes).

347

348 jaccard: Bool (default=True)

349

350 Returns

351 -------

352 Graph : NetworkX graph

353 A graph that is the projection onto the given nodes.

354

355 Examples

356 --------

357 >>> from networkx.algorithms import bipartite

358 >>> B = nx.path_graph(5)

359 >>> nodes = [0, 2, 4]

360 >>> G = bipartite.overlap_weighted_projected_graph(B, nodes)

361 >>> list(G)

362 [0, 2, 4]

363 >>> list(G.edges(data=True))

364 [(0, 2, {'weight': 0.5}), (2, 4, {'weight': 0.5})]

365 >>> G = bipartite.overlap_weighted_projected_graph(B, nodes, jaccard=False)

366 >>> list(G.edges(data=True))

367 [(0, 2, {'weight': 1.0}), (2, 4, {'weight': 1.0})]

368

369 Notes

370 -----

371 No attempt is made to verify that the input graph B is bipartite.

372 The graph and node properties are (shallow) copied to the projected graph.

373

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

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

376

377 See Also

378 --------

379 is_bipartite,

380 is_bipartite_node_set,

381 sets,

382 weighted_projected_graph,

383 collaboration_weighted_projected_graph,

384 generic_weighted_projected_graph,

385 projected_graph

386

387 References

388 ----------

389 .. [1] Borgatti, S.P. and Halgin, D. In press. Analyzing Affiliation

390 Networks. In Carrington, P. and Scott, J. (eds) The Sage Handbook

391 of Social Network Analysis. Sage Publications.

392

393 """

394 if B.is_directed():

395 pred = B.pred

396 G = nx.DiGraph()

397 else:

398 pred = B.adj

399 G = nx.Graph()

400 G.graph.update(B.graph)

401 G.add_nodes_from((n, B.nodes[n]) for n in nodes)

402 for u in nodes:

403 unbrs = set(B[u])

404 nbrs2 = {n for nbr in unbrs for n in B[nbr]} - {u}

405 for v in nbrs2:

406 vnbrs = set(pred[v])

407 if jaccard:

408 wt = len(unbrs & vnbrs) / len(unbrs | vnbrs)

409 else:

410 wt = len(unbrs & vnbrs) / min(len(unbrs), len(vnbrs))

411 G.add_edge(u, v, weight=wt)

412 return G

413

414

415@not_implemented_for("multigraph")

416@nx._dispatch(graphs="B", preserve_all_attrs=True)

417def generic_weighted_projected_graph(B, nodes, weight_function=None):

418 r"""Weighted projection of B with a user-specified weight function.

419

420 The bipartite network B is projected on to the specified nodes

421 with weights computed by a user-specified function. This function

422 must accept as a parameter the neighborhood sets of two nodes and

423 return an integer or a float.

424

425 The nodes retain their attributes and are connected in the resulting graph

426 if they have an edge to a common node in the original graph.

427

428 Parameters

429 ----------

430 B : NetworkX graph

431 The input graph should be bipartite.

432

433 nodes : list or iterable

434 Nodes to project onto (the "bottom" nodes).

435

436 weight_function : function

437 This function must accept as parameters the same input graph

438 that this function, and two nodes; and return an integer or a float.

439 The default function computes the number of shared neighbors.

440

441 Returns

442 -------

443 Graph : NetworkX graph

444 A graph that is the projection onto the given nodes.

445

446 Examples

447 --------

448 >>> from networkx.algorithms import bipartite

449 >>> # Define some custom weight functions

450 >>> def jaccard(G, u, v):

451 ... unbrs = set(G[u])

452 ... vnbrs = set(G[v])

453 ... return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)

454 ...

455 >>> def my_weight(G, u, v, weight="weight"):

456 ... w = 0

457 ... for nbr in set(G[u]) & set(G[v]):

458 ... w += G[u][nbr].get(weight, 1) + G[v][nbr].get(weight, 1)

459 ... return w

460 ...

461 >>> # A complete bipartite graph with 4 nodes and 4 edges

462 >>> B = nx.complete_bipartite_graph(2, 2)

463 >>> # Add some arbitrary weight to the edges

464 >>> for i, (u, v) in enumerate(B.edges()):

465 ... B.edges[u, v]["weight"] = i + 1

466 ...

467 >>> for edge in B.edges(data=True):

468 ... print(edge)

469 ...

470 (0, 2, {'weight': 1})

471 (0, 3, {'weight': 2})

472 (1, 2, {'weight': 3})

473 (1, 3, {'weight': 4})

474 >>> # By default, the weight is the number of shared neighbors

475 >>> G = bipartite.generic_weighted_projected_graph(B, [0, 1])

476 >>> print(list(G.edges(data=True)))

477 [(0, 1, {'weight': 2})]

478 >>> # To specify a custom weight function use the weight_function parameter

479 >>> G = bipartite.generic_weighted_projected_graph(

480 ... B, [0, 1], weight_function=jaccard

481 ... )

482 >>> print(list(G.edges(data=True)))

483 [(0, 1, {'weight': 1.0})]

484 >>> G = bipartite.generic_weighted_projected_graph(

485 ... B, [0, 1], weight_function=my_weight

486 ... )

487 >>> print(list(G.edges(data=True)))

488 [(0, 1, {'weight': 10})]

489

490 Notes

491 -----

492 No attempt is made to verify that the input graph B is bipartite.

493 The graph and node properties are (shallow) copied to the projected graph.

494

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

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

497

498 See Also

499 --------

500 is_bipartite,

501 is_bipartite_node_set,

502 sets,

503 weighted_projected_graph,

504 collaboration_weighted_projected_graph,

505 overlap_weighted_projected_graph,

506 projected_graph

507

508 """

509 if B.is_directed():

510 pred = B.pred

511 G = nx.DiGraph()

512 else:

513 pred = B.adj

514 G = nx.Graph()

515 if weight_function is None:

516

517 def weight_function(G, u, v):

518 # Notice that we use set(pred[v]) for handling the directed case.

519 return len(set(G[u]) & set(pred[v]))

520

521 G.graph.update(B.graph)

522 G.add_nodes_from((n, B.nodes[n]) for n in nodes)

523 for u in nodes:

524 nbrs2 = {n for nbr in set(B[u]) for n in B[nbr]} - {u}

525 for v in nbrs2:

526 weight = weight_function(B, u, v)

527 G.add_edge(u, v, weight=weight)

528 return G