原文地址:陈关荣老师整理的复杂网络的资源 作者: zhengw789
http://www.ee.cityu.edu.hk/~gchen/ComplexNetworks.htm
http://mrvar.fdv.uni-lj.si/sola/info4/programe.htm
原文地址:NetworkX的基本用法(转) 作者: zhengw789
一、建立图或网络
1、无向图
在PythonWin 的Shell里输入:
import networkx as nx
G = nx.Graph()
G.add_node(1)
G.add_edge(2,3)
G.add_edge(3,2)
print G.nodes()
print G.edges()
print G.number_of_edges()
这样就可以建立一个简单的无向图了。如果你的数据是存在文件里的,可以循环从文件中读取节点和边添加到G中。
2、有向图
有向图的建立方式和无向图基本类似,只是在上述代码的第二行,将G = nx.Graph() 改为 G = nx.DiGraph() 。需要注意的是,此时再添加边3-2与边2-3,则被认为是两条不同的边(可以试着运行上述代码,自己查看结果)。
同时,有向图和无向图是可以相互转化的,分别用到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)])
添加0-1和1-2两条边,权重分别是3.0和7.5。
如果想读取权重,可以使用get_edge_data方法,它接受两个参数u和v,即边的起讫点。例如:
print G.get_edge_data(1,2)
二、调用图算法
NetworkX提供了常用的图论经典算法,例如DFS、BFS、最短路、最小生成树、最大流等等,非常丰富,如果不做复杂网络,只作图论方面的工作,也可以应用NetworkX作为基本的开发包。具体的算法调用方法我就不一一介绍了,可以浏览NX的在线手册http://networkx.lanl.gov/reference/algorithms.html,对每个算法都提供了详细的帮助文档和示例。下面只给出一个最短路算法的例子:
path=nx.all_pairs_shortest_path(G)
print path[0][2]
三、小结
作为NetworkX学习笔记的第一部分,今天先简单介绍下NetworkX的安装与基本使用方法。后边有时间会陆续介绍:用NetworkX进行复杂网络拓扑结构统计指标计算、典型复杂网络建模(随机图、小世界、无标度等)以及复杂网络可视化的方法等,请感兴趣的朋友关注并提出批评与意见。
原文地址:NetworkX基本用法二(转) 作者: zhengw789 无论是实际网络还是对模型网络进行分析,都离不开对网络拓扑统计指标的计算。反映网络结构与动力学特性的统计指标有很多,Costa等的Characterization of Complex Networks: A Survey of measurements一文对此有全面的综述,本文仅介绍一些常用的统计指标在NetworkX中如何计算。
一、度、度分布
NetworkX可以用来统计图中每个节点的度,并生成度分布序列。下边是一段示例代码(这段代码可以在Shell里一行一行的输入,也可以将其保存为一个以py结尾的纯文本文件后直接运行),注意看注释部分:
import networkx as nx
对上述结果稍作处理,就可以在Origin等软件里绘制度分布曲线了,当然也可以用matplotlib直接作图,在上述代码后接着输入:
import matplotlib.pyplot as plt
二、群聚系数
这个在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)
in_degree_centrality(G)
out_degree_centrality(G)
Closeness centrality measures.(紧密中心性?)
closeness_centrality(G[, v, weighted_edges])
Betweenness centrality measures.(介数中心性?)
betweenness_centrality(G[, normalized, ...])
edge_betweenness_centrality(G[, normalized, ...])
Current-flow closeness centrality measures.(流紧密中心性?)
current_flow_closeness_centrality(G[, ...])
Current-Flow Betweenness
Current-flow betweenness centrality measures.(流介数中心性?)
current_flow_betweenness_centrality(G[, ...])
edge_current_flow_betweenness_centrality(G)
Eigenvector centrality.(特征向量中心性?)
eigenvector_centrality(G[, max_iter, tol, ...])
eigenvector_centrality_numpy(G)
Load centrality.(彻底晕菜~~~)
load_centrality(G[, v, cutoff, normalized, ...])
edge_load(G[, nodes, cutoff])
六、小结
上边介绍的统计指标只是NetworkX能计算的指标中的一小部分内容,除此之外NetworkX还提供了很多(我还没有用到过的)统计指标计算方法,感兴趣的朋友可以去查NetworkX的在线帮助文档:http://networkx.lanl.gov/reference/index.html。对于加权图的统计指标计算,NetworkX似乎没有直接提供方法(也可能是我没找到),估计需要自己动手编制一些程序来完成。
degree = nx.degree_histogram(G)
x = range(len(degree))
y = [z / float(sum(degree)) for z in degree]
#将频次转换为频率,这用到Python的一个小技巧:列表内涵,Python的确很方便:)
plt.loglog(x,y,color="blue",linewidth=2)
plt.show()
G = nx.random_graphs.barabasi_albert_graph(1000,3)
print G.degree(0)
print G.degree()
print nx.degree_histogram(G)
原文地址:NetworkX用法之三——网络演化模型(转) 作者: zhengw789
NetworkX提供了4种常见网络的建模方法,分别是:规则图,ER随机图,WS小世界网络和BA无标度网络。本文首先介绍在NetworkX生成这些网络模型的方法,然后以BA无标度网络的建模为例,分析利用NetworkX进行复杂网络演化模型设计的基本思路,以便将来开发出我们自己的模型。同时这篇文章里还涉及到一点复杂网络可视化的方法(后边有时间会另文介绍网络可视化的方法)。
一、规则图
规则图差不多是最没有复杂性的一类图了,在NetworkX中,用random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点,每个节点有d个邻居节点的规则图。下面是一段示例代码,生成了包含20个节点、每个节点有3个邻居的规则图:
import networkx as nx
import matplotlib.pyplot as plt
RG = nx.random_graphs.random_regular_graph(3,20) #生成包含20个节点、每个节点有3个邻居的规则图RG
pos = nx.spectral_layout(RG)
nx.draw(RG,pos,with_labels=False,node_size = 30) #绘制规则图的图形,with_labels决定节点是非带标签(编号),node_size是节点的直径
plt.show() #显示图形
运行结果如下:
图1
二、ER随机图
ER随机图是早期研究得比较多的一类“复杂”网络,这个模型的基本思想是以概率p连接N个节点中的每一对节点。在NetworkX中,可以用random_graphs.erdos_renyi_graph(n,p)方法生成一个含有n个节点、以概率p连接的ER随机图:
import networkx as nx
import matplotlib.pyplot as plt
ER = nx.random_graphs.erdos_renyi_graph(20,0.2) #生成包含20个节点、以概率0.2连接的随机图
pos = nx.shell_layout(ER)
nx.draw(ER,pos,with_labels=False,node_size = 30)
plt.show()
运行结果如下:
图2
三、WS小世界网络
在NetworkX中,可以用random_graphs.watts_strogatz_graph(n, k, p)方法生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络,下面是一个例子:
import networkx as nx
import matplotlib.pyplot as plt
WS = nx.random_graphs.watts_strogatz_graph(20,4,0.3) #生成包含20个节点、每个节点4个近邻、随机化重连概率为0.3的小世界网络
pos = nx.circular_layout(WS)
nx.draw(WS,pos,with_labels=False,node_size = 30) #绘制图形
plt.show()
运行结果如下:
图3
四、BA无标度网络
在NetworkX中,可以用random_graphs.barabasi_albert_graph(n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络,下面是一个例子:
import networkx as nx
import matplotlib.pyplot as plt
BA= nx.random_graphs.barabasi_albert_graph(20,1) #生成n=20、m=1的BA无标度网络
pos = nx.spring_layout(BA)
nx.draw(BA,pos,with_labels=False,node_size = 30) #绘制图形
plt.show()
运行结果如下:
图4
五、对BA模型实现代码的分析
前面我们介绍了NetworkX提供的4种网络演化模型的应用方法,但仅停留在使用已有的模型是不够的,实际工作中我们可能会自己开发一些网络演化模型。利用NetworkX提供的数据结构,我们可以比较方便的完成这一工作。下面以NetworkX中BA模型的实现代码为例,分析用NetworkX开发网络演化模型的一般思路。NetworkX中关于网络建模的代码在random_graphs.py这个文件中,可以用记事本打开它。为了叙述简便起见,我删掉了原始代码中的一些错误处理与初始条件定义的语句,红色部分是翻译后的注释。
#定义一个方法,它有两个参数:n - 网络节点数量;m - 每步演化加入的边数量
def barabasi_albert_graph(n, m):
注释1:此步是关键,random.choice方法是从一个数组中随机地挑选一个元素。由于repeated_nodes数组中的节点出现次数是正比于节点度的,所以这样处理可以保证按度大小的概率选出节点,即实现了度优先连接。如果是按正比于节点适应性等非整数值优先连接,可以参考我的另一篇博文《根据值的大小随机取数组元素的方法》。
六、小结
NetworkX的优势之一就是开源,这也是所有Python库的优势(Python是脚本语言,它没有办法隐藏源代码)。NetworkX的源代码结构清晰,风格简练,注释详尽,是学习、研究复杂网络不错的参考资料。当然在这方面我也是初学者,更多的功能还需要在实际应用中不断去发掘和领会…………
原文地址:NetworkX用法之四——网络可视化(转) 作者: zhengw789 科学可视化是利用计算机图形学来创建视觉图像,帮助人们理解那些采取错综复杂而又往往规模庞大的数字呈现形式的科学概念或结果。对于复杂网络研究来说,可视化技术同样重要,它有助于呈现或解释复杂网络数据和模型,进而从中发现(或许是从数据中不易发现的)各种模式、特点和关系。
在我的另一篇博文《 推荐一个复杂网络可视化的网站 》中,介绍了 www.visualcomplexity 这个网站,上边有大量复杂网络和复杂系统的图片,五彩缤纷,令人叹为观止。有的朋友可能会想,这些图形是否都是使用一些专业的平面设计软件制作的呢?其实,通过使用NetworkX,我们同样可以制作出精美的复杂网络图形,它提供了非常丰富的网络可视化功能。下边这幅动画就是用从NetworkX网站上下载的图片拼合而成的,感兴趣的朋友可以到 http://networkx.lanl.gov/gallery.html 这个地址去查看生成这些图形的源代码。
在这篇笔记中,我将简单地介绍使用NetworkX绘制复杂网络图形的基本方法。当然在这方面我也是初学,只略懂一些皮毛,希望能起到抛砖引玉的作用:)
一、基本绘图流程
在NetworkX中,绘制一个网络使用nx.draw()方法,它至少接受一个参数:即你希望绘制的网络G。实际上这个方法非常复杂,它可以指定20多个关键字参数,后边会介绍一些常用的参数,我们先从最简单的情况入手,看看下边的例子:
import networkx as nx
import matplotlib.pyplot as plt
G =nx.random_graphs.barabasi_albert_graph(100,1)
nx.draw(G)
plt.savefig("ba.png")
plt.show()
运行上述代码的结果如下:
这样,用短短的几行代码就完成了一个最基本的网络图形绘制,而且生成了一个功能丰富的窗体。窗口左下方的工具栏可以对图像进行放大、缩小、平移、保存等操作,可以自己动手试一下。同时,在源文件的目录下还生成了一个png格式的图片文件,可以把它插入报告或论文中,是不是很方便呢?
二、运用样式
上边的代码虽然简单,但生成的图形略显单调。NetworkX提供了一系列样式参数,可以用来修饰和美化图形,达到我们想要的效果。常用的参数包括:
灵活运用上述参数,可以绘制不同样式的网络图形,例如: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.csdn/KongDong/archive/2009/07/10/4338826.aspx)。不过有聪明的网友提出了一种偷梁换柱的解决方案:换字体。只要把一个中文字体文件(ttf文件)更名为Vera.ttf,拷贝到matplotlib的字体目录中覆盖原有文件,就可以输出中文了,具体细节见http://hi.baidu/ucherish/blog/item/63155e52b68c90070df3e3ff
五、小结
这篇笔记简单介绍了用NetworkX绘制复杂网络图形的方法,实际上NetworkX的制图能力是很强的(主要是matplotlib的功劳),本文所介绍的功能只是其中最基础的一部分,更多功能还有待我们一起去发掘。再次推荐 http://networkx.lanl.gov/gallery.html上的绘图示例代码,能看懂弄清这些代码,用NetworkX绘图应该就难不住你了:)
原文地址:NetworkX用法之五——二分图(转) 作者: zhengw789 二分图又称二部图,是图论中的一种特殊模型,它的顶点可分割为两个互不相交的子集,并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集。二分图在复杂网络分析中有很多应用,例如科学家合作网络(作者和论文)、商品网络(商品和购买者)、城市公交网络(线路和站点)等都可以用二分图来进行描述。NetworkX提供了一些基本的二分图建模与分析功能,下面对这些功能作一个简单的介绍。
一、建立二分图
建立二分图与建立普通的图方法比较类似,需要注意的是,边只能在不同类节点之间添加,同类节点之间不要添加边就可以。下面是一个简单的例子(本例中用1开头的编号表示项目节点,用2开头的编号表示参与者节点):
import networkx as nx
B = nx.Graph()
#添加一个项目101,它有3个参与者:201,202,203
B.add_edge(101,201)
B.add_edge(101,202)
B.add_edge(101,203)
#添加一个项目102,它有2个参与者:203,202,2034
B.add_edge(102,203)
B.add_edge(102,204)
…………………………
此外,
NetworkX还提供了多种二分图演化模型的建立方法,在这里把它们列出来供大家参考:
-- networkx.generators.classicplete_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)
根据两个度序列建立一个Havel-Hakimi模式的二分图(下面两个模型类似,我没有接触过这个模型,不太理解具体含义)
-- 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篇笔记《网络可视化》)。
三、二分图的投影
二分图可以通过向参与者节点投影或向项目节点投影转换为一个单分图(见下图),NetworkX提供的networkx.project(B, nodes)方法可以完成这一工作。它接受两个参数:一个是二分图B,另一个是投向的节点集合nodes。
二分图投影示意(向下投影) 对于节点集合的提取可以用networkx.bipartite_sets方法,它可以将一个二分图的两类节点提取为两个集合(X,Y),其中X是项目节点,Y是参与者节点。下面是一段示例代码,演示上述两个函数的用法:
(接第一节的代码之后)
NSet = nx.bipartite_sets(B)
Act = nx.project(B,NSet[0])
Actor = nx.project(B,NSet[1]) #向参与者节点投影
print Act.edges() #输出 [(101, 102)]
print Actor.edges()
四、通过派系提取构造二分图
对于一个存在派系(Clique)的图,可以通过提取派系结构生成一个二分图。NetworkX提供的networkx.make_clique_bipartite方法可以从图中查找派系,然后将一个派系作为一个项目节点并和该派系中的节点建立连接,从而构造一个二分图。它是二分图向参与者节点投影的逆过程,下边是一段示例代码:
(接第三节的代码之后)
G = nx.make_clique_bipartite(Actor)
print G.edges() #输出:[(201, -1), (202, -1), (203, -2), (203, -1), (204, -2)]
补充一点,NetworkX的派系提取算法据说效率很高,不过我没有做过这方面的东西,感兴趣的朋友可以去看它的源代码(见http://networkx.lanl.gov/reference/algorithms.clique.html)。
五、小结
本篇笔记介绍了用NetworkX进行二分图建模与分析的方法,到今天为止,我的《NetworkX学习笔记》就暂告一段落了。我目前的工作中只用到了这几篇笔记中所写的功能,以后如果有其他的心得体会我还会继续进行补充。希望这些文章对学习和研究复杂网络的朋友们能起到一点帮助作用,也欢迎各位留言批评、讨论。
最后,向NetworkX的三位开发者Aric Hagberg、Dan Schult 、Pieter Swart 以及许许多多的贡献者致敬*,感谢他们为我们提供了这样一个优秀的复杂网络分析工具!
根据三位开发者的建议,如果要在论文中引用NetworkX,请引用以下文献:
Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008
* 意外发现NetworkX的贡献者里还有复杂网络圈里的周涛、刘建国和汪秉宏老师,佩服啊!见https://networkx.lanl.gov/trac/changeset/681/networkx/trunk/networkx :“Graph A and B are from Tao Zhou, Jian-Guo Liu, Bing-Hong Wang: Comment on ``Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality". http://arxiv/pdf/physics/0511084 ”
建立一个完全二分图
原文地址:igraph/networkx学习笔记之一
igraph中图的数据结构
typedef struct igraph_s {
} igraph_t;
(注意igraph中顶点和边都是从0开始编号一直到总数减一)。其中n是图的顶点个数,directed标志是否是有向图。所有边的顶点存储在from和to两个向量(igraph_vector_t)中,oi[e]对应的是编号为e的边所对应的尾结点在from中的index,同样ii[e]对应于e的头节点在to中的index(也就是是说e 可以表示为 from[oi[e]] -> to[ii[e]])。所以from,to,oi,ii都是长度与边数相同的向量。os和is则和oi,ii相反,表示的是从顶点到边的映射,从顶点v出发的第一条边为 from[oi[os[v]]] -> to[ii[os[v]]],所以当os[v] == os[v + 1]时候就表示从该顶点没有出边。向量is同理。os,is都是长度为顶点数加一的向量。操作igraph_t的一些基本API如igraph_empty, igraph_adjacent等见于文档手册(btw,igraph的文档写的很全很好,有空应该研究一下它制作文档的技术)。
#define BASE_BOOL
#include "igraph_pmt.h"
#include "vector.pmt"
#include "igraph_pmt_off.h"
#undef BASE_BOOL
#define BASE_BOOL
#include "igraph_pmt.h"
#include "vector.pmt"
#include "igraph_pmt_off.h"
#undef BASE_BOOL
其中vector.pmt定义的是类型无关的代码,igraph_pmt_off.h则小心翼翼的将宏清除出去(再一次感慨C++有模板真是太好了。。。)。这种手法还是有借鉴意义的(比起void*我更喜欢这样)。
Networkx的数据结构
本文来自CSDN博客,转载请标明出处:http://blog.csdn/rogerrecharad/archive/2010/11/07/5993723.aspx
更多推荐
复杂网络分析以及networkx学习
发布评论