File Exchange

image thumbnail

k-clique algorithm

version 1.3.0.0 (2.68 KB) by Anh-Dung Nguyen
k-clique community detection algorithm
4.3
4 Ratings

9 Downloads

Updated 29 Oct 2012

View Version History

View License

k-clique algorithm 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)

[X,Y,Z] = k_clique(k,A)

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

Cite As

Anh-Dung Nguyen (2021). k-clique algorithm (https://www.mathworks.com/matlabcentral/fileexchange/34202-k-clique-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (10)

liuxueliang

I run the code with about 1800 items, but it is very slow. Is that any way to speed up the processing? thanks

Tugay Direk

Could you share python code for this if there is one?

Fan Zhang

Hi,

In line 61, why only the 'i = size(C,1)' clique is recorded? Is it supposed to be 'for i = 1:size(C,1)'?

thanks!!!

Shukai Ni

Shukai Ni

Nadia Ghobadipasha

SAMUEL HEROY

I am confused. I created an adjacency matrix that generates a 2x4 scaffold with 8 pairwise adjacent 3-cliques. (My adj matrix is
0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
1 1 1 0 1 1 0 0
0 0 1 1 0 1 1 1
0 0 0 1 1 0 0 1
0 0 0 0 1 0 0 1
0 0 0 0 1 1 1 0
).
However, the cliques output only returns four entries when I query for 3-cliques and associated communities:
[1,3,4]
[3,4,5]
[4,5,6]
[5,7,8]
By my understanding of this algorithm's intention, shouldn't there be four more entries here--and one large community that spans the network?

learn learn

i found after execute the code source this result. but i can't well understand what's mean.
M

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

>> m=4;
>> [X,Y,Z] = k_clique(m,M)

X =

[1x7 double]
[1x4 double]

Y =

[1x5 double]
[1x4 double]
[1x4 double]
[1x4 double]
[1x3 double]
[1x3 double]

Z =

1 1 1 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0

>>

Anh-Dung Nguyen

The result is correct. In fact, the algorithm first extracts all complete subgraphs that are not parts of larger complete subgraphs. These maximal complete subgraphs are called "cliques". I'll modify the description. Thank you.

YANG

I have a question
if A is 4*4 complete graph
[X,Y,Z] = k_clique(3,A);
Y is [1 2 3 4] and not find all cliques of size 3

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!