图与节点的基本

图直径：

图中所有的两两节点他们的最短路径的最大值。·

节点的度中心性：

公式Ndegree/(n-1)   也就是该节点的度/(全部的节点-1)

节点的特征向量中心性Eigenvector Centrality：

如果一个节点连接的度越多，其特征向量中心性越大。

中介中心性Betweenness Centrality :

经过该节点的最短路径/其余两两节点的最短路径。

 

先来看曹操的betweenness的计算，分子的第一项：蔡文姬出发到甄姬的最短路径没有经过曹操，所以为0，假设蔡文姬出发去周瑜的最短路径经过曹操所以为1，从蔡文姬出发去夏侯惇的最短路径经过曹操所以为1，从蔡文姬出发前往典韦的最短路径有两条(都是要经过一个人才到)里面有一条是经过曹操的所以其为0.5,所以分子的第一项为(0+1+1+0.5)。分子的第二项：从甄姬出发到蔡文姬的最短路径不经过曹操所以为0，从甄姬出发到典韦的最短路径不经过曹操所以为0，从甄姬出发到周瑜的最短路径经过曹操所以其为1，从甄姬出发到夏侯惇的最短路径经过曹操，所以其为1，所以分子的第二项为(0+0+1+1)。后面的也是同样来类推。来看分母，先是蔡文姬去除了曹操以外的所有人总共有4条最短路径，除了曹操之外总共有5个人，所以分母为5*4

 连接中心性closeness

 

 

计算曹操的closeness:分子是全部节点的个数-1，任意两个节点之间的距离为1，曹操到任意的其他5个人的距离均是为1，所以分母为5。

再计算甄姬的closeness:分子是全部节点的个数-1，甄姬到曹操和蔡文姬的最短路径是1，而到典韦，夏侯惇，周瑜都需要经过曹操，所以最短距离是2。

网页排序算法pageRank

如果一个网页被很多其他网页所链接，那么说明他受到普遍的承认和信赖，那么他的排名就高。PR值越高说明该网页越受欢迎（越重要

假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都只链向A，那么A的PR（PageRank）值将是B，C及D的和。

换句话说，根据链出总数平分一个页面的PR值。

 

 

 

 

 

使用networkx进行计算

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

edges = pd.DataFrame()  #使用pd构造dataframe
edges["sources"] = [1,1,2,2,3,3,4,4,5,5]  #构造源节点列表
edges["targets"] = [2,4,5,3,1,2,5,1,3,4]  #构造目标节点列
edges["weights"] = [1,1,1,1,1,1,1,1,1,1]  #构造边的权重列
#使用pandas来生成图，比如从1出发到2，权重是1，从1出发到4权重也是1
Graph = nx.from_pandas_edgelist(edges,source="sources",target="targets",edge_attr="weights")
print(nx.degree(Graph)) #打印每一个节点的度
print(list(nx.connected_components(Graph))) #打印连通的成分
print(nx.diameter(Graph)) #打印图直径，图上的任意两个相邻的点之间的路径的最大值为图直径
print(nx.degree_centrality(Graph)) #打印度中心性
print(nx.eigenvector_centrality(Graph)) #打印特征向量中心性
print(nx.betweenness_centrality(Graph)) #betweenness_centrality
print(nx.closeness_centrality(Graph)) #closeness_centrality
print(nx.pagerank(Graph)) #pagerank
print(nx.hits(Graph)) #hits