NetworkX 入门

1.1图论基本概念

1图
一个图G = （V, E）由一些点及点之间的连线（称为边）构成，V、E分别计G的点集合和边集合。在图的概念中，点的空间位置，边的区直长短都无关紧要，重要的是其中有几个点以及那些点之间有变相连。

图1：图示例

Graph分类
Graph：指无向图（undirected Graph），即忽略了两节点间边的方向。
DiGraph：指有向图（directed Graph），即考虑了边的有向性。
MultiGraph：指多重无向图，即两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联。
MultiDiGraph：多重图的有向版本。

G = nx.Graph() # 创建无向图
G = nx.DiGraph() # 创建有向图
G = nx.MultiGraph() # 创建多重无向图
G = nx.MultiDigraph() # 创建多重有向图
G.clear() #清空图

2有向图和无向图
最基本的图通常被定义为“无向图”，与之对应的则被称为“有向图”。两者唯一的区别在于，有向图中的边是有方向性的。

图2：有向图和无向图

注：上图左边为无向图，右边为有向图。黑色加粗部分表示边的方向。比如：1—>2便是边是1到2这个方向。

3图的度
度是相对于图中点的概念，图中任意一点v的度是指：与v相连的边的条数。在有向图中与顶点v出关联的边的数目称为出度，与顶点v入关联的边的数目称为入度。比如上图2：左边无向图顶点2的度是3.右边有向图点点2的出度是2，入度是1.

4图的连通性
在图G中，若顶点u，v之间有路（即找到有u到v之间相连的边）则称u，v连通。若G的任何两点之间有路，则称G是连通图。G的极大连通子图称为连通分支。如果连通图是有向图则称G是强连通的。

5图的最短路径
在图上任取两顶点，分别作为起点和终点，我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”，这些路径中经过顶点最少的那个路径就是最短路径。

6图的简单路径
如果路径上的各顶点均不互相重复，称这样的路径为简单路径。如果路径上的第一个顶点与最后一个顶点重合，这样的路径称为回路(cycle)或环或圈。比如下图中：（1，2，3，4，5，1），（1，2，3，1），（1，3，4，5，1）等都是简单路径。

图3：简单路径

7图的偏心距（eccentricity）
一个节点的偏心距就是这个节点到其他节点的所有节点的最短路径的最大值。

8图的直径和半径
图的所有节点偏心距的最大值就是图的直径，最小值就是半径。

9图的紧密中心性(closeness)
在图论中，紧密度是图中一个节点的中心性度量。比其他节点更“浅”（也就是说，有更短的测地距离）的节点有更高的紧密度。在网络分析中，紧密度倾向于表示最短路径长度，因为这样会有更多的中心节点赋予更高的值，而且通常与其他度量（比如：度）相联系。紧密度是中心性的一种复杂度量。它被定义为节点v到其它可达节点的平均测地距离（比如：最短路径）：

其中当n>=2是从v出发在网络中连通部分V的大小。接近中心性需要考量每个结点到其它结点的最短路的平均长度。也就是说，对于一个结点而言，它距离其它结点越近，那么它的中心度越高。一般来说，那种需要让尽可能多的人使用的设施，它的接近中心度一般是比较高的。

10图的介数中心性(Betweenness Centrality)
对于n各节点的图G=(V, E)，节点v的介数CB(v)按如下方式计算：

1. 对于每对节点(s, t)，计算他们之间所有的最短路径；
2. 对于每对节点(s, t)，通过判断(here, 节点v)求出它在最短路径上的部分；
3. 对每对节点(s, t)求出的部分进行累加

公式表示为：

其中：σst是s到t的最短路径数，σst()是s到t的最短路径中经过v的数量。它可以除以不包括节点v的节点数量（对于无向图是(n-1)(n-2)/2有向图是(n-1)(n-2)类归一化。）中介中心性指的是一个结点担任其它两个结点之间最短路的桥梁的次数。一个结点充当“中介”的次数越高，它的中介中心度就越大。

11图的度中心性
度中心性（Degree Centrality）是在网络分析中刻画节点中心性（Centrality）的最直接度量指标。一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。

12特征向量中心性（eigenvector centrality）
一个节点的重要性既取决于其邻居节点的数量（即该节点的度），也取决于其邻居节点的重要性,记xi为节点vi的重要性度量值，则：

其中，c为一个比例常数，记x=[x1,x2,x3,…,xn]T，经过多次迭代到达稳态时，可以写成如下的矩阵形式：

