圖論與圖學習(一):圖的基本概念

2021-01-08 機器之心Pro

選自towardsdatascience

作者：Mal Fabien

機器之心編譯

參與：熊貓

圖（graph）近來正逐漸變成機器學習的一大核心領域，比如你可以通過預測潛在的連接來理解社交網絡的結構、檢測欺詐、理解汽車租賃服務的消費者行為或進行實時推薦。近日，數據科學家 Mal Fabien 在其博客上發布了涉及圖論、圖算法和圖學習的系列文章《圖論與圖學習》。

本文是其中第一篇，介紹了圖的一些基礎知識並給出了 Python 示例。更多文章和對應代碼可訪問：https://github.com/maelfabien/Machine_Learning_Tutorials。

本文涵蓋以下主題：

圖是什麼？如何存儲圖？圖的類型和性質Python 示例首先進行一些準備工作，打開 Jupyter Notebook，導入以下軟體包：

後面的文章會使用 networkx 最新的 2.0 版本。networkx 是一個用於複雜網絡的結構、動態和功能的創建、操作和研究的 Python 軟體包。

import numpy as npimport randomimport networkx as nxfrom IPython.display import Imageimport matplotlib.pyplot as plt

我會儘量以實用為目標，努力闡釋每個概念。

圖是什麼？

圖是互連節點的集合。

舉個例子，一個簡單的圖可能是這樣：

節點（node）用紅色標出，通過黑色的邊（edge）連接。

圖可用於表示：

社交網絡網頁生物網絡…我們可以在圖上執行怎樣的分析？

研究拓撲結構和連接性群體檢測識別中心節點預測缺失的節點預測缺失的邊…過幾分鐘你就能明白所有這些概念。

我們首先在我們的筆記本中導入第一個預構建的圖：

# Load the graphG_karate = nx.karate_club_graph()# Find key-values for the graphpos = nx.spring_layout(G_karate)# Plot the graphnx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

空手道圖

這個「空手道」圖表示什麼？Wayne W. Zachary 在 1970 到 1972 年這三年中研究的一個空手道俱樂部的社交網絡。該網絡包含了這個空手道俱樂部的 34 個成員，成員對之間的連接表示他們在俱樂部之外也有聯繫。在研究期間，管理員 JohnA 與教練 Mr.Hi（化名）之間出現了衝突，導致俱樂部一分為二。一半成員圍繞 Mr.Hi 形成了一個新的俱樂部，另一半則找了一個新教練或放棄了空手道。基於收集到的數據，除了其中一個成員，Zachary 正確分配了所有成員在分裂之後所進入的分組。

圖的基本表示方法

圖 G=(V, E) 由下列要素構成：

一組節點（也稱為 verticle）V=1,…,n一組邊 EV×V邊 (i,j) ∈ E 連接了節點 i 和 ji 和 j 被稱為相鄰節點（neighbor）節點的度（degree）是指相鄰節點的數量

節點、邊和度的示意圖

如果一個圖的所有節點都有 n-1 個相鄰節點，則該圖是完備的（complete）。也就是說所有節點都具備所有可能的連接方式。從 i 到 j 的路徑（path）是指從 i 到達 j 的邊的序列。該路徑的長度（length）等於所經過的邊的數量。圖的直徑（diameter）是指連接任意兩個節點的所有最短路徑中最長路徑的長度。舉個例子，在這個案例中，我們可以計算出一些連接任意兩個節點的最短路徑。該圖的直徑為 3，因為沒有任意兩個節點之間的最短路徑的長度超過 3。

一個直徑為 3 的圖

測地路徑（geodesic path）是指兩個節點之間的最短路徑。如果所有節點都可通過某個路徑連接到彼此，則它們構成一個連通分支（connected component）。如果一個圖僅有一個連通分支，則該圖是連通的（connected）。舉個例子，下面是一個有兩個不同連通分支的圖：

一個有兩個連通分支的圖

如果一個圖的邊是有順序的配對，則該圖是有向的（directed）。i 的入度（in-degree）是指向 i 的邊的數量，出度（out-degree）是遠離 i 的邊的數量。

有向圖

如果可以回到一個給定節點，則該圖是有環的（cyclic）。相對地，如果至少有一個節點無法回到，則該圖就是無環的（acyclic）。圖可以被加權（weighted），即在節點或關係上施加權重。如果一個圖的邊數量相比於節點數量較小，則該圖是稀疏的（sparse）。相對地，如果節點之間的邊非常多，則該圖是密集的（dense）。Neo4J 的關於圖算法的書給出了清晰明了的總結：

