連通圖 連通分量

1.無向圖連通性

對于一個無向圖，如果任意的節(jié)點i能夠通過一些邊到達(dá)節(jié)點j，則稱之為連通圖。

連通分量：無向圖G的一個極大連通子圖稱為G的一個連通分量（或連通分支）。連通圖只有一個連通分量，即其自身；非連通的無向圖有多個連通分量。

2.有向圖連通性

• 強連通圖：給定有向圖G=(V,E)，并且給定該圖G中的任意兩個節(jié)點u和v，如果節(jié)點u和節(jié)點v相互可達(dá)，即至少存在一條路徑可以由節(jié)點u開始，到終點節(jié)點v結(jié)束，那么就稱該有向圖G是強連通圖。
• 弱連通圖：若至少有一對節(jié)點不滿足單向連通，但去掉邊的方向后從無向圖的觀點看是連通圖，則G稱為弱連通圖。

圖直徑

圖中的任意兩兩節(jié)點之間的最短路徑的最大的值，即為圖直徑。

度中心性

$度中心性=\frac{N_{degree}}{n?1}$，n表示節(jié)點數(shù)量。

特征向量中心性Eigenvetor Centrality

對圖的鄰接矩陣，求出圖的特征值和特征向量。
上圖中可以看到v4節(jié)點的特征向量中心性比v3和v2節(jié)點的特征向量中心性大，雖然它們兩個節(jié)點的度都為2。原因是特征向量中心性不僅考慮了本節(jié)點的度，同時也考慮了鄰居節(jié)點的度。
一個節(jié)點的重要性既取決于其鄰居節(jié)點的數(shù)量（即該節(jié)點的度），也取決于其鄰居節(jié)點的重要性。

中介中心性Betweenness Centrality

以經(jīng)過某個節(jié)點的最短路徑數(shù)目來刻畫節(jié)點重要性的指標(biāo)。
$$Betweenness=\frac{經(jīng)過該節(jié)點的最短路徑}{其余兩兩節(jié)點的最短路徑}$$

這個度量很有意思。這個有點像是我們身邊那種社交達(dá)人，我們認(rèn)識的不少朋友可能都是通過他/她認(rèn)識的，這個人起到了中介的作用。

中介中心性指的是一個結(jié)點擔(dān)任其它兩個結(jié)點之間最短路的橋梁的次數(shù)。一個結(jié)點充當(dāng)“中介”的次數(shù)越高，它的中介中心度就越大。如果要考慮標(biāo)準(zhǔn)化的問題，可以用一個結(jié)點承擔(dān)最短路橋梁的次數(shù)除以所有的路徑數(shù)量。

連接中心性Closeness

$$Closeness=\frac{n?1}{節(jié)點到其他節(jié)點最短路徑之和}$$

對于了解圖論的朋友而言，最短路這個概念一定不陌生。我們設(shè)想一個實際生活中的場景，比如你要建一個大型的娛樂商場，你可能會希望周圍的顧客到達(dá)這個商場的距離都可以盡可能地短。這個就涉及到連接中心性的概念，連接中心性的值為路徑長度的倒數(shù)。

連接中心性需要考量每個結(jié)點到其它結(jié)點的最短路的平均長度。也就是說，對于一個結(jié)點而言，它距離其它結(jié)點越近，那么它的中心度越高。一般來說，那種需要讓盡可能多的人使用的設(shè)施，它的連接中心度一般是比較高的。

PageRank

包括邊的PageRank值和節(jié)點的PageRank。

HITS

舉例

代碼實現(xiàn)

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))

總結(jié)

以上是生活随笔為你收集整理的图神经网络基本知识的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。