Multiscale dynamical embeddings of complex networks

Complex systems and relational data are often abstracted as dynamical processes on networks. To understand, predict, and control their behavior, a crucial step is to extract reduced descriptions of such networks. Inspired by notions from control theory, we propose a time-dependent dynamical similarity measure between nodes, which quantifies the effect a node-input has on the network. This dynamical similarity induces an embedding that can be employed for several analysis tasks. Here we focus on (i) dimensionality reduction, i.e., projecting nodes onto a low-dimensional space that captures dynamic similarity at different timescales, and (ii) how to exploit our embeddings to uncover functional modules. We exemplify our ideas through case studies focusing on directed networks without strong connectivity and signed networks. We further highlight how certain ideas from community detection can be generalized and linked to control theory, by using the here developed dynamical perspective.

Figure 1

Schematic of constructing dynamical similarity measures. Impulses are applied as inputs to different nodes of the network. The responses in time are interpreted as node vectors evolving in state space and can be compared, e.g., via an inner product from which we construct the similarity matrix $\mathrm{\Psi }\left(t\right)$, or alternatively, its associated distance $D^{\left(2\right)}$. Nodes that drive the system similarly (differently) within the projected subspace are assigned a high (low) similarity score. The thus derived vector-space representation of the nodes can be used for a number of different learning tasks.

Figure 2

Constructing dynamical similarity measures. (a) Visualization of an asymmetric directed network (not strongly connected) and its adjacency matrix. Note that the which contains a bipartite (disassortative) substructure. (b) Similarity matrix $\mathrm{\Psi }\left(t\right)=M^t{\left[M^t\right]}^{\top }$ for times $t=\{1,8,16\}$.

Figure 3

Analyzing academic influence using low-dimensional embeddings. (a) We develop a low-dimensional embeddings based on the influence dynamics in the hiring network, as described in the text. The first two dimensions of this embedding are plotted. The first coordinate ${\mathit{\varphi }}_{i,1}^{[0,1]}$ is strongly correlated with the prestige ranking of Clauset et al. [27], highlighting the influential role played by the universities at the top. Interestingly, the second dimension distinguishes the Canadian universities from the U.S. universities, showing that although these universities are well integrated within the faculty hiring market [27], they play a different role and exert a different type of influence on the system. (b) The ranking obtained when projecting onto the first coordinate only and the associated subgraph of faculty hirings. The numbers in parenthesis correspond to the rankings obtained by Clauset et al. [27]. The arrows are proportional to the number of faculty moving between the institutions. Arrows pointing downwards in the ranking are plotted on the left, arrows point upward in terms of the ranking are plotted on the right. The number of hirings from inside the institution itself (self-loops) are indicated by size of the core (darker color) of each node. The area of the core is proportional to the number of self-loops compared to the total out-degree within this subnetwork.

Figure 4

Analyzing academic influence using low-dimensional embeddings. (a) Low-dimensional embeddings based on the influence dynamics in the hiring network, as described in the text (see Fig. 3) for the discipline history. (b) The ranking obtained when projecting onto the first coordinate only and the associated subgraph of faculty hirings (see Fig. 3). The Spearman rank correlation to the results obtained by Clauset et al. is $\rho \approx 0.92$. (c) Low-dimensional embeddings based on the influence dynamics in the hiring network, as described in the text (see Fig. 3) for the discipline Business. (d) The ranking obtained when projecting onto the first coordinate only and the associated subgraph of faculty hirings (see Fig. 3). The Spearman rank correlation to the results obtained by Clauset et al is $\rho \approx 0.96$.

Figure 5

Analysis of a signed social network: The highland tribes in New Guinea. (a) The network of 16 tribes with positive “hina” interactions in red (dark gray) and negative “rova” interactions in blue (light gray). Spectral clustering using $c=2$ eigenvectors of the signed Laplacian $L_s$. The top two eigenvectors of $\mathrm{\Psi }\left(t\right)$ reveals partitions into $k=3$ and $k=2$ groups with positive interactions mostly concentrated within groups and antagonistic interactions across groups. If we instead try to split the signed network into $k=2$ groups based on $c=1$ eigenvector, then we obtain an alternative split as indicated by the dashed gray line. (b) The time evolution of the tribes in state space under the consensus dynamics Eq. (18) is represented through the dynamical embeddings ${\mathit{\varphi }}_i\left(t\right)$. Here we plot only the first two dominant coordinates. As time grows, the Seu've tribe switches from a marginal allegiance to the pink/green groupings (on the upper/lower right side in B with ${\varphi }_{i,1}>0$) to be grouped with the blue block (left side in B with ${\varphi }_{i,1}<0$). This is the result of an “enemy of my enemy is my friend” effect.

Figure 6

Finding dynamical groups in a neural network description. (a) Schematic of the connectivity of the leaky integrate and fire neuronal network, which shows its disassortative feedback structure between inhibitory and excitatory neurons. The exemplar raster plot illustrating its spiking dynamics shows that the system is characterized by slow switching between coherent spiking activity of 10 groups of neurons (each containing both inhibitory and excitatory units). (b) Left: The weighted, signed, and directed synaptic connectivity matrix ($W_N$) of the network does not contain groups of nodes with high internal connection density. However, the analysis of the linear rate model governed by this connectivity matrix Eq. (20) using the dynamical similarity Eq. (21) in conjunction with a Louvain-type optimization reveals the presence of 10 dynamical modules. Right: Visualization of the centered similarity Eq. (21). For visualization purposes only the diagonal of ${\mathrm{\Psi }}_{\perp }$ has been removed. Note that how after an initial short transient period the block structure into 10 groups becomes apparent, in comparison to the original weight matrix. (C) The blocks revealed from the linear rate model coincide with the dynamically coactivated groups of neurons in the full LIF dynamics, as shown by reordering the neuron indices. On the original weight matrix, they correspond, however, to a mixture of the blocks inside the weight-matrix $W_N$.

Figure 7

Dynamical similarities, modules and roles. (a) A small network with two possible partitions with nodes may be described as similar. (b) If we were to group the nodes according to the dynamical similarity measure as defined in the text, then we would pick out configuration A, as the nodes in each group have a similar impulse response after time $t$. (c) However, if we consider the impulse responses up to the action of a permutation $\mathrm{\Omega }$ (isometric mapping), then we could also infer the role partition of configuration B.

Figure 8

Unpredictable influence of teleportation on clustering of directed graphs ($A\ne A^{\top }$). When studying a directed diffusive dynamics (on a directed graph), a teleportation component is usually added to make the process ergodic. The addition of teleportation can lead to unexpected effects when clustering the network, since teleportation also influences the cut (i.e., the probability flow across group boundaries). For concreteness, we illustrate this effect here the map-equation [14] although this effect is general. (a) A directed network of two cliques. The weights between nodes inside each group are drawn from a uniform distribution with mean $1\pm 0.1$; the weights across different groups are drawn from a uniform distribution with mean $0.2\pm 0.02$. The network is directional but the asymmetry of $A$ is so weak as to appear visually virtually undirected. The introduction of teleportation leads to a resolution limit effect in which the groups cannot be resolved. (b) A directed cycle network with equal weights. Without teleportation, a split of the ring into multiple groups is found, whereas the introduction of teleportation improves the result in this case so that the whole cycle is detected. Using an analysis based on $\mathrm{\Psi }$ without teleportation Eq. (C14) finds the dynamical blocks directly in both of these examples.