NetworkX.doc

(word完整版)NetworkXNetworkX是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作。我已经用了它一段时间了，感觉还不错（除了速度有点慢)，下面介绍我的一些使用经验，与大家分享。一、NetworkX及Python开发环境的安装首先到http:/pypi.python.org/pypi/networkx/下载networkx1。1-py2。6.egg,到 2.6版本的。上边四个包中，pywin32、matplotlib和numpy是exe文件，按提示一路next,比较容易安装。而NetworkX是个egg文件，安装稍微麻烦，需要用easyinstall安装。具体方法：启动DOS控制台（在“运行”里输入cmd），输入C：Python26Libsitepackageseasy_install。py C：networkx1。1-py2.6.egg，回车后会自动执行安装。注意我是把networkx1。1-py2.6。egg放到了C盘根目录，读者在安装时应该具体根据情况修改路径。安装完成后,启动 “开始 - 程序 - ActiveState ActivePython 2。6 (32-bit) PythonWin Editor，在shell中输入：import networkx as nxprint nx如果能输出：module networkx from C:Python26libsitepackagesnetworkx-1.1-py2。6。eggnetworkx_init_.pyc说明Networkx已经安装好了，可以正常调用。关于Python语言，如果没有接触过可以找一本Python的语法书来看看（推荐Python 精要参考(第二版），网上有电子版）.这个语言很简单易学，只要有点编程基础，几天就可以学会它,然后就可以自如的运用它调用NetworkX了。二、建立图或网络1、无向图在PythonWin 的Shell里输入:import networkx as nx #导入NetworkX包，为了少打几个字母，将其重命名为nxG = nx.Graph() #建立一个空的无向图GG。add_node(1) 添加一个节点1G.add_edge（2,3) 添加一条边23（隐含着添加了两个节点2、3）G.add_edge（3，2） 对于无向图，边3-2与边23被认为是一条边print G。nodes（） #输出全部的节点： 1， 2, 3print G。edges(） 输出全部的边:(2, 3）print G。number_of_edges() #输出边的数量：1这样就可以建立一个简单的无向图了。如果你的数据是存在文件里的,可以循环从文件中读取节点和边添加到G中。2、有向图有向图的建立方式和无向图基本类似，只是在上述代码的第二行，将G = nx.Graph() 改为 G = nx.DiGraph（） .需要注意的是，此时再添加边32与边23,则被认为是两条不同的边（可以试着运行上述代码，自己查看结果）。同时，有向图和无向图是可以相互转化的,分别用到Graph。to_undirected() 和 Graph.to_directed(）两个方法。3、加权图（网络)有向图和无向图都可以给边赋予权重，用到的方法是add_weighted_edges_from，它接受1个或多个三元组u,v,w作为参数，其中u是起点，v是终点，w是权重。例如：G。add_weighted_edges_from（0，1,3。0)，(1，2，7.5)）添加01和1-2两条边,权重分别是3。0和7.5.如果想读取权重，可以使用get_edge_data方法，它接受两个参数u和v,即边的起讫点。例如：print G.get_edge_data(1，2) 输出weight： 7.5，这是一个字典结构，可以查看python语法了解它的用法。三、调用图算法NetworkX提供了常用的图论经典算法，例如DFS、BFS、最短路、最小生成树、最大流等等，非常丰富，如果不做复杂网络，只作图论方面的工作，也可以应用NetworkX作为基本的开发包.具体的算法调用方法我就不一一介绍了，可以浏览NX的在线手册http：/networkx.lanl.gov/reference/algorithms。html,对每个算法都提供了详细的帮助文档和示例。下面只给出一个最短路算法的例子：path=nx。all_pairs_shortest_path（G) 调用多源最短路径算法,计算图G所有节点间的最短路径print path02 输出节点0、2之间的最短路径序列： 0, 1， 2四、小结作为NetworkX学习笔记的第一部分，今天先简单介绍下NetworkX的安装与基本使用方法。后边有时间会陆续介绍：用NetworkX进行复杂网络拓扑结构统计指标计算、典型复杂网络建模（随机图、小世界、无标度等）以及复杂网络可视化的方法等，请感兴趣的朋友关注并提出批评与意见。复杂网络分析库NetworkX学习笔记（2):统计指标计算已有 7739 次阅读2010-6-21 16：40|个人分类：NetworkX系统分类:科研笔记关键词:复杂网络，NetworkX无论是实际网络还是对模型网络进行分析,都离不开对网络拓扑统计指标的计算。反映网络结构与动力学特性的统计指标有很多，Costa等的Characterization of Complex Networks： A Survey of measurements一文对此有全面的综述，本文仅介绍一些常用的统计指标在NetworkX中如何计算。一、度、度分布NetworkX可以用来统计图中每个节点的度，并生成度分布序列。下边是一段示例代码(这段代码可以在Shell里一行一行的输入，也可以将其保存为一个以py结尾的纯文本文件后直接运行）,注意看注释部分：import networkx as nxG = nx.random_graphs.barabasi_albert_graph(1000,3） #生成一个n=1000，m=3的BA无标度网络print G。degree（0) 返回某个节点的度print G.degree() 返回所有节点的度print nx。degree_histogram(G） 返回图中所有节点的度分布序列（从1至最大度的出现频次）对上述结果稍作处理，就可以在Origin等软件里绘制度分布曲线了，当然也可以用matplotlib直接作图,在上述代码后接着输入：import matplotlib。pyplot as plt #导入科学绘图的matplotlib包degree = nx.degree_histogram(G） #返回图中所有节点的度分布序列x = range（len（degree)） 生成x轴序列，从1到最大度y = z / float（sum(degree) for z in degree将频次转换为频率，这用到Python的一个小技巧：列表内涵，Python的确很方便:）plt。loglog（x,y,color=”blue”，linewidth=2) 在双对数坐标轴上绘制度分布曲线plt。show() #显示图表二、群聚系数这个在NetworkX里实现起来很简单,只需要调用方法nx。average_clustering(G） 就可以完成平均群聚系数的计算，而调用nx。clustering(G) 则可以计算各个节点的群聚系数。三、直径和平均距离nx。diameter(G）返回图G的直径（最长最短路径的长度),而nx。average_shortest_path_length（G）则返回图G所有节点间平均最短路径长度。四、匹配性这个也比较简单，调用 nx.degree_assortativity（G） 方法可以计算一个图的度匹配性.五、中心性这个我大部分不知道怎么翻译,直接上NX的帮助文档吧，需要计算哪方面的centrality自己从里边找：)Degree centrality measures。（点度中心性？）degree_centrality(G) Compute the degree centrality for nodes.in_degree_centrality（G) Compute the in-degree centrality for nodes。out_degree_centrality（G) Compute the out-degree centrality for nodes。Closeness centrality measures.（紧密中心性?)closeness_centrality(G, v， weighted_edges) Compute closeness centrality for nodes。Betweenness centrality measures。（介数中心性?)betweenness_centrality(G， normalized， 。.） Compute betweenness centrality for nodes。edge_betweenness_centrality(G， normalized, 。.。） Compute betweenness centrality for edges.Currentflow closeness centrality measures。（流紧密中心性？）current_flow_closeness_centrality（G， .。) Compute currentflow closeness centrality for nodes。Current-Flow BetweennessCurrent-flow betweenness centrality measures。(流介数中心性？）current_flow_betweenness_centrality（G, 。) Compute currentflow betweenness centrality for nodes.edge_current_flow_betweenness_centrality(G) Compute current-flow betweenness centrality for edges.Eigenvector centrality。(特征向量中心性？）eigenvector_centrality(G， max_iter, tol， .) Compute the eigenvector centrality for the graph G.eigenvector_centrality_numpy（G） Compute the eigenvector centrality for the graph G.Load centrality。（彻底晕菜）load_centrality(G， v, cutoff， normalized, .。) Compute load centrality for nodes.edge_load(G, nodes， cutoff） Compute edge load。六、小结上边介绍的统计指标只是NetworkX能计算的指标中的一小部分内容,除此之外NetworkX还提供了很多（我还没有用到过的）统计指标计算方法，感兴趣的朋友可以去查NetworkX的在线帮助文档：http:/networkx。lanl。gov/reference/index。html。对于加权图的统计指标计算,NetworkX似乎没有直接提供方法（也可能是我没找到)，估计需要自己动手编制一些程序来完成。复杂网络分析库NetworkX学习笔记（3）:网络演化模型已有 7596 次阅读20106-22 09：22|个人分类:NetworkX系统分类:科研笔记关键词:复杂网络,NetworkXNetworkX提供了4种常见网络的建模方法，分别是：规则图，ER随机图,WS小世界网络和BA无标度网络。本文首先介绍在NetworkX生成这些网络模型的方法，然后以BA无标度网络的建模为例,分析利用NetworkX进行复杂网络演化模型设计的基本思路,以便将来开发出我们自己的模型。同时这篇文章里还涉及到一点复杂网络可视化的方法（后边有时间会另文介绍网络可视化的方法)。一、规则图规则图差不多是最没有复杂性的一类图了,在NetworkX中,用random_graphs.random_regular_graph（d， n）方法可以生成一个含有n个节点，每个节点有d个邻居节点的规则图。下面是一段示例代码，生成了包含20个节点、每个节点有3个邻居的规则图：import networkx as nximport matplotlib.pyplot as pltRG = nx.random_graphs.random_regular_graph(3，20) 生成包含20个节点、每个节点有3个邻居的规则图RGpos = nx.spectral_layout(RG） 定义一个布局，此处采用了spectral布局方式，后变还会介绍其它布局方式，注意图形上的区别nx.draw（RG，pos，with_labels=False,node_size = 30) #绘制规则图的图形，with_labels决定节点是非带标签（编号），node_size是节点的直径plt.show() #显示图形运行结果如下：图1 NetworkX生成的规则图二、ER随机图ER随机图是早期研究得比较多的一类“复杂”网络,这个模型的基本思想是以概率p连接N个节点中的每一对节点.在NetworkX中，可以用random_graphs。erdos_renyi_graph（n,p）方法生成一个含有n个节点、以概率p连接的ER随机图：import networkx as nximport matplotlib.pyplot as pltER = nx.random_graphs。erdos_renyi_graph(20，0.2） #生成包含20个节点、以概率0。2连接的随机图pos = nx。shell_layout(ER) 定义一个布局，此处采用了shell布局方式nx.draw（ER，pos,with_labels=False，node_size = 30）plt。show（)运行结果如下：图2 NetworkX生成的随机图三、WS小世界网络在NetworkX中，可以用random_graphs.watts_strogatz_graph（n, k， p)方法生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络，下面是一个例子:import networkx as nximport matplotlib。pyplot as pltWS = nx.random_graphs.watts_strogatz_graph（20,4，0.3) 生成包含20个节点、每个节点4个近邻、随机化重连概率为0.3的小世界网络pos = nx.circular_layout(WS) #定义一个布局,此处采用了circular布局方式nx。draw（WS,pos,with_labels=False,node_size = 30） 绘制图形plt.show（)运行结果如下：图3 NetworkX生成的WS小世界网络四、BA无标度网络在NetworkX中，可以用random_graphs。barabasi_albert_graph（n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络，下面是一个例子:import networkx as nximport matplotlib。pyplot as pltBA= nx。random_graphs.barabasi_albert_graph（20,1） 生成n=20、m=1的BA无标度网络pos = nx.spring_layout（BA) #定义一个布局，此处采用了spring布局方式nx。draw（BA，pos,with_labels=False，node_size = 30) #绘制图形plt。show（）运行结果如下:图4 NetworkX生成的BA无标度网络五、对BA模型实现代码的分析前面我们介绍了NetworkX提供的4种网络演化模型的应用方法，但仅停留在使用已有的模型是不够的，实际工作中我们可能会自己开发一些网络演化模型。利用NetworkX提供的数据结构，我们可以比较方便的完成这一工作。下面以NetworkX中BA模型的实现代码为例，分析用NetworkX开发网络演化模型的一般思路。NetworkX中关于网络建模的代码在random_graphs.py这个文件中,可以用记事本打开它。为了叙述简便起见,我删掉了原始代码中的一些错误处理与初始条件定义的语句，红色部分是翻译后的注释。#定义一个方法，它有两个参数：n - 网络节点数量；m - 每步演化加入的边数量def barabasi_albert_graph(n, m）: 生成一个包含m个节点的空图 （即BA模型中t=0时的m0个节点） G=empty_graph（m） 定义新加入边要连接的m个目标节点 targets=range（m） 将现有节点按正比于其度的次数加入到一个数组中，初始化时的m个节点度均为0，所以数组为空 repeated_nodes= 添加其余的 nm 个节点，第一个节点编号为m（Python的数组编号从0开始） source=m# 循环添加节点 while sourcen: 从源节点连接m条边到选定的m个节点targets上（注意targets是上一步生成的） G。add_edges_from（zip（source*m,targets)）# 对于每个被选择的节点,将它们加入到repeated_nodes数组中（它们的度增加了1） repeated_nodes.extend(targets)# 将源点m次加入到repeated_nodes数组中（它的度增加了m） repeated_nodes.extend(source*m） 从现有节点中选取m个节点 ，按正比于度的概率（即度优先连接） targets=set() while len(targets）m：#按正比于度的概率随机选择一个节点，见注释1 x=random.choice（repeated_nodes）#将其添加到目标节点数组targets中 targets.add(x)#挑选下一个源点,转到循环开始，直到达到给定的节点数n source += 1 #返回所得的图G return G注释1:此步是关键，random。choice方法是从一个数组中随机地挑选一个元素.由于repeated_nodes数组中的节点出现次数是正比于节点度的,所以这样处理可以保证按度大小的概率选出节点,即实现了度优先连接。如果是按正比于节点适应性等非整数值优先连接,可以参考我的另一篇博文根据值的大小随机取数组元素的方法.六、小结NetworkX的优势之一就是开源，这也是所有Python库的优势（Python是脚本语言，它没有办法隐藏源代码)。NetworkX的源代码结构清晰，风格简练，注释详尽，是学习、研究复杂网络不错的参考资料。当然在这方面我也是初学者，更多的功能还需要在实际应用中不断去发掘和领会科学可视化是利用计算机图形学来创建视觉图像，帮助人们理解那些采取错综复杂而又往往规模庞大的数字呈现形式的科学概念或结果.对于复杂网络研究来说,可视化技术同样重要,它有助于呈现或解释复杂网络数据和模型，进而从中发现（或许是从数据中不易发现的)各种模式、特点和关系.在我的另一篇博文推荐一个复杂网络可视化的网站中，介绍了www.visualcomplexity。com这个网站，上边有大量复杂网络和复杂系统的图片，五彩缤纷，令人叹为观止.有的朋友可能会想，这些图形是否都是使用一些专业的平面设计软件制作的呢？其实，通过使用NetworkX，我们同样可以制作出精美的复杂网络图形，它提供了非常丰富的网络可视化功能.下边这幅动画就是用从NetworkX网站上下载的图片拼合而成的，感兴趣的朋友可以到http：/networkx.lanl.gov/gallery。html这个地址去查看生成这些图形的源代码.在这篇笔记中，我将简单地介绍使用NetworkX绘制复杂网络图形的基本方法。当然在这方面我也是初学,只略懂一些皮毛，希望能起到抛砖引玉的作用:）一、基本绘图流程在NetworkX中，绘制一个网络使用nx。draw()方法，它至少接受一个参数：即你希望绘制的网络G。实际上这个方法非常复杂，它可以指定20多个关键字参数，后边会介绍一些常用的参数，我们先从最简单的情况入手，看看下边的例子：import networkx as nx #导入networkx包import matplotlib.pyplot as plt #导入绘图包matplotlib（需要安装，方法见第一篇笔记)G =nx。random_graphs。barabasi_albert_graph（100，1） #生成一个BA无标度网络Gnx。draw（G） #绘制网络Gplt.savefig(ba。png） #输出方式1： 将图像存为一个png格式的图片文件plt.show() #输出方式2： 在窗口中显示这幅图像运行上述代码的结果如下：这样,用短短的几行代码就完成了一个最基本的网络图形绘制,而且生成了一个功能丰富的窗体。窗口左下方的工具栏可以对图像进行放大、缩小、平移、保存等操作，可以自己动手试一下。同时,在源文件的目录下还生成了一个png格式的图片文件，可以把它插入报告或论文中，是不是很方便呢？二、运用样式上边的代码虽然简单，但生成的图形略显单调。NetworkX提供了一系列样式参数，可以用来修饰和美化图形，达到我们想要的效果。常用的参数包括： node_size： 指定节点的尺寸大小（默认是300,单位未知,就是上图中那么大的点) - node_color: 指定节点的颜色 （默认是红色,可以用字符串简单标识颜色，例如r为红色，b为绿色等,具体可查看手册) - node_shape: 节点的形状（默认是圆形，用字符串o标识，具体可查看手册） alpha: 透明度 (默认是1。0，不透明，0为完全透明） width： 边的宽度 (默认为1.0） edge_color: 边的颜色（默认为黑色) - style: 边的样式(默认为实现，可选： solid|dasheddotted,dashdot） with_labels： 节点是否带标签（默认为True) - font_size: 节点标签字体大小 （默认为12） - font_color： 节点标签字体颜色(默认为黑色)灵活运用上述参数，可以绘制不同样式的网络图形，例如：nx。draw（G，node_size = 30,with_labels = False) 是绘制节点尺寸为30、不带标签的网络图.三、运用布局NetworkX在绘制网络图形方面提供了布局的功能，可以指定节点排列的形式.这些布局包括:circular_layout：节点在一个圆环上均匀分布random_layout：节点随机分布shell_layout：节点在同心圆上分布spring_layout： 用Fruchterman-Reingold算法排列节点(这个算法我不了解，样子类似多中心放射状)spectral_layout：根据图的拉普拉斯特征向量排列节点？我也不是太明白布局用pos参数指定，例如：nx.draw(G，pos = nx.circular_layout(G)）。在上一篇笔记中,四个不同的模型分别是用四种布局绘制的，可以到那里去看一下效果，此处就不再重复写代码了。另外,也可以单独为图中的每个节点指定一个位置(x、y坐标），不过比较复杂，我还没有这样做过.感兴趣的朋友可以看一下NetworkX文档中的一个例子：http:/networkx。lanl。gov/examples/drawing/knuth_miles.html.四、添加文本用plt.title（）方法可以为图形添加一个标题，该方法接受一个字符串作为参数,fontsize参数用来指定标题的大小。例如:plt。title（BA Networks”， fontsize = 20）.如果要在任意位置添加文本，则可以采用plt。text()方法。事实上这些功能（包括前边的图形保存等功能）并不是由NetworkX提供的，从包的名字上可以看出，这些绘图函数都是由matplotlib这个包提供的.NetworkX只是把与复杂网络绘图相关的功能重新包装了一下,让用户调用更方便而已.需要补充的一点是，matplotlib并不直接支持中文文本，如果想输出中文，走正规方法还是挺麻烦的（见http:/blog。.五、小结这篇笔记简单介绍了用NetworkX绘制复杂网络图形的方法，实际上NetworkX的制图能力是很强的（主要是matplotlib的功劳），本文所介绍的功能只是其中最基础的一部分,更多功能还有待我们一起去发掘。再次推荐http：/networkx.lanl.gov/gallery.html上的绘图示例代码,能看懂弄清这些代码，用NetworkX绘图应该就难不住你了：)复杂网络分析库NetworkX学习笔记（5）：二分图已有 4918 次阅读20106-23 19：53个人分类：NetworkX|系统分类:科研笔记|关键词:复杂网络,NetworkX二分图又称二部图，是图论中的一种特殊模型,它的顶点可分割为两个互不相交的子集,并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集。二分图在复杂网络分析中有很多应用，例如科学家合作网络（作者和论文）、商品网络（商品和购买者）、城市公交网络(线路和站点)等都可以用二分图来进行描述。NetworkX提供了一些基本的二分图建模与分析功能，下面对这些功能作一个简单的介绍。一、建立二分图建立二分图与建立普通的图方法比较类似,需要注意的是，边只能在不同类节点之间添加，同类节点之间不要添加边就可以。下面是一个简单的例子（本例中用1开头的编号表示项目节点,用2开头的编号表示参与者节点）：import networkx as nxB = nx.Graph(）#添加一个项目101，它有3个参与者:201，202,203B.add_edge（101,201）B.add_edge（101,202)B.add_edge(101,203)添加一个项目102，它有2个参与者：203，202，2034B.add_edge(102,203）B。add_edge（102，204)此外，NetworkX还提供了多种二分图演化模型的建立方法,在这里把它们列出来供大家参考： plete_bipartite_graph(n1， n2， create_using=None)建立一个完全二分图networkx.generators.bipartite.bipartite_configuration_model （aseq, bseq, create_using=None, seed=None)根据两个度序列建立一个二分图-networkx。generators.bipartite。bipartite_random_regular_graph(d, n， create_using=None， seed=None）建立一个随机的规则二分图networkx。generators。bipartite。bipartite_preferential_attachment_graph（aseq, p， create_using=None， seed=None）建立一个优先连接的二分图-networkx。generators.bipartite.bipartite_havel_hakimi_graph（aseq, bseq, create_using=None)根据两个度序列建立一个HavelHakimi模式的二分图(下面两个模型类似，我没有接触过这个模型，不太理解具体含义）-networkx.generators.bipartite。bipartite_reverse_havel_hakimi_graph(aseq, bseq, create_using=None）-networkx.generators。bipartite.bipartite_alternating_havel_hakimi_graph(aseq, bseq， create_using=None)二、检测图的二分性用networkx。is_bipartite（）方法可以检测一个图是否是二分图。例如对上边代码建立的二分图，nx。is_bipartite(B)返回的结果是True，而对一个随机图R = nx.random_graphs.gnp_random_graph(100，0。2)，由于它不是二分图，nx。is_bipartite（R）返回的结果是False.NetworkX并没有提供图的二分度计算方法，如果使用到这一功能需要自己编制代码。何大韧老师等编写的复杂系统与复杂网络一书的132页有二分度的计算公式,感兴趣的朋友可以自己实现这一程序.此外,NetworkX还提供了对二分图节点进行着色的算法:networkx。bipartite_color()，它可以返回一个字典结构，分别为二分图中的两类节点赋予一个颜色值以示区别。例如对前面建立的二分图进行着色:print nx。bipartite_color（B),将返回结果 ：101： 1, 102： 1, 201： 0, 202： 0, 203: 0, 204: 0，项目节点被赋予颜色值1，参与者节点的颜色值是0。可以用这个值来检测节点类型，也可以用它来进行绘图(参看第4篇笔记网络可视化）。