總結（來自 Neo4J Graph Book）

我們看看如何用 Python 檢索一個圖的這些信息：

n=34G_karate.degree()

.degree() 屬性會返回該圖的每個節點的度（相鄰節點的數量）的列表：

DegreeView({0: 16, 1: 9, 2: 10, 3: 6, 4: 3, 5: 4, 6: 4, 7: 4, 8: 5, 9: 2, 10: 3, 11: 1, 12: 2, 13: 5, 14: 2, 15: 2, 16: 2, 17: 2, 18: 2, 19: 3, 20: 2, 21: 2, 22: 2, 23: 5, 24: 3, 25: 3, 26: 2, 27: 4, 28: 3, 29: 4, 30: 4, 31: 6, 32: 12, 33: 17})

然後，隔離度的值：

# Isolate the sequence of degreesdegree_sequence = list(G_karate.degree())

計算邊的數量，但也計算度序列的度量：

nb_nodes = nnb_arr = len(G_karate.edges())avg_degree = np.mean(np.array(degree_sequence)[:,1])med_degree = np.median(np.array(degree_sequence)[:,1])max_degree = max(np.array(degree_sequence)[:,1])min_degree = np.min(np.array(degree_sequence)[:,1])

最後，列印所有信息：

print("Number of nodes : " + str(nb_nodes))print("Number of edges : " + str(nb_arr))print("Maximum degree : " + str(max_degree))print("Minimum degree : " + str(min_degree))print("Average degree : " + str(avg_degree))print("Median degree : " + str(med_degree))

得到：

Number of nodes : 34Number of edges : 78Maximum degree : 17Minimum degree : 1Average degree : 4.588235294117647Median degree : 3.0

平均而言，該圖中的每個人都連接了 4.6 個人。

我們可以繪出這些度的直方圖：

degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float')plt.figure(figsize=(12, 8))plt.stem(degree_freq)plt.ylabel("Frequence")plt.xlabel("Degre")plt.show()

度的直方圖

我們後面會看到，度的直方圖相當重要，可用於確定我們看到的圖的種類。

如何存儲圖？

你可能會好奇我們如何存儲複雜的圖結構？

存儲圖的方式有三種，取決於你想用它做什麼：

存儲為邊列表：1 21 31 42 33 4...

我們存儲有邊連接的每一對節點的 ID。

使用鄰接矩陣，這通常是在內存中加載的方式：

鄰接矩陣

對於圖中的每一個可能的配對，如果兩個節點有邊相連，則設為 1。如果該圖是無向圖，則 A 是對稱的。

使用鄰接列表：1 : [2,3, 4]2 : [1,3]3: [2, 4]...

最好的表示方式取決於用法和可用的內存。圖通常可存為 .txt 文件。

圖可能包含一些擴展：

加權的邊節點/邊上加標籤加上與節點/邊相關的特徵向量圖的類型

在這一節，我們將介紹兩種主要的圖類型：

Erdos-RényiBarabasi-AlbertErdos-Rényi 模型

定義

在 Erdos-Rényi 模型中，我們構建一個帶有 n 個節點的隨機圖模型。這個圖是通過以概率 p 獨立地在節點 (i,j) 對之間畫邊來生成的。因此，我們有兩個參數：節點數量 n 和概率 p。

Erdos-Rényi 圖

在 Python 中，networkx 軟體包有用於生成 Erdos-Rényi 圖的內置函數。

# Generate the graphn = 50p = 0.2G_erdos = nx.erdos_renyi_graph(n,p, seed =100)# Plot the graphplt.figure(figsize=(12,8))nx.draw(G_erdos, node_size=10)

這會得到類似於下圖的結果：

生成的圖

度分布

令 pk 為隨機選取的節點的度為 k 的概率。由於圖構建所使用的隨機方式，這種圖的度的分布是二項式的：

二項式節點度分布

每個節點的度數量的分布應該非常接近於均值。觀察到高數量節點的概率呈指數下降。

degree_freq = np.array(nx.degree_histogram(G_erdos)).astype('float')plt.figure(figsize=(12, 8))plt.stem(degree_freq)plt.ylabel("Frequence")plt.xlabel("Degree")plt.show()

為了可視化該分布，我將所生成的圖中的 n 增大到了 200。

度分布

描述性統計

平均度由 n×p 給出。在 p=0.2 和 n=200 時，中心在 40 左右度期望由 (n1)×p 給出平均值附近的度最多我們用 Python 來檢索這些值：

