1

This is related to this question, with a small difference. Namely, I am already given a graph G, which is a bi-partite graph, meaning that there exist two sets of vertices, set U and set I, and the connection could only exist between a node from the set U and a node from the set I.

I want to extend this unconnected graph by making it connected and still bi-partite, and I also want that the probability of a new edge (when extending the graph with edges) is proportional to the nodes degrees (i.e., higher probability that an edge links two nodes of large degrees). The code that I would like to extend:

import random
from itertools import combinations, groupby

components = dict(enumerate(nx.connected_components(G)))
components_combs = combinations(components.keys(), r=2)

for _, node_edges in groupby(components_combs, key=lambda x: x[0]):
    node_edges = list(node_edges)
    random_comps = random.choice(node_edges)
    source = random.choice(list(components[random_comps[0]]))
    target = random.choice(list(components[random_comps[1]]))
    G.add_edge(source, target)
kevin_was_here
  • 77
  • 7
  • @yatu Maybe you could help... – kevin_was_here May 04 '22 at 13:28
  • Hi! Could you please add a definition for a small example graph G at the top of your code? – Stef May 04 '22 at 14:17
  • 1
    The code you've found is already pretty good. The only thing you need to change is the way `source` and `target` are chosen. Instead of choosing `source` among all vertices from the source component, choose it only from the vertices that are both from the source component and set U. Then instead of choosing `target` among all vertices from the target component, choose it only from the vertices that are both from the target component and set I. – Stef May 04 '22 at 14:22
  • @Stef Thanks. How about incorporating probabilities of new links that are dependent on node degrees? – kevin_was_here May 04 '22 at 15:32
  • 1
    Then instead of `random.choice`, use `random.choices`, with the node degrees as the optional weights parameter. See https://docs.python.org/3/library/random.html#functions-for-sequences – Stef May 04 '22 at 15:34
  • @Stef Thanks! You may (if you want) write the above as your answer and I will accept it. – kevin_was_here May 04 '22 at 20:02

0 Answers0