编写Matlab代码筛选满足条件的M阶Clique节点集群

初始矩阵生成代码 #

clear
rng default
A= nchoosek(1:1:10,2);
A(:,3)=randn(size(A,1), 1);
sA=size(A,1);

矩阵A的前两列为1到10之间所有可能的无序整数对，第三列为每个配对对应的实数。需实现以下功能：

• 定义函数r(k,h)，将{1,...,10}^2映射到{1,...,sA}，返回配对(k,h)或(h,k)在A中的行索引；
• 设置整数M<=10与实数R（例如M=3、R=0）；
• 返回1到10中的M个不同整数k₁,…,k_M，使得该集合中任意配对{k_i,k_j}满足A(r(k_i,k_j),3)>=R；
• 若不存在这样的M个整数，返回NaN。

示例：当M=3、R=0时，可返回{1,2,3}（存在多个符合条件的集合，只需返回任意一个即可）。

现有实现及问题 #

本人尝试编写的代码如下，但在处理含999行的实际A矩阵时出现内存问题，需优化：

clear
rng default
A= nchoosek(1:1:10,2);
A(:,3)=randn(size(A,1), 1);
sA=size(A,1);

% Step 1: define function rowIndex
function rowIndex = r(k, h, A)
if k > h
    [k, h] = deal(h, k);
end
rowIndex = find(A(:,1) == k & A(:,2) == h);
end

% Step 2: Set parameters M and R
M = 3;
R = -1;

% Step 3: Construct adjacency matrix for the graph
adjMatrix = false(10, 10);
for i = 1:10
    for j = i+1:10
        if A(r(i, j, A), 3) >= R
            adjMatrix(i, j) = true;
            adjMatrix(j, i) = true;
        end
    end
end

% Step 4: Find a clique of size M
foundClique = false;
cliqueNodes = NaN;

combinations = nchoosek(1:10, M);
for i = 1:size(combinations, 1)
    subset = combinations(i, :);
    if all(all(adjMatrix(subset, subset) | eye(M)))  % Check if all pairs are connected
        foundClique = true;
        cliqueNodes = subset;
        break
    end
end

% Display the result
if foundClique
    disp('Found clique:');
    disp(cliqueNodes);
else
    disp('No clique found. Returning NaN.');
    cliqueNodes = NaN;
end

优化方案 #

1. 预构建索引映射，替代低效的r函数 #

原r函数每次调用都用find遍历矩阵，当A行数很大时（比如999行对应节点数n≈45），多次调用会严重拖慢效率。我们可以预建一个二维索引表，直接通过k和h快速定位行号：

% 获取总节点数（A中出现的最大编号）
n = max(A(:,[1,2]));
% 初始化索引映射矩阵
indexMap = zeros(n, n);
for row = 1:size(A,1)
    k = A(row,1);
    h = A(row,2);
    indexMap(k,h) = row;
    indexMap(h,k) = row;
end

% 改写r函数，直接查表
function rowIndex = r(k, h, indexMap)
    rowIndex = indexMap(k, h);
end

2. 优化邻接矩阵构建 #

利用预建的indexMap直接获取行号，避免重复遍历A矩阵：

adjMatrix = false(n, n);
for i = 1:n
    for j = i+1:n
        rowIdx = indexMap(i,j);
        % 若配对存在且满足阈值条件，标记为连通
        if rowIdx ~= 0 && A(rowIdx,3) >= R
            adjMatrix(i,j) = true;
            adjMatrix(j,i) = true;
        end
    end
end

3. 高效寻找M阶团（避免生成所有组合） #

原代码用nchoosek生成所有组合，当n=45、M=10时，组合数超过1亿，完全无法处理。改用贪心算法逐步构建团，大幅减少计算量：