这里表示x是矩阵A的特征值c-1对应的特征向量，也可表示为如下形式：

计算：
一个节点的特征向量中心性与其临近节点的中心性得分的总和成正比。与重要的节点连接的节点更重要，有少量有影响的联系人的节点其中心性可能超过拥有大量平庸的联系人的节点。
1、计算图的成对临近矩阵的特征分解
2、选择有最大特征值的特征向量
3、第i个节点的中心性等于特征向量中的第i元素
另外PageRank算法是特征向量中心性的一个变种。

1.2图论基本算法

1图遍历之BFS算法（广度优先搜索）
算法步骤：

1. 首先选择一个顶点作为起始节点，并将其染成灰色，其余结点为白色。
2. 将起始结点放入队列中。
3. 从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部，将已访问过结点涂成黑色，没访问过的结点是白色。如果顶点的颜色是灰色，表示已经发现并且放入了队列，如果顶点的颜色是白色，表示还没有发现 。
4. 按照同样的方法处理队列中的下一个结点。

例如：下图

图：BFS搜索

从上图节点1开始搜索，染成灰色，其余白色。此时队列中只有节点{1}
搜索1的邻居节点2， 3，此时1出队染成黑色表示已经访问，23入队{2， 3}
搜索2的邻居节点3， 4，节点3已经在队列所以2出队染成黑色添加4进入队列{3， 4}
搜索3的邻居节点2，4，节点2已经变黑表示已经访问，节点3出队变成黑色4此时就在队列{4}
搜索4的邻居节点1，节点1已变成黑色。所以4出队变成黑色。队列为空。
此时1， 2， 3， 4， 都已经变成黑色。还剩节点5，再从5开始搜索，结束。
2图遍历之DFS算法（深度优先搜索）
算法步骤：

1. 选择起始顶点涂成灰色，表示还未访问；
   从该顶点的邻接顶点中选择一个，继续这个过程（即再寻找邻接结点的邻接2. 结点），一直深入下去，直到一个顶点没有邻接结点了，涂黑它，表示访问过了；
2. 回溯到这个涂黑顶点的上一层顶点，再找这个上一层顶点的其余邻接结点，继续如上操作，如果所有邻接结点往下都访问过了，就把自己涂黑，再回溯到更上一层；
3. 上一层继续做如上操作，知道所有顶点都访问过。

实例：用下图作为说明

图：DFS搜索

1. 从节点1开始依次访问1à2à 3之后终止于节点3；
2. 从节点3回溯到节点2，从2à5终止于节点5；
3. 从节点5回溯到2终止于2；
4. 从节点2回溯到1并终止于1；
5. 从顶点4开始访问终止于4.
   算法实现基本代码

# -*- coding: utf-8 -*-

class Mygraph(object):

    def __init__(self, *args, **kwargs):
        self.node_neighbors = {}
        self.visited = {}

    def nodes(self):
        return self.node_neighbors

    def add_node(self, node):
        if not node in self.nodes():
            self.node_neighbors = []

    def add_nodes(self, nodelist):
        for node in nodelist:
            self.add_node(node)

    def add_edge(self, edge):
        u, v = edge
        if u not in self.nodes():
            self.node_neighbors[u] = []
        if v not in self.nodes():
            self.node_neighbors[v] = []
        if (v not in self.node_neighbors[u]) and (u not in self.node_neighbors[v]):
            self.node_neighbors[u].append(v)
            if u != v:
                self.node_neighbors[v].append(u)

    def add_edges(self, edges):
        for edge in edges:
            self.add_edge(edge)

    def depth_first_search(self, root=None):
        order = []
        def dfs(node):
            self.visited[node] = True
            order.append(node)
            for n in self.node_neighbors[node]:
                if not n in self.visited:
                    dfs(n)
        if root:
            dfs(root)
        for node in self.nodes():
            if not node in self.visited:
                dfs(node)
        return order

    def breath_first_search(self, root=None):
        queue = []
        order = []
        def bfs():
            while len(queue) > 0:
                node = queue.pop(0)
                self.visited[node] = True
                for n in self.node_neighbors[node]:
                    if (not n in self.visited) and (not n in queue):
                        queue.append(n)
                        order.append(n)
        if root:
            queue.append(root)
            order.append(root)
            bfs()

        for node in self.nodes():
            if not node in self.visited:
                queue.append(node)
                order.append(node)
                bfs()
        return order


