File Exchange

## 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

Updated

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.

Benjamin Friedrich

### Benjamin Friedrich (view profile)

Works nicely.

function [B] = largestcomponent(A)
% INPUT

% 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

Maria Priestley

### Maria Priestley (view profile)

Deepesh Nagarajan

### Deepesh Nagarajan (view profile)

Used on Octave, works as advertised.

Fabio Gori

### Fabio Gori (view profile)

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

Puck Rombach

### Puck Rombach (view profile)

You are right. Thank you!

Xin Dong

### Xin Dong (view profile)

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.