如何在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源代码，试图弄清楚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实现。

- Yanirmr

---

据我所知，networkx不是一个非常高效的包。我认为它是为非常小的图设计的。您可能会对像neo4j或snap这样的替代包感兴趣。 - Jérôme Richard

Answer 1

仅供参考：

• 在DynGraph中，创建快照列表而不进行合并阶段比合并它们要少得多，这是完全正常的：这主要是因为需要压缩复制边缘的时间信息作为边缘属性；

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

• dynetx是通过扩展networkx构建的，后者在内存消耗和执行时间方面都不特别可扩展：当处理密集的、具有重要边缘属性的图形时，这种限制更加明显；

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

实际上，DyNetx并不适用于处理特别大的图形，但是我们利用它来分析基于在线社交网络数据构建的交互网络，这些网络比报告的示例大几个数量级（以节点为单位）。

如我之前所说：真实网络比您模拟的网络更稀疏。此外，（社交）交互通常会在“突发”中发生。这两个数据特征经常缓解库限制。

无论如何，我们欢迎对该库的每一项贡献：如果任何人想要改善其可扩展性，他将得到我们所有的支持！

- Giulio Rossetti