if __name__ == '__main__':
    edges = [(1, 2), (1, 3), (2, 3),
             (2, 5), (3, 4), (4, 2),
             (4, 5), (5, 3)]

    G = Mygraph()
    G.add_edges(edges)
    print(G.nodes())
    print("广度优先遍历：")
    bfs_order = G.breath_first_search(1)
    print(bfs_order)
    G = Mygraph()
    G.add_edges(edges)
    dfs_order = G.depth_first_search(1)
    print("深度优先遍历：")

print(dfs_order)

注：为什么创建图写了两遍，因为只写一次，进行广度优先访问之后，有些会被标记为TRUE，会影响后面深度访问结果。

2.1Networkx概述与安装

1概述
NetworkX是一款Python的软件包，用于创造、操作复杂网络，以及学习复杂网络的结构、动力学及其功能。 有了NetworkX你就可以用标准或者不标准的数据格式加载或者存储网络，它可以产生许多种类的随机网络或经典网络，也可以分析网络结构，建立网络模型，设计新的网络算法，绘制网络等等

2安装
方式一：pip3 install networkx就行

2.2Networkx使用

1创建图添加节点和边
G = nx.Graph() # 创建无向图（nx.DiGraph() 创建有向图）
G.add_node(0) # 添加一个节点
G.add_nodes_from([1, 2])# 一次添加多个节点
顶点操作

1，向图中增加顶点
在向图中增加顶点时，可以一次增加一个顶点，也可以一次性增加多个顶点，顶点的ID属性是必需的。在添加顶点之后，可以通过g.nodes()函数获得图的所有顶点的视图，返回的实际上NodeView对象；如果为g.nodes(data=True)的data参数设置为true，那么返回的是NodeDataView对象，该对象不仅包含每个顶点的ID属性，还包括顶点的其他属性。
g.add_node(1)
g.add_nodes_from([2,3,4])
g.nodes()
#NodeView((1, 2,3,4))
在向图中添加顶点时，除ID属性之外，也可以向顶点中增加自定义的属性，例如，名称属性，权重属性：
g.add_node(1,name='n1',weight=1)
g.add_node(2,name='n2',weight=1.2)
2，查看顶点的属性
通过属性_node获得图的所有顶点和属性的信息，_node属性返回的是一个字典结构，字典的Key属性是顶点的ID属性，Value属性是顶点的其他属性构成的一个字典。
g._node
{1: {'name': 'n1', 'weight': 1}, 2: {'name': 'n2', 'weight': 1.2}, 3: {}, 4: {}}
g.nodes(data=True)
可以通过顶点的ID属性来查看顶点的其他属性：
g.node[1]
{'name': 'n1', 'weight': 1}
g.node[1]['name']
'n1 new'
通过g.nodes()，按照特定的条件来查看顶点：
list(g.nodes(data=True))
 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
3，删除顶点
通过remove函数删除图的顶点，由于顶点的ID属性能够唯一标识一个顶点，通常删除顶点都需要通过传递ID属性作为参数。
g.remove_node(node_ID)
g.remove_nodes_from(nodes_list)
4，更新顶点
更新图的顶点，有两种方式，第一种方式使用字典结构的_update函数，第二种方式是通过索引来设置新值：
g._node[1].update({'name':'n1 new'})
g.node[1]['name']='n1 new'
{1: {'name': 'n1 new', 'weight': 1}, 2: {'name': 'n2', 'weight': 1.2}, 3: {}, 4: {}}
5，删除顶点的属性
使用del命令删除顶点的属性
del g.nodes[1]['room'] 
6，检查是否存在顶点
检查一个顶点是否存在于图中，可以使用 n in g方式来判断，也可以使用函数：
g.has_node(n)

G.add_edge(0, 1) # 添加一条边
G.add_edge(2, 3) # 如果边的节点已经存在，直接覆盖
G.add_edge(4, 5) # 如果边的节点不存在，则添加新节点
G.add_edges_from([(2, 1), (5, 1), (0, 4), (3, 4)]) #添加多条边基于上面添加的
边的更多操作

