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

Question

TL;DR:生成静态网络列表比将这些静态网络合并为单个动态网络要快十倍。为什么会这样？

正在关注 this answer ，我尝试使用 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 source code并尝试找出 add_interactions_from 方法有什么问题。

这个函数简短而简单，但我很好奇为什么它需要这么多时间和内存，以及我如何改进它。你有什么想法？

---

这是 source code :

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)

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

Answer 1

只是一些注意事项:

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

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

• dynetx 是在扩展 networkx 的基础上构建的，它不是特别可扩展(在内存消耗和执行时间方面):在处理密集的、高度边缘属性的图形时，这种限制比以往任何时候都更加明显；

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

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

正如我之前所说:真实网络比您模拟的网络稀疏。此外，(社交)互动通常以“爆发”的形式发生。这两个数据特征通常可以减轻库的局限性。

无论如何，我们欢迎对库的每一个贡献:如果有人愿意致力于它的可扩展性，他将得到我们的全力支持!