Я пытаюсь создать крупномасштабные графики без использования пакета networkx в Python 3.
Это мои версии программного обеспечения:
python --version
Python 3.7.3
pip --version
pip 19.0.3 from /home/user/bin/python3/lib/python3.7/site-packages/pip (python 3.7)
pip show networkx
Name: networkx
Version: 2.3
Summary: Python package for creating and manipulating graphs and networks
В частности, мне нужно создать безмасштабные графы с количеством вершин 100K, 1M и 10M соответственно.
Мой код очень лаконичен:
n = 1000000 # 100K, then 1M, then 10M...
G = nx.scale_free_graph(n)
file_stamp = str(datetime.datetime.now()).split('.')[0].replace(' ', '_').replace(':', '-')
target_file_name = str(args.n) + "V_" + str(G.number_of_edges()) + "E_" + file_stamp + ".tsv"
target_file_path = os.path.join(args.out_dir, target_file_name)
print("> Target edge file:\t\t{}".format(target_file_path))
with open(target_file_path, 'wb') as f:
nx.write_edgelist(G, f, data = False)
Для n = 100000 (сто тысяч) выполнение заняло несколько секунд.
Однако для n = 1000000 (один миллион) или n = 10000000 (десять миллионов) скрипт работает уже несколько дней.
Я заметил, что использование памяти очень медленно растет.
Я ожидаю, что эти графики будут занимать больше памяти, чем то, что в настоящее время удерживают процессы, что намекает на то, что виновником является логика генератора.
Из-за прошедшего времени я начал думать, что процесс генерации просто медленный.
Я пошел проверить источник функции networkx.scale_free_graph :
@py_random_state(7)
def scale_free_graph(n, alpha=0.41, beta=0.54, gamma=0.05, delta_in=0.2,
delta_out=0, create_using=None, seed=None):
"""Returns a scale-free directed graph.
Parameters
----------
n : integer
Number of nodes in graph
alpha : float
Probability for adding a new node connected to an existing node
chosen randomly according to the in-degree distribution.
beta : float
Probability for adding an edge between two existing nodes.
One existing node is chosen randomly according the in-degree
distribution and the other chosen randomly according to the out-degree
distribution.
gamma : float
Probability for adding a new node connected to an existing node
chosen randomly according to the out-degree distribution.
delta_in : float
Bias for choosing nodes from in-degree distribution.
delta_out : float
Bias for choosing nodes from out-degree distribution.
create_using : NetworkX graph constructor, optional
The default is a MultiDiGraph 3-cycle.
If a graph instance, use it without clearing first.
If a graph constructor, call it to construct an empty graph.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:`Randomness<randomness>`.
Examples
--------
Create a scale-free graph on one hundred nodes::
>>> G = nx.scale_free_graph(100)
Notes
-----
The sum of `alpha`, `beta`, and `gamma` must be 1.
References
----------
.. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,
Directed scale-free graphs,
Proceedings of the fourteenth annual ACM-SIAM Symposium on
Discrete Algorithms, 132--139, 2003. """
def _choose_node(G, distribution, delta, psum):
cumsum = 0.0
# normalization
r = seed.random()
for n, d in distribution:
cumsum += (d + delta) / psum
if r < cumsum:
break
return n
if create_using is None or not hasattr(create_using, '_adj'):
# start with 3-cycle
G = nx.empty_graph(3, create_using, default=nx.MultiDiGraph)
G.add_edges_from([(0, 1), (1, 2), (2, 0)])
else:
G = create_using
if not (G.is_directed() and G.is_multigraph()):
raise nx.NetworkXError("MultiDiGraph required in create_using")
if alpha <= 0:
raise ValueError('alpha must be > 0.')
if beta <= 0:
raise ValueError('beta must be > 0.')
if gamma <= 0:
raise ValueError('gamma must be > 0.')
if abs(alpha + beta + gamma - 1.0) >= 1e-9:
raise ValueError('alpha+beta+gamma must equal 1.')
number_of_edges = G.number_of_edges()
while len(G) < n:
psum_in = number_of_edges + delta_in * len(G)
psum_out = number_of_edges + delta_out * len(G)
r = seed.random()
# random choice in alpha,beta,gamma ranges
if r < alpha:
# alpha
# add new node v
v = len(G)
# choose w according to in-degree and delta_in
w = _choose_node(G, G.in_degree(), delta_in, psum_in)
elif r < alpha + beta:
# beta
# choose v according to out-degree and delta_out
v = _choose_node(G, G.out_degree(), delta_out, psum_out)
# choose w according to in-degree and delta_in
w = _choose_node(G, G.in_degree(), delta_in, psum_in)
else:
# gamma
# choose v according to out-degree and delta_out
v = _choose_node(G, G.out_degree(), delta_out, psum_out)
# add new node w
w = len(G)
G.add_edge(v, w)
number_of_edges += 1
return G
Основной цикл этого кода будет повторять количество раз, равное количеству вершин n.
Не вдаваясь в дальнейший анализ, внутри основного цикла, _choose_node вызывается как минимум один раз и максимум два раза для каждой итерации.
Внутри этой функции существует другой цикл, повторяющийся в степени входа / выхода (распределения).
Я принимаю это по мере увеличения n, равно как и вычислительное время внутри _choose_node.
Есть ли более быстрое внедрение этого безмасштабного генератора в сети?
Или, может быть, функция в другой библиотеке (без языковых ограничений), которая генерирует безмасштабные графы с той же семантикой, что и эта?