A 2D lattice

2D_lattice 

We consider the noise-corrupted leader selection problem for a 2D regular lattice with 81 nodes.

Matlab code

lattice_publish
% A 2D lattice example for the noise-corrupted leader-selection problem.
%
% form the incidence matrix and graph Laplacian matrix for 2D lattice
%
% number of nodes for the N x N 2D lattice
n = 81;
N = sqrt(n);

% compute the number of edges
ne = 0.5*( 2*4 + (N-2)*3*4 + (N-2)^2*4 );

% form the index set of edges
idx = zeros(2,ne);

% evaluate the indices for those edges on the rows of the grid
for i = 1:N
    idx(1,(N-1)*(i-1)+1:(N-1)*i) = N*(i-1)+1:N*(i-1)+(N-1);
    idx(2,(N-1)*(i-1)+1:(N-1)*i) = N*(i-1)+2:N*(i-1)+N;
end

% evaluate the indices for those edges on the columns of the grid
for i = 1:N
    idx(1,ne/2+ ((N-1)*(i-1)+1:(N-1)*i) ) = i:N:(i+(N-2)*N);
    idx(2,ne/2+ ((N-1)*(i-1)+1:(N-1)*i) ) = (i:N:(i+(N-2)*N))+N;
end

% form the incidence matrix Eg of the 2D lattice
Eg = incmat(idx);

% form the graph Laplacian
L = Eg*Eg';

% kappa is taken as the diagonal of L
kappa = diag(L);

% Start solving the leader selection problem
%
% choose the number of leaders
kval = 1:1:40;

% pre-allocate memory for data collection
Jlow = zeros(size(kval));
Jup = zeros(size(kval));
LSgreed = zeros(n,length(kval));

for i = 1:length(kval)

    Nl = kval(i);
    flag = 1; % for the noise-corrupted leader selection formulation
    [Jlow(i),Jup(i),LSgreed(:,i)] = leaders(L,Nl,kappa,flag);

end

Computational results

Download Matlab code lattice_example.m to reproduce these figures.

Performance bounds

lower_upper_bounds 

Bounds on the global optimal value of the noise-corrupted leader selection problem {rm (LS1)} for the 2D lattice example.

Selection of leaders

leaders 

Selection of noise-corrupted leaders (bullet) obtained using greedy algorithm (i.e., one-leader-at-a-time algorithm followed by the swap procedure) for the 2D lattice example.

For N_l = 1, the center node (5,5) provides the optimal selection of a single leader. As N_l increases, nodes away from the center node are selected; for example, for N_l = 2, nodes {(3,3), (7,7)} are selected and for N_l = 3, nodes {(2,6), (6,2), (8,8)} are selected. Selection of nodes farther away from the center becomes more significant for N_l = 4 and N_l = 8.

The selection of leaders exhibits symmetry with respect to the center of the lattice. For example, in Fig. (b), the leaders at {(3,7), (7,3)} denoted by (*) provide the same objective function J as leaders denoted by (bullet). Similarly, in Fig. (c), the four selections of three leaders denoted by (bullet), (*), (times), and (circ) all provide the same performance J.

Also note that when N_l is large, almost uniform spacing between leaders is observed; see Fig. (f). This is in contrast to the random network example where boundary nodes were selected when the number of leaders is large.