图分析工具库networkx
networkx是用python下开发的图论和复杂网络建模工具,内置了常用的图和复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。
一、图的构建
STEP 1: 声明图对象
networkx有四种图 Graph 、DiGraph、MultiGraph、MultiDiGraph,分别为无多重边无向图、无多重边有向图、有多重边无向图、有多重边有向图。
1 | import networkx as nx |
STEP 2: 添加顶点和边
1 | # 方法一-------------------------------------- |
STEP 3: 查看图的信息
1 | print('顶点的个数为', G.number_of_nodes()) |
STEP 4: 可视化
1 | # 方法一-------------------------------------- |
二、图的操作
1、移除某些顶点和边
1 | import networkx as nx |
2、子图抽取
直接按顶点抽取:
1 | import networkx as nx |
按条件抽取:
1 | import networkx as nx |
3、图的合并
1 | import networkx as nx |
4、有向图和无向图的转化
1 | import networkx as nx |
三、图的分析
1、度、度分布
1 | import networkx as nx |
2、图矩阵
1 | import networkx as nx |
3、遍历
广度遍历:
1 | import networkx as nx |
深度遍历:
1 | import networkx as nx |
4、连通分析
连通子图:
1 | import networkx as nx |
弱连通子图:
1 | import networkx as nx |
强连通子图:
1 | import networkx as nx |
5、最短路径
无权图:
1 | import networkx as nx |
加权图(迪杰斯特拉算法):
1 | import networkx as nx |
加权图(贝尔曼-福特算法):
1 | import networkx as nx |
加权图(Astar算法):
1 | import networkx as nx |
6、最小/最大生成树
最小生成树:
1 | import networkx as nx |
最大生成树:
1 | import networkx as nx |
7、群聚系数
1 | import networkx as nx |
8、中心性度量
度中心性:
在社会网络中,对于具有更多连接关系的顶点,度中心性度量方法认为他们具有更高的中心性。可以利用顶点的度来衡量连接关系。
1 | import networkx as nx |
特征向量中心性:
在度中心性度量中,我们认为具有较多连接的顶点更重要。然而在现实中,拥有更多朋友并不能确保这个人就是重要的,拥有更多重要的朋友才能提供更有力的信息。
因此,我们试图用邻居顶点的重要性来概括本顶点的重要性。
1 | import networkx as nx |
Katz中心性:
在特征向量中心性度量中,会有这么一个问题:某个点被大量的关注,但是关注该点的点的中心性很低(甚至为0),这样会导致网络中存在被大量关注但中心值却为0的点。因此,我们需要在特征向量中心性度量的基础上加入一个偏差项(或者说是中心值下限),来解决这个问题。
1 | import networkx as nx |
PageRank:
Katz在某些情况下存在一些与特征向量中心性相似的问题。在有向图中,一旦一个顶点成为一个权威顶点(高中心值结点),它将向它所有的外连接传递其中心性,导致其它顶点中心性变的很高。但这是不可取的,因为不是每一个被名人所知的人都是有名的。因此我们在katz中心性的基础上,累加时让每一个邻居的中心性除以该邻居顶点的出度,这种度量称为PageRank。
1 | import networkx as nx |
betweenness:
另一种中心性度量方法是考虑顶点在连接其他顶点时所表现出的重要性。
1 | import networkx as nx |
closeness:
接近中心性的思想是顶点越趋于中心,它们越能快速地到达其他的顶点。更形式化的描述,这些顶点满足与其他顶点之间有最小的平均最短路径。
1 | import networkx as nx |
四、网络图模型
1、随机图模型
随机网络(如ER模型),连接是随机设置的,但大部分顶点的连接数目会大致相同,即顶点的分布方式遵循钟形的泊松分布,有一个特征性的“平均数”。连接数目比平均数高许多或低许多的顶点都极少,随着连接数的增大,其概率呈指数式迅速递减。故随机网络亦称指数网络。
1 | import networkx as nx |
2、小世界模型
在网络理论中,小世界网络是一类特殊的复杂网络结构,在这种网络中大部份的顶点彼此并不相连,但绝大部份顶点之间经过少数几步就可到达。
在日常生活中,有时你会发现,某些你觉得与你隔得很“遥远”的人,其实与你“很近”。小世界网络就是对这种现象(也称为小世界现象)的数学描述。用数学中图论的语言来说,小世界网络就是一个由大量顶点构成的图,其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外,小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。
二十世纪60年代,美国哈佛大学社会心理学家斯坦利·米尔格伦(Stanley Milgram)做了一个连锁信实验。他将一些信件交给自愿的参加者,要求他们通过自己的熟人将信传到信封上指明的收信人手里,他发现,20%的信件最终送到了目标人物手中。而在成功传递的信件中,平均只需要6.5次转发,就能够到达目标。也就是说,在社会网络中,任意两个人之间的“距离”是6。这就是所谓的“六度分隔”理论。
1 | import networkx as nx |
3、优先链接模型
无标度网络模型(BA模型)具有两个特性,其一是增长性,所谓增长性是指网络规模是在不断的增大的,在研究的网络当中,网络的顶点是不断的增加的;其二就是优先连接机制,这个特性是指网络当中不断产生的新的顶点更倾向于和那些连接度较大的顶点相连接。BA模型对很多的现象都是可以解释的,例如研究生对导师的选择,在这个网络当中,研究生和导师都是不断增加的,而研究生总是倾向于选择已经带过很多研究生的导师。
1 | import networkx as nx |