图神经网络基本知识

深碍√TFBOYSˉ_ 2022-09-07 12:09 285阅读 0赞

# 连通图 连通分量 #

## 1.无向图连通性 ##

对于一个无向图，如果任意的节点`i`能够通过一些边到达节点`j`，则称之为连通图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]

![撒地方][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]  
连通分量：无向图`G`的一个极大连通子图称为`G`的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

## 2.有向图连通性 ##

*  强连通图：给定有向图`G=(V,E)`，并且给定该图`G`中的任意两个节点`u`和`v`，如果节点`u`和节点`v`相互可达，即至少存在一条路径可以由节点`u`开始，到终点节点`v`结束，那么就称该有向图`G`是强连通图。
 *  弱连通图：若至少有一对节点不满足单向连通，但去掉边的方向后从无向图的观点看是连通图，则`G`称为弱连通图。

# 图直径 #

图中的任意两两节点之间的最短路径的最大的值，即为图直径。

# 度中心性 #

度 中 心 性 = N d e g r e e n − 1 度中心性=\\frac\{N\_\{degree\}\}\{n-1\} 度中心性=n−1Ndegree，n表示节点数量。

# 特征向量中心性Eigenvetor Centrality #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 2]  
对图的邻接矩阵，求出图的特征值和特征向量。  
上图中可以看到`v4`节点的特征向量中心性比`v3和v2`节点的特征向量中心性大，虽然它们两个节点的度都为2。原因是特征向量中心性不仅考虑了本节点的度，同时也考虑了邻居节点的度。  
一个节点的重要性既取决于其邻居节点的数量（即该节点的度），也取决于其邻居节点的重要性。

# 中介中心性Betweenness Centrality #

以经过某个节点的最短路径数目来刻画节点重要性的指标。  
 B e t w e e n n e s s = 经 过 该 节 点 的 最 短 路 径 其 余 两 两 节 点 的 最 短 路 径 Betweenness=\\frac\{经过该节点的最短路径\}\{其余两两节点的最短路径\} Betweenness=其余两两节点的最短路径经过该节点的最短路径

这个度量很有意思。这个有点像是我们身边那种社交达人，我们认识的不少朋友可能都是通过他/她认识的，这个人起到了中介的作用。

中介中心性指的是一个结点担任其它两个结点之间最短路的桥梁的次数。一个结点充当“中介”的次数越高，它的中介中心度就越大。如果要考虑标准化的问题，可以用一个结点承担最短路桥梁的次数除以所有的路径数量。

# 连接中心性Closeness #

C l o s e n e s s = n − 1 节 点 到 其 他 节 点 最 短 路 径 之 和 Closeness = \\frac\{n-1\}\{节点到其他节点最短路径之和\} Closeness=节点到其他节点最短路径之和n−1

对于了解图论的朋友而言，最短路这个概念一定不陌生。我们设想一个实际生活中的场景，比如你要建一个大型的娱乐商场，你可能会希望周围的顾客到达这个商场的距离都可以尽可能地短。这个就涉及到连接中心性的概念，连接中心性的值为路径长度的倒数。

连接中心性需要考量每个结点到其它结点的最短路的平均长度。也就是说，对于一个结点而言，它距离其它结点越近，那么它的中心度越高。一般来说，那种需要让尽可能多的人使用的设施，它的连接中心度一般是比较高的。

# PageRank #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 3]  
包括边的PageRank值和节点的PageRank。

# HITS #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 4]

# 举例 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 5]

# 代码实现 #

import numpy as np
    import pandas as pd
    import networkx as nx
    np.set_printoptions(suppress=True)
    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]
    
    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(np.array(nx.adjacency_matrix(G).todense()))
    eigenvalue, featurevector=np.linalg.eig(np.array(nx.adjacency_matrix(G).todense()))
    print('特征值', eigenvalue.tolist())
    print('特征向量', featurevector.tolist())
    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))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]: /images/20220829/7c6edd7f8d7b4a58bd8aa0a0e7afd38b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]: /images/20220829/68a4d59f9b2d43f4a4934899da52726a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 2]: /images/20220829/a1704c1667b1497cbb2fc4935780303c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 3]: /images/20220829/3c34e4cebec545289117a57e88d3fd0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 4]: /images/20220829/8be1b66df68d410a8eef8361c0b7a8ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 5]: /images/20220829/305e61ef4ff24421a1dba66de32f561c.png