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?
%?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