圖論與圖學習（一）：圖的基本概念

選自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 np

import random

import networkx as nx

from IPython。display import Image

import matplotlib。pyplot as plt

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

圖是什麼？

圖是互連節點的集合。

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

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

圖可用於表示：

社交網路

網頁

生物網路

…

我們可以在圖上執行怎樣的分析？

研究拓撲結構和連線性

群體檢測

識別中心節點

預測缺失的節點

預測缺失的邊

…

過幾分鐘你就能明白所有這些概念。

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

# Load the graph

G_karate = nx。karate_club_graph（）

# Find key-values for the graph

pos = nx。spring_layout（G_karate）

# Plot the graph

nx。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 和 j

i 和 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=34

G_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 degrees

degree_sequence = list（G_karate。degree（））

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

nb_nodes = n

nb_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 ： 34

Number of edges ： 78

Maximum degree ： 17

Minimum degree ： 1

Average degree ： 4。588235294117647

Median 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 2

1 3

1 4

2 3

3 4

。。。

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

使用鄰接矩陣，這通常是在記憶體中載入的方式：

鄰接矩陣

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

使用鄰接列表：

1 ： ［2，3， 4］

2 ： ［1，3］

3： ［2， 4］

。。。

最好的表示方式取決於用法和可用的記憶體。圖通常可存為 。txt 檔案。

圖可能包含一些擴充套件：

加權的邊

節點/邊上加標籤

加上與節點/邊相關的特徵向量

圖的型別

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

Erdos-Rényi

Barabasi-Albert

Erdos-Rényi 模型

定義

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

Erdos-Rényi 圖

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

# Generate the graph

n = 50

p = 0。2

G_erdos = nx。erdos_renyi_graph（n，p， seed =100）

# Plot the graph

plt。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 degrees

degree_sequence_erdos = list（G_erdos。degree（））

nb_nodes = n

nb_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）*p

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（“Expected degree ： ” + str（esp_degree））

print（“Median degree ： ” + str（med_degree））

會得到類似這樣的結果：

Number of nodes ： 200

Number of edges ： 3949

Maximum degree ： 56

Minimum degree ： 25

Average degree ： 39。49

Expected degree ： 39。800000000000004

Median 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 graph

n = 150

m = 3

G_barabasi = nx。barabasi_albert_graph（n，m）

# Plot the graph

plt。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 degrees

degree_sequence_erdos = list（G_erdos。degree（））

nb_nodes = n

nb_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）*p

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（“Expected degree ： ” + str（esp_degree））

print（“Median degree ： ” + str（med_degree））

會得到類似以下的結果：

Number of nodes ： 200

Number of edges ： 3949

Maximum degree ： 56

Minimum degree ： 25

Average degree ： 39。49

Expected degree ： 39。800000000000004

Median 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。pdf

Networkx 文件：https：//networkx。github。io/documentation/stable/

原文連結：https：//towardsdatascience。com/introduction-to-graphs-part-1-2de6cda8c5a5