1. 图的基础知识

1.1 中心性

1.1.1 度中心性

• 度中心性的计算公式

$$度中心性=\frac{N_{degree}}{n-1}$$

• $N_{degree}$ 是指当前节点的度
• n 是指节点数

1.1.2 特征向量中心性

• 特征向量中心性

  

• 特征向量中心性不仅仅考虑当前节点的度还考虑了和它相邻节点的度

1.1.3 中介中心性

• 中介中心性

$$Betweeness=\frac{其他节点经过该节点的最短路径}{其余两两节点的最短路径经过该节点的个数}$$

• 每条边的长度是 0.5

1.1.4 连接中心性

• 连接中心性

$$
Closeness = \dfrac{n-1}{当前节点到其他节点的最短路径之和} \ \

注意 : n 是节点的个数
$$

1.2 PageRank

• 阻尼系数 :

1.3 HITS

2. 图基本知识代码

2.1 NetWorkX库

• 主要是 networkx 库的基本使用, 计算中心性和PageRank和HIPS值

• 下载 networkx 库

  pip install networkx
  pip install scipy
  

• 下面的基本的使用的代码

  # -*- coding: utf-8 -*-
  # @Time    : 2022/2/28 17:34
  # @Author  : 王天赐
  # @Email   : 15565946702@163.com
  # @File    : graph_base.py
  # @Software: PyCharm
  
  import pandas as pd
  import networkx as nx
  
  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]
  
  # 设置图
  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))
  
  # 中介中心性 : Betweenness
  print("中介中心性 : Betweenness : ", nx.betweenness_centrality(G))
  
  # 连接中心性 : Closeness
  print("连接中心性 : Closeness : ", nx.closeness_centrality(G))
  
  # PageRank值
  print("PageRank : ", nx.pagerank(G))
  
  # HITS
  print("HITS : ", nx.hits(G))