---

一、图的表示

1.1 什么是图？

图是由点和边组成的数据结构

二、图的特征

2.1 子图

2.2 连通分量

无向图G的一个极大连通子图称为G的一个连通分量（连通分支）。连通图只有一个连通分量，即其自身；非连通图的无向图有多个连通分量

2.3 接通图

2.3.1 无向图连通图

对于一个无向图，如果任意的节点i能够到达另一个节点j，则称之为连通图

2.3.2 有向连通图

2.4 最短路径

图上一点到另一点的最短路径

2.5 图直径

图中两节点的最短路径的最大值

三、图中心性

3.1 度中心性

3.2 特征向量中心性

3.3 中介中心性

3.4 连接中心性

四、网页排序算法

4.1 PageRank

4.2 HITS

4.3 例子

五、代码实现

import pandas as pd
import networkx as nxedges = 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]
G = nx.from_pandas_edgelist(edges, source='sources', target='targets', edge_attr='weights')print("度:", nx.degree(G))
print("连通分量:", list(nx.connected_components(G)))
print("图直径:", nx.diameter(G))print("度中心性:", nx.degree_centrality(G))
print("特征向量中心性:", nx.eigenvector_centrality(G))
print("Betweeness:", nx.betweenness_centrality(G))
print("Closedness:", nx.closeness_centrality(G))print("PageRank:",nx.pagerank(G))
print("HITS:",nx.hits(G))

输出：

度: [(1, 3), (2, 2), (4, 2), (5, 3), (3, 2)]
连通分量: [{1, 2, 3, 4, 5}]
图直径: 2
度中心性: {1: 0.75, 2: 0.5, 4: 0.5, 5: 0.75, 3: 0.5}
特征向量中心性: {1: 0.529898889076173, 2: 0.35775191431708964, 4: 0.4271316779596083, 5: 0.5298988890761731, 3: 0.35775191431708964}
Betweeness: {1: 0.25, 2: 0.08333333333333333, 4: 0.0, 5: 0.25, 3: 0.08333333333333333}
Closedness: {1: 0.8, 2: 0.6666666666666666, 4: 0.6666666666666666, 5: 0.8, 3: 0.6666666666666666}
PageRank: {1: 0.24369622576677993, 2: 0.1722562971205864, 4: 0.16809495422526696, 5: 0.24369622576677993, 3: 0.1722562971205864}
HITS: ({1: 0.24059715204600776, 2: 0.162434564716677, 4: 0.19393656647463048, 5: 0.24059715204600784, 3: 0.16243456471667694}, {1: 0.24059715204600784, 2: 0.16243456471667692, 4: 0.1939365664746304, 5: 0.24059715204600773, 3: 0.16243456471667697})