Multiagent Systems

6.2.6    Selection of the pinned nodes

Assume in what follows that the graph G is strongly connected and balanced. The Laplacian matrix of the mirror graph G_m (see Definition 4) is $\widehat{L}=\frac{L+L^T}{2}$. If G is balanced, then λ₂($\widehat{L}$) > 0. As in [502], define

$\phi \left(s\right)={\lambda }_{min}\left(b\widehat{L}+s\mathcal{Q}\right)\ge \frac{bms{\lambda }_2\left(\widehat{L}\right)}{bn{\lambda }_2\left(\widehat{L}\right)+smn}$

the network relative connectivity

$\chi =\frac{{\lambda }_2\left(\widehat{L}\right)}{n}$

and the fraction of pinned nodes $\rho =\frac{m}{n}$. Thus, φ(s) can be rewritten as

$\phi \left(s\right)=\left(\frac{1}{\rho s}+\frac{1}{b\chi }\right)$

(6.59)

For the mirror graph G_m of G, one has the lower bound on the Fiedler eigenvalue given by [485]:

${\lambda }_2\widehat{L}\ge \frac{1}{D_m\text{vol }{G}_m}$

(6.60)

where the distance between two nodes is the number of edges in shortest path joining the two nodes, the diameter D_m is the maximum distance between any two nodes of G_m, and volG_m denotes the volume ...