File size: 3,200 Bytes
2795186 |
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
"""
Generate scale-free graph and output degree-distribution CSV file
"""
import numpy as np
import networkx as nx
from collections import Counter
import csv
import sys
def kronecker_generator(scale, edge_factor):
"""Kronecker graph generator
Ported from octave code in https://graph500.org/?page_id=12#alg:generator
"""
N = 2 ** scale # Number of vertices
M = N * edge_factor # Number of edges
A, B, C = (0.57, 0.19, 0.19) # Initiator probabilities
ijw = np.ones((3, M)) # Index arrays
ab = A + B
c_norm = C / (1 - (A + B))
a_norm = A / (A + B)
for ib in range(scale):
ii_bit = (np.random.rand(1, M) > ab).astype(int)
ac = c_norm * ii_bit + a_norm * (1 - ii_bit)
jj_bit = (np.random.rand(1, M) > ac).astype(int)
ijw[:2, :] = ijw[:2, :] + 2 ** ib * np.vstack((ii_bit, jj_bit))
ijw[2, :] = np.random.rand(1, M)
ijw[:2, :] = ijw[:2, :] - 1
q = range(M)
np.random.shuffle(q)
ijw = ijw[:, q]
edges = ijw[:2, :].astype(int).T
_g = nx.DiGraph()
_g.add_edges_from(edges)
return _g
def kronecker_generator_general(_n, _m):
# TODO: Accept general number of nodes and edges
A, B, C = (0.57, 0.19, 0.19) # Initiator probabilities
ijw = np.ones((3, _m)) # Index arrays
ab = A + B
c_norm = C / (1 - (A + B))
a_norm = A / (A + B)
tmp = _n
while tmp > 0:
tmp //= 2
ii_bit = (np.random.rand(1, _m) > ab).astype(int)
ac = c_norm * ii_bit + a_norm * (1 - ii_bit)
jj_bit = (np.random.rand(1, _m) > ac).astype(int)
ijw[:2, :] = ijw[:2, :] + tmp * np.vstack((ii_bit, jj_bit))
ijw[2, :] = np.random.rand(1, _m)
ijw[:2, :] = ijw[:2, :] - 1
q = range(_m)
np.random.shuffle(q)
ijw = ijw[:, q]
edges = ijw[:2, :].astype(int).T
_g = nx.DiGraph()
_g.add_edges_from(edges)
return _g
def powerlaw_cluster_generator(_n, _edge_factor):
edges = nx.barabasi_albert_graph(_n, _edge_factor, seed=0).edges() # Undirected edges
# Swap the direction of half edges to diffuse degree
di_edges = [(edges[i][0], edges[i][1]) if i % 2 == 0 else (edges[i][1], edges[i][0]) for i in range(len(edges))]
_g = nx.DiGraph()
_g.add_edges_from(di_edges) # Create a directed graph
return _g
if __name__ == "__main__":
argv = sys.argv
if len(argv) < 4:
print("Usage: python3 %s [NumVertices] [EdgeFactor] [DegCSV]" % argv[0])
exit(1)
n = int(argv[1])
factor = int(argv[2])
g = powerlaw_cluster_generator(n, factor)
print("Number of vertices: %d" % g.number_of_nodes()) # Number of vertices (accounts)
print("Number of edges: %d" % g.number_of_edges()) # Number of edges (transactions)
in_deg = Counter(g.in_degree().values())
out_deg = Counter(g.out_degree().values())
keys = set(sorted(list(in_deg.keys()) + list(out_deg.keys())))
with open(argv[3], "w") as wf:
writer = csv.writer(wf)
writer.writerow(["Count", "In-degree", "Out-degree"])
for k in keys:
# Degree, number of vertices for in-degree, number of vertices for out-degree
writer.writerow([k, in_deg[k], out_deg[k]])
|