MATLAB Examples

L-RCM: MATRIX BLOCK DETECTION ALGORITHM

by F. Pedroche, M. Rebollo, C. Carrascosa and A. Palomares (2012) Universitat Politècnica de València (Spain)

Matrix block detection using the Laplacian and RCM algorithm. This is an efficien method to determine in a network is strongly connected. If not, the algorithm identifies the blocks that form the network. The algorithm is based on the Laplacian of the adjacency matrix and it uses the Reverse Cuthill-McKee (RCM) algorithm

Contents

Syntax

[v_per freq] = lrcm( A )

Description

In this paper we consider undirected graphs with no loops and multiple edges, consisting of k connected components. In these cases, it is well known that one can find a numbering of the vertices such that the adjacency matrix A is block diagonal with k blocks. This also holds for the (unnormalized) Laplacian matrix L= D-A, with D a diagonal matrix with the degrees of the nodes. In this paper we propose to use the Reverse Cuthill-McKee (RCM) algorithm to obtain a block diagonal form of L that reveals the number of connected components of the graph. We present some theoretical results about the irreducibility of the Laplacian matrix ordered by the RCM algorithm. As a practical application we present a very efficient method to detect connected components with a computational cost of O(m+n), being m the number of edges and n the number of nodes.

Step 1: Define a matrix

The input matrix is passed as argument of the function. Must be a square and symmetric matrix (sure?)

A = [0 0 1 0 1;0 0 0 1 0;1 0 0 0 1; 0 1 0 0 0; 1 0 1 0 0]
A =

     0     0     1     0     1
     0     0     0     1     0
     1     0     0     0     1
     0     1     0     0     0
     1     0     1     0     0

Step 2: Calculation of the Laplacian

Defined as $L = D - A$, where $D$ is the degree matrix (diagonal). The final code uses the sparse function to handle big matrices

L = diag( sum(A,2) ) - A
L =

     2     0    -1     0    -1
     0     1     0    -1     0
    -1     0     2     0    -1
     0    -1     0     1     0
    -1     0    -1     0     2

Step 3: Applies RCM to identify the blocks

The permutation vector |v_per! defines the new order for rows and columns

v_per = symrcm( L )
v_per =

     5     1     3     4     2

Step 4: Permute the Laplacian to separate the blocks

When the matrix is reordered, the blocks are clearly identified

Lp = L(v_per,v_per)
Lp =

     2    -1    -1     0     0
    -1     2    -1     0     0
    -1    -1     2     0     0
     0     0     0     1    -1
     0     0     0    -1     1

Step 5: Sum the permuted laplacian to identify the blocks

The number of element in freq are the number of detected blocks. The vector storesd in freq determines the end positions of each block.

value = sum( triu(Lp) );
freq = find( value == 0 )
freq =

     3     5

Referenes

  1. F. Pedroche, M. Rebollo, C. Carrascosa, A. Palomares: L-RCM: a method to detect connected components in undirected graphs by using the Laplacian matrix and the RCM algorithm arXiv:1206.5726

See also

symrcm

MATLAB® CODE

function [v_per freq] = lrcm( A )
  %Calculation of the Laplacian
  L = sparse(diag( sum(A,2) ) - A);
  %Applies RCM to identify the blocks
  v_per = symrcm( L );
  %Permute the Laplacian to separate the blocks
  Lp = L(v_per,v_per);
  %Sum the permuted laplacian to identify the blocks
  value = sum( triu(Lp) );
  freq = find( value == 0 );