File Exchange

image thumbnail

Largest Component

version 1.4 (1.22 KB) by

Takes an adj. matrix of a network and outputs a list of the nodes in its largest connected component

11 Downloads

Updated

View License

B=largestcomponent(A)

This function find the largest connected component of a networks.

Input A is the adjacency matrix of the network.

Output B is a list of the nodes that are in the largest component.

A(B,B) will give the adj. matrix of the largest component.

Comments and Ratings (6)

Works nicely.

I added some comments to better understand what the code does:

function [B] = largestcomponent(A)
% INPUT
% A ... adjecency matrix

% OUTPUT
% B ... indices of nodes belonging to the largest component

% n ... number of nodes
% mz .. set of neighbors
% x ... for each node: index of the connected component it belongs to
% v ... set of nodes of these current component, whose neighbors have to be checked still
% c ... for each component: number of its nodes

% deterimine number of nodes
n=length(A);

% loop over all nodes to get list of neighbors
for i=1:n
mz{i}=find(A(i,:));
end

x(1:n)=0;
z=0; % number of components detected so far
k=0; % set of nodes already dealt with
for i=1:n
% node i does not yet belong to any component?
if x(i)==0;
z=z+1; % increase number of detected components
clear v
v(1)=i;
while nnz(v)>0 % while v not empty
x(v(1))=z; % update component entry for current node v(1)
k=union(k,v(1)); % flag current node v(1) as done
b=setdiff(mz{v(1)},k); % neighbors of node v(1) that still have to be taken care of
v=setdiff(v,v(1)); % delete current node from stack
v=union(v,b); % add newly detected nodes to interim list of nodes of current component
end
end
end

% size of components
c(1:max(x))=0;
% loop over components
for i=1:max(x)
c(i)=length(find(x==i)); % determine size of components
end

% size of the largest component(s)
cm=find(c==max(c));

% pick largest component
B=find(x==cm(1));

end

Used on Octave, works as advertised.

Fabio Gori

It would be nice if you commented the code, so that the procedure would be more comprehensible.

Puck Rombach

You are right. Thank you!

Xin Dong

There is a bug in this script. It fails when there are several largest connected components of the same size, because now cm is a vector.

If you only need to find any one of them, than it should be:

B=find(x==cm(1));

Otherwise, a loop is needed to print out all the largest components.

Updates

1.4

Fixed bug about multiple largest components.

1.1

Made the code faster by not using the 'find' function.

MATLAB Release
MATLAB 7.9 (R2009b)

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

» Watch video

Win prizes and improve your MATLAB skills

Play today