[人工智能]图论基础知识

graph：

邻接矩阵（adjacency）:

adjacency=[ [0,1,1,0,0,0],
            [1,0,1,1,0,0],
            [1,1,0,1,1,0],
            [0,1,1,0,1,1],
            [0,0,1,1,0,0],
            [0,0,0,1,0,0]
            ]

度 （degree）：
无向图的度： A：2；B：3
有向图：分为入度和出度

连通图和非连通图

最短路径

度中心性
度中心性=该点的degree / n-1

特征向量中心性（eigenvector）

中介中心性（betweens）

连接中心性

HITS
区别好箭头指向即可

#使用pandas初始化图包括起始点，末尾点，关系权重

import networkx as nx
import pandas as pd
import numpy as np

edges=pd.DataFrame()
edges['sources']=[1,1,1,2,2,3,3,4,4,5,5,5]
edges['targets']=[2,4,5,3,1,2,5,1,5,1,3,4]
edges['weights']=[1,1,1,1,1,1,1,1,1,1,1,1]
print(edges)

    sources  targets  weights
0         1        2        1
1         1        4        1
2         1        5        1
3         2        3        1
4         2        1        1
5         3        2        1
6         3        5        1
7         4        1        1
8         4        5        1
9         5        1        1
10        5        3        1
11        5        4        1

使用networkx包生成图

G=nx.from_pandas_edgelist(edges,source='sources',target='targets',edge_attr='weights')
print(G)

得到：

Graph with 5 nodes and 6 edges

#degree
print(nx.degree(G))
#图直径
print(nx.diameter(G))
#连通分量
print(list(nx.connected_components(G)))
#度中心性
print(nx.degree_centrality((G)))
#特征向量中心性
print(nx.eigenvector_centrality(G))
#betweeness
print(nx.betweenness_centrality(G))
#pagerank
print(nx.pagerank(G))
#HITS
print(nx.hits(G))

[(1, 3), (2, 2), (4, 2), (5, 3), (3, 2)]
2
[{1, 2, 3, 4, 5}]
{1: 0.75, 2: 0.5, 4: 0.5, 5: 0.75, 3: 0.5}
{1: 0.5298988890761731, 2: 0.35775191431708964, 4: 0.4271316779596084, 5: 0.5298988890761731, 3: 0.35775191431708964}
{1: 0.25, 2: 0.08333333333333333, 4: 0.0, 5: 0.25, 3: 0.08333333333333333}