0. 前言

社交網站的崛起是近年來數字媒體領域最活躍的發展趨勢之一，數字社交互動已經融入人們的日常生活中。社交網絡中，用戶既能分享觀點、發布動態與反饋、參與線上活動，又能在社交平臺上展示廣泛的生活興趣。
此外，社交網絡為研究用戶行為、解讀人際互動及預測興趣偏好提供了海量數據資源。將其構建為圖結構(頂點代表人，邊代表連接關系)，便形成了提取有效信息的強大工具。然而，由于涉及大量可變參數，理解驅動社交網絡演變的動態機制是一個復雜問題。
本節將探討如何運用圖論分析社交網絡，并通過機器學習解決鏈接預測和社區發現等實際問題。

1. 數據集分析

本節將使用 SNAP Facebook 公共數據集。該數據集通過收集調查參與者的 Facebook 用戶信息創建，包含 10 位用戶的自我網絡 (ego network)。每位用戶需標注其好友所屬的社交圈子，平均每位用戶標注了 19 個社交圈，每個圈子平均包含 22 位好友。針對每位用戶，數據集收集了以下信息：

• 邊關系：若兩位用戶在 Facebook 互為好友則存在邊連接
• 節點特征：用戶個人資料若具備某項特征則標記為 1，否則為 0。

最終將這 10 個自我網絡合并為統一圖結構供研究使用。

1.1 數據集介紹

數據集主要包含三個可下載文件：facebook.tar.gz、facebook_combined.txt.gz 和 readme-Ego.txt。各文件說明如下：

• facebook.tar.gz：包含每個 ego 用戶的四個文件(共 40 個文件)。文命名格式為 nodeId.extension，其中 nodeId 表示 ego 用戶節點 ID，extension 包括 edges、circles、feat、egofeat 或 featnames：
  • nodeId.edges：包含 nodeId 節點網絡的邊列表
  • nodeId.circles：包含多行記錄(每行對應一個社交圈)，每行由圈子名稱和系列節點 ID 組成
  • nodeId.feat：記錄自我中心網絡中所有節點的特征( 0 表示 nodeId 具備該特征，1 則相反)
  • nodeId.egofeat：包含 ego 用戶的特征
  • nodeId.featname：保存特征名稱列表
• facebook_combined.txt.gz：包含文件 facebook_combined.txt，列出了所有 ego 網絡的邊
• readme-Ego.txt：提供上述文件的詳細說明文檔

在開始任何機器學習任務前，充分熟悉數據集結構至關重要。

1.2 使用 networkx 加載數據集

使用 networkx 加載聚合的 ego 網絡，合并的 ego 網絡以邊列表形式呈現。我們可以通過 networkx 從邊列表創建無向圖：

G = nx.read_edgelist("facebook_combined.txt", create_using=nx.Graph(), nodetype=int)

打印關于圖的基本信息：

print(f"Number of nodes: {G.number_of_nodes()}")
print(f"Number of edges: {G.number_of_edges()}")

輸出如下所示，可以看到聚合網絡包含 4039 個節點和 88234 條邊，其邊數達到節點數的 20 倍以上，表明這是一個連接高度密集的網絡：

Number of nodes: 4039
Number of edges: 88234 

可視化網絡將有助于更好地理解分析對象，使用 networkx 繪制圖：

nx.draw_networkx(G, pos=spring_pos, with_labels=False, node_size=35)

輸出結果如下所示：

可以觀察到存在多個高度互聯的樞紐節點。從社交網絡分析視角來看，這些樞紐節點可能是潛在社交機制作用的結果，深入研究這些機制有助于理解個體社交關系網絡的結構特征。
保存網絡中自我用戶的節點 ID。這些 ID 可從 facebook.tar.gz 壓縮包內的文件中提取。首先，解壓 facebook.tar.gz，解壓后的文件夾名為 facebook，通過獲取每個文件名的第一部分來檢索 ID：

ego_nodes = set([int(name.split('.')[0]) for name in os.listdir("facebook/")])

在下一小節中，我們將通過檢查圖的屬性來深入理解其結構特征，這將幫助我們更清晰地把握其拓撲結構和關鍵特性。

2. 網絡拓撲和社區檢測

理解網絡拓撲結構及節點角色是社交網絡分析的關鍵步驟。在社交網絡中，節點實質上是具有獨特興趣、習慣和行為模式的真實用戶。

2.1 網絡拓撲

(1) 首先，計算同配性 (assortativity)，該指標能揭示用戶是否傾向與連接度相似的節點建立連接：

assortativity = nx.degree_pearson_correlation_coefficient(G)

輸出結果如下：

0.06357722918564912

可以看到，同配性為正值，這表明高度連接的用戶傾向于相互關聯，因為每個社交圈內部的用戶通常存在密集連接。

(2) 傳遞性 (transitivity) 也有助于理解用戶間的連接模式。該指標表示擁有共同好友的兩人本身也是朋友的平均概率：

t = nx.transitivity(G)

輸出結果如下所示：

