基于多边的社区构建问题（Louvain算法 Python实现）

问题背景 #

数据结构 #

现有如下结构的DataFrame：

需求 #

若任意仓库与店铺、所有者或卖家存在关联，则所有相关实体归为同一社区（仓库作为关联锚点），因此第1-4行应属于同一社区。

现有实现问题 #

使用Louvain算法的代码运行后，每次结果随机波动，且第4行未归入预期社区，实际结果如下：

原因分析 #

1. 算法选型错误：需求本质是识别图的连通分量（只要实体间有路径相连就归为一组），但误用了Louvain社区检测算法。Louvain的目标是最大化模块化值，即使图是连通的，它也可能将其拆分为多个社区，与需求完全不符。
2. Louvain的随机性：community.best_partition()内置随机过程，节点遍历顺序、社区合并的随机选择会导致每次运行结果不一致。

解决方案：使用连通分量检测 #

直接用NetworkX的连通分量检测来实现，完全匹配需求且结果稳定。

代码实现 #

import networkx as nx
import pandas as pd

# 初始化原始DataFrame
df_sales = pd.DataFrame([
    ["JFK1", "John F K 1", "Store 2", "Shore Line", "LTR1", "Rakual", "Big toys"],
    ["ABL2", "Ab Linc 2", "Store 3", "MarkTech", "LTR1", "Rakual", "Amazon"],
    ["JFK1", "John F K 1", "Store 5", "JBL", "LTR1", "Rakual", "Amazon"],
    ["MNY5", "Mani Co", "Store 5", "JBL", "PRR1", "JHason", "Decor"],
    ["NXN9", "Nixon Pvt Ltd", "Store 9", "Camera", "LMR7", "Jose", "EBAY"]
], columns=["仓库ID", "仓库名称", "店铺ID", "店铺名称", "所有者ID", "所有者名称", "卖家"])

# 创建无向图
G = nx.Graph()

# 添加所有关联边：仓库-店铺、仓库-所有者、仓库-卖家
G.add_edges_from(df_sales[["仓库ID", "店铺ID"]].values)
G.add_edges_from(df_sales[["仓库ID", "所有者ID"]].values)
G.add_edges_from(df_sales[["仓库ID", "卖家"]].values)

# 为每个连通分量分配唯一ID
component_map = {}
for community_id, component in enumerate(nx.connected_components(G)):
    for node in component:
        component_map[node] = community_id

# 将社区ID映射回DataFrame
df_sales["CommunityID"] = df_sales["仓库ID"].map(component_map)

print(df_sales)

代码说明 #

• 连通分量检测：nx.connected_components()会找出图中所有相互连通的节点集合，完全满足“所有关联实体归为同一社区”的需求。
• 确定性结果：该算法无随机过程，每次运行结果一致。
• 全关联覆盖：只要实体间存在间接关联（比如MNY5和JFK1通过Store5连通），就会被分到同一社区。

运行结果 #

输出结果与预期完全一致：

内容的提问来源于stack exchange，提问作者john_sab1