工具学习_社区检测算法
1. 算法概述
社区检测算法（Community Detection Algorithm） 是一类用于在图（网络）中发现节点的聚集结构（即“社区”或“模块”）的算法。社区是指一个图中的一部分节点，它们之间的连接比与其他节点的连接更紧密。这些算法广泛应用于社交网络分析、推荐系统、生物网络、金融市场分析等领域。
2. 常见的社区检测算法
常见的社区检测算法包括，Louvain 算法、Girvan-Newman 算法、Label Propagation 算法、谱聚类算法（Spectral Clustering）、Infomap 算法。
2.1 Louvain 算法
Louvain 算法是一种基于模块度（Modularity）优化的社区检测算法，其核心原理是通过最大化模块度来发现图中的社区结构。该算法以分层方式递归地合并节点和社区，从而提高模块度，直到无法进一步优化。由于其计算速度快、适合大规模网络，Louvain 算法广泛应用于社交网络分析、推荐系统等领域，帮助识别用户群体、兴趣圈或商品聚类。
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
# 1️⃣ 初始化图 G
G = nx.Graph()
# 添加边，构建图的社区结构
edges = [
(1, 2), (2, 3), (3, 4), (4, 1), # 社区 1
(5, 6), (6, 7), (7, 8), (8, 5), # 社区 2
(9, 10), (10, 11), (11, 12), (12, 9), # 社区 3
(4, 5), (8, 9) # 跨社区连接
]
G.add_edges_from(edges)
# 2️⃣ 假设有一个字典记录每个节点的名称和重要性
node_importance = {
1: 0.9, 2: 0.8, 3: 0.7, 4: 0.6,
5: 0.5, 6: 0.4, 7: 0.3, 8: 0.2,
9: 0.9, 10: 0.8, 11: 0.7, 12: 0.6
}
# 3️⃣ 使用 Girvan-Newman 算法进行社区检测
def girvan_newman(G):
# 计算图的边介数
def edge_betweenness(G):
return nx.edge_betweenness_centrality(G)
# 逐步删除边，直到图分裂为多个组件
while len(list(nx.connected_components(G))) == 1:
# 计算边介数
edge_betweenness = edge_betweenness(G)
# 找到边介数最高的边
max_edge = max(edge_betweenness, key=edge_betweenness.get)
# 删除该边
G.remove_edge(*max_edge)
# 返回图分裂后的各个子图（社区）
return list(nx.connected_components(G))
# 获取图 G 的社区
communities = girvan_newman(G.copy())
# 4️⃣ 计算每个社区的平均节点重要性
community_importance = {}
# 遍历每个社区，计算其节点的平均重要性
for community_id, community in enumerate(communities):
avg_importance = sum(node_importance.get(node, 0) for node in community) / len(community)
community_importance[community_id] = avg_importance
# 5️⃣ 找到具有最高平均节点重要性的社区
max_community_id = max(community_importance, key=community_importance.get)
max_community_nodes = list(communities[max_community_id])
# 6️⃣ 提取该社区的子图
main_subgraph = G.subgraph(max_community_nodes)
# 7️⃣ 为节点设置颜色：根据节点重要性为节点指定颜色
# 将节点的重要性值归一化到 0 到 1 范围，用于颜色映射
node_colors = [node_importance.get(node, 0) for node in G.nodes]
norm = plt.Normalize(vmin=min(node_colors), vmax=max(node_colors))
cmap = plt.cm.viridis # 选择渐变色条
# 8️⃣ 可视化原图和最重要社区的子图
plt.figure(figsize=(12, 6))
# 原图可视化（节点颜色根据重要性显示）
plt.subplot(1, 2, 1)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color=node_colors, cmap=cmap, node_size=500, font_color="white")
plt.title("Original Graph (Node Color by Importance)")
# 最重要子图可视化（节点颜色根据重要性显示）
plt.subplot(1, 2, 2)
node_colors_subgraph = [node_importance.get(node, 0) for node in main_subgraph.nodes]
nx.draw(main_subgraph, pos, with_labels=True, node_color=node_colors_subgraph, cmap=cmap, node_size=500, font_color="white")
plt.title(f"Main Community Subgraph (Avg Importance: {community_importance[max_community_id]:.2f})")
# 显示图像
plt.show()
# 输出最重要社区的节点和其平均重要性
print(f"Nodes in the Main Community: {max_community_nodes}")
print(f"Average Importance of Main Community: {community_importance[max_community_id]:.2f}")
2.2 Girvan-Newman 算法
Girvan-Newman 算法是一种基于边介数（Edge Betweenness）的社区检测算法。其核心原理是递归移除介数最高的边，逐步将图划分为多个子图，从而识别不同的社区。该算法的优势在于直观且能够生成多个社区分割层次，非常适合分析网络的层次结构。然而，由于其计算复杂度较高，更适合用于小规模网络的社区检测任务。
import networkx as nx
import community.community_louvain as community_louvain
import matplotlib.pyplot as plt
# 1️⃣ 初始化图 G
G = nx.Graph()
# 添加边，构建图的社区结构
edges = [
(1, 2), (2, 3), (3, 4), (4, 1), # 社区 1
(5, 6), (6, 7), (7, 8), (8, 5), # 社区 2
(9, 10), (10, 11), (11, 12), (12, 9), # 社区 3
(4, 5), (8, 9) # 跨社区连接
]
G.add_edges_from(edges)
# 2️⃣ 假设有一个字典记录每个节点的名称和重要性
node_importance = {
1: 0.9, 2: 0.8, 3: 0.7, 4: 0.6,
5: 0.5, 6: 0.4, 7: 0.3, 8: 0.2,
9: 0.9, 10: 0.8, 11: 0.7, 12: 0.6
}
# 3️⃣ 使用 Louvain 算法对图进行社区划分
partition = community_louvain.best_partition(G)
# 4️⃣ 计算每个社区的平均节点重要性
community_importance = {}
# 遍历每个社区，计算其节点的平均重要性
for community_id in set(partition.values()):
nodes_in_community = [node for node, comm in partition.items() if comm == community_id]
avg_importance = sum(node_importance.get(node, 0) for node in nodes_in_community) / len(nodes_in_community)
community_importance[community_id] = avg_importance
# 5️⃣ 找到具有最高平均节点重要性的社区
max_community_id = max(community_importance, key=community_importance.get)
max_community_nodes = [node for node, comm in partition.items() if comm == max_community_id]
# 6️⃣ 提取该社区的子图
main_subgraph = G.subgraph(max_community_nodes)
# 7️⃣ 可视化原图和最重要社区的子图
plt.figure(figsize=(12, 6))
# 原图可视化
plt.subplot(1, 2, 1)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color="lightblue")
plt.title("Original Graph")
# 最重要子图可视化
plt.subplot(1, 2, 2)
nx.draw(main_subgraph, pos, with_labels=True, node_color="orange", node_size=500, font_color="white")
plt.title(f"Main Community Subgraph (Avg Importance: {community_importance[max_community_id]:.2f})")
# 显示图像
plt.show()
# 输出最重要社区的节点和其平均重要性
print(f"Nodes in the Main Community: {max_community_nodes}")
print(f"Average Importance of Main Community: {community_importance[max_community_id]:.2f}")
2.3 谱聚类算法
谱聚类算法是一种基于矩阵分解的社区检测方法。它通过计算图的拉普拉斯矩阵的特征值和特征向量来进行聚类。该算法能够有效地发现复杂的社区结构，适用于高维数据和非欧几里得空间中的聚类任务，但其缺点是需要预设社区数量，且计算复杂度较高。
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import SpectralClustering
# 1️⃣ 初始化图 G
G = nx.Graph()
# 添加边，构建图的社区结构
edges = [
(1, 2), (2, 3), (3, 4), (4, 1), # 社区 1
(5, 6), (6, 7), (7, 8), (8, 5), # 社区 2
(9, 10), (10, 11), (11, 12), (12, 9), # 社区 3
(4, 5), (8, 9) # 跨社区连接
]
G.add_edges_from(edges)
# 2️⃣ 假设有一个字典记录每个节点的名称和重要性
node_importance = {
1: 0.9, 2: 0.8, 3: 0.7, 4: 0.6,
5: 0.5, 6: 0.4, 7: 0.3, 8: 0.2,
9: 0.9, 10: 0.8, 11: 0.7, 12: 0.6
}
# 3️⃣ 使用谱聚类算法进行社区检测
def spectral_clustering_algorithm(G, n_clusters):
# 获取图的拉普拉斯矩阵
A = nx.adjacency_matrix(G).todense()
# 进行谱聚类
clustering = SpectralClustering(n_clusters=n_clusters, affinity='precomputed', random_state=42)
labels = clustering.fit_predict(A)
# 按照标签分割节点
communities = {}
for node, label in zip(G.nodes(), labels):
if label not in communities:
communities[label] = []
communities[label].append(node)
return list(communities.values())
# 假设我们已经知道图有3个社区
n_clusters = 3
communities = spectral_clustering_algorithm(G, n_clusters)
# 4️⃣ 计算每个社区的平均节点重要性
community_importance = {}
# 遍历每个社区，计算其节点的平均重要性
for community_id, community in enumerate(communities):
avg_importance = sum(node_importance.get(node, 0) for node in community) / len(community)
community_importance[community_id] = avg_importance
# 5️⃣ 找到具有最高平均节点重要性的社区
max_community_id = max(community_importance, key=community_importance.get)
max_community_nodes = list(communities[max_community_id])
# 6️⃣ 提取该社区的子图
main_subgraph = G.subgraph(max_community_nodes)
# 7️⃣ 为节点设置颜色：根据节点重要性为节点指定颜色
# 将节点的重要性值归一化到 0 到 1 范围，用于颜色映射
node_colors = [node_importance.get(node, 0) for node in G.nodes]
norm = plt.Normalize(vmin=min(node_colors), vmax=max(node_colors))
cmap = plt.cm.viridis # 选择渐变色条
# 8️⃣ 可视化原图和最重要社区的子图
plt.figure(figsize=(12, 6))
# 原图可视化（节点颜色根据重要性显示）
plt.subplot(1, 2, 1)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color=node_colors, cmap=cmap, node_size=500, font_color="white")
plt.title("Original Graph (Node Color by Importance)")
# 最重要子图可视化（节点颜色根据重要性显示）
plt.subplot(1, 2, 2)
node_colors_subgraph = [node_importance.get(node, 0) for node in main_subgraph.nodes]
nx.draw(main_subgraph, pos, with_labels=True, node_color=node_colors_subgraph, cmap=cmap, node_size=500, font_color="white")
plt.title(f"Main Community Subgraph (Avg Importance: {community_importance[max_community_id]:.2f})")
# 显示图像
plt.show()
# 输出最重要社区的节点和其平均重要性
print(f"Nodes in the Main Community: {max_community_nodes}")
print(f"Average Importance of Main Community: {community_importance[max_community_id]:.2f}")
3. 算法比较
为了比较三种社区检测方法（Girvan-Newman、Louvain 和 Spectral Clustering）在子图提取能力上的表现，我们设计了一个实验来分析它们在不同场景下的效果。实验的核心在于使用这三种算法对图进行社区划分，并从中提取具有最高节点重要性的子图。我们将通过以下几个性能指标来评估这些方法的表现：
- 子图的大小：每种方法提取的子图包含的节点数。
- 平均节点重要性：每个方法提取的子图中，节点重要性的平均值。
- 社区纯度：每种方法提取的子图中，同一社区节点的比例。
- 时间性能：每种方法执行社区检测所需要的时间。
实验步骤包括：首先生成一个已知社区结构的图，并为每个节点分配一个重要性值；然后，应用Girvan-Newman、Louvain 和谱聚类算法对图进行社区检测；接着，针对每种方法提取的社区，计算并输出上述四个性能指标；最后，比较这三种方法在提取具有最高节点重要性的子图时的差异，以分析它们在不同场景下的表现。
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import time
import community.community_louvain as community_louvain
from sklearn.cluster import SpectralClustering
# 1️⃣ 初始化图 G
G = nx.Graph()
# 添加边，构建图的社区结构
edges = [
(1, 2), (2, 3), (3, 4), (4, 1), # 社区 1
(5, 6), (6, 7), (7, 8), (8, 5), # 社区 2
(9, 10), (10, 11), (11, 12), (12, 9), # 社区 3
(4, 5), (8, 9) # 跨社区连接
]
G.add_edges_from(edges)
# 2️⃣ 假设有一个字典记录每个节点的名称和重要性
node_importance = {
1: 0.9, 2: 0.8, 3: 0.7, 4: 0.6,
5: 0.5, 6: 0.4, 7: 0.3, 8: 0.2,
9: 0.9, 10: 0.8, 11: 0.7, 12: 0.6
}
# 3️⃣ 使用 Girvan-Newman 算法进行社区检测
def girvan_newman(G):
def edge_betweenness(G):
return nx.edge_betweenness_centrality(G)
while len(list(nx.connected_components(G))) == 1:
edge_betweenness = edge_betweenness(G)
max_edge = max(edge_betweenness, key=edge_betweenness.get)
G.remove_edge(*max_edge)
return list(nx.connected_components(G))
# 4️⃣ 使用 Louvain 算法进行社区检测
def louvain_community(G):
return community_louvain.best_partition(G)
# 5️⃣ 使用谱聚类算法进行社区检测
def spectral_clustering_algorithm(G, n_clusters):
A = nx.adjacency_matrix(G).todense()
clustering = SpectralClustering(n_clusters=n_clusters, affinity='precomputed', random_state=42)
labels = clustering.fit_predict(A)
communities = {}
for node, label in zip(G.nodes(), labels):
if label not in communities:
communities[label] = []
communities[label].append(node)
return list(communities.values())
# 6️⃣ 计算每个社区的平均节点重要性
def calculate_community_importance(communities, node_importance):
community_importance = {}
for community_id, community in enumerate(communities):
avg_importance = sum(node_importance.get(node, 0) for node in community) / len(community)
community_importance[community_id] = avg_importance
return community_importance
# 7️⃣ 计算社区纯度
def calculate_purity(community, node_importance):
avg_importance = sum(node_importance.get(node, 0) for node in community) / len(community)
return avg_importance
# 8️⃣ 运行实验并记录结果
methods = ['Girvan-Newman', 'Louvain', 'Spectral Clustering']
results = {}
# 用来存储每个方法提取的最重要子图
subgraphs = {}
for method in methods:
start_time = time.time()
# 根据不同的算法进行社区划分
if method == 'Girvan-Newman':
communities = girvan_newman(G.copy())
elif method == 'Louvain':
partition = louvain_community(G)
communities = [list(node for node, comm in partition.items() if comm == comm_id) for comm_id in set(partition.values())]
elif method == 'Spectral Clustering':
n_clusters = 3 # 假设我们已经知道有 3 个社区
communities = spectral_clustering_algorithm(G, n_clusters)
# 计算每个社区的平均节点重要性
community_importance = calculate_community_importance(communities, node_importance)
# 找到具有最高平均节点重要性的社区
max_community_id = max(community_importance, key=community_importance.get)
max_community_nodes = communities[max_community_id]
# 提取该社区的子图
main_subgraph = G.subgraph(max_community_nodes)
subgraphs[method] = main_subgraph # 存储子图
# 计算指标
avg_importance = community_importance[max_community_id]
subgraph_size = len(main_subgraph.nodes())
purity = calculate_purity(max_community_nodes, node_importance)
# 记录结果
elapsed_time = time.time() - start_time
results[method] = {
'Subgraph Size': subgraph_size,
'Avg Importance': avg_importance,
'Purity': purity,
'Time': elapsed_time
}
# 9️⃣ 输出比较结果
print("\nComparison of Community Detection Methods:")
for method, result in results.items():
print(f"\n{method}:")
for key, value in result.items():
print(f" {key}: {value:.2f}")
# 10️⃣ 可视化所有子图在一张图中
plt.figure(figsize=(16, 8))
# 原图可视化
plt.subplot(2, 2, 1)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color="lightblue")
plt.title("Original Graph")
# Girvan-Newman子图可视化
plt.subplot(2, 2, 2)
main_subgraph_gn = subgraphs['Girvan-Newman']
node_colors_gn = [node_importance.get(node, 0) for node in main_subgraph_gn.nodes]
nx.draw(main_subgraph_gn, pos, with_labels=True, node_color=node_colors_gn, cmap=plt.cm.viridis, node_size=500, font_color="white")
plt.title(f"Girvan-Newman Subgraph (Avg Importance: {results['Girvan-Newman']['Avg Importance']:.2f})")
# Louvain子图可视化
plt.subplot(2, 2, 3)
main_subgraph_louvain = subgraphs['Louvain']
node_colors_louvain = [node_importance.get(node, 0) for node in main_subgraph_louvain.nodes]
nx.draw(main_subgraph_louvain, pos, with_labels=True, node_color=node_colors_louvain, cmap=plt.cm.viridis, node_size=500, font_color="white")
plt.title(f"Louvain Subgraph (Avg Importance: {results['Louvain']['Avg Importance']:.2f})")
# Spectral Clustering子图可视化
plt.subplot(2, 2, 4)
main_subgraph_sc = subgraphs['Spectral Clustering']
node_colors_sc = [node_importance.get(node, 0) for node in main_subgraph_sc.nodes]
nx.draw(main_subgraph_sc, pos, with_labels=True, node_color=node_colors_sc, cmap=plt.cm.viridis, node_size=500, font_color="white")
plt.title(f"Spectral Clustering Subgraph (Avg Importance: {results['Spectral Clustering']['Avg Importance']:.2f})")
# 显示图像
plt.tight_layout()
plt.show()
3.1 Subgraph Size (子图大小)分析
Girvan-Newman方法生成的子图大小为12，接近整个图的大小，表明它可能未能有效地将图拆分为多个子图。这是因为Girvan-Newman方法通过逐步删除边进行社区划分，可能在图中存在较强的跨社区连接，导致分割效果不明显。相比之下，Louvain方法只提取了大小为4的子图，显示出它能够更好地识别紧密连接的节点并将其划分为单独的社区。而Spectral Clustering方法生成的子图大小为6，介于Girvan-Newman和Louvain之间，表明它在分割图时能够取得相对平衡的效果。
3.2 Avg Importance (平均节点重要性)分析
Louvain方法在提取的子图中具有最高的平均节点重要性（0.83750），这表明它能够较好地识别并保留重要节点在同一社区内，捕捉到社区内部较为集中的重要性特征。Spectral Clustering的平均节点重要性为0.82500，虽然略低于Louvain，但仍展现出较强的能力，能够保留一定比例的重要节点。而Girvan-Newman方法的平均重要性为0.69583，较低的平均重要性反映出它可能将一些重要性较低的节点分配到关键社区中，影响了提取的子图的整体质量。
3.3 Time (执行时间)分析
Louvain方法在所有方法中表现出最低的执行时间（0.00162秒），表明它在计算效率上非常高，适合处理大规模图数据。其优化模块度的方式非常高效，尤其适用于需要快速处理大规模网络的应用。Girvan-Newman方法的执行时间为0.00474秒，虽然比Louvain慢，但仍然相对较快。该方法的执行时间较短是因为它通过逐步删除边来进行社区划分，但仍涉及较高的计算开销。Spectral Clustering方法的执行时间最长（0.01222秒），因为它需要计算图的拉普拉斯矩阵并进行特征分解，这导致了较高的计算复杂度，特别是在节点和边较多时。
3.4 综合分析
Louvain方法在实验中表现最为出色，不仅在纯度和平均节点重要性上取得了最高成绩，而且其执行时间也最为高效，适合应用于大规模图数据。Spectral Clustering方法同样表现优秀，尤其是在重要性和纯度上，其计算开销虽高于Louvain，但仍能提供较为准确的社区划分。Girvan-Newman方法尽管计算速度较快，但其较低的纯度和平均节点重要性显示出它的社区划分效果较为逊色，特别是在处理复杂图结构时，可能无法有效地识别重要节点和明确的社区边界。