社区发现算法 - Louvain
内容提要
Louvain是常用社区发现算法，以最大化模块度为目标划分图结构。模块度衡量社区划分质量：社区内连边越多、社区间连边越少则越高。算法分两阶段：先将每个节点视为独立社区，遍历节点计算移入邻居社区带来的模块度增益，移至增益最大处，直至无增益；再将同社区节点融合为新节点重建图，迭代至结构稳定。该算法基于贪心，平均复杂度O(nlogn)，但模块度最优求解为NP问题。
延伸解读
模块度公式的直观理解
模块度公式可拆解为两部分：第一项是社区内部边权总和，越大表示社区内部连接越紧密；第二项是各社区节点度之和的平方和，反映节点度在社区间的分布均匀程度。当节点度分布越均匀，第二项越小，模块度越大。但文章指出，在风控等社区大小极不均匀的场景中，第二项会偏大，导致模块度偏小，可能使优化目标与实际业务需求冲突。
节点移动的增益计算
Louvain算法在阶段1遍历节点，计算将其从当前社区D移动到邻居社区C带来的模块度增益。增益公式表明，节点i与社区D中节点的边权比与社区C中的边权越大，越容易转移到D；同时，社区C比社区D越大，越容易发生从C到D的转移，这促使社区分布更均匀。每次计算只涉及当前两个社区，因此计算成本较低。
算法复杂度与贪心局限
Louvain基于贪心策略，阶段1不断尝试节点移动，复杂度可能超过O(max(M,N))，最坏情况难以预估。实际平均复杂度为O(nlogn)，当每轮迭代节点数量减半时可达到。由于模块度最优求解是NP问题（时间复杂度O(M!)），Louvain通过贪心优化求解过程，但可能陷入局部最优，文章提到或许可在此基础上进一步优化。
Q&A
Louvain算法是什么？它主要用来做什么？
Louvain是一种常用的社区发现算法，以最大化模块度为目标对图结构进行划分，用于发现图中的聚集性社区。
模块度是如何衡量社区划分质量的？
模块度衡量社区划分的好坏：社区内部连边越多、社区之间连边越少，模块度越大，表示划分越好。
Louvain算法的具体步骤是什么？
Louvain算法分两阶段：1. 将每个节点视为独立社区，遍历节点，计算移入邻居社区带来的模块度增益，移至增益最大的社区，直到无增益；2. 将同一社区的节点融合为新节点，重建图，迭代直到图结构稳定。
Louvain算法的时间复杂度是多少？
Louvain基于贪心算法，平均复杂度为O(nlogn)，但最坏复杂度不好预估，可能超过O(max(M, N))。
Louvain算法有哪些优点和缺点？
优点：基于贪心，平均复杂度O(nlogn)，能有效划分社区。缺点：模块度最优求解是NP问题，无法在短时间内求到最优解，且模块度优化目标可能与实际场景冲突（如社团大小分布极不均匀时）。
模块度公式中第二项有什么作用？
第二项描述每个社团中所有节点的边权和平方，当节点度在不同社区中分布越均匀，第二项越小，模块度越大。但第二项重要程度与社团实际分布有关，如风控场景社团大小分布极不均匀，会导致第二项偏大，模块度偏小，与优化目标冲突。
