File Exchange

image thumbnail

Bron-Kerbosch maximal clique finding algorithm

version 1.2.0.0 (2.68 KB) by Jeffrey Wildman
Implementation of the Bron-Kerbosch algorithm to find all maximal cliques of an undirected graph.

7 Downloads

Updated 27 Oct 2011

View Version History

View License

[MC] = MAXIMALCLIQUES(A,V_STR) Given a graph's boolean adjacency matrix, A, find all maximal cliques on A using the Bron-Kerbosch algorithm in a recursive manner.

V_STR is an optional input string with the version of the Bron-Kerbosch algorithm to be used (either 'v1' or 'v2'). Version 2 is faster (and default), and version 1 is included for posterity.

The output matrix MC contains the maximal cliques in its columns.

Note: This function can be used to compute the maximal independent sets of a graph A by providing the complement of A as the input graph.

Note: This function can be used to compute the maximal matchings of a graph A by providing the complement of the line graph of A as the input graph.

Ref: Bron, Coen and Kerbosch, Joep, "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM, vol. 16, no. 9, pp: 575–577, September 1973.

Ref: Cazals, F. and Karande, C., "A note on the problem of reporting maximal cliques", Theoretical Computer Science (Elsevier), vol. 407, no. 1-3, pp: 564-568, November 2008.

Cite As

Jeffrey Wildman (2020). Bron-Kerbosch maximal clique finding algorithm (https://www.mathworks.com/matlabcentral/fileexchange/30413-bron-kerbosch-maximal-clique-finding-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (12)

Kin Cheong Sou

leander moes

linying lu

D N

I would like to ask if you know how to convert a matrix based on number of contacts between nodes to a boolean matrix. With boolean matrix I would like to create a k-clique community. thanks for the answers

Sepehr Farhand

Jdeen

Adrian Wanner

Nice work and very instructive, thanks.
In order to speed up the process I suggest to adapt the algorithm as follows:
% first, some input checking

if size(A,1) ~= size(A,2)
error('MATLAB:maximalCliques', 'Adjacency matrix is not square.');
elseif any((A(:)~=1) & (A(:)~=0))
error('MATLAB:maximalCliques', 'Adjacency matrix is not boolean (zero-one valued).')
elseif any(A(:)~=reshape(A.',[],1))
error('MATLAB:maximalCliques', 'Adjacency matrix is not undirected (symmetric).')
elseif any(diag(A)~= 0)
error('MATLAB:maximalCliques', 'Adjacency matrix contains self-edges (check your diagonal).');
end

% second, set up some variables

n = size(A,2); % number of vertices
MC = cell(n,1); % storage for maximal cliques
R = false(n,1); % currently growing clique
P = true(n,1); % prospective nodes connected to all nodes in R
X = false(n,1); % nodes already processed
iclique=0;

A=A.'; %this speeds up some of the calculations below because we do not have to transpose A for each recursion

% third, run the algorithm!
BKv2(R,P,X);
MC((iclique+1):end)=[];

% version 2 of the Bron-Kerbosch algo
function [] = BKv2 ( R, P, X )

if ~any(P | X)
% report R as a maximal clique
iclique=iclique+1;
MC{iclique}=find(R);
else
% choose pivot
ppivots = P | X; % potential pivots
binP = zeros(1,n);
binP(P) = 1; % binP contains ones at indices equal to the values in P
pcounts = binP*double(A(:,ppivots)); % cardinalities of the sets of neighbors of each ppivots intersected with P
% select one of the ppivots with the largest count
[~,ind] = max(pcounts);
temp_u=find(ppivots,ind,'first');
u_p=temp_u(ind);

for u = find(~A(:,u_p) & P).' % all prospective nodes who are not neighbors of the pivot
P(u)=false;
Rnew = R;
Rnew(u)=true;
Nu = A(:,u);
Pnew = P & Nu;
Xnew = X & Nu;
BKv2(Rnew, Pnew, Xnew);
X(u)=true;
end
end

end % BKv2

end % maximalCliques

Isay

i have an error :

??? Input argument "A" is undefined.

Error in ==> maximalCliques at 39
if size(A,1) ~= size(A,2)

can you help me ?!

Habib

Very nice work. How can one modify the code in order to limit the number of maximal cliques found so far. That is, one may need only a subset of maximal cliques and only the number of them is important but not specified ones.

Edmund Brekke

Akli Benali

Very nice work. The function is very fast, efficient and accurate. When compared with the one posted by Ahmad, it is about 1000 times faster.

Akli Benali

MATLAB Release Compatibility
Created with R2011a
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!