con*_*lee 38 python graph social-networking libraries
我对拥有数百万个节点和数千万个边缘的大型网络进行网络分析感兴趣.我希望能够执行诸如从多种格式解析网络,查找连接组件,检测社区以及运行像PageRank这样的中心度量之类的事情.
我被NetworkX所吸引,因为它有一个很好的api,良好的文档,并且多年来一直在积极开发.另外,因为它是在python中,它应该快速开发.
在最近的一个演示文稿中(幻灯片可以在github上找到),它声称:
与许多其他工具不同,NX旨在处理与现代问题相关的规模数据...... NX中的大多数核心算法都依赖于极快的遗留代码.
该演示文稿还指出NetworkX的基本算法是在C/Fortran中实现的.
但是,看一下源代码,看起来NetworkX主要是用python编写的.我对源代码不太熟悉,但我知道有几个例子,其中NetworkX使用numpy进行繁重的提升(后者又使用C/Fortran进行线性代数).例如,该文件networkx/networkx/algorithms/centrality/eigenvector.py使用numpy来计算特征向量.
有没有人知道这种调用优化库如numpy的策略是否在整个NetworkX中非常流行,或者只是少数算法呢？任何人都可以描述与NetworkX相关的其他可扩展性问题吗？
来自NetworkX首席程序员的回复 我在NetworkX邮件列表上提出了这个问题,Aric Hagberg回答说:
NetworkX中使用的数据结构适合于扩展到大问题(例如,数据结构是邻接列表).算法具有各种缩放属性,但您提到的一些属性是可用的(例如,PageRank,连接的组件,边缘数量是线性复杂度).
此时,NetworkX是纯Python代码.邻接结构使用Python字典编码,以牺牲内存和计算速度为代价提供了极大的灵活性.大图会占用大量内存,最终会耗尽.
NetworkX确实将NumPy和SciPy用于主要基于线性代数的算法.在那种情况下,使用NumPy矩阵或SciPy稀疏矩阵将图表表示(复制)为邻接矩阵.这些算法可以受益于NumPy和SciPY中使用的传统C和FORTRAN代码.
Tia*_*oto 23
这是一个老问题,但我认为值得一提的是图形工具具有与NetworkX非常相似的功能,但它是用C++实现的模板(使用Boost Graph Library),因此速度更快(最多两个)数量级)并使用更少的内存.
免责声明:我是图表工具的作者.
wis*_*sty 18
你的大问题将是记忆.Python根本无法处理数以千万计的对象,而无需在类实现中跳过箍.许多对象的内存开销太高,你达到2GB,32位代码将无法工作.有办法解决它 - 使用插槽,数组或numpy.它应该没问题,因为networkx是为性能而编写的,但如果有一些东西不起作用,我会检查你的内存使用情况.
至于缩放,算法基本上是图表唯一重要的事情.如果做错了,图形算法往往会有非常丑陋的缩放,并且它们在Python中与其他任何语言一样可行.