1，向图中增加边
边是由对应顶点的名称构成的，例如，顶点2和3之间有一条边，记作e=(2,3)，通过add_edge(node1,node2)向图中添加一条边，也可以通过add_edges_from(list)向图中添加多条边；在添加边时，如果顶点不存在，那么networkx会自动把相应的顶点加入到图中。
g.add_edge(2,3)
g.add_edges_from([(1,2),(1,3)])
g.edges()
#EdgeView([(1, 2), (1, 3), (2, 3)])
可以向边中增加属性，例如，权重，关系等：
g.add_edge(1, 2, weight=4.7, relationship='renew')
由于在图中，边的权重weight是非常有用和常用的属性，因此，networkx模块内置以一个函数，专门用于在添加边时设置边的权重，该函数的参数是三元组，前两个字段是顶点的ID属性，用于标识一个边，第三个字段是边的权重：
g.add_weighted_edges_from([(1,2,0.125),(1,3,0.75),(2,4,1.2),(3,4,0.375)])
在增加边时，也可以一次增加多条边，为不同的边设置不同的属性：
g.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
2，查看边的属性
查看边的属性，就是查看边的数据(data)，查看所有边及其属性：
g.edges(data=True)
EdgeDataView([(1, 2, {}), (1, 3, {}), (2, 3, {})])
查看特定的边的信息有两种方式：
g[1][2]
g.get_edge_data(1,2)
{'weight': 0.125, 'relationship': 'renew', 'color': 'blue'}
3，删除边
边是两个顶点的ID属性构成的元组，通过 edge=(node1,node2) 来标识边，进而从图中找到边：
g.remove_edge(edge)
g.remove_edges_from(edges_list)
4，更新边的属性
通过边来更新边的属性，由两种方式，一种是使用update函数，一种是通过属性赋值来实现：
g[1][2]['weight'] = 4.7
g.edge[1][2]['weight'] = 4
g[1][2].update({"weight": 4.7})
g.edges[1, 2].update({"weight": 4.7})   
5，删除边的属性
通过 del命令来删除边的属性
del g[1][2]['name']
6，检查边是否存在
检查一条边是否存在于图中
g.has_edge(1,2)

节点和边绘制有向图和无向图如下：

注：左图表示有向图，黑色加粗部分表示边的方向。右图表示无向图没有方向之分。图的显示还有两个比较好用的工具就是Cytoscape和Gephi也比较好用，显示图像方便又美观，其中Cytoscape可以读取CSV文件，可以对图进行拖拽。感兴趣的朋友可以研究一下。

2求图的常用属性

1. 读取CSV文件获取图的边集合列表
   部分原始数据如图：
   
2. 计算图的各种属性
   整体图，看到所有人都是有联系的，由于人物比较多，所以图显示不出具体的效果。
   
   图：整体关系图
   计算属性代码如下：

# -*- coding: utf-8 -*-

import re
import networkx as nx
import matplotlib.pyplot as plt

def create_graph():

    G = nx.Graph()
    # G = nx.DiGraph()
    G.add_node(0) # 添加一个节点
    G.add_nodes_from([1, 2])# 一次添加多个节点
    G.add_edge(0, 1) # 添加一条边
    G.add_edge(2, 3) # 如果边的节点已经存在，直接覆盖
    G.add_edge(4, 5) # 如果边的节点不存在，则添加新节点
    G.add_edges_from([(2, 1), (5, 1), (0, 4), (3, 4)]) #添加多条边
    nx.draw(G, pos=nx.spring_layout(G), with_labels=True)
    plt.show()

def read_nodes(filename):

    '''读取文件，获取边列表'''
    edges_list = []
    with open(filename, 'r') as f:
        while True:
            line = f.readline()
            if line:
                line = re.sub('\r\n', '', line)
                lines = line.split(',')
                edges_list.append((lines[0], lines[1]))
                edges_list.append((lines[1], lines[0]))
            else:
                break
    return edges_list

'''注：因为networkx中求最大连通子图的实现都是基于有向图的，所以在读取数据的时候，添加边的时候都是双向的，这样保证求出来的最大连通子图和无向图是一样的。'''

