问题标签 [complex-networks]

PS：我已经提到了我的问题的可能解决方案，但对它们有很多困惑，请给我一些建议。另外，如果这个问题不适合这个网站，请指点我到正确的网站，我会把问题移到那里。提前致谢。

对于一些研究工作，我需要执行一些重复的图论和复杂的网络算法来分析大约 2000 个无自环的无向简单图。每个图有大约 40,000 个节点和大约 600,000 条边（基本上使它们成为稀疏图）。

目前，我正在使用 NetworkX 进行分析，目前正在运行nx.algorithms.cluster.average_clustering(G)500nx.average_shortest_path_length(G)个这样的图表，代码运行了 3 天，并且只运行了一半。这让我担心我的全面分析会花费大量的出乎意料的时间。

在详细说明我的问题和我想到的可能的解决方案之前，让我提一下我的计算机配置，因为它可能会帮助您建议最佳方法。我在配备 32GB RAM 和一个 Zotac GeForce GTX 1050 Ti OC 版 ZT-P10510B-10L 4GB PCI Express 显卡的 Intel i7-9700K 处理器上运行 Windows 10。

解释我可能的解决方案以及我对它们的困惑：

A) 使用带有邻接矩阵的 GPU 作为图形数据结构：我可以在 GPU 上放置一个邻接矩阵，并通过使用循环手动使用PyCuda或Numba对它们进行编码来执行我的分析，因为递归无法由 GPU 处理。我能够搜索的最近的是stackoverflow上的this，但它没有很好的解决方案。

我的期望：我希望加速算法，例如所有对最短路径、两个节点之间的所有可能路径、平均聚类、平均最短路径长度和小世界属性等。如果它对每个图有显着的加速，我的结果可以是达到非常快。

我的困惑：

1. 这些图算法可以在 GPU 中高效编码吗？
2. 哪个会更好用？PyCuda 还是 Numba？
3. 有没有其他方法可以在 GPU 上存储图，因为我的图是稀疏图，所以效率更高。
4. 我是一名普通的 Python 程序员，没有 GPU 编程经验，所以我必须了解和学习使用 PyCuda/Numba 进行 GPU 编程。哪个更容易学？

B) 在 CPU 本身上并行化程序：我可以使用 Joblib 或任何其他库在我的 CPU 本身上并行运行程序。我可以再安排 2-3 台计算机，我可以在这些计算机上运行独立的小程序部分，或者每台计算机可以运行 500 个图形。

我的期望：我希望通过在计算机之间并行化和划分任务来加速算法。如果GPU解决方案不起作用，我可能通过这种方法仍然有一些希望。

我的困惑：

1. 哪些其他库可作为 Joblib 的良好替代品？
2. 我应该为我的程序分配所有 CPU 内核（i7 中的 8 个内核）还是使用更少的内核？

C）除了我可能的解决方案之外，您对我还有其他建议吗？如果除了 C/C++ 之外的任何其他语言都有更好更快的解决方案，您也可以建议它们，因为如果没有任何效果，我已经考虑将 C++ 作为后备计划。

正在进行的更新

1. 在我社区中对此问题的评论和讨论的不同建议中，这些是我建议探索的要点。

   • GraphBLAS
   • boost.graph + 带有 python-wrappers 的扩展
   • 图形工具
   • 火花/黄昏
   • PyCuda/Numba
   • 使用 Pytorch 的线性代数方法

2. 我尝试n_job=-1使用 Joblib 在我的 CPU 上运行 100 个图表（使用 ），CPU 持续达到 100°C 的温度。处理器运行 3 小时后跳闸。- 作为一种解决方案，我在多台计算机上使用了 75% 的可用内核（因此，如果可用内核为 8，我使用 6 个内核）并且程序运行良好。加速也不错。

我有一个具有以下属性的无向图，我需要对完全随机图和具有相同属性的常规图进行一些分析。

属性：

为了研究随机图的属性，我使用networkx.gnm_random_graph(37764,518151)并执行了我的分析来创建它们。但是我对如何使用相同的属性生成规则图感到非常困惑。

我在这里找到了两种使用networkx.random_regular_graph(k, n)（文档）和igraph.Graph().K_Regular(n, k)（文档）生成常规图形的方法，但注意到它们需要度数k是整数值。

但在我的原始图表中，该值是一个浮点值27.44153161741341。现在我无法理解如何为我的分析创建一个常规图（或许多图以在平均时给出相同的上述属性）。

