Louvain 算法

一、直观理解：把网络自动分成“内部密、外部疏”的团体

社区发现（community detection）要在图中找出组：组内边密、组间边稀。Louvain 算法是实践中最常用的模块度优化启发式之一，速度快，能处理百万边量级，适合建模赛的网络结构分析。

模块度 $Q$ 比较“真实组内边比例”与“随机情况下的期望”：

$$Q=\frac{1}{2m}\sum_{ij}\left(A_{ij}-\frac{k_i k_j}{2m}\right)\delta(c_i,c_j)$$

$Q$ 越高，划分相对随机零模型越“成团”。Louvain 通过两阶段迭代贪婪提升 $Q$：

1. 局部移动：每个点尝试搬到使 $Q$ 增益最大的邻居社区；
2. 聚合：把社区缩成超级点，在新图上重复。

直到 $Q$ 不再提升，得到层次化社区。

二、适用场景与优缺点

类型	说明
适用场景	无向（可加权）网络的社区结构；社交团、功能模块、区域分区；中等以上规模图。
核心优点	极快；实现相对直接；层次结果可多分辨率观察；加权自然。
局限与缺点	启发式不保证全局最大 $Q$；分辨率极限（小社区可能被吞并）；随机次序导致结果波动；高 $Q$ 不等于唯一真社区。

三、核心原理

1. 模块度增益

把孤立点 $i$ 移入社区 $C$ 的 $\Delta Q$ 有闭式，依赖 $i$ 与 $C$ 的连边、以及 $C$ 的总度等，从而可快速评估。

2. 两阶段

• 阶段一反复扫点直到局部稳定；
• 阶段二构图：社区间边权求和，得到更粗图；
• 多层后得到树状层级。

3. 分辨率

经典模块度偏好一定尺度的社区。可用 RB 势或 Leiden 算法改进稳定性与连通性。建模中至少：多种子运行 + 一致性。

4. 评价

• $Q$ 值；
• 与元数据标签的 NMI/ARI（若有）；
• 社区规模分布；
• 随机重连网络的 $Q$ 对照。

四、关键决策

1. 有向/二分图

经典 Louvain 面向无向；有向需专用模块度。

2. 加权含义

权是联系强度时直接用；若是距离需转换。

3. 稳定性

跑 20 次不同点顺序，看社区共现或共识划分。

4. 与聚类系数/中心性

社区是中观结构，应和微观度量一起报告。

五、MATLAB 示例

MATLAB 近年 graph 对象可能提供社区函数；下面给教学级 Louvain 简化版（小图）与模块度计算。

rng(30);
% 生成三个块的随机块模型
n = 60; sizes = [20 20 20];
A = zeros(n);
idx = [ones(1,20) 2*ones(1,20) 3*ones(1,20)];
pin = 0.35; pout = 0.03;
for i = 1:n
    for j = i+1:n
        p = pout; if idx(i)==idx(j), p = pin; end
        if rand < p
            A(i,j)=1; A(j,i)=1;
        end
    end
end
G = graph(A);

% 若有内置
try
    comm = centrality_placeholder(); %#ok<NASGU>
catch
end

if exist("community_louvain", "file")
    % 某些工具箱
else
    [comm, Q] = louvain_simple(A);
end
[comm, Q] = louvain_simple(A);
fprintf("Louvain Q=%.4f, 社区数=%d\n", Q, numel(unique(comm)));

figure;
p = plot(G);
p.NodeCData = comm;
colorbar; title(sprintf("Louvain 划分 Q=%.3f", Q));

% 与真实块的一致（ARI 简版：成对准确）
pairs_ok = 0; pairs = 0;
for i=1:n-1
    for j=i+1:n
        pairs = pairs+1;
        sameC = comm(i)==comm(j); sameT = idx(i)==idx(j);
        pairs_ok = pairs_ok + (sameC==sameT);
    end
end
fprintf("成对一致性≈%.3f\n", pairs_ok/pairs);

function [comm, Q] = louvain_simple(A)
    A = A - diag(diag(A)); A = (A+A')/2;
    n = size(A,1); m2 = sum(A(:)); % 2m
    if m2==0, comm=(1:n)'; Q=0; return; end
    k = sum(A,2);
    comm = (1:n)';
    improved = true;
    while improved
        improved = false;
        order = randperm(n);
        for ii = 1:n
            i = order(ii);
            % 邻居社区候选
            nbr = find(A(i,:)>0);
            if isempty(nbr), continue; end
            cand = unique(comm(nbr));
            bestC = comm(i); bestDQ = 0;
            % 移出原社区后的增益比较（简化计算）
            for c = cand'
                dQ = deltaQ(A, k, m2, comm, i, c);
                if dQ > bestDQ + 1e-15
                    bestDQ = dQ; bestC = c;
                end
            end
            if bestC ~= comm(i)
                comm(i) = bestC; improved = true;
            end
        end
    end
    % 重新编号
    [~,~,comm] = unique(comm);
    Q = modularity(A, comm);
end

function dQ = deltaQ(A, k, m2, comm, i, cnew)
    % 近似：全局重算差（小 n 教学用，非高效实现）
    cold = comm(i);
    if cold==cnew, dQ=0; return; end
    Q0 = modularity_from(A,k,m2,comm);
    comm2 = comm; comm2(i)=cnew;
    Q1 = modularity_from(A,k,m2,comm2);
    dQ = Q1-Q0;
end

function Q = modularity(A, comm)
    k = sum(A,2); m2 = sum(A(:));
    Q = modularity_from(A,k,m2,comm);
end

function Q = modularity_from(A,k,m2,comm)
    Q = 0; n=numel(comm);
    for i=1:n
        for j=1:n
            if comm(i)==comm(j)
                Q = Q + (A(i,j) - k(i)*k(j)/m2);
            end
        end
    end
    Q = Q/m2;
end

说明：上表实现为教学简化（用全局重算 $\Delta Q$），复杂度不适合大图。正式应用应使用高效增益公式或成熟库（Python networkx/leidenalg 等），但叙事与检验流程相同。

六、如何解释结果

1. 图与边权含义；
2. 算法与随机种子次数；
3. 社区个数、规模、模块度 $Q$；
4. 可视化着色图；
5. 稳定性与对照（随机图 $Q$）；
6. 业务命名社区（需依据内部节点特征，防过度解读）。

七、常见误区

1. $Q$ 最大就等于真社区

零模型与分辨率限制。

2. 只跑一次

点顺序影响结果。

3. 有向图直接套

定义不匹配。

4. 把社区当行政分区硬解释

需外部变量验证。

八、小结

Louvain 的核心是：

通过局部移动与图聚合贪婪最大化模块度，从而快速得到层次社区。

它是复杂网络中观分析的默认武器。写清 $Q$、稳定性与可视化，并克制命名，才能让社区发现从“算法演示”变成“结构证据”。