Louvain算法：模块度计算与集群划分示例

Louvain算法：模块度计算与集群划分示例

Louvain算法是一种贪心算法，用于寻找图中的最佳社区结构。算法的核心是通过不断调整节点的所属集群，来最大化图的模块度。模块度衡量了图中社区结构的质量，其值越高，表示社区结构越清晰。

模块度计算公式

模块度的计算公式如下：

Q = sum((B(i,j) - k(i)k(j)/(2m))^delta*(cluster(i) == cluster(j)), 'all')

其中：

• B(i,j) 为节点 i 和节点 j 之间的边权重
• k(i) 为节点 i 的度数
• m 为边的总权重
• delta 为分辨率参数，通常取 1
• cluster(i) 为节点 i 所属的集群编号

代码示例

delta = 1; % 设置分辨率参数为 1
m = sum(adj_matrix, 'all') / 2; % 计算边的总权重
% 计算每个节点的度数
degree = sum(adj_matrix, 2);
% 计算边权重矩阵 B
B = adj_matrix - degree * degree' / (2 * m);
% 计算模块度函数
Q = sum((B - delta * degree * degree' / (2 * m)) .* (cluster == cluster'), 'all') / (2 * m);

示例：5节点无向图

假设有一个无向图，共有 5 个节点，邻接矩阵为：

adj_matrix = [0 1 1 0 0;
              1 0 1 1 0;
              1 1 0 1 0;
              0 1 1 0 1;
              0 0 0 1 0];

假设已经对这个图进行了集群划分，得到的结果为：

cluster = [1; 1; 1; 2; 2];

则 cluster 表示这 5 个节点被划分到了两个集群中，第 1、2、3 个节点被划分到了第 1 个集群中，第 4、5 个节点被划分到了第 2 个集群中。

cluster 矩阵是一个 5x1 的矩阵，表示每个节点所属的集群编号。

通过上述示例，我们可以理解 Louvain 算法中的模块度计算方法，以及如何使用邻接矩阵和集群划分结果来计算模块度。