-
Notifications
You must be signed in to change notification settings - Fork 0
/
utils.py
53 lines (40 loc) · 1.51 KB
/
utils.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import random
import networkx as nx
def generate_bipartite_scale_free_graph(n1, n2, m):
"""Generate a scale-free bipartite graph using Albert-Barabasi algorithm.
Args:
n1: Number of nodes in partition A.
n2: Number of nodes in partition B.
m: Degree (m_0 in the original paper).
References:
A. L. Barabási and R. Albert “Emergence of scaling in random networks”,
Science 286, pp 509-512, 1999.
"""
if n1 < m or n2 < m:
raise Exception("Both n1 and n2 must be greater than m.")
graph = nx.complete_bipartite_graph(m, m)
repeated_A = []
repeated_B = []
for node, data in graph.nodes(data=True):
if data["bipartite"] == 0:
repeated_A.extend([node] * m)
else:
repeated_B.extend([node] * m)
new_nodes = set(range(2 * m, n1 + n2))
nodes_A = random.sample(new_nodes, n1 - m)
for source in new_nodes:
if source in nodes_A:
repeated_A.extend([source] * m)
targets = random.sample(repeated_B, m)
for target in targets:
repeated_B.append(target)
graph.add_edge(source, target)
graph.node[source]["bipartite"] = 0
else:
repeated_B.extend([source] * m)
targets = random.sample(repeated_A, m)
for target in targets:
repeated_A.append(target)
graph.add_edge(source, target)
graph.node[source]["bipartite"] = 1
return graph