Network connectivity during mergers and growth: Optimizing the addition of a module

The principal eigenvalue $\lambda$ of a network’s adjacency matrix often determines dynamics on the network (e.g., in synchronization and spreading processes) and some of its structural properties (e.g., robustness against failure or attack) and is therefore a good indicator for how “strongly” a network is connected. We study how $\lambda$ is modified by the addition of a module, or community, which has broad applications, ranging from those involving a single modification (e.g., introduction of a drug into a biological process) to those involving repeated additions (e.g., power-grid and transit development). We describe how to optimally connect the module to the network to either maximize or minimize the shift in $\lambda$, noting several applications of directing dynamics on networks.

Figure 1

A module (described by matrix $S$) is connected to the original network (described by matrix $A$) using directed connections (described by the matrices $X$ and $Y$).

Figure 2

$\delta \lambda$ and approximation errors $\epsilon$ were averaged over ${10}^4$ realizations of connecting a three-node module to the networks in Table using 10 random links (see text). Equation (4) (stars) is shown to be accurate in the upper panel for typical results for the neural network of C. elegans. The average relative error $\langle \epsilon \rangle$ for the neural network of C. elegans (circles) and a network of political blogs (triangles) are given in the lower plot, where Eq. (2) (solid lines) and Eq. (5) with $k=1$ (dotted) and $k=2$ (dashed) are shown.

Figure 3

Eigenvalue shift $\delta \lambda$ for connecting a two-node module to (a) the word association network and (b) the PPI network. Equation (2) (crosses) agrees well with actual values ${\delta }^{\lambda }$ (solid line) for strategy B. The x’s and circles show the same respective quantities for strategy A. As indicated by the drawing, increasing $k$ corresponds to connecting the module to nodes with increasing degrees (strategy A) or eigenvector entries (strategy B).

Figure 4

A typical optimal connection for example I: node $i$ (a point of contraction with large left eigenvector entry $v_i$) points to a node in the module, which in turn points to node $j$ (a point of expansion with large right eigenvector entry $u_j$).

Figure 5

(a) Typical optimal link selections for example II for $x=y=2$. Two points of contraction (NO) link to two module nodes (SI) and the remaining two module nodes (SO) link to two points of expansion (NI). The module also contains a directed complete bipartite graph pointing from SI to SO. (b) Under the restrictions of example II, the module in Fig. 5a was connected to the neural network for C. elegans using various orientations. Solid lines indicate letting $\mathrm{NI}=\{l_1,l_2\}$ and either $\mathrm{NO}=\{1,2\}$ (thick) or $\mathrm{NO}=\{2,1\}$ (thin). Symbols show Eq. (2). Approximating points of contraction (expansion) by nodes with large $d^{\mathrm{in}}$ ($d^{\mathrm{out}}$) also offers a decent strategy (dashed).