改写我的问题：在我的情况下，如何处理平均学位的小数部分？

语言/库不受解决方案的限制。

我使用 MATLAB 模拟了两个相互依赖的网络/层的级联故障（我基于小世界 - watts strogatz 算法生成了两个层）。

我的代码运行良好，但与时间无关。 我想要有时间步骤，例如，对一个节点的初始攻击发生在 t1，然后在一段时间后，下一个易受攻击的节点在不同的时间 t2 失败，以此类推其他失败事件。我的代码只模拟电信节点（所有事件都是瞬间发生的），我希望它适用于其他物流网络，例如社交网络，其中每个事件的时间戳可能以分钟或小时为单位。您的想法和想法将不胜感激。

注意：如果有帮助，我可以提供我的代码。

有人能帮忙吗。我正在获取一个网络并将其绘制为如下图：

nx.info(g) 给我的节点数是 18772。

我得到了它的图表如下：

然而，在删除 30% 的最重要节点后，如下所示：

它提供了有关新图表的正确信息，但图表非常糟糕，似乎节点是添加而不是删除！

最近我开始了解skggm，它利用概率方法来预测边缘。我想知道NetworkX中是否有等效的东西。这样做的原因是因为我在使用/理解 skggm 时遇到了麻烦。

我的目标是为时间序列数据创建复杂的网络（每一秒的矩阵）。我目前将图像转换为矩阵（每个像素的强度），然后创建相应的相邻矩阵并使用阈值（由我选择）将每个像素转换为 0 或 1。之后，可以使用NetworkX创建图形. 但是，我想通过使用类似skggm的东西来绕过它，它可以自动选择边和节点，而不必选择阈值。

如果您有任何想法或想到任何可以帮助我的事情，请告诉我。

谢谢

我有一个程序，每次目标数据源（动态网络）发生变化时，都会使用 Networkx 生成有向图。我通过将交互组合在一起并分析新添加或删除的边来利用这些图表。但我还想提取另一个信息：

说，对于 t = 0，我有一个指向另一个节点的节点：

N1 -> N2

对于 t = 1，在 N2 和 N3 之间出现一条新边：

N1 -> N2 -> N3

对于 t = 2，在 N2 和 N3 之间出现一个新节点：

N1 -> N2 -> N4 -> N3

等等。我不知道给 N1 命名的正确方法，但也许是种子？因为我想获得像 N1 这样的节点，它们的影响范围越来越广，比如疾病传播。但我只想能够返回这些节点，而不是模拟传播。如果这个节点在每个 t 时刻都可以访问越来越多的节点，我可以称这个节点为什么，我可以使用什么算法来检测它？我认为也许可以衡量一个不断增长的中介中心性，但是如果有一个现有的算法，我宁愿依靠别人的洞察力，而不是我的菜鸟直觉。

我认为 Networkx 不支持很多时间图算法，但我见过支持的库；pathpy，DyNetx。

我将不胜感激，提前谢谢你。

我想要解决一个复杂的网络系统，该系统涉及通过多维数组起作用的高阶交互项。我已经编写了相应的代码，但是获得结果需要花费太多时间。有什么方法可以更快地求解微分方程吗？代码如下：

#= 我发现的问题是在我的代码中计算广义订单参数需要太多时间。我是朱莉娅的新手。谁能向我建议一种更快的方法来计算该术语/以某种方式使代码更快，以便我可以在更短的时间内解决问题？=#

如何将 2 个节点作为质心传递给 sklearn.kmeans(n_clusters,init,....) 而不是随机或 kmeans++？算法['kmeans'] = KMeans(n_clusters=k_clusters,init='random', n_init=200)

图形工具中是否有一种方法可以检查两个节点是否连接（作为第一邻居）而无需迭代？

例如，类似graph_tool.is_connected(v,u)which 根据是否连接的顶点v返回一个布尔值。u类似于检查某个边缘是否存在的函数。

谢谢

我有 4 个函数用于复杂网络分析中的一些统计计算。

图的度数分布：

图的社区检测：

图的模块化分数：

最后是图熵：

问题

我现在想要实现的是找到每个社区的局部熵（变成一个子图），并保留边缘信息。

这可能吗？怎么会这样？

编辑

正在使用的矩阵在此链接中：

数据集

然后将邻接矩阵变成一个图，“图”或“G”，如下所示：

编辑 2

根据下面提出的答案，我创建了另一个函数：

和：

但它会抛出错误：

类型错误：subgraph() 缺少 1 个必需的位置参数：'nodes'