社交网络的k-clique算法

基于社交网络的k-clique算法，完成社团划分

function [componentscliquesCC] = k_clique（kM）
% k-clique algorithm for detecting overlapping communities in a network 
% as defined in the paper “Uncovering the overlapping 
% community structure of complex networks in nature and society“ - 
% G. Palla I. Derényi I. Farkas and T. Vicsek - Nature 435 814–818 （2005）
% 
% [XYZ] = k_clique（kA）
% 
% Inputs: 
% k - clique size 
% A - adjacency matrix
% 
% Outputs: 
% X - detected communities 
% Y - all cliques （i.e. complete subgraphs that are not parts of larger
% complete subgraphs）
% Z - k-clique matrix
%
% Author : Anh-Dung Nguyen
% Email : anh-dung.nguyen@isae.fr


% The adjacency matrix of the example network presented in the paper
% M = [1 1 0 0 0 0 0 0 0 1;
%     1 1 1 1 1 1 1 0 0 1;
%     0 1 1 1 0 0 1 0 0 0;
%     0 1 1 1 1 1 1 0 0 0;
%     0 1 0 1 1 1 1 1 0 0;
%     0 1 0 1 1 1 1 1 0 0;
%     0 1 1 1 1 1 1 1 1 1;
%     0 0 0 0 1 1 1 1 1 1;
%     0 0 0 0 0 0 1 1 1 1;
%     1 1 0 0 0 0 1 1 1 1];

nb_nodes = size（M1）; % number of nodes 

% Find the largest possible clique size via the degree sequence:
% Let {d1d2...dk} be the degree sequence of a graph. The largest
% possible clique size of the graph is the maximum value k such that
% dk >= k-1
degree_sequence = sort（sum（M2） - 1‘descend‘）;
max_s = 0;
for i = 1:length（degree_sequence）
    if degree_sequence（i） >= i - 1
        max_s = i;
    else 
        break;
    end
end

cliques = cell（0）;
% Find all s-size kliques in the graph
for s = max_s:-1:3
    M_aux = M;
    % Looping over nodes
    for n = 1:nb_nodes
        A = n; % Set of nodes all linked to each other
        B = setdiff（find（M_aux（n:）==1）n）; % Set of nodes that are linked to each node in A but not necessarily to the nodes in B
        C = transfer_nodes（ABsM_aux）; % Enlarging A by transferring nodes from B
        if ~isempty（C）
            for i = size（C1）
                cliques = [cliques;{C（i:）}];
            end
        end
        M_aux（n:） = 0; % Remove the processed node
        M_aux（:n） = 0;
    end
end

% Generating the clique-clique overlap matrix
CC = zeros（length（cliques））;
for c1 = 1:length（cliques）
    for c2 = c1:length（cliques）
        if c1==c2
            CC（c1c2） = numel（cliques{c1}）;
        else
            CC（c1c2） = numel（intersect（cliques{c1}cliques{c2}））;
            CC（c2c1） = CC（c1c2）;
        end
    end
end

% Extracting the k-clique matrix from the clique-clique overlap matrix
% Off-diagonal elements <= k-1 --> 0
% Diagonal elements <= k --> 0
CC（eye（size（CC））==1） = CC（eye（size（CC））==1） - k;
CC（eye（size（CC））~=1） = CC（eye（size（CC））~=1） - k + 1;
CC（CC >= 0） = 1;
CC（CC < 0） = 0;

% Extracting components （or k-clique communities） from the k-clique matrix
components = [];
for i = 1:length（cliques）
    linked_cliques = find（CC（i:）==1）;
    new_component = [];
    for j = 1:length（linked_cliques）
        new_component = union（new_componentcliques{linked_cliques（j）}）;
    end
    found = false;
    if ~isempty（new_component

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        5021  2012-10-29 10:45  k_clique2.m
     文件        1336  2012-10-29 10:45  license.txt