# Get the list of the degreesdegree_sequence_erdos = list(G_erdos.degree())nb_nodes = nnb_arr = len(G_erdos.edges())avg_degree = np.mean(np.array(degree_sequence_erdos)[:,1])med_degree = np.median(np.array(degree_sequence_erdos)[:,1])max_degree = max(np.array(degree_sequence_erdos)[:,1])min_degree = np.min(np.array(degree_sequence_erdos)[:,1])esp_degree = (n-1)*pprint("Number of nodes : " + str(nb_nodes))print("Number of edges : " + str(nb_arr))print("Maximum degree : " + str(max_degree))print("Minimum degree : " + str(min_degree))print("Average degree : " + str(avg_degree))print("Expected degree : " + str(esp_degree))print("Median degree : " + str(med_degree))

會得到類似這樣的結果：

Number of nodes : 200Number of edges : 3949Maximum degree : 56Minimum degree : 25Average degree : 39.49Expected degree : 39.800000000000004Median degree : 39.5

這裡的平均度和期望度非常接近，因為兩者之間只有很小的因子。

Barabasi-Albert 模型

定義

在 Barabasi-Albert 模型中，我們構建一個有 n 個節點的隨機圖模型，其有一個優先連接（preferential attachment）分量。這種圖可通過以下算法生成：

步驟 1：以概率 p 執行步驟 2，否則執行步驟 3步驟 2：將一個新節點連接到隨機均勻選取的已有節點步驟 3：以與 n 個已有節點成比例的概率將這個新節點連接到這 n 個已有節點這個圖的目標是建模優先連接（preferential attachment），真實世界網絡中常會觀察到這一點。（註：優先連接是指根據各個個體或對象已有的量來分配某個量，這通常會進一步加大優勢個體的優勢。）

在 Python 中，networkx 軟體包有用於生成 Barabasi-Albert 圖的內置函數。

# Generate the graphn = 150m = 3G_barabasi = nx.barabasi_albert_graph(n,m)# Plot the graphplt.figure(figsize=(12,8))nx.draw(G_barabasi, node_size=10)

這會得到類似下圖的結果：

Barabasi-Albert 圖

可以看到，某些節點的度顯然比其它節點多很多！

度分布

令 pk 為隨機選取的節點的度為 k 的概率。則這個度分布遵循冪律：

冪律度分布

這個分布是重尾分布。其中有很多節點的度都很小，但也有相當數量的節點有較高的度。

degree_freq = np.array(nx.degree_histogram(G_barabasi)).astype('float')plt.figure(figsize=(12, 8))plt.stem(degree_freq)plt.ylabel("Frequence")plt.xlabel("Degree")plt.show()

度分布

據說這個分布是無標度的（scale-free），平均度不能提供什麼信息。

描述性統計

如果 α≤2，平均度為一個常量，否則就會發散。最大度遵照以下順序：

# Get the list of the degreesdegree_sequence_erdos = list(G_erdos.degree())nb_nodes = nnb_arr = len(G_erdos.edges())avg_degree = np.mean(np.array(degree_sequence_erdos)[:,1])med_degree = np.median(np.array(degree_sequence_erdos)[:,1])max_degree = max(np.array(degree_sequence_erdos)[:,1])min_degree = np.min(np.array(degree_sequence_erdos)[:,1])esp_degree = (n-1)*pprint("Number of nodes : " + str(nb_nodes))print("Number of edges : " + str(nb_arr))print("Maximum degree : " + str(max_degree))print("Minimum degree : " + str(min_degree))print("Average degree : " + str(avg_degree))print("Expected degree : " + str(esp_degree))print("Median degree : " + str(med_degree))

會得到類似以下的結果：

Number of nodes : 200Number of edges : 3949Maximum degree : 56Minimum degree : 25Average degree : 39.49Expected degree : 39.800000000000004Median degree : 39.5

總結

我們介紹了主要的圖類型以及用於描述圖的最基本的屬性。下一篇文章我們將深入圖分析/算法以及用於分析圖的不同方法。圖可用於：

實時欺詐檢測實時推薦精簡法規遵從性複雜網絡的管理和監控身份和訪問管理社交應用/功能…擴展閱讀：

Neo4j 的圖算法全面指南，Mark Needham & Amy E. Hodler：https://go.neo4j.com/rs/710-RRC-335/images/Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook-EN-US.pdfNetworkx 文檔：https://networkx.github.io/documentation/stable/原文連結：https://towardsdatascience.com/introduction-to-graphs-part-1-2de6cda8c5a5

