Code covered by the BSD License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

### Highlights from k-clique algorithm

4.0
4.0 | 3 ratings Rate this file 20 Downloads (last 30 days) File Size: 2.68 KB File ID: #34202 Version: 1.3

# k-clique algorithm

### Anh-Dung Nguyen (view profile)

14 Dec 2011 (Updated )

k-clique community detection algorithm

File Information
Description

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

MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Comments and Ratings (7)
19 Jul 2016 Shukai Ni

### Shukai Ni (view profile)

19 Jul 2016 Shukai Ni

### Shukai Ni (view profile)

05 Jun 2014 SAMUEL HEROY

### SAMUEL HEROY (view profile)

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?

Comment only
27 Dec 2013 learn learn

### learn learn (view profile)

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

>>

Comment only
29 Oct 2012 Anh-Dung Nguyen

### Anh-Dung Nguyen (view profile)

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.

Comment only
13 Sep 2012 YANG

### YANG (view profile)

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

Comment only