Cuthill$$McKee algorithm

Matlab function $$ cluster$\_$custom$\_$rcm$.$m

function C $=$ cluster$\_$custom$\_$rcm$($A$)$

$\%$ Symmetrize adjacency matrix

S $=$ A $+$ A$\text{'}$;

$\%$ Reverse Cuthill$-$McKee ordering using your custom method

r $=$ ReverseCuthillMckee$($S$)$;

$\%$ Get the clusters

C $=\{$r$(1)\}$;

for i $=2$:numel$($r$)$

if any$($S$($C$\{$end$\},$ r$($i$)))$

C$\{$end$\}($end$+1)=$ r$($i$)$;

else

C$\{$end$+1\}=$ r$($i$)$;

end

end

Matlab function: ReverseCuthillMckee.m

function R $=$ ReverseCuthillMckee$($matrix$)$

cuthill $=$ CuthillMckee$($matrix$)$; $\%$ Apply the Cuthill$-$Mckee algorithm

R $=$ flip$($cuthill$)$; $\%$ Reverse the order of elements to achieve RCM order

end

Matlab function: CuthillMckee.m

function R $=$ CuthillMckee$($matrix$)$

n $=$ size$($matrix$,1)$; $\%$ Get the number of rows $($or nodes$)$ in the matrix

degrees $=$ sum$($matrix$,2)$; $\%$ Compute the degrees of nodes $($sum of rows$)$

Q $=[]$; $\%$ Initialize an empty queue

R $=$ zeros$(1,$ n$)$; $\%$ Initialize the output array for reordered indices

notVisited $=$ true$(1,$ n$)$; $\%$ Boolean array to keep track of unvisited nodes

position $=0$; $\%$ Initialize the position counter

$\%$ Loop until all nodes have been visited

while any$($notVisited$)$

i $=$ find$($notVisited$,1)$; $\%$ Find the first unvisited node

Q$($end $+1)=$ i; $\%$ Enqueue the first unvisited node

notVisited$($i$)=$ false; $\%$ Mark it as visited

$\%$ Process the queue

while ~isempty$($Q$)$

u $=$ Q$(1)$; $\%$ Dequeue the first element of the queue

Q$(1)=[]$; $\%$ Remove the first element from the queue

position $=$ position $+1$; $\%$ Increment position index

R$($position$)=$ u; $\%$ Store the node in the result array at the current position

adj$\_$nodes $=$ find$($matrix$($u$,$ :$))$; $\%$ Find all adjacent nodes

$[$~$,$ idx$]=$ sort$($degrees$($adj$\_$nodes$))$; $\%$ Sort adjacent nodes by degree

adj$\_$nodes $=$ adj$\_$nodes$($idx$)$; $\%$ Reorder adjacent nodes by increasing degree

$\%$ Check each adjacent node

for v $=$ adj$\_$nodes

if notVisited$($v$)\%$ If the node has not been visited

Q$($end $+1)=$ v; $\%$ Enqueue the node

notVisited$($v$)=$ false; $\%$ Mark it as visited

end

end

end

end

R $=$ R$(1$:position$)$; $\%$ Truncate the result array to the actual size $($number of positions filled$)$

end

Matlab function: spectral$\_$clustering.m

function clusters $=$ spectral$\_$clustering$($A$,$ num$\_$clusters$)$

$\%$ Ensure the adjacency matrix is symmetric

A $=($A $+$ A$\text{'})/2$;

$\%$ Compute the degree matrix

D $=$ diag$($sum$($A$,2))$;

$\%$ Compute the unnormalized Laplacian

L $=$ D $-$ A;

$\%$ Make sure the Laplacian is positive semi$-$definite

L $=($L $+$ L$\text{'})/2$;

$\%$ Compute the eigenvalues and eigenvectors

$[$eigVectors$,$ ~$]=$ eigs$($L$,$ num$\_$clusters$+1,\text{'}$SA$\text{'})$;

$\%$ Ignore the first eigenvector $($corresponding to the eigenvalue $0)$

reducedEigVectors $=$ eigVectors$($:$,2$:num$\_$clusters$+1)$;

$\%$ Normalize the eigenvectors row$-$wise

for i $=1$:size$($reducedEigVectors$,1)$

reducedEigVectors$($i$,$ :) $=$ reducedEigVectors$($i$,$ :) $/$ norm$($reducedEigVectors$($i$,$ :$))$;

end

$\%$ Perform custom k$-$means clustering on the rows of the normalized eigenvectors

clusters $=$ custom$\_$kmeans$($reducedEigVectors$,$ num$\_$clusters$)$;

end

Matlab function: custom$\_$eigen$\_$decomp.m

function $[$eigVectors$,$ eigValues$]=$ custom$\_$eigen$\_$decomp$($L$,$ num$\_$eigenvectors$)$

eigVectors $=$ zeros$($size$($L$,1),$ num$\_$eigenvectors$)$;

eigValues $=$ zeros$($num$\_$eigenvectors, $1)$;

for i $=1$:num$\_$eigenvectors

$\%$ Initial vector to start the iteration

v $=$ rand$($size$($L$,1),1)$;

$\%$ Power Iteration

for j $=1$:$1000$

v $=$ L $*$ v;

v $=$ v $/$ norm$($v$)$;

end

eigVectors$($:$,$ i$)=$ v;

eigValues$($i$)=($v$\text{'}*$ L $*$ v$)/($v$\text{'}*$ v$)$;

end

end

Matlab function: custom$\_$kmeans.m

function labels $=$ custom$\_$kmeans$($data$,$ k$)$

$\%$ Randomly initialize the centroids from the data points

centroids $=$ data$($randperm$($size$($data$,1),$ k$),$ :$)$;

$\%$ Initialize labels

labels $=$ zeros$($size$($data$,1),1)$;

$\%$ Previous labels for checking convergence

prev$\_$labels $=$ labels;

$\%$ Maximum number of iterations to prevent infinite loops

max$\_$iters $=1000$;

for iter $=1$:max$\_$iters

$\%$ Assign data points to the nearest centroid

for i $=1$:size$($data$,1)$

$[$~$,$ labels$($i$)]=$ min$($sum$(($data$($i$,$ :) $-$ centroids$).^2,2))$;

end

$\%$ Update centroids based on the mean of assigned data points

for j $=1$:k

centroids$($j$,$ :) $=$ mean$($data$($labels $==$ j$,$ :$),1)$;

end

$\%$ Check for convergence $($no change in labels$)$

if labels $==$ prev$\_$labels

break;

else

prev$\_$labels $=$ labels;

end

end

end

show mathematical calculation how cuthill mckee algorithm and spectral clustering with kmeans clustering can be used to to create clusters in a graph w$.$r$.$t the code above