相關焦點

  • 圖論1.1圖的基本概念
    圖的基本概念圖論起源於一個非常經典的問題——柯尼斯堡（Konigsberg）七橋問題。
  • 2007年度國家精品課程:集合論與圖論
    哈工大報訊  離散教學是計算機科學的重要工具，也是軟體及其應用必不可少的數學工具，內容包括集合論、圖論、近世代數和數理邏輯。我校《集合論與圖論》涵蓋了前兩部分。集合論是整個數學的基礎；圖論可以看成是集合論的一個應用。
  • 一文帶你入門圖論和網絡分析(附Python代碼)
    本文從圖的概念以及歷史講起，並介紹了一些必備的術語，隨後引入了networkx庫，並以一個航班信息數據集為例，帶領讀者完成了一些基本分析。簡介俗話說一圖勝千言。但是「圖」（Graph）說的遠不止於此。以圖形式呈現的數據可視化能幫助我們獲得見解，並基於它們做出更好的數據驅動型決策。
  • 圖論Graph theory
    有關圖論的基本定義，請參閱圖論術語表。Refer to the glossary of graph theory for basic definitions in graph theory.一個圖的圖畫 A drawing of a graph01—定義 Definitions圖論中的定義各不相同。
  • 5月,《圖論》(原書第五版)中譯本來啦
    更重要的是, 增加了關於糾纏(tangle)的一節. 這個概念最先由Robertson 和Seymour 引進, 作為證明圖子式定理的技術工具, 但後來它超越了原來的功能, 成為更基礎的工具：他們定義了一個範例來確定圖中的高連通部分.
  • 應遊戲而生的數學圖論，多棲發展的數學家哈密頓，傳奇人生
    把他與圖論聯繫在一起的是他提出的一個趣味問題：從正十二面體（共有20個頂點）的一個頂點出發，沿著邊行進，把20個頂點無遺漏地全部通過，每一頂點只許過一次而回到原處。問這種走法是否存在。將這一問題略加轉化，哈密頓於1857年發明了著名的週遊世界遊戲，並以25英鎊把這個遊戲賣給一家公司。後來，這一遊戲還進入了市場。
  • plc梯形圖編程實例_plc梯形圖編程基本概念
    plc梯形圖編程中，用到以下四個基本概念： 01軟繼電器 PLC梯形圖中的某些編程元件沿用了繼電器這一名稱，如輸入繼電器、輸出繼電器、內部輔助繼電器等，但是它們不是真實的物理繼電器，而是一些存儲單元（軟繼電器），每一軟繼電器與PLC存儲器中映像寄存器的一個存儲單元相對應
  • 深度| 一文概覽圖卷積網絡基本結構和最新進展
    選自tkipf.github作者：Thomas Kipf機器之心編譯參與：李詩萌、劉曉坤本文介紹了圖卷積網絡的基本結構，和最新的研究進展，並指出了當前模型的優缺點。通過對半監督學習應用 GCN 證明三層 GCN 模型不需要節點的任何特徵描述就可以對只有一個標籤實例的類進行線性分離。
  • 應遊戲而生的數學圖論,多棲發展的數學家哈密頓,傳奇人生
    把他與圖論聯繫在一起的是他提出的一個趣味問題：從正十二面體（共有20個頂點）的一個頂點出發，沿著邊行進，把20個頂點無遺漏地全部通過，每一頂點只許過一次而回到原處。問這種走法是否存在。將這一問題略加轉化，哈密頓於1857年發明了著名的週遊世界遊戲，並以25英鎊把這個遊戲賣給一家公司。後來，這一遊戲還進入了市場。
  • 專訪喬治亞理工宋樂教授:用強化學習為圖論組合優化問題尋找「元...
    專訪喬治亞理工宋樂教授：用強化學習為圖論組合優化問題尋找「元算法」大數據文摘作品，轉載要求見文末作者｜錢天培導讀：從交通優化、信息傳播優化、用戶網絡分析，組合優化這一傳統計算問題在日常應用中無處不在。然而，這類問題往往是NP難題（NP-hard），並需要大量的專業知識和試錯來解決。
  • 搭建圖與網絡之間的橋梁：網絡科學的下一個突破在哪裡？
    在大數據革命的推動下，網絡這一概念已經成為描述對物理、生物和社會現象的無數經驗觀察的強大工具。 與網絡類似，圖是由若干頂點和連接這些頂點的邊構成的圖形，研究圖的數學分支也就是圖論。受社會學和經濟學中開創性研究的啟發，網絡科學從圖論中繼承了其最初的概念。然而自此之後，圖論和網絡科學就分道揚鑣了，無論是它們研究的問題，還是研究它們的學術團體都幾乎沒有重疊。
  • 圖論的各種基本算法
    原標題：圖論的各種基本算法 本篇主要涉及到圖論的基本算法，不包含有關最大流的內容。圖論的大部分算法都是由性質或推論得出來的，想樸素想出來確實不容易。 證明：分為兩種情況，情況一，先搜索到A頂點，情況二，先搜索到B頂點。對於情況一，由命題可得，A一定存儲在B之後，那麼取出時先取出的是頂點A。對於情況二，先搜索到B頂點，由於B頂點搜索不到A頂點，則A一定存儲在B之後，那麼取出時仍先取出的是頂點A，命題得證。
  • 讀懂概率圖模型:你需要從基本概念和參數估計開始
    文章從基礎的概念開始談起，並加入了基礎的應用示例來幫助初學者理解概率圖模型的實用價值。機器之心對該文章進行了編譯介紹。第一部分：基本術語和問題設定機器學習領域內很多常見問題都涉及到對彼此相互獨立的孤立數據點進行分類。比如：預測給定圖像中是否包含汽車或狗，或預測圖像中的手寫字符是 0 到 9 中的哪一個。事實證明，很多問題都不在上述範圍內。
  • 深度學習 vs. 概率圖模型 vs. 邏輯學
    以下為正文：今天，我們一起來回顧過去50年人工智慧（AI）領域形成的三大範式：邏輯學、概率方法和深度學習。如今，無論依靠經驗和「數據驅動」的方式，還是大數據、深度學習的概念，都已經深入人心，可是早期並非如此。
  • 思維導圖用得好,提高孩子學習效率,一起來了解思維導圖!
    在這裡介紹常見八種思維導圖：圓圈圖（Circle Map） ：主要用於把一個主題展開來，聯想或描述細節樹狀圖（Tree Map） ：用這種圖來整理歸納一些知識氣泡圖（Bubble Map） ：學習知識、描述事物雙重氣泡圖（Double Bubble Map）：對兩個事物做比較和對照，找到它們的差別和共同點。
  • 思維導圖:化學學習小助手
    思維導圖是一種圖形工具，也可以稱之為思維地圖或者樹枝圖、概念地圖等，通過思維導圖的圖文技巧，可以設置關鍵詞，通過線條、顏色等將關鍵詞與各個分支線條建立記憶連結，將知識的不同聯繫利用層次圖表現出來。思維導圖對於大腦的記憶十分有幫助，可以充分發揮大腦的想像力，通過知識建構過程形成一個知識網絡資料庫，當用到的時候可以很快調用。九年級的化學知識點多，可以每個單元構建一個思維導圖，或者構建某種物質思維導圖將不同單元的知識快速聯繫在一起，快速確定不同知識之間的聯繫。
  • 簡單圖神經網絡(GNN)的基礎知識
    在社交網絡分析等一些應用中，圖神經網絡已經得到了廣泛的應用。新加坡科技研究局（A*STAR）的研究者 Rishabh Anand 近日通過圖解的方式介紹了圖與圖神經網絡的基本概念，或許能幫助初學者更直觀地理解圖神經網絡的內涵和價值。
  • 離散數學是近年來產生的一門新課程,它是現代數學的一個重要分支
    離散數學是近幾十年來產生的一門新課程，它是現代數學的一個重要分支，是計算機科學中專業基礎理論的核心課程，其整個內容體系都是圍繞計算機可以接受和處理的數據對象展開研究，並隨著計算機科學的發展而逐步發展、逐步完善和逐步深入。
  • 沒有完整圖時,如何使用圖深度學習?你需要了解流形學習2.0版本
    在生物學中尤其如此，諸如蛋白質 - 蛋白質相互作用的圖只有部分已知，因為發現蛋白質相互作用的實驗費用昂貴，而且噪聲很大。因此，研究者從數據中推斷出圖並在其上應用 GNN，並將其稱為「潛圖學習」。潛圖學習特定於應用，並針對下遊任務進行了優化。此外，有時這樣的圖可能比任務本身更重要，因為它可以傳達關於數據的重要洞察，並提供解釋結果的方法。潛圖學習是學習具有空邊集的圖。
  • 你還分不清認知地圖、思維導圖、概念圖?
    本文筆者將與大家介紹較為流行的三種圖標方式——認知地圖、思維導圖、概念圖在用農戶研究中的應用。認知地圖、概念圖和思維導圖都是繪圖技術，可以在整個用戶研究的過程中來可視化知識和概念之間的表面關係。認知映射、思維映射和概念映射是組織、溝通和學習知識的三種強大的可視化映射策略。它們幫助我們提出複雜的想法、過程，並識別其中的模式和關係。