社群偵測是網路分析的核心任務，旨在識別緊密連結的節點群組。本文探討了根據模組度最大化的貪婪演算法和根據邊介數的 Girvan-Newman 演算法，並以 Zachary 空手道俱樂部和線上社交網路為例，示範如何在 Python 中使用 NetworkX 函式庫執行社群偵測。程式碼涵蓋了社群識別、節點與邊屬性設定，以及根據社群劃分結果進行視覺化呈現的完整流程。同時，文章也介紹了派系和 K 核心的概念，作為理解網路密集區域的補充方法，並討論了社會網路分析中的強弱連結、小世界問題和資訊傳播等相關概念，提供更廣泛的網路分析視角。
社群偵測與視覺化：以 Zachary 空手道俱樂部與線上社交網路為例
在複雜網路分析中，社群偵測是一項重要的任務，旨在識別網路中緊密連結的節點群組。模組度（Modularity）是一種廣泛使用的衡量指標，用於評估社群劃分的品質。本文將介紹如何使用 NetworkX 函式庫中的貪婪模組度社群偵測演算法（Clauset-Newman-Moore community detection）來分析 Zachary 空手道俱樂部網路與線上社交網路，並視覺化社群結構。
模組度最大化與貪婪演算法
模組度衡量社群內部的邊緣密度是否高於社群之間的邊緣密度。尋找最大模組度的社群劃分是一個計算困難的問題，但貪婪演算法提供了一個有效的近似解。NetworkX 中的 greedy_modularity_communities() 函式實作了 Clauset-Newman-Moore 社群偵測演算法。
程式碼範例：Zachary 空手道俱樂部網路
import networkx as nx
# 生成 Zachary 空手道俱樂部網路
G_karate = nx.karate_club_graph()
# 使用貪婪模組度社群偵測演算法找出社群
communities = sorted(nx.community.greedy_modularity_communities(G_karate), key=len, reverse=True)
# 列印社群數量
print(len(communities))
內容解密：
nx.karate_club_graph()生成 Zachary 空手道俱樂部網路，這是一個經典的社交網路資料集。nx.community.greedy_modularity_communities(G_karate)使用貪婪模組度社群偵測演算法找出網路中的社群。sorted(..., key=len, reverse=True)將社群按照大小排序，大的社群排在前面。len(communities)列印出社群的數量。
社群視覺化
為了視覺化社群結構，我們需要定義一些輔助函式來設定節點和邊緣的社群屬性，並根據社群屬性賦予不同的顏色。
程式碼範例：視覺化 Zachary 空手道俱樂部網路中的社群
def set_node_community(G, communities):
for c, v_c in enumerate(communities):
for v in v_c:
G.nodes[v]['community'] = c + 1
def set_edge_community(G):
for v, w in G.edges:
if G.nodes[v]['community'] == G.nodes[w]['community']:
G.edges[v, w]['community'] = G.nodes[v]['community']
else:
G.edges[v, w]['community'] = 0
def get_color(i, r_off=1, g_off=1, b_off=1):
r0, g0, b0 = 0, 0, 0
n = 16
low, high = 0.1, 0.9
span = high - low
r = low + span * (((i + r_off) * 3) % n) / (n - 1)
g = low + span * (((i + g_off) * 5) % n) / (n - 1)
b = low + span * (((i + b_off) * 7) % n) / (n - 1)
return (r, g, b)
# 設定節點和邊緣的社群屬性
set_node_community(G_karate, communities)
set_edge_community(G_karate)
# 根據社群屬性設定顏色
node_color = [get_color(G_karate.nodes[v]['community']) for v in G_karate.nodes]
external = [(v, w) for v, w in G_karate.edges if G_karate.edges[v, w]['community'] == 0]
internal = [(v, w) for v, w in G_karate.edges if G_karate.edges[v, w]['community'] > 0]
internal_color = [get_color(G_karate.edges[e]['community']) for e in internal]
# 視覺化網路
karate_pos = nx.spring_layout(G_karate)
nx.draw_networkx(G_karate, pos=karate_pos, node_size=0, edgelist=external, edge_color="#333333")
nx.draw_networkx(G_karate, pos=karate_pos, node_color=node_color, edgelist=internal, edge_color=internal_color)
內容解密：
set_node_community()和set_edge_community()設定節點和邊緣的社群屬性。get_color()根據社群編號生成顏色。node_color、external、internal和internal_color分別儲存節點顏色、外部邊緣、內部邊緣和內部邊緣顏色的列表。- 使用
nx.draw_networkx()分兩次繪製網路：第一次繪製外部邊緣，第二次繪製節點和內部邊緣。
線上社交網路的社群偵測與視覺化
同樣的演算法和視覺化方法可以應用於更大的線上社交網路。
程式碼範例：線上社交網路
from pathlib import Path
# 載入線上社交網路資料
data_dir = Path('.') / 'data'
G_social = nx.read_edgelist(data_dir / 'mcauley2012' / 'facebook_combined.txt')
# 使用貪婪模組度社群偵測演算法找出社群
communities = sorted(nx.community.greedy_modularity_communities(G_social), key=len, reverse=True)
# 設定節點和邊緣的社群屬性，並視覺化網路
set_node_community(G_social, communities)
set_edge_community(G_social)
external = [(v, w) for v, w in G_social.edges if G_social.edges[v, w]['community'] == 0]
internal = [(v, w) for v, w in G_social.edges if G_social.edges[v, w]['community'] > 0]
internal_color = [get_color(G_social.edges[e]['community']) for e in internal]
pos = nx.spring_layout(G_social, k=0.1)
nx.draw_networkx(G_social, pos=pos, node_size=0, edgelist=external, edge_color="#333333", alpha=0.2, with_labels=False)
nx.draw_networkx(G_social, pos=pos, node_size=0, edgelist=internal, edge_color=internal_color, alpha=0.05, with_labels=False)
內容解密：
- 使用
nx.read_edgelist()載入線上社交網路資料。 - 其餘步驟與 Zachary 空手道俱樂部網路的分析類別似。
社群分析：揭露網路中的隱藏結構
在探討複雜網路的結構時，社群分析扮演著至關重要的角色。社群代表著網路中緊密相連的節點群組，這些群組內部的節點之間的連線比與外部節點的連線更為頻繁。瞭解社群結構有助於我們深入洞察網路的組織方式和資訊傳播的模式。
Girvan-Newman演算法：根據邊介數的社群檢測
Girvan-Newman演算法是一種根據邊介數中心性的社群檢測方法。該演算法透過逐步移除網路中邊介數最高的邊，將網路劃分為不同的社群。邊介數中心性衡量了一條邊在網路中所有最短路徑中的重要程度。
程式碼實作
import networkx as nx
import itertools
# 載入空手道俱樂部網路
G_karate = nx.karate_club_graph()
karate_pos = nx.spring_layout(G_karate)
# 使用Girvan-Newman演算法進行社群檢測
result = nx.community.girvan_newman(G_karate)
communities = next(result)
# 設定節點和邊的社群屬性
def set_node_community(G, communities):
for i, community in enumerate(communities):
for node in community:
G.nodes[node]['community'] = i + 1
def set_edge_community(G):
for v, w in G.edges:
if G.nodes[v]['community'] == G.nodes[w]['community']:
G.edges[v, w]['community'] = G.nodes[v]['community']
else:
G.edges[v, w]['community'] = 0
set_node_community(G_karate, communities)
set_edge_community(G_karate)
# 根據社群屬性設定節點顏色
node_color = [G_karate.nodes[v]['community'] for v in G_karate.nodes]
# 區分內部邊和外部邊
external = [(v, w) for v, w in G_karate.edges if G_karate.edges[v, w]['community'] == 0]
internal = [(v, w) for v, w in G_karate.edges if G_karate.edges[v, w]['community'] > 0]
internal_color = [G_karate.edges[e]['community'] for e in internal]
# 繪製網路圖
nx.draw_networkx(G_karate, pos=karate_pos, node_size=0, edgelist=external, edge_color="#333333", with_labels=False)
nx.draw_networkx(G_karate, pos=karate_pos, node_color=node_color, edgelist=internal, edge_color=internal_color)
內容解密：
- 載入必要的函式庫：首先，我們載入了
networkx用於處理網路資料，以及itertools用於處理迭代器。 - 載入空手道俱樂部網路：使用
nx.karate_club_graph()載入了一個經典的社交網路資料集——空手道俱樂部網路。 - Girvan-Newman演算法應用：透過
nx.community.girvan_newman(G_karate)對網路進行社群檢測，獲得初始的社群劃分。 - 節點和邊的社群屬性設定：定義了兩個函式
set_node_community和set_edge_community來為節點和邊賦予社群屬性。 - 視覺化：根據社群屬性對節點進行著色，並區分內部邊和外部邊進行不同的繪製。
派系（Cliques）：網路中的緊密團體
在網路分析中，派系代表著一群彼此之間都相互連線的節點。這種結構往往是社群的核心部分。
程式碼實作
# 尋找網路中的所有派系
cliques = list(nx.find_cliques(G_karate))
# 找出最大的派系
max_clique = max(cliques, key=len)
# 視覺化最大派系
node_color = [(0.5, 0.5, 0.5) for v in G_karate.nodes()]
for i, v in enumerate(G_karate.nodes()):
if v in max_clique:
node_color[i] = (0.5, 0.5, 0.9)
nx.draw_networkx(G_karate, node_color=node_color, pos=karate_pos)
內容解密：
find_cliques函式：使用nx.find_cliques(G_karate)來找出網路中的所有派系。- 最大派系的識別：透過
max(cliques, key=len)找出最大的派系。 - 視覺化最大派系：將最大派系中的節點以不同的顏色標示出來，以便視覺化區分。
K-核心（K-cores）：密集區域的另一種表示
當網路規模較大時，計算派系可能會變得非常耗時。K-核心提供了一種替代方案，用於識別網路中的密集區域。
K-核心的概念
K-核心是指透過移除所有度小於k的節點後得到的子圖。這種方法可以有效地揭示網路中的密集區域。
社會網路與資訊傳播
網路分析常用於理解群體行為，而社會網路是其中一個重要的研究領域。社會網路是網路科學中研究最久的領域之一，其研究成果對日常生活有直接的影響。本章將介紹社會網路分析的基本概念，包括社會網路的歷史、強弱連結的概念、小世界問題以及資訊傳播等主題。
社會網路的定義與重要性
社會網路的特點是節點代表人，邊代表人與人之間的某種關係。這種關係可以是友誼、溝通，甚至是觀看影片的相似行為。社會網路的研究起源於社會學，早期的社會學家如 Jacob L. Moreno 和 Helen Hall Jennings 開發了社會計量學，為現代社會網路分析奠定了基礎。
社會網路值得特別關注，因為人類的行為模式會形成特定的網路結構，而這種結構對於社會過程（如求職、思想傳播、疾病傳播和健康行為）有重要的影響。
強弱連結
在社會網路中，不同的關係具有不同的強度。衡量這種關係強度的概念稱為連結強度（tie strength）。連結強度反映了人際關係的親密程度或互動頻率。1973 年，社會學家 Mark Granovetter 提出了弱連結的重要性，認為弱連結在連線不同社群方面發揮著關鍵作用。
連結強度的衡量
衡量連結強度的一種方法是觀察節點之間的互動頻率或親密度。以 Zachary 的空手道俱樂部網路為例，可以透過分析成員之間的互動來評估連結強度。
import networkx as nx
# 載入 Zachary 空手道俱樂部網路
G = nx.karate_club_graph()
# 標註成員所屬俱樂部
member_club = [
0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
0, 0, 0, 0, 1, 1, 0, 0, 1, 0,
# ... 其他成員標註
]
連結強度分析
透過分析連結強度，可以瞭解不同社群之間的連線方式。弱連結往往是連線不同社群的橋樑，使得資訊能夠跨越社群傳播。
小世界問題
小世界問題探討的是在大規模網路中，任意兩個節點之間的平均路徑長度相對較短的現象。這一現象表明，即使在龐大的網路中，資訊也可以透過相對較少的步驟傳播到達目標節點。
資訊傳播
資訊傳播是社會網路中的一個重要研究主題。瞭解資訊如何在網路中傳播，可以幫助我們掌握思想、疾病或創新技術的傳播規律。
本章重點解密：
本章主要介紹了社會網路的基本概念，包括其定義、重要性以及強弱連結的概念。同時，還探討了小世界問題和資訊傳播等主題。這些內容對於理解和分析社會網路具有重要意義。透過本章的學習，讀者可以掌握社會網路分析的基本工具和方法，為進一步研究網路科學奠定基礎。