def get_graph_attr(edges):
    # 1根据边的列表创建无向图
    G = nx.DiGraph()
    G.add_edges_from(edges)
    # 2 查看图中的节点有多少个
    nodes = G.nodes()
    print(len(nodes)) # 107
    # 2 求无向图的最大连通子图
    max_component = max(nx.strongly_connected_component_subgraphs(G), key=len)# 最大连通子图
    print(len(max_component.nodes())) # 107最大连通子图就是本身
    # 3 将图转换为无向图
    G = nx.to_undirected(max_component)
    # 4 计算图中节点的度,按大小排序
    degrees = G.degree() # 所有节点的度
    print(sorted(degrees, key=lambda x:x[1], reverse=True))
    # 5 计算图的偏心距和直径以及半径
    eccdis = nx.eccentricity(G) # 偏心距
    print(eccdis)
    diamter = max(eccdis.values()) # 直径
    radius = min(eccdis.values()) # 半径
    print(diamter, radius) # 6, 3
    #5 计算图中节点的最短路径
    path = nx.shortest_path(G, source='Jon')# 查看谁到谁的最短路径
    print(path)
    path_length = nx.shortest_path_length(G, source='Jon')# 查看最短路径的长度
    print(path_length)
    #6 计算图中节点的紧密中心性
    close = nx.closeness_centrality(G)#紧密中心性
    print(close)
    # 7 介数中心性
    jie = nx.betweenness_centrality(G)
    print(jie)
    # 度中心性,一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。
    deg_cen = nx.degree_centrality(G)
    print(deg_cen)
    # 特征向量中心性
    eig_cen = nx.eigenvector_centrality(G)
    print(eig_cen)


if __name__=='__main__':

    filename = './inputdata/stormofswords.csv'
    edges = read_nodes(filename)
    get_graph_attr(edges)

3.1Louvain算法原理

Louvain算法是基于模块度的社区发现算法，该算法在效率和效果上都表现较好，并且能够发现层次性的社区结构，其优化目标是最大化整个社区网络的模块度。

模块度：
模块度是评估一个社区网络划分好坏的度量方法，它的物理含义是社区内节点的连边数与随机情况下的边数只差，它的取值范围是 [−1/2,1)其公式如下：

其中，Aij节点i和节点j之间边的权重，网络不是带权图时，所有边的权重可以看做是1；ki=∑jAij表示所有与节点i相连的边的权重之和（度数）；ci表示节点i所属的社区；m=12∑ijAij表示所有边的权重之和（边的数目）。公式中Aij−kikj2m=Aij−kikj2m，节点j连接到任意一个节点的概率是kj2m，现在节点i有ki的度数，因此在随机情况下节点i与j的边为kikj2m.

算法步骤：
1）将图中的每个节点看成一个独立的社区，次数社区的数目与节点个数相同；

2）对每个节点i，依次尝试把节点i分配到其每个邻居节点所在的社区，计算分配前与分配后的模块度变化ΔQ，并记录ΔQ最大的那个邻居节点，如果maxΔQ>0，则把节点i分配ΔQ最大的那个邻居节点所在的社区，否则保持不变；

3）重复2），直到所有节点的所属社区不再变化；

4）对图进行压缩，将所有在同一个社区的节点压缩成一个新节点，社区内节点之间的边的权重转化为新节点的环的权重，社区间的边权重转化为新节点间的边权重；

5）重复1）直到整个图的模块度不再发生变化。

图：算法过程图

3.2社团划分实践

需要安装包
pip3 install python-louvain
pip3 install networkx
测试数据集
我们下载使用 astro-gh数据集。
测试代码

import community
from community import community_louvain
data = "./data/astro-ph/astro-ph.gml"
Graph=nx.read_gml(data)
# network2.x的图划分
part = community_louvain.best_partition(Graph)
# network1.x的图划分
part =community.best_partition(Graph)

测试代码2

import community
import networkx as nx
import matplotlib.pyplot as plt

#better with karate_graph() as defined in networkx example.
#erdos renyi don't have true community structure
#G = nx.erdos_renyi_graph(30, 0.05)
data = "./data/astro-ph/astro-ph.gml"
G=nx.read_gml(data)

#first compute the best partition
partition = community.best_partition(G)
#drawing
size = float(len(set(partition.values())))
pos = nx.spring_layout(G)
count = 0.
for com in set(partition.values()) :
    count = count + 1.
    list_nodes = [nodes for nodes in partition.keys()
                                if partition[nodes] == com]
    nx.draw_networkx_nodes(G, pos, list_nodes, node_size = 20,
                                node_color = str(count / size))
nx.draw_networkx_edges(G, pos, alpha=0.5)
plt.show()

参考连接
复杂网络社区发现算法python实战准备.
Python包 - networkx
LOUVAIN——社交网络挖掘之大规模网络的社区发现算法
基于networkx分析Louvain算法的社团网络划分
networkx整理