0.5191742775433075

可以看到，概率大約為 50%，表示兩個有共同好友的用戶既可能建立也可能不存在朋友關系。可以通過計算平均聚類系數得到進一步驗證——該系數可視為傳遞性的另一種定義形式：

aC = nx.average_clustering(G)

輸出結果如下所示：

0.6055467186200876

需要注意的是，聚類系數通常高于傳遞性。這是因為根據定義，該指標更關注低連接度節點——由于這類節點的鄰居對數量有限(即局部聚類系數公式中的分母較小)，其權重會被放大。

(3) 在明確整體拓撲結構后，我們可以進一步探究網絡中每個個體的重要性。正節點重要性最基礎的定義可通過中介中心性 (betweenness centrality) 來衡量——該指標統計經過某節點的最短路徑數量，反映該節點在信息傳播中的樞紐程度：

bC = nx.betweenness_centrality(G)
np.mean(list(bC.values()))

輸出結果如下所示：

0.0006669573568730229

(4) 平均中介中心性較低，這與網絡中大量非橋接節點的存在相符。但通過可視化增強處理，我們能更直觀地觀察關鍵節點。定義一個增強繪制函數來突顯高中介中心性節點：

def draw_metric(G, dct, spring_pos):top = 10max_nodes =  sorted(dct.items(), key = lambda v: -v[1])[:top]max_keys = [key for key,_ in max_nodes]max_vals = [val*300 for _, val in max_nodes]plt.axis("off")nx.draw_networkx(G, pos=spring_pos, cmap='Blues', edge_color=default_edge_color,node_color=default_node_color, node_size=3,alpha=0.4, with_labels=False)nx.draw_networkx_nodes(G, pos=spring_pos, nodelist=max_keys, node_color=enhanced_edge_color,node_size=max_vals)

調用該函數進行繪制：

draw_metric(G, bC, spring_pos)

輸出結果如下所示：

(5) 接下來，計算每個節點的度中心性，該指標與節點的直接連接數相關，能清晰反映節點的本地連接密度：

deg_C = nx.degree_centrality(G)
np.mean(list(deg_C.values()))
draw_metric(G,deg_C,spring_pos)

輸出結果如下所示：

0.010819963503439287

度中心性可視化結果如下所示：

(6) 最后，結算接近中心性 (closeness centrality) 指標。該指標通過計算節點到網絡中所有其他節點的最短路徑平均長度，幫助我們理解節點間的信息傳播效率：

clos_C = nx.closeness_centrality(G)
np.mean(list(clos_C.values()))
draw_metric(G,clos_C,spring_pos)

輸出平均接近中心性：

0.2761677635668376

接近中心性可視化結果如下所示：

通過中心性分析可以發現，每個核心節點似乎都隸屬于某個社區(因為這些核心節點可能對應網絡中的自我中心節點)。尤其值得注意的是存在多個高度互連的節點群(從接近中心性分析中尤為明顯)。因此，我們將在接下來的分析中重點識別這些社區結構。

2.2 社區檢測

在社交網絡分析中，最值得探索的圖結構特征之一就是社區劃分。以 Facebook 為例，用戶的好友關系往往反映生活的不同維度：教育背景好友(中學、大學等)、每周足球活動的伙伴、聚會結識的朋友等。社交網絡分析能夠自動識別這類群體，既可以通過拓撲特性自動推斷，也能結合先驗知識進行半自動劃分。
理想的社區劃分標準是：最小化社區間連接(不同社區成員間的邊)，同時最大化社區內連接(同一社區成員間的邊)：

import communityparts = community.best_partition(G)
values = [parts.get(node) for node in G.nodes()]
n_sizes = [5]*len(G.nodes())
plt.axis("off")
nx.draw_networkx(G, pos=spring_pos, cmap=plt.get_cmap("Blues"),
edge_color=default_edge_color, node_color=values, node_size=n_sizes, with_labels=False)

輸出結果如下所示：

在這個分析階段，也可以探究自我用戶 (ego user) 在已檢測社區中的角色分布，增強這些特殊節點的顯示效果：

for node in ego_nodes:print(node, "is in community number", parts.get(node))n_sizes = [5]*len(G.nodes())
for node in ego_nodes:n_sizes[node] = 250plt.axis("off")
nx.draw_networkx(G, pos=spring_pos, cmap=plt.get_cmap("Blues"), edge_color=default_edge_color, node_color=values, node_size=n_sizes, with_labels=False)# enhance color and size of the ego-nodes
nodes = nx.draw_networkx_nodes(G,spring_pos,ego_nodes,node_color=[parts.get(node) for node in ego_nodes])
nodes.set_edgecolor(enhanced_node_color)

輸出結果如下所示：

可以看到，部分 ego 用戶同屬一個社區，這些用戶在 Facebook 上可能存在真實好友關系，因此他們的自我網絡存在部分重疊。通過對圖結構的分析，可以發現網絡中可識別出若干重要節點，同時這些節點所屬的社群具有明顯邊界特征。