图分区

从 Edge-cut/Vertex-cut 目标函数出发，系统讲解 METIS 多层分区思想与工程落地，重点解释分区如何影响查询延迟和跨机通信量。

副标题 / 摘要 社区发现不是“把图分几堆”这么简单，而是要在准确性、可解释性、速度和可维护性之间做平衡。本文按 ACERS 结构拆解两种工程最常见算法：Louvain（模块度优化） 与 Label Propagation（标签传播）。 预计阅读时长：12~16 分钟 标签：社区发现、Louvain、Label Propagation、图分区 SEO 关键词：community detection, Louvain, Label Propagation, modularity, graph partition 元描述：社区发现工程入门：Louvain 与 LPA 的原理、复杂度、选型与落地模板，覆盖群体识别、图分区、冷启动分析。 目标读者 做社交图、风控图、推荐系统图分析的工程师 想把“社区发现”从论文概念落到生产实践的开发者 需要在“图分区/冷启动”场景做群体结构建模的人 背景 / 动机 社区发现在工程里很常见： 群体识别：识别强关联账号簇、异常团伙、兴趣圈层 图分区：把高连通子图放在同一分片，减少跨分片通信 冷启动分析：新用户/新实体通过邻域社区快速归类 痛点在于： 全局最优通常不可得（NP-hard 相关目标） 数据规模大、更新快，离线算法难以频繁重跑 不同业务对“稳定性/速度/解释性”优先级不同 所以工程上最常见的两类方法是： Louvain：追求较高质量社区（模块度） Label Propagation (LPA)：追求速度与简单实现 核心概念 概念 含义 工程影响 Community 内部边密、外部边疏的节点集合 影响分区与推荐质量 Modularity(Q) 度量社区划分质量的指标 Louvain 优化目标 Label Propagation 节点迭代采用邻居主流标签 速度快、结果有随机性 Graph Partition 按社区切分存储/计算 降低跨机通信成本 Cold Start 用邻域结构给新节点快速归群 提升启动期召回 A — Algorithm（题目与算法） 题目还原（工程抽象版） 给定无向图 G=(V,E)，输出每个节点所属社区 ID，并支持以下用途： ...