一、 图的表示
1.1 按方向划分图表示
图是由点和边构成的，它可以分为两种表示方法分别是： 1. 有向图 2. 无向图
1.2 用邻接矩阵来表示图
1.3 图像的度
图像的度分为两种：1. 有向图的度 2. 无向图的度
①度 可以理解为点之间的连接线 ②入度指向当前节点的连线， 出度当前节点连出去的连线
二、 图的特性
2.1 子图（subgraph）
子图表示某张图的子集
2.2 连通图 (connected graph)
对于一个无向图，如果任意的节点i能够通过一些边达到节点j，则称之为连通图
其中对于图中任意两点都可以相互到达，我们称之为强连通图，反之称为弱连通图。
2.3 连通分量（connected component）
可以理解为所有的连通在一起的图算一个连通分量。如上图左边连通分量是1， 右边连通分量是2。
2.4 最短路径 (shortest path)
图中的两个节点所能达到的最短路径。
2.5 图直径 (diameter)
图中的两两节点最短路径最大的值称之为图直径。
三、图中心性
在图论和网络分析中，中心性（Centrality）是判断网络中节点重要性/影响力的指标。在社会网络分析中，一项基本的任务就是鉴定一群人中哪些人比其他人更有影响力，从而帮助我们理解他们在网络中扮演的角色。
3.1 度中心性（degree centrality）
公式：
重要的节点就是拥有许多连接的节点， 你的社会关系越多， 你的影响力就越强
3.2 特征向量中心性 （eigenventor centrality）
思想就是与你连接的人越重要，你也就越重要
3.3 中介中心性 （betweenness centrality）
公式：
中间成员对路径两端的成员具有“更大的人际关系影响”。
3.4 接近中心性 （closeness centrality）
接近中心性高的节点一般扮演的是八婆的角色（gossiper）。他们不一定是名人，但是乐于在不同的人群之间传递消息。
image.png
四、 网页排序算法
4.1 PageRank
4.2 HITS
指出去的为hub， 被指的为authority
总结
点度中心性：一个人的社会关系越多，他/她就越重要
中介中心性：如果一个成员处于其他成员的多条最短路径上，那么该成员就是核心成员
接近中心性：一个人跟所有其他成员的距离越近，他/她就越重要
特征向量中心性：与你连接的人社会关系越多，你就越重要
PageRank：来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转
四、 代码演示：
import numpy as np
import pandas as pd
import networkx as nx
edges = pd.DataFrame()
edges['sources'] = [0,1,2,3,4,4,6,7,7,9,1,4,4,4,6,7,5,8,9,8]
edges['targets'] = [1,4,4,4,6,7,5,8,9,8,0,1,2,3,4,4,6,7,7,9]
#edges['weights'] = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
# source 为起点，target为终点， weight为度
G = nx.from_pandas_edgelist(edges, source='sources',target='targets')
# degree
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,tol=0.00001))
网友评论