《介绍几个图论和复杂网络的程序库.doc》由会员分享，可在线阅读，更多相关《介绍几个图论和复杂网络的程序库.doc（4页珍藏版）》请在三一文库上搜索。
1、介绍几个图论和复杂网络的程序库刚加入复杂网络圈子，暂时还没有成熟的研究内容，先发个资料性的东西占坑：）作复杂网络研究离不开对各种实际或模拟网络的统计、计算、绘图等工作。对于一般性的工作，我们可以用Pajek、Netdraw和Ucinet等软件完成。但对一些特殊应用（比如自己开发了一个新模型），现有的软件不能提供相应的建模或计算功能，这时就必须要通过编程的办 法来解决问题了。在这篇文章中，向大家介绍我使用过的4个面向图论及复杂网络分析的程序库，它们可以（分别或同时）用C、C+、C#和Python等语言调用。同时这些库都是开源的，可以通过研读它们的源代码提高编程水平。好，下边开始介绍，第一位出场的
2、是：一、Boost Graph Library准” C+标准库Boost Graph Library （ BGL ）是C+ Boost库的成员之一。Boost是一个经过千锤百炼的C+库，作为标准模板库 STL的后备，是 C+标准化进程的发动机之一。Boost库由C+标准委员会库工作组成员发起，在C+社区中影响甚大，是不折不扣的准”标准库。BGL的特点是灵活性和高运行效率。BGL是以模板的形式提供的，这意味着你可以在模板的基础上创建自己的类型，比如自定义的节点类。BGL的开发者是世界上最顶尖的C+专家，这个库中实现的各种图算法具有非常高的执行效率，而且BGL本身具有工业强度，你可以放心的使用它。
3、此外， BGL的代码结构良好，是非常值得研读的精品，对于学习算法 与数据结构会有很大的帮助。从我的角度来看，BGL的缺点是没有提供复杂网络分析的算法，所以在实际中我使用的还 不多。建议对于分析大规模的网络问题时使用这个库，利用它良好的图数据结构，开发自己的复杂网络分析算法，将会获得很高的执行效率。参考资源：BGL 官方网站： http:/www .boost.org/doc/libs/1_42_0/libs/graph/技术书籍The Boost Graph Library，作者：Jeremy G. Siek， Lie-Qua n Lee，An drew Lumsdaine，见：使用Boost
4、 Graph library，一个简短的BGL使用介绍，适合快速上手，见： Boost Graph Library 学习笔记，讨论学习 BGL 中遇到的问题，见： http:/blog.csd n.n et/magicblue/archive/2009/05/22/4208976.aspx二、QuickGraph .NET 平台下的 BGLQuickGraph是一个用C#语言编写的.NET组件库，所提供的算法与BGL类似，可以看作是Boost Graph Library 在.NET平台下的实现。目前 QuickGraph 的最高版本是 3.3，支持.NET 2.0 和.NET 3.5 平台。对
5、于复杂网络研究， QuickGraph能够提供的帮助与 BGL基本类似。如果你对 C#语言（以 及其它支持.NET的语言）比较熟悉，可以考虑选择这个库。但由于 .NET程序是在虚拟机 下运行的原因，所以效率不够高，不适合处理大规模的计算问题。参考资源：QuickGraph 官方网站：中文资料暂时还找不到。三、igraphC语言写的复杂网络分析库igraph是一个建立和操纵无向图、有向图的开源C程序库，它既包含经典图论里的各种算法（例如最小支撑树、网络流等），也包含了最近的出现的一些网络分析算法（如社团结构 搜索等）。igraph是C写的，这意味着你很容易在C/C+中使用它。如果你不熟悉这两种语
6、言，或者觉得用C/C+太繁琐的话，igraph还提供了 R语言（一种国外很流行的统计分析语言）和 Python语言的接口，所以也很适合科研人员使用（我现在用的是 Python，调用igraph很简单）。参考资料：igraph 官方网站：关于 Python 语言的介绍，见：http:/zh.wikipedia.org/wiki/Python关于 R 语言的介绍，见： http:/zh.wikipedia.Org/wiki/R 语言四、NetworkX全面支持复杂网络分析的Python包NetworkX 是一个创建和操纵复杂网络，并对复杂网络的结构、功能和动力学进行研究的Python包，它提供了目
7、前应用最广泛的一些复杂网络分析算法，当然也包括基本的经典图论算法。NetworkX目前只能在 Python语言中使用（这也是我学 Python的原因之一，见从C#到Python谈谈我学习 Python 周来的体会）。我个人认为NetworkX比igraph要好用，因为NetworkX的文档更清晰易读，程序结构组织 得也很好，我现在主要在用这个包。但NetworkX的执行效率多数情况下会比 igraph要低（见 Drew Con way 所作的对比：http:/files.meetup.eom/1406240/s na_in _R.pdf）。所以也不适合作太大规模的网络分析计算。此外，Netwo
8、rkX和Python的一个绘图包Matplotlib结合得很好，可很方便地进行复杂网络可视化。参考资源:NetworkX 官方网站：http:/networkx.lanl.gov/Matplotlib （科学绘图的 Python 包）：五、总结本文介绍了图论与复杂网络研究常用的一些程序库。用好这些程序库（以及其它一些软件工具），可以避免我们无谓的 re-invent the wheel ，从而提高工作效率。在网上了解到，国外 同行用这些库的很多，而在国内还很少搜索到这方面的资料（除了BGL ）。作为我进复杂网络圈的敲门砖，向各位圈友推荐这几个库。另外，我近期正在学习Python 和 NetworkX ，如果您感兴趣，欢迎和我交流： ）附：几个库的开发及调用语言对比 （*看来学 Python 还是不错的， 这几个库都可以调用 -_- ） 库名称 原始开发语言 可用某语言调用BGL C+ C+/ Python （通过 boost-python ）QuickGrap C#支持 .NET 平台的任何语言 （Python 程序员可用 IronPython）igrap C C/C+/R/Python （理论上至少有 50 种语言可直接或间接调用 C 程序）Network Python Python