使用Python生成连接/网络图

Question

我有一个文本文件，其中包含大约850万个数据点，格式如下：

Company 87178481
Company 893489
Company 2345788
[...]

我想使用Python创建一个连接图，以查看公司之间的网络关系。从上面的示例中，如果第二列中的值相同，则两个公司将共享一条边（来自/为 Hooked 的澄清）。

我一直在使用 NetworkX 包，并已能够为几千个点生成网络，但它无法通过完整的850万节点文本文件。我运行了它并离开了大约15个小时，当我回来时，shell中的光标仍在闪烁，但没有输出图。

可以假设它仍在运行吗？有更好/更快/更简单的方法来绘制数百万个点的图吗？

- Jon

---

这些公司是如何相连的？也就是说，如果第二列相同，公司A和B之间是否共享一条边？ - Hooked

我在networkx中使用850万个顶点没有遇到任何问题。你有多少个不同的顶点？你是使用有向还是无向图？另外，当你说“没有输出图”时，你具体指的是什么？[例如，你没有尝试打印它或其他操作吗？] - Jon Clements

我只是指我没有看到生成的图表...没有弹出新窗口显示绘制的图表。 - Jon

Answer 1

如果你有1000K数据点，你需要一种查看整体情况的方法。根据你所寻找的内容，如果你可以给公司之间分配一个“距离”（例如连接数），你可以通过Dendrogram可视化关系（或聚类）。

Scipy进行聚类：

http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html#module-scipy.cluster.hierarchy

并且它有一个将它们转换为树状图以进行可视化的功能：

http://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.dendrogram.html#scipy.cluster.hierarchy.dendrogram

通过networkx实现最短路径距离函数的示例：

http://networkx.lanl.gov/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html#networkx.algorithms.shortest_paths.generic.shortest_path

最终，您将需要决定如何权衡图中两个公司（顶点）之间的距离。

- Hooked

---

在 SAS 或 R 中，是否有更简单或更优选的方法来构建这个网络？ - Jon

@Jon 这个答案（即使提供了链接）是与编程语言无关的。你想用你的一百万点图表展示什么？一般联系、不同聚类、中心枢纽？不清楚你想从数据集中得到什么，因为可以问很多不同的问题。 - Hooked

有点含糊不清。我想看到聚类和聚类之间的连接点。这个想法是利用数据进行网络推广，以查看主聚类和较小聚类之间存在的单一连接的位置。然后可以利用这些单一的业务联系来实现更有针对性的营销目的等。 - Jon

@Jon 这是在图论中一个非常普遍的问题（而且这个领域有大量的研究！）但我会指出一些事情。networkx作为可视化是不相关的，对于这么多点，你需要一个算法的方法。我首先会通过某个阈值来聚类顶点（参见答案）。然后通过查看谱系图，我可以看到在稍微提高阈值时哪些集群被连接。这些新连接就是您的“奇异业务关系”。 - Hooked

我认为你已经帮助我确定了这个范围。谢谢，Hooked。 - Jon

Answer 2

您的数据点太多了，如果您将其可视化，它就没有任何意义。您需要有方法来：1）通过删除那些不太重要/不太相关的公司来减少公司数量；2）以某种方式对图进行总结，然后进行可视化。

为了减小数据规模，最好独立创建网络（使用自己的代码创建公司的边缘列表）。这样，您可以减小图形的大小（例如，通过删除单例，这可能很多）。

对于总结，我建议运行聚类或社区检测算法。即使是非常大的网络，也可以非常快地完成。在igraph软件包中使用“fastgreedy”方法：http://igraph.sourceforge.net/doc/R/fastgreedy.community.html （还有一种更快的算法在线上也可用，这是由Blondel等人提供的：http://perso.uclouvain.be/vincent.blondel/publications/08BG.pdf 我知道他们的代码在网上某个地方可用）

- Roja