聚类系数

一、直观理解：朋友的朋友也是朋友吗

聚类系数（clustering coefficient）刻画网络的抱团程度：若 $i$ 的邻居们彼此也大量相连，则 $i$ 处局部聚类高。

生活直觉：同学圈子里大家互相认识 → 高聚类；纯随机碰边 → 低聚类。

小世界网络的经典特征之一就是：高聚类 + 短平均路径（相对同规模随机图）。

二、适用场景与优缺点

类型	说明
适用场景	社交/合作网络结构；与 ER 随机图对比；小世界判定；局部社区迹象的初探。
核心优点	含义直观；点式与全局两种；计算相对容易。
局限与缺点	度很小的点定义退化；加权/有向需推广；高聚类不等于唯一社区划分。

三、核心原理

1. 局部聚类系数

点 $i$ 度 $k_i\ge 2$，邻居之间实际边数 $e_i$，则

$$C_i=\frac{2e_i}{k_i(k_i-1)}$$

（无向简单图）。$C_i\in[0,1]$。

2. 全局平均聚类

$$C=\frac{1}{n}\sum_i C_i$$

（对 $k_i<2$ 的点常跳过或置 0，需声明）。

3. 传递性（另一全局定义）

$$T=\frac{3\times\#\triangle}{\#\text{连通三元组}}$$

与平均 $C$ 不完全相同，报告时写明用的哪一种。

4. 对照

同 $n,\langle k\rangle$ 的 ER 图 $C\sim\langle k\rangle/n$，往往远小于真实社交网络。

四、关键决策

1. 点聚类还是传递性

关注局部差异用 $C_i$ 分布；关注整体闭三角形用 $T$。

2. 加权网络

可用 Onnela 等加权聚类，避免直接无视权。

3. 与模体

三角形只是 3 点模体之一，可扩展。

五、MATLAB 示例

rng(29);
% 两个完全子图桥接：高聚类
A = zeros(10);
A(1:5,1:5)=1; A(6:10,6:10)=1;
A(1:11:end)=0; A(6:11:end)=0;
A(5,6)=1; A(6,5)=1;
G = graph(A);

c = clustering_coef_bu_simple(A);
fprintf("平均聚类 C=%.3f\n", mean(c(isfinite(c))));

% ER 对照
n=10; m=numedges(G);
% 近似同边数随机图
GER = graph(sprandsym(n, 2*m/(n*(n-1)))>0);
% 清洗对角线
AER = adjacency(GER); AER(1:n+1:end)=0; GER=graph(AER);
cER = clustering_coef_bu_simple(AER);
fprintf("ER 对照 C=%.3f\n", mean(cER(isfinite(cER))));

figure;
subplot(1,2,1); plot(G); title(sprintf("结构图 C=%.2f", mean(c)));
subplot(1,2,2); bar(c); xlabel("节点"); ylabel("C_i"); title("局部聚类");

% Watts-Strogatz 小世界
Gws = WattsStrogatz(30, 3, 0.1);
Aws = adjacency(Gws);
cws = clustering_coef_bu_simple(full(Aws));
fprintf("WS 平均聚类=%.3f, 平均最短路≈%.3f\n", mean(cws), mean(distances(Gws), "all"));

function c = clustering_coef_bu_simple(A)
    A = A~=0; n = size(A,1); A(1:n+1:end)=0;
    c = zeros(n,1);
    for i = 1:n
        nbr = find(A(i,:));
        k = numel(nbr);
        if k < 2
            c(i) = NaN;
        else
            e = sum(A(nbr, nbr), "all")/2;
            c(i) = 2*e/(k*(k-1));
        end
    end
end

function h = WattsStrogatz(N,K,beta)
    % 简化 WS：环上连 K 近邻，再重连
    s=[]; t=[];
    for i=1:N
        for j=1:K
            s(end+1)=i; t(end+1)=mod(i+j-1,N)+1; %#ok<AGROW>
        end
    end
    for e=1:numel(s)
        if rand < beta
            t(e) = randi(N);
            while t(e)==s(e)
                t(e)=randi(N);
            end
        end
    end
    h = graph(s,t);
    h = simplify(h);
end

六、如何解释结果

1. 定义（局部平均还是传递性）；
2. 全网 $C$ 与 $C_i$ 分布；
3. 与随机对照的倍数关系；
4. 高聚类区域的业务含义；
5. 与平均路径长度联合判断小世界性。

七、常见误区

1. 把平均聚类当社区发现结果

还需社区算法。

2. 度=1 的点强行解释 $C_i=0$

定义本就不适用。

3. 只比绝对值不比随机基线

不同密度网络的 $C$ 不可瞎比。

4. 有向图用无向公式

需有向聚类定义。

八、小结

聚类系数的核心是：

度量邻居之间互连形成三角形的比例，从而刻画局部抱团。

它是小世界与社会网络分析的基本量。报告定义、分布与随机对照，才能把“聚类高”说成有比较的结构事实。