function clique = findGreedyClique(adjMatrix, M)
    n = size(adjMatrix,1);
    clique = [];
    availableNodes = 1:n;
    
    while ~isempty(availableNodes) && length(clique) < M
        if isempty(clique)
            % 初始选择度数最高的节点
            degrees = sum(adjMatrix,2);
            [~, idx] = max(degrees(availableNodes));
            selected = availableNodes(idx);
        else
            % 筛选与当前团所有节点相连的候选
            candidates = availableNodes(all(adjMatrix(availableNodes, clique),2));
            if isempty(candidates)
                break;
            end
            % 选择候选中度数最高的节点
            degrees = sum(adjMatrix(candidates,:),2);
            [~, idx] = max(degrees);
            selected = candidates(idx);
        end
        clique = [clique, selected];
        % 更新可用节点：仅保留与选中节点连通的节点
        availableNodes = intersect(availableNodes, find(adjMatrix(selected,:)));
    end
    
    % 若团的大小不足M，返回NaN
    if length(clique) < M
        clique = NaN;
    end
end

完整优化代码 #

clear
rng default

% 模拟999行的A矩阵（n=45时nchoosek(45,2)=990，补充9行随机对）
n = 45;
A = nchoosek(1:n,2);
% 补充随机无序对（确保前两列k<h）
extraPairs = unique([randi(n,9,1), randi(n,9,1)], 'rows');
extraPairs = extraPairs(extraPairs(:,1)~=extraPairs(:,2),:);
extraPairs = sort(extraPairs,2);
A = [A; extraPairs(1:min(9,size(extraPairs,1)),:)];
A(:,3) = randn(size(A,1),1);
sA = size(A,1);

% Step 1: 预构建索引映射表
indexMap = zeros(n, n);
for row = 1:sA
    k = A(row,1);
    h = A(row,2);
    indexMap(k,h) = row;
    indexMap(h,k) = row;
end

% 定义r函数
function rowIndex = r(k, h, indexMap)
    rowIndex = indexMap(k, h);
end

% Step 2: 设置参数M和R
M = 5;
R = 0;

% Step 3: 构建邻接矩阵
adjMatrix = false(n, n);
for i = 1:n
    for j = i+1:n
        rowIdx = indexMap(i,j);
        if rowIdx ~= 0 && A(rowIdx,3) >= R
            adjMatrix(i,j) = true;
            adjMatrix(j,i) = true;
        end
    end
end

% Step 4: 贪心寻找M阶团
cliqueNodes = findGreedyClique(adjMatrix, M);

% 显示结果
if ~isnan(cliqueNodes)
    disp('找到符合条件的集合：');
    disp(cliqueNodes);
else
    disp('不存在符合条件的M个整数，返回NaN');
    cliqueNodes = NaN;
end

% 贪心找团函数
function clique = findGreedyClique(adjMatrix, M)
    n = size(adjMatrix,1);
    clique = [];
    availableNodes = 1:n;
    
    while ~isempty(availableNodes) && length(clique) < M
        if isempty(clique)
            degrees = sum(adjMatrix,2);
            [~, idx] = max(degrees(availableNodes));
            selected = availableNodes(idx);
        else
            candidates = availableNodes(all(adjMatrix(availableNodes, clique),2));
            if isempty(candidates)
                break;
            end
            degrees = sum(adjMatrix(candidates,:),2);
            [~, idx] = max(degrees);
            selected = candidates(idx);
        end
        clique = [clique, selected];
        availableNodes = intersect(availableNodes, find(adjMatrix(selected,:)));
    end
    
    if length(clique) < M
        clique = NaN;
    end
end

优化说明 #

1. 索引映射表：将O(n)的查找时间降为O(1)，彻底避免反复遍历A矩阵，大幅提升效率；
2. 邻接矩阵构建：利用索引表直接定位行号，减少无效计算；
3. 贪心找团：无需生成所有组合，通过逐步筛选候选节点，在大多数情况下能快速找到可行团，内存占用极低，适合处理大节点数的场景，满足“返回任意一个即可”的需求。

内容的提问来源于stack exchange，提问作者Star