如何在Python中高效地创建随机动态图

Question

TL；DR：生成静态网络列表的速度是将这些静态网络合并为单个动态网络的速度的十倍。为什么会这样

根据这个答案，我尝试使用NetworkX和DyNetx生成一个随机动态图。

当处理中等规模的网络(大约1000个节点和1000个时间戳(时，就会出现内存崩溃的问题。同样，在较小的规模上(大约100个节点和300个时间戳(，该过程极其缓慢。我相信我已经发现了障碍，但我不确定如何应对

以下是生成随机时间网络的代码的简单示例：

import dynetx as dnx
import networkx as nx
import itertools
from random import random
def dynamic_random_graph(n, steps, up_rate, seed=42):
# Create list of static graphs
list_of_snapshots = list()
for t in range(0, steps):
G_t = nx.Graph()
edges = itertools.combinations(range(n), 2)
G_t.add_nodes_from(range(n))
for e in edges:
if random() < up_rate:
G_t.add_edge(*e)
list_of_snapshots.append(G_t)
# Merge the static graphs into dynamic one
dynamic_graph = dnx.DynGraph()
for t, graph in enumerate(list_of_snapshots):
dynamic_graph.add_interactions_from(graph.edges(data=False), t=t)

return dynamic_graph

如果我们运行以下命令：

%timeit dynamic_random_graph(300, 100, 0.5) # Memory was crahsed on larger networks.
>> 1 loop, best of 5: 15.1 s per loop

相比之下，如果我们在没有网络合并的情况下运行代码，我们将获得明显更好的结果：

%timeit dynamic_random_graph_without_merge(300, 100, 0.5) # Ignore the merge part in the function
>> 1 loop, best of 5: 15.1 s per loop

如果我们在没有合并部分的情况下运行函数，我们可以在具有1000个节点的网络上工作而不会出现内存崩溃。

因此，我想查看DyNetx源代码，并尝试找出add_interactions_from方法的问题所在。

这个功能简短而简单，但我很好奇为什么它需要这么多时间和记忆，以及我如何改进它。你有什么想法

---

这是源代码：

def add_interactions_from(self, ebunch, t=None, e=None):
"""Add all the interaction in ebunch at time t.
Parameters
----------
ebunch : container of interaction
Each interaction given in the container will be added to the
graph. The interaction must be given as as 2-tuples (u,v) or
3-tuples (u,v,d) where d is a dictionary containing interaction
data.
t : appearance snapshot id, mandatory
e : vanishing snapshot id, optional
See Also
--------
add_edge : add a single interaction
Examples
--------
>>> import dynetx as dn
>>> G = dn.DynGraph()
>>> G.add_edges_from([(0,1),(1,2)], t=0)
"""
# set up attribute dict
if t is None:
raise nx.NetworkXError(
"The t argument must be a specified.")
# process ebunch
for ed in ebunch:
self.add_interaction(ed[0], ed[1], t, e)

我想最后的循环是所有问题的根源。链接到add_interaction实现。

Answer 1

只有几个注意事项：

• 在没有合并阶段的情况下创建快照列表比在DynGraph中合并它们成本更低是完全正常的：这主要是因为复制边缘的时间信息必须压缩为边缘的属性；

• 您生成的随机图是密集的(50%的边都存在，这在大多数真实环境中是不现实的(，这需要不断更新边的属性。通过减少边缘的数量，您将能够扩展到更大的网络。举个例子，考虑一下，对于您正在模拟的ER模型，p=1/N(其中N是图中的节点数(就足以保证超临界状态(即，单个连接组件(；

• dynetx是对networkx的扩展而构建的，它不是特别可扩展(无论是在内存消耗还是执行时间方面(：当处理密集的、高度边缘化的图形时，这种限制比以往任何时候都更加明显；

• 构建动态图的方式可能是最耗时的。您在每对节点之间添加交互，而不利用其有效持续时间的知识。如果交互(u，v(从t到t+k发生了k次，则可以只插入一次这样的边，指定其消失时间，从而减少图形操作。

事实上，DyNetx并不是为了处理特别大的图而设计的，然而，我们利用它来分析建立在在线社交网络数据之上的交互网络，这些数据比报道的例子大几个数量级(就节点而言(。

正如我之前所说：真实的网络比你模拟的网络更稀疏。此外，(社交(互动通常发生在"；突发"；。这两个数据特性通常会减轻库的限制。

无论如何，我们欢迎对该库的每一项贡献：如果有人想提高其可扩展性，我们将全力支持他！